Quel niveau de «confiance» du résultat d'un ordinateur quantique est possible?

À un niveau très basique, la lecture ou la mesure d'un qubit l'oblige à se trouver dans un état ou dans l'autre, de sorte que le fonctionnement d'un ordinateur quantique pour obtenir un résultat réduit l'état en l'une des nombreuses possibilités.

Mais comme l'état de chaque qubit est probabiliste, cela signifie sûrement que le résultat peut en fait être l'une de ces possibilités, avec une probabilité variable. Si je relance le programme - dois-je m'attendre à voir des résultats différents?

Comment puis-je être sûr d'avoir le "meilleur" résultat? Qu'est-ce qui donne cette confiance? Je suppose que ce ne peut pas être les mesures intermédiaires décrites dans cette question car elles ne réduisent pas la sortie.

La majorité des algorithmes utiles / relativement efficaces ¹ pour les ordinateurs quantiques appartiennent à la classe de complexité du «temps polynomial quantique à erreurs bornées» (BQP) . Selon cette définition, vous voulez que le «taux d'échec» de tout algorithme quantique soit , ouP(succès)≥$\leq\frac{1}{3}$ , bien que le résultat puisse encore contenir une petite erreur. Un algorithme non probabiliste (qui peut s'exécuter en temps polynomial) sera toujours dans cette classe de complexité, à la seule différence qu'ilrenvoietoujoursle résultat correct².$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$

Cependant, comme vous pouvez exécuter un algorithme un nombre arbitraire de fois, cela équivaut à avoir une probabilité de réussite d'au moins pour une entrée de longueurnet toute constante positivec.$\frac{1}{2} + n^{-c}$$n$$c$

Ainsi, le résultat «correct» est celui qui apparaît au moins deux tiers du temps, à moins que vous ne vouliez un calcul «ponctuel», comme si vous voulez générer des nombres aléatoires, ou si vous voulez faire quelque chose comme un benchmark la puce quantique, où les statistiques comptent et font partie du «résultat».

En dehors de ceux-ci (ou d'autres algorithmes qui n'ont pas un seul «résultat correct»), si vous trouvez un algorithme avec un taux de réussite inférieur à la moitié, ce n'est plus une «erreur bornée» et il peut ne pas être possible pour l'utilisateur pour connaître le bon résultat - il peut simplement y avoir une mauvaise réponse avec une probabilité plus élevée de se produire que la bonne.

Oui, vous pouvez voir un résultat différent chaque fois que vous exécutez un calcul. La confiance dans le résultat est apportée par:

1. L'algorithme quantique lui-même garantissant que le résultat correct se produit avec une probabilité élevée et;
2. Répéter l'algorithme plusieurs fois afin de trouver le résultat le plus probable.

^{1 Ici, des algorithmes qui peuvent être calculés en temps polynomial pour donner une solution avec une «probabilité élevée», bien qu'aux fins de cette réponse, la complexité temporelle soit de moindre importance}

^{2 Eh bien, idéalement, au moins}

Élaborer un peu sur Mithrandir24601la réponse de -

La caractéristique qui vous inquiète, à savoir qu'un ordinateur quantique pourrait produire une réponse différente lors de la prochaine exécution du calcul, est également une caractéristique du calcul aléatoire. À certains égards, il est bon de pouvoir obtenir une seule réponse de manière répétée, mais au final, cela suffit pour pouvoir obtenir une réponse correcte avec une confiance suffisante. Tout comme avec un algorithme aléatoire, ce qui est important, c'est que vous pouvez être sûr des chances d'obtenir la bonne réponse dans une exécution donnée du calcul.

Par exemple, votre ordinateur quantique peut vous donner la bonne réponse à une question OUI / NON deux fois sur trois. Cela peut sembler une mauvaise performance, mais cela signifie que si vous l'exécutez plusieurs fois, vous pouvez simplement prendre la réponse majoritaire et être très confiant que la règle de la majorité vous donne la bonne réponse. (Il en va de même pour le calcul aléatoire normal.) La façon dont la confiance augmente avec le nombre de runes signifie que tant qu'une exécution donne une réponse qui a beaucoup plus que 50% de chances d'être correcte, vous pouvez augmenter votre confiance aussi haut que vous le souhaitez simplement en effectuant un nombre modeste de répétitions (bien que plus de répétitions soient nécessaires, plus les chances de réponse correcte dans une même exécution sont proches de 50%).

$\mathrm{poly}(n)$$n$

Pour les problèmes qui ont des réponses plus élaborées que les questions OUI / NON, nous ne pouvons pas nécessairement supposer que la même réponse sera produite plus d'une fois afin que nous puissions voter à la majorité. (Si vous utilisez un ordinateur quantique pour échantillonner à partir d'un nombre exponentiel de résultats, il est possible qu'il y ait une quantité plus petite mais toujours exponentielle de réponses correctes et utiles!) Supposons que vous essayez de résoudre un problème d'optimisation: il peut ne pas être facile de vérifier que vous avez trouvé la solution optimale, ou une solution presque optimale - ou que la réponse que vous avez obtenue est même la meilleure que l'ordinateur quantique puisse faire (et si la prochaine exécution vous donne un meilleure réponse par hasard?). Dans ce cas, l'important est de déterminer ce que vous savez du problème,NP , ce qui signifie que vous pouvez en principe vérifier efficacement toutes les réponses qui vous sont données?), Et quelle qualité de solution vous conviendrait.

Encore une fois, cela est également vrai pour les algorithmes randomisés - la différence étant que nous nous attendons à ce que les ordinateurs quantiques soient capables de résoudre des problèmes qu'un ordinateur randomisé seul ne pourrait pas facilement résoudre.

$15$$3\times5$

C'est une bonne réplique, en particulier avec le rythme bien synchronisé d'Aaronson, et le public semblait toujours rire au moins un peu, mais bien sûr, nous savons tous que c'est une petite simplification excessive de la nature probabiliste de l'algorithme de Shor.

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$

$\mathrm{BQP}$$\mathrm{NP}$

(Je sais qu'il y a déjà deux bonnes réponses; cependant, la question permet une exposition / clarification sur la citation / anectdote d'Aaronson.)