Problème de comptage approximatif lors de la capture de BQP

Dans le modèle à boîte noire, le problème de la détermination de la sortie d'une machine BPP sur l'entrée est le problème de comptage approximatif de la détermination de avec une erreur additive 1/3 (disons). $M(x,r)$ $x$ $E_r M(x,r)$

Existe-t-il un problème similaire pour BQP? Ce commentaire de Ken Regan suggère un tel problème

Vous pouvez réduire une question BPP à approximer une seule fonction #P, mais avec BQP ce que vous obtenez est la différence de deux fonctions #P, appelez-les et . Approximer et séparément ne vous aide pas à approximer lorsque est proche de zéro! $f$ $g$ $f$ $g$ $f - g$ $f - g$

BQP vous aide un peu: lorsque la réponse à la question BQP sur une entrée est oui, vous obtenez que est proche de la racine carrée de , où les prédicats de comptage définissant et ont m variables binaires après avoir remplacé . (Il n'y a pas de barres de valeur absolue; «par magie», vous obtenez toujours . Sous les représentations courantes des circuits quantiques pour BQP, devient le nombre de portes Hadamard.) Lorsque la réponse est non, le la différence est proche de 0. $x$ $f(x) - g(x)$ $2^m$ $f$ $g$ $x$ $f(x) > g(x)$ $m$

Pouvez-vous formuler avec précision un tel problème le plus près possible du BQP? J'espère quelque chose comme: donner accès à la boîte noire aux fonctions mapper à , avec la promesse que ..., estimer à l'intérieur de . $f,g$ $X$ $Y$ $f-g$ $\varepsilon$

cc.complexity-theory quantum-computing black-box Manu
la source

Je pense que le commentaire de Ken Regan fait référence au résultat BQP⊆AWPP de Fortnow et Rogers (JCSS 1999; people.cs.uchicago.edu/~fortnow/papers/quantum.pdf ).

Tsuyoshi Ito du

Réponses:

Emanuele: Malheureusement, nous ne connaissons aucun problème de boîte noire pour capturer BQP aussi simple que celui que vous avez mentionné pour capturer BPP.

Intuitivement, c'est parce qu'il est difficile de parler de BQP sans introduire l' uniformité sous une forme ou une autre. La capacité à additionner à la fois des nombres positifs et négatifs est ce qui rend BQP plus puissant que BPP, mais alors l'unité est ce qui rend BQP moins puissant que #P! :-)

Cela dit, outre Dawson et al. papier auquel Martin Schwarz a lié, vous devriez certainement vérifier ceci et cela par Janzing et Wocjan, qui donnent des problèmes de promesse "étonnamment classiques" qui capturent le BQP.

Soit également S ⊆ {0,1} ⁿ , et considérons une fonction booléenne f: S → {0,1}. Ensuite, j'ai une conjecture d'il y a des années qui dit que Q (f), la complexité de la requête quantique d'erreur bornée de f, est polynomialement liée au degré minimum d'un polynôme réel p: R ⁿ → R tel que

(i) p (x) ∈ [0,1] pour tout x∈ {0,1} ⁿ , et

(ii) | p (x) -f (x) | ≤ ε pour tous les x∈S.

Si cette conjecture se vérifie, un "problème de comptage approximatif capturant BQP" consisterait simplement à approximer la valeur d'un polynôme de degré polylogique (n) p: R ⁿ → R, à un point spécifié du cube booléen, étant donné que p est délimité partout sur le cube booléen. Cela pourrait être aussi proche que possible de la réponse à votre question.

Scott Aaronson
la source

Merci. J'ai vérifié cette réponse car "Cela pourrait être à peu près aussi proche que possible d'une réponse à votre question." Question: quel est le rôle du "S" dans votre conjecture? Je suis confus en (i) parlant de {0,1} ^ n et les autres parlant de S.

Manu

Emanuele: Si S = {0,1} ^ n, alors f est une fonction booléenne totale. Dans ce cas, il est déjà connu que la complexité de la requête quantique est liée de manière polynomiale au degré approximatif (ainsi qu'à la complexité de la requête déterministe et randomisée). Donc, le cas intéressant est lorsque f est une fonction booléenne partielle : c'est-à-dire que l'algorithme quantique n'a besoin de travailler que sur des entrées satisfaisant la promesse que x appartient à S. devenir possible.

Scott Aaronson

Notez que, alors que l'algorithme quantique n'a besoin que de calculer f sur les entrées appartenant à l'ensemble S, la probabilité d'acceptation de l'algorithme sur les entrées qui ne sont pas dans S appartient toujours à l'intervalle [0,1]! Aussi stupide que cela puisse paraître, cela a souvent été une observation cruciale pour prouver les limites inférieures quantiques via la méthode polynomiale. Et si je n'avais pas exigé que le polynôme p soit borné en [0,1] pour tout x dans {0,1} ^ n (même x pas dans S), alors ma conjecture aurait été trivialement fausse.

Scott Aaronson

Cet article développe en détail les idées esquissées ci-dessus.

Martin Schwarz
la source

Merci pour le lien. La connexion aux équations polynomiales sur semble intéressante.

Z_{2}

$Z_2$

Manu

@Emanuele Viola, @Martin Schwarz: Je ne vois pas vraiment comment ce document répond à la question d'origine. D'une part, ce document ne parle pas du tout des problèmes de boîte noire. Je n'arrive pas à obtenir une formulation nette d'un problème de boîte noire du papier, du type de celui qui est posé dans la question. Peut-être que l'un de vous pourrait faire la lumière là-dessus?

Robin Kothari

@Robin Kothari: Je suis d'accord, que le papier ne pose pas de problème de boîte noire, comme demandé à l'origine. Il précise cependant le commentaire de Ken Regan. J'aurais dû en faire un "commentaire" plutôt qu'une "réponse".

Martin Schwarz

Oh d'accord. Aucun problème. Je suppose donc que la question n'est toujours pas résolue.

Robin Kothari