PostBQP

En théorie de la complexité computationnelle , PostBQP est une classe de complexité composée de tous les problèmes de calcul résolubles en temps polynomial sur une machine de Turing quantique avec post-sélection et erreur bornée (dans le sens où l'algorithme est correct au moins 2/3 du temps sur toutes les entrées).

La postsélection n'est pas considérée comme une caractéristique qu'un ordinateur réaliste (même quantique) posséderait, mais les machines à postsélection sont néanmoins intéressantes d'un point de vue théorique.

La suppression de l'une ou l'autre des deux principales caractéristiques (quantité, post-sélection) de PostBQP donne les deux classes de complexité suivantes, qui sont toutes deux des sous-ensembles de PostBQP :

• BQP est identique à PostBQP, à l'exception de l'absence de postsélection.
• _{Le chemin} BPP est le même que PostBQP sauf qu'au lieu d'être quantique, l'algorithme est un algorithme randomisé classique (avec post-sélection)

L'ajout de la postsélection semble rendre les machines de Turing quantiques beaucoup plus puissantes : Scott Aaronson a démontré que PostBQP est égal à PP , une classe considérée comme relativement puissante, alors que BQP ne contiendrait même pas la classe apparemment plus petite NP . En utilisant des techniques similaires, Aaronson a également prouvé que de petites modifications des lois du calcul quantique auraient des effets significatifs. À titre d'exemples concrets, avec chacune des deux modifications suivantes, la « nouvelle » version de BQP serait égale à PP :

• si nous élargissions la définition de « porte quantique » pour inclure non seulement les opérations unitaires mais aussi les opérations linéaires, ou
• si la probabilité de mesurer un état de base était proportionnelle à au lieu de pour tout entier pair p > 2 .

Afin de décrire certaines propriétés de PostBQP, nous définissons une manière formelle de décrire la postsélection quantique. Définissons un algorithme quantique comme une famille de circuits quantiques (plus précisément, une famille de circuits uniformes ). Nous désignons un qubit comme qubit de postsélection P et un autre comme qubit de sortie Q. PostBQP est alors défini par la postsélection lors de l'événement où le qubit de postsélection est P. Plus précisément, un langage L appartient à PostBQP s'il existe un algorithme quantique A tel qu'après l'exécution de A sur l'entrée x et la mesure des deux qubits P et Q ,

• P = 1 avec une probabilité non nulle
• si l'entrée x est dans L, alors Pr[ Q = 1| P = 1] ≥ 2/3
• si l'entrée x n'est pas dans L alors Pr[ Q = 0| P = 1] ≥ 2/3 .

On peut démontrer que l'autorisation d'une seule étape de post-sélection à la fin de l'algorithme (comme décrit ci-dessus) ou l'autorisation d'étapes de post-sélection intermédiaires au cours de l'algorithme sont équivalentes.

Voici trois propriétés fondamentales de PostBQP (qui sont également valables pour BQP via des preuves similaires) :

1. PostBQP est fermé par complément . Étant donné un langage L dans PostBQP et une famille de circuits de décision correspondante, créez une nouvelle famille de circuits en inversant le qubit de sortie après la mesure ; alors, la nouvelle famille de circuits prouve que le complément de L est dans PostBQP .
2. Il est possible d' amplifier les probabilités dans PostBQP . La définition de PostBQP reste inchangée si l'on remplace la valeur 2/3 par une constante comprise entre 1/2 et 1. Par exemple, étant donné un algorithme PostBQP A ayant une probabilité de succès de 2/3, on peut concevoir un autre algorithme qui exécute trois copies indépendantes de A , génère un bit de post-sélection égal à la conjonction des trois bits « internes », et génère un bit de sortie égal à la majorité de ces trois bits « internes ». Ce nouvel algorithme aura une probabilité conditionnelle de succès supérieure à la probabilité initiale de 2/3.
3. L'algorithme PostBQP est fermé par intersection . Supposons que nous ayons des familles de circuits PostBQP pour deux langages et , avec respectivement des qubits de postsélection et des qubits de sortie . Par amplification de probabilité , nous pouvons supposer que les deux familles de circuits ont une probabilité de succès d'au moins 5/6. Nous créons alors un algorithme composite où les circuits pour et sont exécutés indépendamment , et nous définissons P comme la conjonction de et , et Q comme la conjonction de et . Il est aisé de constater, par une borne d' union , que cet algorithme composite détermine correctement l'appartenance à avec une probabilité (conditionnelle) d'au moins 2/3.

Plus généralement, la combinaison de ces idées montre que PostBQP est fermé par union et par réduction de la table de vérité de BQP.

Scott Aaronson a démontré que les classes de complexité ( temps polynomial quantique à erreur bornée post-sélectionnée) et PP ( temps polynomial probabiliste) sont égales. Ce résultat était important car cette reformulation en termes de calcul quantique a permis de nouvelles perspectives et des démonstrations plus simples des propriétés de .

La définition usuelle d'une famille de circuits est celle d' un circuit comportant deux qubits de sortie P (post-sélection) et Q (sortie), avec une seule mesure de P et Q à la fin, de sorte que la probabilité de mesurer P = 1 soit non nulle, la probabilité conditionnelle Pr[ Q = 1| P = 1] ≥ 2/3 si l'entrée x appartient au langage, et Pr[ Q = 0| P = 1] ≥ 2/3 si l'entrée x n'appartient pas au langage. Pour des raisons techniques, nous modifions la définition de la famille de circuits comme suit : nous exigeons que Pr[ P = 1] ≥ 2 ^{− n c,} où c est une constante dépendant de la famille de circuits. Ce choix n'affecte pas les propriétés fondamentales de la famille de circuits , et l'on peut démontrer que tout calcul composé de portes logiques typiques (par exemple, Hadamard, Toffoli) possède cette propriété dès que Pr[ P = 1] > 0 .

Supposons qu'on nous donne une famille de circuits pour décider d'un langage L. Nous supposons sans perte de généralité (voir par exemple les propriétés non essentielles des ordinateurs quantiques ) que toutes les portes ont des matrices de transition représentées par des nombres réels, au prix de l'ajout d'un qubit supplémentaire.

Soit Ψ l'état quantique final du circuit avant la mesure de post-sélection. L'objectif principal de la démonstration est de construire un algorithme permettant de déterminer L. Plus précisément , il suffit que L compare correctement le carré de l'amplitude de Ψ dans les états Q = 1, P = 1 au carré de l'amplitude de Ψ dans les états Q = 0, P = 1 afin de déterminer laquelle est la plus grande. L'idée clé est que la comparaison de ces amplitudes peut être ramenée à la comparaison de la probabilité d'acceptation d'une machine avec 1/2.

Soit n la taille de l'entrée, B = B ( n ) le nombre total de qubits dans le circuit (qubits d'entrée, auxiliaires, de sortie et de post-sélection), et G = G ( n ) le nombre total de portes. Représentons la i -ème porte par sa matrice de transition A ^_i (une matrice unitaire réelle) et soit l'état initial (complété par des zéros). Alors … Définissons S _₁ (resp. S_₀ ) comme l'ensemble des états de base correspondant à P = 1, Q = 1 (resp. P = 1, Q = 0 ) et définissons les probabilités…

La définition de ⁠ ⁠ garantit que soit ou selon que x est dans L ou non.

Notre machine comparera et . Pour ce faire, nous élargissons la définition de la multiplication matricielle :

où la somme porte sur toutes les listes de vecteurs de base G. et peuvent alors être exprimés comme la somme de produits deux à deux de ces termes. Intuitivement, nous souhaitons concevoir une machine dont la probabilité d'acceptation est de l'ordre de , car alors impliquerait que la probabilité d'acceptation est , tandis que impliquerait que la probabilité d'acceptation est . $\{\; frac\; \{1\}\{2\frac{1}{2}(1+{\pi }_1-{\pi }_0)>\frac{1}{2}${ frac {1}{2

La définition de ⁠ ⁠ nous indique que si x appartient à L , et que sinon . Remplaçons tous les éléments de A par la fraction la plus proche dont le dénominateur correspond à un grand polynôme ⁠ ⁠ que nous allons décrire. On utilisera plus tard le fait que les nouvelles valeurs de π satisfont si x appartient à L , et si x n'appartient pas à L. En utilisant l'hypothèse technique précédente et en analysant comment la norme 1 de l'état de calcul change, on constate que cette condition est satisfaite si ; il existe donc clairement un f suffisamment grand qui est polynomial en n . $\{\; frac\; \{1\}\{2\}\}(\backslash pi\; \_\{0\}+\backslash pi\; \_\{1\}){\pi }_1>\frac{1}{2}({\pi }_0+{\pi }_1)${ frac {1}{2}}(\pi _{0}+\pi _{1}) $\{\; frac\; \{1\}\{2\}\}(\backslash pi\; \_\{0\}+\backslash pi\; \_\{1\}){\pi }_0>\frac{1}{2}({\pi }_0+{\pi }_1)${ frac {1}{2}}(\pi _{0}+\pi _{1})

Nous présentons maintenant l'implémentation détaillée de notre machine . Soit α la séquence et définissons la notation abrégée.

alors

Nous définissons notre machine à

• choisir un état de base ω uniformément au hasard
• Si alors ARRÊTEZ et acceptez avec une probabilité de 1/2, rejetez avec une probabilité de 1/2
• choisir deux séquences d' états de base G uniformément au hasard
• calculer (qui est une fraction avec un dénominateur tel que )
• alors accepter avec probabilité et rejeter avec probabilité (ce qui prend au plus ⁠ ⁠ lancers de pièce)
• sinon (alors ) accepter avec probabilité et rejeter avec probabilité (ce qui prend encore au plus ⁠ ⁠ lancers de pièce)

Il est alors simple de calculer que cette machine accepte avec probabilité, donc c'est une machine pour le langage L , comme nécessaire.

Supposons une machine de complexité temporelle O ( n ) sur une entrée x de longueur T. Cette machine effectue donc au plus T lancers de pièce pendant le calcul. On peut ainsi la considérer comme une fonction déterministe f (implémentée, par exemple, par un circuit classique) qui prend deux entrées ( x, r ), où r , une chaîne binaire de longueur T , représente le résultat des lancers de pièce aléatoires effectués par le calcul, et la sortie de f est 1 (acceptation) ou 0 (rejet). La définition de O( n) nous indique que

$2^\{T-1x\in L\iff \#\{r\in \{0,1{\}}^T\mid f(x,r)=1\}>2^{T-1}$2^{T-1

Nous souhaitons donc un algorithme capable de déterminer si l'affirmation ci-dessus est vraie .

Définissons s comme le nombre de chaînes aléatoires qui mènent à l'acceptation.

et il en va de même pour le nombre de chaînes rejetées. Il est facile de démontrer, sans perte de généralité, que ; pour plus de détails, voir une hypothèse similaire, sans perte de généralité, dans la preuve que ⁠ ⁠ est stable par complémentation .

L'algorithme d'Aaronson pour résoudre ce problème est le suivant. Par souci de simplicité, nous écrirons tous les états quantiques non normalisés. Premièrement, nous préparons l'état . Deuxièmement, nous appliquons des portes de Hadamard au deuxième registre (chacun des T premiers qubits), mesurons ce registre et effectuons une post-sélection sur le fait qu'il s'agit de la chaîne de zéros. Il est facile de vérifier que cela laisse le dernier registre (le dernier qubit) dans l'état résiduel

Où H désigne la porte de Hadamard, nous calculons l'état

Où sont des nombres réels positifs à choisir ultérieurement avec , nous calculons l'état et mesurons le second qubit, en post-sélectionnant sur sa valeur égale à 1, ce qui laisse le premier qubit dans un état résiduel dépendant de lequel nous désignons

En visualisant les états possibles d'un qubit comme un cercle, on constate que si x = 0 (c'est-à-dire si x ≠ 0 ), alors x se situe dans le quadrant ouvert , tandis que si x = 0 (c'est-à-dire si x ≠ 0 ), alors x se situe dans le quadrant ouvert . En fait, pour tout x fixé (et son s correspondant ), lorsque l'on fait varier le rapport x/s , l'image de x/s est précisément le quadrant ouvert correspondant. Dans la suite de la démonstration, nous précisons l'idée que l'on peut distinguer ces deux quadrants. $2^\{T-1s>2^{T-1}$2^{T-1

Soit , le centre de , et soit orthogonal à . Tout qubit de , mesuré dans la base , donne la valeur moins de la moitié du temps. En revanche, si et , la mesure dans la base donnerait toujours la valeur . Comme nous ne connaissons pas , nous ne connaissons pas non plus la valeur précise de r* , mais nous pouvons tester plusieurs valeurs différentes (en nombre polynomial) pour dans l'espoir d'en trouver une proche de r* .

Plus précisément, notons et attribuons successivement à chaque valeur de la forme pour . Des calculs élémentaires montrent alors que pour l'une de ces valeurs de i , la probabilité que la mesure de dans la base donne est au moins

Globalement, l' algorithme est le suivant. Soit k une constante comprise entre 1/2 et . Pour chaque , on effectue l'expérience suivante : on construit et mesure dans la base un total de fois où C est une constante. Si la proportion de mesures est supérieure à k , on rejette . Sinon , on accepte . Les bornes de Chernoff montrent alors que pour une constante universelle C suffisamment grande , on classe correctement x avec une probabilité d'au moins 2/3.

Notez que cet algorithme satisfait l'hypothèse technique selon laquelle la probabilité globale de post-sélection n'est pas trop faible : chaque mesure individuelle de a une probabilité de post-sélection et donc la probabilité globale est .