Des épreuves interactives via la post-sélection?

Définissez le modèle de calcul MPostBQP comme étant identique à PostBQP, sauf que nous autorisons de nombreuses mesures de qubit polynomiales avant la post-sélection et la mesure finale.

Pouvons-nous fournir des preuves indiquant que MPostBQP est plus puissant que PostBQP?

Définissez MPostBQP [k] pour autoriser plusieurs cycles de mesure et de post-sélection avant d'effectuer la mesure finale. Choisissez l'indexation afin que MPostBQP [1] = PostBQP et MPostBQP [2] = MPostBQP et ainsi de suite. (Mise à jour: une définition formelle est donnée ci-dessous.)

Considérez les jeux Arthur-Merlin. Peut-être pouvons-nous les simuler dans ce modèle de calcul: la post-sélection peut prendre le rôle de Merlin de produire des messages convaincants et les mesures intermédiaires peuvent jouer le rôle de lancer de pièces publiques d'Arthur. Cette possibilité me fait demander:

Avons-nous AM [k] MPostBQP [k]? $\subset$

Ceci est en effet connu pour , qui dit MA PP. L'afficher pour signifierait MPostBQP = PP uniquement si AM PP. Puisqu'il y a un oracle par rapport auquel AM n'est pas contenu dans PP , cela pourrait donner une réponse affirmative à ma première question. $k=1$ $\subset$ $k=2$ $\subset$

Enfin, pour le cas polynomial à plusieurs tours,

Avons-nous PSPACE MPostBQP [poly]? Si oui, est-ce l'égalité? $\subset$

Ce serait philosophiquement intéressant (du moins pour moi) car cela nous dirait que la classe de problèmes "traitable" pour un "sorcier post-sélection" comprend (ou est ) tout de PSPACE.

EDIT: On m'a demandé une définition formelle de MPostBQP. (J'ai mis à jour ce qui suit.)

MPostBQP [k] est la classe de langages pour laquelle il existe une famille uniforme de circuits quantiques de taille polynomiale tels que pour tous entrées , la procédure ci - dessous les rendements vrais avec une probabilité au moins si , et avec une probabilité d' au plus si . La procédure, qui permet certains choix qui peuvent dépendre de (mais pas de ), est définie comme suit: $L \subset \{0,1\}^*$ $\{C_n\}_{n \geq 1}$ $x$ $2/3$ $x \in L$ $1/3$ $x \notin L$ $L$ $x$

Procédure: étape 1. Appliquez l'opérateur unitaire correspondant à à l'état d'entrée . Notez que la longueur du premier est au plus polynomiale dans la longueur de . Étape 2. Pour : si est pair, alors mesurez le nombre souhaité de qubits du premier registre (au plus polynomialement, étant donné la taille du registre). Si est impair, alors la post-sélection ainsi un qubit unique choisi dans le premier registre mesure comme $C_n$ $\left\vert 0\cdots 0\right> \otimes \left\vert x \right>$ $\left\vert0\cdots 0\right>$ $x$ $i = 1 \cdots k$ $i$ $i$ $\left\vert 0 \right>$ (et avoir la garantie que la probabilité est non nulle, la post-sélection est donc valide, bien sûr). Étape 3. Enfin, mesurez un dernier qubit dans le premier registre et retournez vrai si nous mesurons et false sinon. $\left \vert 1 \right>$

Nous avons MPostBQP [0] = BQP, MPostBQP [1] = PostBQP et MPostBQP: = MPostBQP [2]. J'essaie de refléter les classes Arthur-Merlin où AM [0] = BPP, AM [1] = MA et AM [2] = AM.

EDIT (3/27/11 5 PM): Il semble y avoir un débat sur la manière de définir la post-sélection dans ce contexte. Évidemment, je veux dire pour une définition qui ne banalise pas ma question! :) La définition que j'ai supposée est la suivante: la post-sélection sur le kième bit signifie que nous projetons l'état dans le sous-espace dans lequel le kième bit est $0$ et normaliser. Il s'avère que dans un schéma où nous post-sélectionnons avant de faire des mesures, nous pouvons alors obtenir les statistiques finales en examinant les probabilités conditionnelles dans un schéma où les post-sélections sont remplacées par des mesures. Cependant, je prétends que cette caractérisation tombe en panne lorsque les mesures et les post-sélections sont intercalées. Je pense que la confusion vient du fait que les gens utilisent cette "définition de probabilité conditionnelle" (qui fonctionne dans le cas spécial que je généralise) comme définition de la post-sélection, plutôt que la définition de "mesure forcée" que je viens de donner, qui dépend clairement de ordre en raison du manque de commutativité. J'espère que ça aide!

EDIT (3/27/11 9 PM): J'ai déjà défini la post-sélection dans le formalisme à l'état pur. Niel a donné une analyse dans le formalisme de la matrice de densité qui n'est pas d'accord avec la mienne pour l'exemple à 3 qubits. Le coupable est, encore une fois, la définition de la post-sélection. Définissez la post-sélection dans le paramètre de matrice de densité comme suit. Étant donné une matrice de densité , réécrivez-la comme un mélange d'états séparables . Soit le résultat de la post-sélection (sur certains qubit) en utilisant le formalisme à l'état pur que j'ai défini ci-dessus. Définissez le résultat de la post-sélection sur comme . $M$ $M = \sum p_i \left\vert a_i \right> \left< a_i \right\vert$ $\left\vert A_i \right>$ $M$ $\sum p_i \left\vert A_i \right> \left< A_i \right\vert$

C'est une définition plus sensée, car elle ne nous donne pas de résultats qui disent qu'après avoir post-sélectionné, nous modifions les statistiques des événements (mesures) que nous avons déjà observés se produire. Autrement dit, les sont des probabilités de pièces que nous avons "déjà retournées". Cela n'a pas de sens pour moi de dire que nous allons remonter dans le temps et biaiser un tirage au sort qui s'est déjà produit parce que cela rendrait la sélection de postes actuelle plus probable. $p_i$

EDIT (28/03/11 1 PM): Niel concède qu'avec mes définitions le problème a du sens et ne banalise pas - mais avec la stipulation que je ne devrais pas l'appeler post-sélection . Étant donné le degré de confusion, je dois être d'accord avec lui. Appelons donc ce que j'ai défini comme étant la sélection , qui effectue une "mesure forcée". Je devrais probablement changer le nom des classes de complexité que j'ai également définies (pour ne pas avoir "Post" en elles) alors appelons-les QMS [k] (quantum-measure-select).

cc.complexity-theory complexity-classes quantum-computing interactive-proofs Shaun Harker
la source

Pouvez-vous définir MPostBQP de manière plus formelle? Si vous voulez simplement dire que cette classe a le pouvoir de post-sélectionner en fonction du résultat de plusieurs bits, alors cette classe doit être contenue dans PostBQP.

Robin Kothari

L'idée clé n'est pas de post-sélectionner sur plusieurs bits à la fois, car comme le souligne Robin, cela n'aide pas. Il est à intercaler des mesures et postselections. Nous ne pouvons pas faire la navette entre eux; l'ordre est important. Par exemple, il ne fonctionnerait pas dans PostBQP pour mesurer la réponse, puis post-sélection.

Shaun Harker

Voir le commentaire sur la réponse de Niel; nous pouvons différer les mesures et les post-sélections jusqu'après l'évolution quantique. Je fais déjà ça! Cependant, le même argument ne semble pas réorganiser les post-sélections après les mesures, car les mesures ne sont pas unitaires. En particulier, je dis que les mesures et les sélections sont des opérations non unitaires sur l'état quantique qui ne commutent pas, pour autant que je sache, nous ne pouvons pas, sans perte, reporter toutes les sélections jusqu'à après toutes les mesures.

Shaun Harker

@Shaun Harker: le fait que les mesures et les post-sélections ne soient pas unitaires ne nous donne en fait pas plus d'informations pour savoir si elles feront la navette. Peut-être pourriez-vous identifier pourquoi vous pensez qu'ils ne font pas la navette?

