Vérification quantique unidirectionnelle

La théorie du calcul de l'état du cluster est désormais bien établie, montrant que tout circuit BQP peut être modifié de sorte qu'il n'utilise que des portes quantiques à qubit unique, éventuellement contrôlées de manière classique, à condition de fournir amplement un état connu sous le nom d '"état de cluster" - qui est un état de stabilisation simple à produire.

Ma question est la suivante: une notion similaire est-elle connue pour la vérification quantique - c.-à-d. Peut-on remplacer les circuits QMA par des portes à 1 qubit à commande classique, en utilisant éventuellement un "état spécial"? Au moins au début, je ne sais pas pourquoi l'état du cluster peut même fonctionner dans ce cas.

quantum-computing Lior Eldar
la source

Si je comprends bien, est-ce que le problème dans QMA Merlin vous donne une preuve quantique que vous devez d'une manière ou d'une autre intégrer dans le modèle? En d'autres termes, si c'était QCMA au lieu de QMA, où Merlin vous tend juste une chaîne classique, alors nous pourrions simplement utiliser les résultats connus pour BQP, non?

Robin Kothari

Oui c'est correct. Merci d'avoir fait cette distinction.

Lior Eldar

Pour commencer, on pourrait poser la même question pour BQP: pouvons-nous effectuer n'importe quel calcul quantique étant donné la puissance de faire des mesures à 1 qubit, et étant donné une alimentation d'états de cluster non fiables (ou un autre état approprié)?

Norbert Schuch

Réponses:

Il est possible de restreindre le vérificateur QMA aux mesures à un seul qubit et au pré et post-traitement classique (avec aléatoire) tout en conservant l'exhaustivité QMA.

Pour voir pourquoi, prenez n'importe quelle classe de -hamiltoniens complets QMA-locaux sur qubits. En ajoutant une constante d'ordre et en la redimensionnant avec un facteur , l'hamiltonien peut être amené sous la forme où , , et $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{i} w_{i} h_{i},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, où

est un produit de Paulis. L'estimation de la plus petite valeur propre de

jusqu'à la précision

est toujours difficile à effectuer avec l'AMQ.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

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

Nous pouvons maintenant construire un circuit qui utilise uniquement des mesures à un seul qubit qui, étant donné un état , accepte avec une probabilité (qui par construction est compris entre et ). À cette fin, choisissez d'abord au hasard l'un des fonction de la distribution . Ensuite, mesurer chacun des Paulis dans , et prendre la parité des résultats, qui est maintenant liés à $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ via Le circuit émet maintenant, et la sortie est donc distribuée selon.

⟨ ψ | h_{i} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

Autrement dit, si nous avons choisi une instance oui du problème hamiltonien local (QMA-complet), il y a un état de telle sorte que ce vérificateur accepte avec une certaine probabilité , alors que par ailleurs sera rejeté tout état avec une probabilité , avec . La variante de QMA où le vérificateur est limité aux mesures à un qubit est donc QMA complète pour environ $|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ écart. Enfin, cette version de QMA peut être amplifiée en utilisant uniquement les techniques d'amplification conventionnelles pour QMA, ce qui prouve finalement qu'elle est complète en QMA indépendamment de l'écart (dans la même plage que QMA).

Norbert Schuch
la source

Pourriez-vous donner une brève explication ou une référence à la raison pour laquelle le problème de l'estimation de la plus petite valeur propre de

est toujours difficile à l'AMQ? Merci!

H

$H$

Henry Yuen

On part d'un hamiltonien

pour lequel ce problème [jusqu'à

] est QMA-complet, on le change en hamiltonien

, où

, estimant ainsi l'énergie GS de

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$

y = p o l y (n)

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

H

$H$ jusqu'à la précision

est toujours dur QMA.

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$

Norbert Schuch du

Pouvez-vous toujours supposer que

est un projecteur sur un espace propre d'un hamiltonien de Pauli?

h_{i}

$h_i$

Henry Yuen

Eh bien, chaque terme

dans l'hamiltonien d'origine peut être écrit comme une somme de

produits de Pauli (

pour

), et le préfacteur de chaque Pauli le produit

est

h^{'}

$h'$

4^{k}

$4^k$

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$

k = O (\log (n))

$k=O(\log(n))$

P_{i}

$P_i$

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$

Norbert Schuch

Mon interprétation de la question est la suivante: pouvons-nous supposer que le circuit de vérification d'un protocole QMA utilise uniquement des mesures à un seul qubit? (L'idée étant que le prouveur vous envoie à la fois la preuve quantique et l'état de cluster quantique nécessaires pour implémenter le circuit de vérification d'origine par "l'informatique quantique à sens unique".)

