Qu'est-ce qui rend les ordinateurs quantiques particulièrement utiles?

18

Je sais que les ordinateurs quantiques sont capables de traiter une superposition de tous les états possibles en un seul passage à travers la logique.

Cela semble être ce que les gens indiquent comme étant ce qui rend les ordinateurs quantiques spéciaux ou utiles.

Cependant, après avoir traité les entrées superpositionnelles, vous avez un résultat superpositionnel, auquel vous ne pouvez poser qu'une seule question et il se réduit en une seule valeur. Je sais également qu'il n'est pas (actuellement?) Possible de cloner l'état de superposition, vous êtes donc obligé d'obtenir une réponse à cette seule question.

Dans les deux cas, il semble que cette capacité de traitement multiple ne vous ait vraiment rien donné, car c'est comme si un seul état avait été traité.

Suis-je en train de mal interpréter les choses, ou l'utilité réelle de l'informatique quantique vient-elle d'autre chose?

Quelqu'un peut-il expliquer ce que c'est que quelque chose d'autre?

Alan Wolfe
la source
2
Certaines tâches peuvent être résolues plus rapidement en utilisant des ordinateurs quantiques. Voir quelques pointeurs sur cs.stackexchange.com/a/751/157
Ran G.
Merci pour le lien, je vais le vérifier. Je sais qu'ils sont plus rapides sur certaines choses mais j'essaie de comprendre comment et pourquoi si vous pouvez aider avec ça (:
Alan Wolfe
4
L'essentiel est l' interférence . Scott Aaronson a écrit plusieurs essais populaires à ce sujet; essayez de les rechercher en ligne. Voir également son livre "Quantum Computing Since Democritus", basé sur les notes de cours qui peuvent être trouvées ici . Quelque part autour du chapitre 10 devrait être l'endroit à regarder, comme point de départ.
Ran G.
j'ai lu certains de ces trucs et j'ai suivi des liens. intéressant! J'aime la façon dont Scott dit à fond que c'est BS que les ordinateurs quantiques peuvent évaluer toutes les possibilités et trouver la bonne réponse en une seule étape. Puis-je deviner quelle est l'interférence? Est-ce qu'il détruit (ou s'effondre ou se débarrasse) des états possibles de la superposition qui ne sont pas des solutions valables?
Alan Wolfe
1
"Je sais aussi qu'il n'est pas (actuellement?) Possible de cloner l'état de superposition" Le théorème du non-clonage dit qu'il s'agit d'une impossibilité absolue, plutôt que d'une limite de la technologie actuelle. ("Absolue" dans le sens où, si les systèmes quantiques concernent vraiment les transformations unitaires des espaces de Hilbert, vous ne pouvez pas le faire; si les transformations unitaires des espaces de Hilbert se révèlent être uniquement des approximations, alors je suppose que vous pouvez peut-être le faire, après tout .)
David Richerby

Réponses:

13

L'interférence destructive est la principale chose qui rend les ordinateurs quantiques plus puissants. Dans un calcul probabiliste classique, avoir deux chemins vers une sortie rend toujours ce résultat plus probable. Dans un ordinateur quantique, cela peut rendre le résultat moins probable.

Les algorithmes quantiques sont soigneusement conçus de sorte que les mauvaises réponses ont tendance à interférer de manière destructrice, ne laissant que les solutions souhaitées comme résultats de mesure. C'est délicat à faire et tous les problèmes ne le permettent pas. L'algorithme de recherche de Grover est un excellent exemple de cet effet, voici donc un article de niveau débutant sur l'algorithme de Grover .

D'autres propriétés utiles aux ordinateurs quantiques ont accès à:

(Scott Aaronson aime dire que tout ce qui est intéressant au sujet du quantique est dû aux superpositions préservant la norme 2 au lieu de la norme 1 comme le font les distributions de probabilité. Tous les effets utiles plus spécifiques que j'ai mentionnés découlent des mathématiques sous-jacentes.)

Craig Gidney
la source
5

Certaines de vos questions sont des questions théoriques ouvertes. Il existe plusieurs façons de répondre à votre question. Une manière générale de penser le calcul QM est qu'il exploite la spintronique, c'est-à-dire la propriété quantique du spin pour le calcul. Il s'agit donc d'une prochaine étape logique dans la miniaturisation de l'électronique / logique, et du calcul en général. Il existe des limites théoriques sur la largeur de la porte qui sont repoussées dans la technologie de fabrication actuelle, un plateau conséquent de la loi de Moores et de la spintronique représente la "prochaine frontière".

2XXest le nombre de qubits, c'est-à-dire une augmentation exponentielle de la capacité de calcul pour une augmentation linéaire des qubits. Cela ressemble presque à de la science-fiction mais est une propriété apparemment "réelle / intrinsèque" pour autant que quiconque le sache.

Une percée clé en 1996 est l'algorithme de Shor , qui a montré que l'affacturage peut être résolu en "temps polynmomial quantique" et il est crédité comme incitant un intérêt majeur pour l'informatique quantique. L'affacturage est bien sûr au cœur des systèmes cryptographiques modernes dans l' algorithme RSA largement utilisé .

C'est une question théorique ouverte si les ordinateurs quantiques peuvent résoudre d'autres problèmes majeurs en un temps "plus rapide". Ceci est connu comme le BPP =? Question BQP .

Un ordinateur QM controversé est construit par DWave qui s'est avéré "utile" pour résoudre certains problèmes, et ils ont réussi à démontrer une forme de mise à l'échelle quantique sur un type de système QM "un peu plus faible" connu sous le nom d' informatique adiabatique . C'est une question ouverte de savoir si elle peut / va jamais démontrer des augmentations de vitesse sans équivoque, activement à la recherche par exemple par Google, Nasa, Lockheed etc.

En bref, les ordinateurs quantiques ne sont pas exactement "utiles" au même sens que les ordinateurs classiques, cette nature exacte de leur utilité est activement recherchée, et seuls des systèmes limités / expérimentaux / prototypes existent actuellement. Ils sont supposés être "au moins aussi utiles" que le calcul conventionnel lors de leur réalisation, et peut-être / espérons-le "plus utiles" de certaines manières pas exactement prévisibles.

vzn
la source
1
ps aucun algorithme classique n'est connu pour factoriser les nombres en temps polynomial et c'est un problème majeur de théorie de la complexité ouverte s'il est possible, il est supposé impossible et la sécurité RSA ("presque") en dépend.
vzn
5

Une réponse assez controversée, mais gardez-la néanmoins à l'esprit.

je dirais que rien ne rend les ordinateurs quantiques plus utiles (au moins actuellement)!

Bien sûr, le traitement théorique standard de la mécanique quantique en informatique, par rapport à un traitement théorique classique, offre en effet de nouvelles possibilités (comme d'autres réponses l'ont noté). Alors, quel est le problème ici?

Le problème est le suivant: il n'est pas certain que les ordinateurs quantiques soient en effet plus puissants que les ordinateurs ordinaires / classiques (un fait lié à laP contre NPproblème aussi) et que les ordinateurs classiques ne peuvent pas simuler des ordinateurs quantiques. Bien sûr, la " théorie quantique " vous le dira. Pourquoi des citations en " théorie quantique "? Parce que ce n'est pas de la théorie quantique, en réalité c'est juste une " interprétation spécifique de la théorie quantique ". J'espère que tout cela est compris et clair.

Références connexes:

  1. Existe-t-il une preuve formelle que l'informatique quantique est ou sera plus rapide que l'informatique classique?
  2. Ordinateur quantique émulé par un système classique ( papier IOP )
  3. Le premier «ordinateur quantique» n'est pas plus rapide qu'un PC classique
  4. Les mesures quantiques peuvent-elles battre les ordinateurs classiques?
  5. Battre un ordinateur quantique en simulant la mécanique quantique
Nikos M.
la source
Oui, merci pour la réponse. C'est une bonne perspective à garder à l'esprit. Si nous pouvions faire un calcul de norme L2, ou un calcul superpositionnel sur un ordinateur qui permettait des interférences destructives, ou similaire, nous pourrions obtenir ce que nous voulons par algorithme, sans avoir à faire un ordinateur quantique. Bons points!
Alan Wolfe
@AlanWolfe, ouais, recherchez autour de "ordinateur quantique classique" et / ou "quantique d'émulation classique" et voyez ce que vous obtenez. Réponse mise à jour avec quelques références au point
Nikos M.