Niel de Beaudrap

À cause de l'enchevêtrement. Voici un exemple. Préparez l'état . Choisissez . Si nous mesurons d'abord le premier qubit, puis sélectionnons le troisième qubit, puis mesurons le deuxième qubit pour notre résultat, alors nous obtenons ou avec une probabilité égale. Si nous post-sélectionnons d'abord sur le troisième qubit, puis mesurons le premier qubit et enfin mesurons le deuxième qubit pour notre résultat, nous obtenons moins souvent que nous obtenons .

α | 000 ⟩ + \sqrt{1 / 2 - α^{2}} | 011 ⟩ + \sqrt{1 / 2 - β^{2}} | 101 ⟩ + β | 110 ⟩

$\alpha\left\vert 000 \right> + \sqrt{1/2 - \alpha^2} \left\vert 011 \right> + \sqrt{1/2 - \beta^2} \left\vert 101 \right> + \beta\left\vert 110 \right>$

0 < α < β < 1

$0 < \alpha < \beta < 1$

0

$0$

1

$1$

0

$0$

1

$1$

Shaun Harker

Réponses:

Il semble d'après les commentaires que Shaun a en tête quelque chose de différent de ce qui est normalement compris par post-sélection. Je comprends maintenant que cela signifie que les statistiques pour toutes les mesures effectuées avant une post-sélection particulière ne doivent pas être modifiées par la post-sélection suivante. Cela revient à avoir un opérateur de projection où la normalisation est effectuée sur chaque branche de la fonction d'onde correspondant à un résultat de mesure particulier, plutôt que sur la fonction d'onde dans son ensemble.

Dans ce cas, les arguments donnés dans d'autres réponses par moi-même et Neil ne tiennent plus. En effet, on voit facilement que MPostBQP [k], puisque MPostBQP peut être vu comme une machine BQP qui peut faire requêtes vers un oracle PP, et donc MPostBQP . $P^{PP[k]}\subseteq$ $[k]$ $k$ $P^{\# P}\subseteq$

Alors maintenant, nous avons une borne inférieure non triviale, qu'en est-il d'une borne supérieure? Eh bien, le problème est clairement dans PSPACE , mais pouvons-nous faire mieux? En fait, je pense que nous le pouvons.

Nous pouvons écrire n'importe quel calcul dans MPostBQP sous la forme d'une séquence de couches de la forme: calcul quantique suivi d'une post-sélection, suivi d'une mesure de qubit unique. En effet, cela pourrait être une autre façon de formuler MPostBQP [k], comme un calcul composé de telles couches (ce qui est légèrement différent de la définition de Shaun qui, je crois, est destiné à ne compter que le nombre de post-sélections), suivi d'un couche finale de post-traitement classique. J'utiliserai cette définition de MPostBQP [k] dans la suite, car elle conduit à un résultat plus esthétique. $k$

Ce qui suit est mis à jour à partir de la version originale pour corriger un trou dans l'épreuve.

Nous souhaitons d'abord calculer le résultat de la mesure du premier qubit mesuré (non post-sélectionné!). Pour ce faire, nous notons d'abord que tout calcul quantique peut être exprimé en utilisant uniquement les portes Hadamard et les portes Toffoli, et l'amplitude d'un état de base de calcul particulier dans la sortie peut être écrite comme la somme d'au plus termes , où est le nombre total de portes Hadamard, chacune correspondant à un chemin de calcul unique. Clairement, . La probabilité d'obtenir un état final est alors donnée par $\alpha_w$ $|w\rangle$ $2^{H}$ $a_{j,w}$ $H$ $a_{j,w} = \pm 2^{-H/2}$ $|w\rangle$ $\alpha_w^2 = (\sum_j a_{j,w})^2 = \sum_{i,j} a_{j,w}a_{i,w}$ . Nous souhaitons calculer la probabilité totale de mesurer un 1. Soit l'ensemble des états de base de calcul qui répondent aux critères de post-sélection (c'est-à-dire que le qubit de post-sélection est 1) et aboutissent à 0 pour le qubit mesuré, et soit être l'ensemble des états de base de calcul qui répondent aux critères de post-sélection et donnent 1 pour le qubit mesuré. Nous pouvons définir et $S_0$ $S_1$

