Comment l'informatique quantique changera-t-elle la programmation? [fermé]

En quoi la programmation d'un algorithme quantique est-elle différente? À quoi ressemblerait un langage de type C s'il était conçu pour les qubits? Les types changeraient-ils?

Lorsque j'ai étudié la question il y a quelque temps, il était clair que les algorithmes quantiques, sans être particulièrement rapides, permettaient un parallélisme massif et exponentiel. Ils vont donc briller dans les cas de recherche dans des espaces qui ne sont pas pratiques avec du matériel séquentiel, même du matériel séquentiel massivement parallèle.

Une propriété des algorithmes quantiques est qu'ils doivent être réversibles . Tout algorithme donné peut être traduit en un réversible, en lui ajoutant une tenue de registres suffisante pour lui permettre d'être exécuté en arrière.

Une autre propriété est que l'obtention d'une réponse à partir d'un algorithme quantique est une affaire de hasard, car ce que vous obtenez à la fin d'un calcul est constitué de plusieurs réponses, chacune avec sa propre probabilité. Il doit être exécuté de manière à ce que la réponse souhaitée ait une probabilité élevée. Cela peut impliquer l'exécution de l'algorithme plusieurs fois en avant et en arrière.

Découvrez l'algorithme de recherche de Grover .

INSERTED pour montrer le fonctionnement fondamental de l'algorithme de Grover. Supposons qu'il y ait un problème de recherche. Les réponses possibles sont 0, 1, 2 et 3, mais la bonne réponse est 2. Si l'ordinateur quantique est placé dans une superposition des quatre états, et il effectue une séquence d'étapes pour déterminer lequel est correct. inverse son amplitude, comme les points noirs et les flèches ci-dessous:

Vous pouvez voir que la flèche 2 a été inversée à l'intérieur de la machine, mais il n'y a aucun moyen de le savoir à l'extérieur, car seules les probabilités sont visibles à l'extérieur, qui sont des amplitudes au carré et quand ils sont carrés, ils sont tous égaux.

Cependant, les amplitudes ont une moyenne, indiquée par la ligne rouge, et l’ordinateur peut être amené à suivre une séquence d’étapes qui inverse chaque amplitude autour de la moyenne . Lorsque cela est fait, les amplitudes et les probabilités passent à l'état 2, la bonne réponse ! Donc, si la machine est observée, l'état 2 brille.

Ce n'est pas si simple. Généralement, il faut plusieurs cycles de la machine, avant et arrière, inversés à la fin de chaque cycle, pour maximiser la probabilité de la bonne réponse. En outre, il faut veiller à ne pas le faire plus que ce nombre de fois, car cela peut tout aussi bien se retourner.

Alors, pourquoi disent-ils que les ordinateurs quantiques sont si rapides ? Parce que chaque fois que vous doublez le nombre de qubits, vous quadrillez le parallélisme, mais vous ne définissez pas la durée, donc finalement, il gagne.

N'est-ce pas amusant?

J'étais personnellement intéressé par la façon dont cela pourrait être appliqué à la vérification de l'exactitude des logiciels. Maintenant, nous testons un logiciel en lui envoyant un grand nombre d’entrées de test et (pour que ce soit trop simple) de voir s’il frappe une assertion. Dans un ordinateur quantique, il pourrait être possible de l'exécuter en parallèle sur un ensemble d'entrées beaucoup plus dense et de voir si l'un de ces cas a atteint un assert.

Comme si l'entrée de l'algorithme était de 128 octets ou 1024 bits, il y a 2 ^ 1024 ou 10 ^ 308 entrées différentes possibles. Il n'y a aucun moyen de tester autant d'entrées sur un ordinateur conventionnel, mais un ordinateur quantique pourrait toutes les tester en parallèle.

À quoi ressemblerait un langage de type C s'il était conçu pour les qubits? Les types changeraient-ils?

Ce serait tellement différent d'être incompréhensible que C.

Le problème principal (si je comprends bien) est que l’informatique quantique ne fonctionne pas de manière impérative: «faites ceci, alors cela, alors cet autre chose». Essayer de forcer la capacité de C à faire cela dans le "processeur" de l'ordinateur quantique sera sinon impossible, extrêmement inefficace.

Les algorithmes de programmation pour les ordinateurs quantiques (encore une fois, si je comprends bien) ont tendance à être plus proches du style fonctionnel de programmation / réduction, car l’informatique quantique permet à tous les candidats de la partie "réduction" d’exister simultanément et de "tomber" de l’ordinateur quand observé.

Notez qu'il existe des algorithmes pour les ordinateurs quantiques, même si les périphériques n'existent pas pour les exécuter. L'algorithme de Simon par exemple.

Afin de tirer le meilleur parti possible d’un ordinateur quantique, il faut pouvoir gérer les entrées et les sorties qui sont les états d’un registre quantique, pour lequel il n’existe vraiment pas d’analogue classique. Fort de quelques années d’expérience dans le domaine de l’information quantique, je dois vous avertir que personne n’a vraiment une bonne intuition à ce sujet, si ce n’est la mathématique abstraite de C * algebras, et on me dit que même cette intuition s’avère inadéquate. si vous commencez à vous interroger sur la théorie de la relativité.

La classe de problèmes qui peuvent être résolus efficacement sur un ordinateur quantique est appelée BQP, pour Bounded Quantum Polynomial. Ceci est la version quantique de BPP, et vous pouvez trouver plus d'informations dans cet article: http://www.scottaaronson.com/papers/bqpph.pdf

Un chercheur en algorithmes quantiques m'a dit hier soir qu'il y avait un problème très important, celui du BQP-complet: la résolution d'un système linéaire de N équations. Classiquement, ceci est soluble dans les étapes O (N) avec élimination gaussienne. L'algorithme Harrow-Hassidim-Lloyd ( http://arxiv.org/abs/0811.3171 ) le résout en polylog (N), à condition que vous soyez prêt à accepter une réponse dont la solution est codée sous forme d'état quantique. Si vous voulez utiliser pleinement un ordinateur quantique, il vous semble donc nécessaire d’avoir un type correspondant à l’état d’un registre quantique.

Bien que je sois un peu en dehors de mes compétences particulières en ce moment, je me risquerais à deviner que vous seriez en mesure de programmer un ordinateur quantique à condition de pouvoir accéder à un type correspondant à des états magiques. C'est un concept difficile, cependant, qui nécessite une étude approfondie du sujet.

Soyez averti que nous n’avons pas beaucoup de temps pour utiliser un langage de programmation quantique, car nous en sommes à un stade très primitif de la recherche en informatique quantique. Demander un C quantique maintenant équivaudrait à demander à Alan Turing de concevoir Python. Nous n'avons même pas encore la version quantique du tube à vide!