Le problème, bien sûr, est que le prouveur peut ne pas vous envoyer du tout un état de cluster valide. Le vérificateur devrait donc tester l'état reçu pour s'assurer qu'il s'agit bien d'un état de cluster. Le vérificateur le fait en effectuant des mesures sur un seul qubit et en vérifiant les corrélations pour satisfaire les vérifications de stabilisateur nécessaires. Étant donné que ces tests sont destructeurs pour l'État, il devrait y avoir une procédure dans laquelle le vérificateur reçoit de nombreuses copies de l'état, vérifie la plupart d'entre elles et en utilise une aléatoire pour le calcul. Polynomialement, plusieurs copies suffisent-elles?

Je ne pense pas que ce soit un théorème connu. Je ne vois pas de contre-exemple évident (avec une minute de réflexion), donc cela pourrait être crédible. La technologie de preuve connue sur les états de test semble être suffisante pour le vérifier. Par exemple, voir l'article arXiv: 1010.1989 de Matthew McKague [quant-ph]. Si vous obtenez une épreuve, envoyez le papier à QIP (date limite le 5 octobre)!

Anonyme
la source

Peut-être que je comprends mal cette question. Si vous demandez si vous pouvez implémenter le circuit du vérificateur pour un problème dans QMA à l'aide d'un calcul basé sur des mesures, où Merlin fournit la couche d'entrée, et Arthur fournit tous les autres qubits à l'état de ressource et entremêle les deux ensembles de qubits avant le début des mesures, alors la réponse est trivialement oui. Cela découle directement du fait que tout circuit quantique peut être implémenté comme un calcul basé sur des mesures, que vous vous souciez de l'entrée classique ou quantique.

Vous remarquerez que dans la plupart des articles sur le calcul basé sur la mesure, les sites d'entrée sont généralement identifiés séparément des autres sites, et c'est pourquoi (c'est-à-dire spécifiquement pour traiter le cas de l'entrée quantique).

Joe Fitzsimons
la source

En fait, je ne suis pas clair sur ce point. Dans les articles sur le calcul basé sur des mesures que j'ai examinés, la transformation s'effectue à partir de n'importe quel circuit BQP avec entrée classique, en un circuit de calcul unidirectionnel à partir de l'état du cluster. C'est-à-dire qu'elle n'est PAS décrite comme une transformation prenant tout circuit unitaire arbitraire U en un circuit basé sur la mesure U_1, quelle que soit l'entrée. Bien que la question de complexité que j'avais posée soit maintenant résolue à la suite de la réponse de Norbert, je voudrais quand même comprendre ce point.

Lior Eldar

@LiorEldar: Alors vous devriez regarder le papier Raussendorf et Briegel original ou celui de Raussendorf, Browne et Briegel. Ils construisent explicitement des circuits une porte à la fois, montrant que chaque modèle de mesure implémente une porte donnée sur la couche d'entrée, qui peut être dans un état arbitraire. Vous pouvez certainement implémenter des circuits arbitraires sur des entrées arbitraires.

Joe Fitzsimons

Lior était en fait ici à Aix-la-Chapelle lorsque nous en avons discuté, et une façon de comprendre la question est basée sur cette idée: Merlin pourrait-il fournir la preuve intégrée dans un état de cluster (non approuvé), et Arthur utilise ses mesures à un qubit pour vérifier le cluster ou vérifier la preuve en utilisant MBQC? (Peut-être que l'on pourrait utiliser des idées similaires à celles des compositions aveugles. Où la correction d'erreur est utilisée?) Malheureusement, on n'a pas besoin de cette belle idée pour prouver la dureté QMA. ;-( Cependant, je pense que c'est toujours une question intéressante pour comprendre si cela fonctionnerait, et vous seriez l'expert pour le montrer :-)

Norbert Schuch

@Lior: Si vous souhaitez utiliser MBQC pour vérifier l'entrée, vous devez bien sûr également utiliser des portes à 2 qubits en plus des mesures à 1 qubit (car vous devez enchevêtrer l'entrée avec votre état de cluster).

Norbert Schuch

@Joe: BTW, la même question pour BQP (pouvons-nous exécuter BQP en utilisant des mesures à 1 qubit en utilisant un état de cluster non approuvé) est bien sûr toujours ouverte, et il me semble que les idées utilisées dans le calcul aveugle pourraient être la voie à suivre .

Norbert Schuch