Comme cela est bien connu, la PARITÉ ne peut pas être effectuée dans des circuits de profondeur constante de taille poly, et en fait, les circuits const-dept nécessitent un nombre de portes EXP.
Qu'en est-il des circuits QUANTUM?
a) La PARITE peut-elle être effectuée avec un circuit quantique qui a une profondeur constante et un nombre poly de portes?
b) Ma question a-t-elle même un sens?
cc.complexity-theory
quantum-computing
circuit-complexity
Bill GASARCH
la source
la source
Réponses:
La question est logique et la réponse courte est que c'est un problème ouvert.
Voici la réponse longue: selon la façon dont vous définissez les circuits quantiques de fanin illimité à profondeur constante, vous pouvez obtenir différentes classes. Le QAC 0 est généralement défini comme ayant des portes fanoff Toffoli sans limites et des portes à qubit unique. QAC 0 wf est la classe dans laquelle nous autorisons également une porte "fanout", qui copie un bit d'entrée sur de nombreuses sorties. (Elle implémente | a> | 0> ... | 0> -> | a> | a> ... | a>) Cette classe est vraiment puissante car elle contient, outre PARITY et AC 0 , aussi ACC 0 et TC 0 .
Donc, la question évidente à se poser est de savoir si PARITY est contenu dans QAC 0 , et c'est un problème ouvert. Cela revient à demander si QAC 0 = QAC 0 wf . Je suppose que la croyance est que PARITY n'est pas dans QAC 0 . De plus amples informations peuvent être trouvées dans l'enquête Circuits quantiques de faible profondeur par Bera, Green et Homer.
la source
Étonnamment, le nombre de qubits de travail supplémentaires (ancilla) est important. À l'heure actuelle, il est connu que PARITY n'est pas dans QAC_0 avec des ancilles bornées. Les bornes inférieures quantiques pour le fanout donnent une preuve pour les circuits utilisant au plus linéairement plusieurs ancilla et doi: 10.1016 / j.ipl.2011.05.002 donne une autre preuve pour les circuits sans ancillae.
la source