π_{0}^{\pm} = \sum w \in S_{0} \pm \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w}

$\pi_0^\pm = \sum{w \in S_0} \pm \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}$

π_{1}^{\pm} = \pm \sum_{w \in S_{1}} \sum_{s i g n (a_{j, w} a_{i, w}) = \pm} a_{j, w} a_{i, w} .

$\pi_1^\pm = \pm \sum_{w \in S_1} \sum_{sign(a_{j,w}a_{i,w}) = \pm} a_{j,w}a_{i,w}.$

Dans ce cas, la probabilité de mesurer un 1 conditionné par un 1 pour le qubit post-sélectionné est donnée par . Comme nous pouvons le déterminer avec 4 appels à un oracle #P. Nous l'utilisons pour produire un bit aléatoire qui est 1 avec une probabilité , identique à la mesure quantique. Ainsi, MPostBQP [1] est dans . $\frac{\pi_1^+ - \pi_1^-}{\pi_1^+ - \pi_1^- - \pi_0^- + \pi_0^+}$ $b_1$ $X_1$ $BPP^{\# P[4]}$

Ensuite, nous calculons le résultat de la mesure du deuxième qubit. Pour ce faire, nous exécutons les mêmes requêtes #P que pour la première couche, mais sur le circuit obtenu en composant les deux premières couches, et où nous post-sélectionnons sur 1 pour chacun des qubits post-sélectionnés, mais aussi sur pour le sortie de la mesure 1. Notez que bien qu'il s'agisse d'une post-sélection sur les états de 3 qubits plutôt que de 1, il s'agit d'une modification triviale des requêtes , en ajoutant simplement une ancilla qui n'est définie que si les 3 qubits remplissent les conditions requises et post-sélection à la place sur cette ancilla. Cela génère alors les probabilités de sortie conditionnelles correctes pour le résultat du deuxième qubit mesuré, que nous appelons $b_1$ $\# P$ $b_2$ . Notez que nous avons maintenant utilisé 8 appels vers l' oracle #P .

Nous répétons ce processus de manière itérative, de sorte qu'à une couche nous sélectionnons sur 1 pour tous les qubits post-sélectionnés précédents et sur pour toutes les mesures précédentes, et étiquetons le résultat du machine . Au total, cela a nécessité requêtes oracle. $j$ $j$ $b_{i<j}$ $P^{\# P}$ $b_j$ $4j$

Nous avons donc MPostBQP [k] , qui combiné avec le résultat précédent que MPostBQP , implique que MPostBQP [k] , et donc MPostBQP . $\subseteq P^{\# P[4k]}$ $P^{PP[k]}\subseteq$ $[k]$ $P^{PP[k]} \subseteq$ $\subseteq BPP^{\# P[4k]}$ $= P^{\# P}$

Joe Fitzsimons
la source

[Révisé.] J'ai révisé ma réponse en fonction de vos révisions à votre question, j'ai conservé le contenu de ma réponse d'origine, mais je l'ai raccourcie. La description plus élaborée du processus de "simulation" a été remplacée, mais je suppose qu'elle peut être vue en consultant l'historique des modifications de ce message.

La plupart des gens comprendront la «post-sélection» dans le sens d'une probabilité conditionnelle. En effet, la version actuelle de l'article Wikipedia sur PostBQP le décrit de cette façon; et vu comme une opération sur les opérateurs de densité (dans laquelle on applique une carte trace-non-croissante complètement positive such, telle que Φ ² = Φ, puis renormalise la trace) on récupère cette définition.

Compte tenu de cette définition de la post-sélection , votre définition d'un algorithme MPostBQP [ k ] peut être simulée par un algorithme PostBQP , en différant les post-sélections et en les exécutant simultanément, de manière appropriée. Ceci est noté plus ou moins explicitement à la page 3 de l'article d'Aaronson sur l' informatique quantique, la post-sélection et le temps polynomial probabiliste qui présente la classe PostBQP .

Cela peut être démontré explicitement en notant que, pour une séquence de bits P ₁ , P ₂ , ... à être post-sélectionnés ( par exemple dans l' 1état, ce qui est habituel), il n'y a pas de différence entre le fait de les conditionner 1au milieu de le calcul et le conditionnement sur eux étant 1en fin de calcul, tant que les valeurs de ces bits ne sont pas modifiées entre-temps. Ensuite, plutôt que de post-sélectionner sur chacun d'eux individuellement 1, nous pouvons calculer leur ET logique avant la post-sélection et ensuite sélectionner sur cette conjonction étant1. De plus, le calcul de l'AND peut être effectué à tout moment entre la dernière transformation du bit et sa post-sélection. Cela n'affectera en rien les statistiques conjointes de l'une des propriétés de l'État.

Ainsi, en utilisant la définition commune de la post-sélection en termes de probabilités conditionnelles, nous aurions MPostBQP [ k ] = PostBQP pour tout k > 0.

Comme je l'ai noté dans les commentaires ci-dessus, je ne pense pas que l'opération que vous décrivez sur l'état vecteurs - en particulier, impliquant la renormalisation des vecteurs d'état indépendamment dans chaque branche de la distribution de probabilité sur les résultats de mesure- correspond à la post-sélection, car de nombreuses personnes sur le terrain (surtout des expérimentateurs) décriraient le concept. Elle peut même donner lieu à certaines propriétés «non physiques», si elle est étendue à une cartographie sur les opérateurs de densité. Cependant, c'est un moyen possible de construire quelque chose comme des arbres de décision dont les nœuds sont étiquetés par des vecteurs d'état, et c'est donc en principe un processus d'étude raisonnable à part entière. Je n'appellerais simplement pas ce processus «post-sélection».

[Modifier.] Par souci de propreté, j'ai supprimé l'exemple calculé. Je suppose que cela peut être vu en consultant l'historique des modifications de ce message.

Niel de Beaudrap
la source

L'argument semble incomplet. Le commentaire dans l'article d'Aaronson souligne que nous n'obtenons aucun pouvoir en intercalant les post-sélections avec les évolutions unitaires, tout comme cela n'aide pas à intercaler les mesures avec les évolutions unitaires. Mais je ne fais ni l'un ni l'autre; J'entremêle la post-sélection et la mesure. Pour répondre à ma question par la négative de cette manière, il faudrait prouver que l'on peut toujours commander les post-sélections après les mesures sans perte de puissance. (Ce n'est pas du tout évident pour moi.) Le reste de la réponse explique seulement pourquoi j'ai défini la classe pour ne post-sélectionner qu'un bit à chaque tour.

Shaun Harker

@Shaun Harker: Peu importe si le document d'Aaronson répond à votre question, ma réponse ci-dessus devrait. L'effet de la post-sélection est essentiellement de permettre aux mesures de réaliser des probabilités conditionnelles plutôt que des probabilités "non conditionnelles". La post-sélection sur les bits est essentiellement la même que la sélection pour les conjonctions de conditions pour les probabilités conditionnelles. Ces probabilités conditionnelles sur les bits ne changent pas, simplement en différant l'évaluation de la condition, tant que les bits sont pas .

C_{j}

$C_j$

C_{j}

$C_j$

C_{j}

$C_j$

Niel de Beaudrap

Il semble que vous souteniez que nous obtenons les mêmes statistiques si nous réorganisons les sélections et les mesures. Mais si nous mesurons quelques bits avant une post-sélection, nous mesurons à partir d'une distribution différente, alors nous aurions si nous mesurions ces mêmes bits après la post-sélection. Les statistiques ne sont donc pas les mêmes.

Shaun Harker

Aux fins de la collecte de statistiques, une post-sélection peut être mise en œuvre physiquement (quoique de manière inefficace) en rejetant simplement les essais dans lesquels la post-condition souhaitée ne tient pas. L'état de maintien d'une condition ( par exemple, "ce bit unique est dans l'état | 1⟩" ou "ces cinq bits sont tous dans l'état | 1⟩") n'est pas affecté par l'ordre de mesure, tant que les opérations ne sont pas appliqué pour changer les bits stockant les résultats. Comme le fait qu'un essai soit rejeté ou non est indépendant de l'ordre de mesure dans PostBQP , nous pouvons différer la post-sélection jusqu'à la fin.

Niel de Beaudrap

Cette caractérisation de la post-sélection s'applique uniquement lorsque nous effectuons la post-sélection avant les mesures. L'exemple à trois qubits que j'ai donné l'a déjà démontré. Si je me trompe, veuillez répondre en réfutant directement cet exemple qui donne des statistiques différentes selon l'ordre des mesures et des post-sélections.

Shaun Harker

Il semblerait d'après votre définition de MPostBQP , qu'il s'agit simplement de PostBQP en tenue de soirée. Plutôt que d'essayer de vous convaincre que les mesures peuvent être réorganisées, vous trouverez peut-être plus convaincant de prouver MPostBQP = PP , car il est connu que PostBQP = PP (voir quant-ph / 0412187 ). Pour le prouver, nous le séparons en deux tâches:

prouvant que PP MPostBQP $\subseteq$ et
prouvant que MPostBQP PP $\subseteq$

La première tâche est triviale, car PP = PostBQP = MPostBQP [1] MPostBQP $\subseteq$ . La deuxième tâche est vraiment la question principale ici, mais elle peut être répondue en faisant une simple adaptation à la preuve que PostBQP = PP , donnée dans quant-ph / 0412187 (voir la page Wikipedia sur PostBQP pour un aperçu de la preuve).

Ce qui suit est adapté de l'esquisse de preuve Wikipedia pour PostBQP = PP .

Nous pouvons écrire le circuit correspondant à tout calcul MPostBQP comme une série de portes unitaires et de post-sélections. Sans perte de généralité, nous pouvons supposer qu'une fois qu'un qubit est post-sélectionné, il n'est plus jamais appliqué. Ainsi, l'état quantique obtenu à la fin du calcul est donné par , où désigne le projecteur pour qubit sur le sous-espace et sont les matrices correspondant aux portes élémentaires. Notez que sans perte de généralité, nous pouvons supposer que toutes les entrées dans sont réelles au détriment d'un qubit supplémentaire. $|\psi\rangle = \prod_i (P_i^1 \prod_j A^{ij}) |x\rangle$ $P_i^1$ $i$ $|1\rangle$ $A^{ij}$ $A^{ij}$

Maintenant, soit l'ensemble des qubits qui sont post-sélectionnés, et soit le qubit de sortie. Nous définissons and , où ( ) est l'ensemble des états de base de calcul pour lesquels et ( ). La définition de MPostBQP garantit alors que ou . L'idée est alors de construire une machine PP pour comparer et $\{p_i\}$ $q$ $\pi_0 = \sum_{w \in S_0} \psi_w^2$ $\pi_1 = \sum_{w \in S_1} \psi_w^2$ $S_0$ $S_1$ $p_i = 1 \forall i$ $q=0$ $q=1$ $\pi(1) \geq 2\pi(0)$ $\pi_0 \geq 2\pi_1$ $\pi_0$ $\pi_1$ . Exprimant , la partie de la fonction d'onde finale correspondant à un état de base de calcul particulier , comme une somme sur les chemins et remplaçant les indices et sur par un seul indice allant de 1 à , on obtient . $\psi_w$ $\psi$ $w$ $i$ $j$ $A^{ij}$ $k$ $G$ $\psi_w = \sum_{\alpha_1 ... \alpha_G} A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$

L'idée est donc de construire une machine PP qui accepte avec probabilité pour certains , car alors impliquerait que et si . $\frac{1}{2}(1+C(\pi_1-\pi_0))$ $C>0$ $x \in L$ $\frac{1}{2}(1+\pi_1-\pi_0)> \frac{1}{2}$ $\frac{1}{2}(1+\pi_1-\pi_0) < \frac{1}{2}$ $x \notin L$

Soit maintenant et . Alors . $\alpha = \{\alpha_i\}$ $F(A,w,\alpha,X) = A^{G}_{w,\alpha_G} A^{G-1}_{\alpha_G,\alpha_{G-1}} ... A^{1}_{\alpha_2,\alpha_1} x_{\alpha_1}$ $\pi_1 - \pi_0 = \sum_{w \in S_1} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X) - \sum_{w \in S_0} \sum{\alpha,\alpha'} F(A,w,\alpha,X)F(A,w,\alpha',X)$

