Séparations oraculaires entre les circuits quantiques poly et log-profondeur

Le problème suivant apparaît dans la liste d'Aaronson Dix demi-grands défis pour la théorie de l'informatique quantique .

Est-ce que $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ En d'autres termes, la partie "quantique" de n'importe quel algorithme quantique peut-elle être compressée à profondeur, à condition que nous soyons prêts à faire du classique polynomial post-traitement? (Ceci est connu pour l'algorithme de Shor.) Si c'est le cas, la construction d'un ordinateur quantique à usage général serait beaucoup plus facile qu'on ne le pense généralement! , il n'est pas difficile de séparer oracle entre et , mais la question est de savoir s'il existe une fonction concrète "instanciant" un tel oracle. $\mathrm{polylog}(n)$ $\mathsf{BQP}$ $\mathsf{BPP}^{\mathsf{BQNC}}$

Il a été conjecturé par Jozsa que la réponse à la question est oui dans le '' modèle basé sur la mesure du calcul quantique ": où les mesures locales, les portes locales adaptatives et le post-traitement classique efficace sont autorisés. Voir aussi cet article connexe .

Question . Je voudrais connaître les séparations oraculaires actuellement connues entre ces classes (ou, au moins, la séparation oracle à laquelle Aaronson fait référence).

cc.complexity-theory quantum-computing circuit-complexity quantum-information circuit-depth Juan Bermejo Vega
la source

Je suppose que le problème des arbres collés est un bon candidat pour la séparation. L'intuition étant qu'un ordinateur classique est essentiellement inutile pour cette tâche, et un circuit quantique de profondeur de polylog ne peut atteindre le polylog profondément dans les arbres collés, mais vous devez atteindre le sommet de sortie qui est polynomialement loin du sommet d'entrée.

Robin Kothari

Je m'excuse; J'étais trop content quand j'ai écrit ça. Bien que je pense qu'il est possible de prouver une séparation oracle entre et utilisant les techniques actuelles, cela n'a pas été fait (12 ans après avoir d'abord pensé au problème, puis le remettre à plus tard!), et vaut certainement un papier pour celui qui l'a fait. Peut-être que votre message m'aidera à me motiver pour enfin éliminer ce problème! $BQP$ $BPP^{BQNC}$

Scott Aaronson
la source

Je vois, merci Scott. Eh bien, j'aime personnellement ce BQP = BPP ^ BQNC? question, en raison de son importance pour la construction d'ordinateurs quantiques. Je pense que cela devrait valoir la peine d'y réfléchir une ou deux fois.

Juan Bermejo Vega

Cette question semble avoir été résolue: voir arXiv: 1909.10303 et arXiv: 1909.10503 .

Sanketh Menda

Séparations oraculaires entre les circuits quantiques poly et log-profondeur

Réponses: