Complexité informatique de l'optique quantique

Dans "Exigence pour le calcul quantique" , Bartlett et Sanders résument certains des résultats connus pour le calcul quantique à variable continue dans le tableau suivant:

Tableau de Bartlett et Sanders, 2003

MA question est triple:

Neuf ans plus tard, la dernière cellule peut-elle être remplie?
Si une colonne est ajoutée avec le titre "Universal for BQP", à quoi ressemblerait le reste de la colonne?
Le chef-d'œuvre de 95 pages d' Aaronson et Arkhipov peut -il être résumé dans une nouvelle ligne?

quantum-computing Chris Ferrie
la source

La réponse de Chris Granade suggère que la ligne KLM de la colonne de mesure devrait être "comptage de photons, post-sélection". Est-ce que quelqu'un sait du haut de sa tête si les autres régimes nécessitent également une post-sélection?

Chris Ferrie

Peut-être une question stupide, mais le fait que vous puissiez violer une inégalité de Bell avec des photons uniques et une détection homodyne n'est-il pas une preuve que la dernière entrée du tableau n'est pas efficacement simulable?

@ MateusAraújo - La preuve la plus convaincante que la complexité informatique n'a rien à voir avec la localité vient de deux faits: (1) que le formalisme du stabilisateur de qubit est classiquement efficacement simulable via le théorème de Gottesman-Knill mais on peut violer une inégalité de Bell avec les états de stabilisateur; (2) le formalisme du stabilisateur qutrit est également classique et efficacement simulable mais on peut également trouver une variable cachée locale le reproduisant.

Chris Ferrie

Risquer de nuire davantage à votre question, mais: est-il connu un système qui a un modèle local à variable cachée mais qui n'est pas efficacement simulable? Cela me surprendrait vraiment.

@ MateusAraújo - Je pense que tout système chaotique classique fera l'affaire, non?

Chris Ferrie

Réponses:

$n$ $\text{poly}(n) \ge m \ge n$

| 1_{n} ⟩ = | 1, \dots, 1, 0, \dots, 0 ⟩ (n 1s) .

$\left|1_n\right>=\left|1,\dots,1,\ 0,\dots,0\right>\quad (n\text{ 1s}).$

m \times m

$m\times m$

(s_{1}, s_{2}, \dots, s_{m})

$(s_1, s_2, \dots, s_m)$

\sum_{i} s_{i} = n

$\sum_i s_i = n$

s_{i} \geq 0

$s_i \ge 0$

i

$i$ . (La plupart de ces définitions se trouvent aux pages 18-20 de A&A.)

$n$

$1/16^\Gamma$ $\Gamma$

Aaronson explore davantage le cas de l'optique linéaire post-sélectionné dans son article de suivi sur la dureté # P du permanent. Ce résultat a été précédemment prouvé par Valiant, mais Aaronson présente une nouvelle preuve basée sur le théorème de KLM. En guise de remarque, je trouve que ce document constitue une très belle introduction à de nombreux concepts que A&A utilise dans leur chef-d'œuvre BosonSampling.

Chris Granade
la source

Très bonne réponse! Ainsi, les x dans la dernière colonne devraient également avoir une note de bas de page ou, plus précisément, être des points d'interrogation car nous ne savons pas si P = BQP ou non?

Chris Ferrie

Merci! La dernière colonne est au mieux hypothétique, car nous n'avons pas de preuve que P ≠ BQP. Le résultat A&A est l'un des résultats les plus solides que j'ai vu pour séparer le calcul classique et quantique, cependant, en ce qu'il fournit une conséquence concrète et théorique de la complexité de l'existence d'un simulateur classique efficace. Peut-être qu'une colonne plus descriptive serait "les conséquences d'une simulation classique efficace?"

Chris Granade

Une question de suivi qui mérite probablement une question à elle seule: savez-vous s'il existe un moyen naturel de prouver que l'optique linéaire en soi n'est pas universelle pour BQP? Ou existe-t-il un obstacle à la preuve (par exemple en impliquant d'autres choses que nous ne savons pas montrer mais qui sont probablement encore vraies)?

Abhinav

$\cos^2(\frac\pi8)$

Je pense qu'il est juste de dire que la dernière entrée dans le tableau est un "X" en raison de l' informatique quantique avec des clusters à variation continue par Gu et al . Ils montrent que les états de cluster non gaussiens peuvent être influencés par des mesures homodynes pour l'UQC.
La colonne hypothétique "Universel pour BQP" aurait un "X" pour la première ligne et "vérifie" pour le repos - sauf la ligne hypothétique sur le résultat d'Aaronson et Arkhipov, qui aurait un "?" (bien qu'il s'agisse probablement d'un "X" selon les auteurs).
Voir la réponse de Chris Granade ci-dessus.

MISE À JOUR: J'aurais également dû demander si de nouvelles lignes peuvent être ajoutées. En tout cas, on peut en effet: entrez la description de l'image ici

Cela vient de Veitch et al . Voir aussi Mari et Eisert .

Chris Ferrie
la source