Une telle machine PP peut alors être définie comme suit:

Choisissez un état de base de calcul uniformément au hasard. $w$
Si , alors arrêtez-vous et acceptez avec la probabilité , et rejetez autrement. $w \notin S_0 \cup S_1$ $1/2$
Choisissez deux séquences et des états de base de calcul uniformément au hasard. $\alpha$ $\alpha'$ $G$
Calculez . $X = F(A,w,\alpha,x)F(A,w,\alpha',x)$
Si alors acceptez avec probabilité , et rejetez sinon. Alternativement, si alors acceptez avec probabilité , et rejetez autrement. $w\in S_1$ $\frac{1+X}{2}$ $w\in S_0$ $\frac{1-X}{2}$

Cela met alors MPostBQP [k] PP $\subseteq$ , pour tout , et donc MPostBQP n'est pas plus puissant que PostBQP . $k$

Joe Fitzsimons
la source

Cet argument montre qu'entrecouper plusieurs postsélections avec des évolutions unitaires ne nous donne rien de plus que PP. Je suis entièrement d'accord. Nous pouvons sans perte de puissance les reporter à la fin et nous n'en avons besoin que d'un. Je ne vois pas que cet argument me dit autre chose que cela. Mais ma question demande quelque chose de différent; elle concerne l'évolution unitaire suivie de cycles de mesure et de sélection (les probabilités finales étant calculées via cette méthode d'arbre de décision). Je ne vois donc pas que cela répond à ma question.

