Przybliżony problem z liczeniem przechwytywania BQP

W modelu czarnej skrzynki problem określania wydajności maszyny BPP na wejściu jest przybliżonym problemem zliczania określania 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 . Przybliżenie i osobno nie pomaga w przybliżeniu gdy 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 jest zbliżone do pierwiastka kwadratowego z , gdzie liczenie predykuje zdefiniowanie i mają m zmiennych binarnych po podstawieniu na . (Nie ma słupków wartości bezwzględnej; „magicznie” zawsze dostajesz . 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 na , z obietnicą, że ... oszacuj na . $f,g$ $X$ $Y$ $f-g$ $\varepsilon$

cc.complexity-theory quantum-computing black-box

— Manu
źródło

Myślę, że komentarz Kena Regana odnosi się do wyniku BQP⊆AWPP autorstwa Fortnow i Rogers (JCSS 1999; people.cs.uchicago.edu/~fortnow/papers/quantum.pdf ).

— Tsuyoshi Ito,

Odpowiedzi:

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.

— Scott Aaronson
źródło

Dzięki. Sprawdziłem tę odpowiedź, ponieważ „Może być tak blisko, jak tylko można uzyskać odpowiedź na twoje pytanie”. Pytanie: jaka jest rola „S” w twoim przypuszczeniu? Jestem zmieszany tym, że (i) mówię o {0,1} ^ n, a reszta mówi o S.

— Manu

Emanuele: Jeśli S = {0,1} ^ n, to f jest całkowitą funkcją logiczną. W takim przypadku wiadomo już, że złożoność kwantowych zapytań jest wielomianowo związana z przybliżonym stopniem (a także z deterministyczną i losową złożonością zapytań). Ciekawym przypadkiem jest zatem, gdy f jest częściową funkcją boolowską: tj. Algorytm kwantowy musi działać tylko na danych wejściowych spełniających obietnicę, że x należy do S. To jest sytuacja, w której algorytmy kwantowe takie jak Simon (które wykładniczo przewyższają najlepszy klasyczny algorytm) stać się możliwym.

— Scott Aaronson

Zauważ, że chociaż algorytm kwantowy musi tylko obliczać f na wejściach należących do zbioru S, prawdopodobieństwo akceptacji algorytmu na wejściach spoza S nadal należy do przedziału [0,1]! To głupie, jak się wydaje, często była to kluczowa obserwacja w dowodzeniu kwantowych dolnych granic metodą wielomianową. A gdybym nie wymagał ograniczenia wielomianu p w [0,1] dla wszystkich x w {0,1} ^ n (nawet x nie w S), to moja hipoteza byłaby trywialnie fałszywa.

— Scott Aaronson

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

— Martin Schwarz
źródło

Z_{2}

$Z_2$

@Emanuele Viola, @Martin Schwarz: Naprawdę nie rozumiem, w jaki sposób ten artykuł odpowiada na pierwotne pytanie. Po pierwsze, ten artykuł w ogóle nie mówi o problemach z czarnymi skrzynkami. Wydaje mi się, że nie mogę uzyskać wyraźnego sformułowania problemu czarnej skrzynki z papieru, takiego typu, jaki jest zadany w pytaniu. Być może któryś z was mógłby rzucić nieco światła na to?

— Robin Kothari,

@Robin Kothari: Zgadzam się, że papier nie powoduje problemu czarnej skrzynki, jak pierwotnie pytano. Rozwija jednak komentarz Kena Regana. Powinienem uczynić to „komentarzem”, a nie „odpowiedzią”.

— Martin Schwarz

Och w porządku. Nie ma problemu. Sądzę więc, że pytanie wciąż pozostaje nierozwiązane.

— Robin Kothari,