Przybliżony problem z liczeniem przechwytywania BQP

W modelu czarnej skrzynki problem określania wydajności maszyny BPP na wejściu x jest przybliżonym problemem zliczania określania E r M ( x , r ) z błędem addytywnym 1/3 (powiedzmy) .$M(x,r)$$x$$E_r M(x,r)$

Czy istnieje podobny problem dla BQP? Ten komentarz Kena Regana sugeruje taki problem

Możesz sprowadzić pytanie BPP do aproksymacji pojedynczej funkcji #P, ale dzięki BQP otrzymujesz różnicę dwóch funkcji #P, nazwij je i g . Przybliżenie f i g osobno nie pomaga w przybliżeniu f - g, gdy f - g jest bliskie zeru!$f$$g$$f$$g$$f - g$$f - g$

BQP daje ci małą pomoc: gdy odpowiedź na pytanie BQP na wejściu jest twierdząca, otrzymujesz, że f ( x ) - g ( x ) jest zbliżone do pierwiastka kwadratowego z 2 m , gdzie liczenie predykuje zdefiniowanie f i g mają m zmiennych binarnych po podstawieniu na x . (Nie ma słupków wartości bezwzględnej; „magicznie” zawsze dostajesz f ( x ) > g ( x ) . Przy wspólnych reprezentacjach obwodów kwantowych dla BQP, $x$$f(x) - g(x)$$2^m$$f$$g$$x$$f(x) > g(x)$$m$ staje się liczbą bramek Hadamarda.) Gdy odpowiedź brzmi „nie”, różnica jest bliska 0.

Czy potrafisz precyzyjnie sformułować taki problem jak najbliżej BQP? Mam nadzieję na coś takiego: danie czarnej skrzynce dostępu do funkcji odwzorowanie X na Y , z obietnicą, że ... oszacuj f - g na ε .$f,g$$X$$Y$$f-g$$\varepsilon$

Emanuele: Niestety, nie znamy żadnego problemu z czarną skrzynką przechwytywania BQP tak prostego jak ten, o którym wspominałeś przechwytywania BPP.

Intuicyjnie dzieje się tak dlatego, że trudno mówić o BQP bez wprowadzenia jednolitości w takiej czy innej formie. Zdolność do sumowania zarówno liczb dodatnich, jak i ujemnych sprawia, że ​​BQP jest silniejszy niż BPP, ale dzięki jednolitości BQP jest mniej wydajny niż #P! :-)

Powiedziawszy to, oprócz Dawson i in. gazetę, z którą Martin Schwarz napisał link, zdecydowanie powinieneś sprawdzić to i to przez Janzinga i Wocjana, które dają „zaskakująco klasyczny” problem obiecujący chwytanie BQP.

Niech S ⊆ {0,1} ⁿ i rozważmy funkcję boolowską f: S → {0,1}. Następnie mam przypuszczenie sprzed lat, które mówi, że Q (f), złożoność kwantowego zapytania kwantowego błędu f, jest wielomianowo powiązana z minimalnym stopniem prawdziwego wielomianu p: R ⁿ → R, tak że

(i) p (x) ∈ [0,1] dla wszystkich x∈ {0,1} ⁿ , oraz

(ii) | p (x) -f (x) | ≤ ε dla wszystkich x∈S.

Jeśli ta hipoteza się utrzymuje, wówczas „przybliżonym problemem zliczania przechwytującym BQP” byłoby po prostu przybliżenie wartości wielomianu stopni polilog (n) stopni p: R ⁿ → R, w określonym punkcie kostki logicznej, biorąc pod uwagę, że p jest ograniczone wszędzie na kostce boolowskiej. To może być tak blisko, jak tylko można uzyskać odpowiedź na twoje pytanie.

W niniejszym dokumencie szczegółowo omówione zostały pomysły przedstawione powyżej.