Shaun Harker

Pour ne pas dire que je n'apprécie pas (extrêmement) l'effort que vous mettez dans votre réponse. Je ne vois tout simplement pas que cela répond à ce que j'essayais vraiment de faire, ce que je n'ai certes pas fait trop de travail pour expliquer.

Shaun Harker

@Shaun: Je ne vois pas la distinction. Suggérez-vous que l'ajout de mesures modifie la puissance? Ce n'est certainement pas le cas, car les mesures sont toujours équivalentes à une évolution unitaire sur un espace de Hilbert plus grand.

Joe Fitzsimons

@Shaun: Mon point est que mathématiquement la situation avec des mesures et la situation sans (mais avec un espace Hilbert convenablement agrandi) sont identiques. Je n'essaye pas de faire une quelconque remarque philosophique, ou de favoriser une interprétation de la mécanique quantique, je souligne simplement que l'ajout de mesures ne fait aucune différence pour la puissance de calcul en raison d'un résultat (mathématique) bien établi.

Joe Fitzsimons

@Shaun: Il me semble que vous n'implémentez pas correctement la post-sélection. Si vous l'implémentez de la manière normale (c'est-à-dire en considérant les statistiques que vous obtenez si vous ne considérez que les résultats qui correspondent à un critère particulier), vous obtenez PostBQP = MPostBQP, comme l'ont montré Niel et moi. Vous obtenez également des statistiques identiques indépendamment de la commande des mesures de l'état que vous avez donné dans les commentaires. Surtout, le premier qubit ne donne pas 0 et 1 avec une probabilité égale. (à suivre)

Joe Fitzsimons