Czy BQP jest równe BPP z dostępem do ukrytej podgrupy Abelian?
Czy BQP jest równe BPP z dostępem do ukrytej podgrupy Abelian?
Odpowiedzi:
Podobnie jak wiele separacji klas złożoności, naszym najlepszym przypuszczeniem jest to, że odpowiedź brzmi: BPP ^ {HSP}! = BQP, ale możemy to tylko rygorystycznie udowodnić względem wyroczni. Ten rozdział zaobserwował Scott Aaronson w tym wpisie na blogu, w którym zauważył, że przyspieszenie Childs, Cleve, Deotto, Farhi, Gutmann i Spielman nie zostało zawarte w SZK.
Z drugiej strony, BPP ^ {HSP} jest zawarty w SZK, przynajmniej jeśli celem jest określenie rozmiaru ukrytej podgrupy. Obejmuje to nawet abelowy HSP, chociaż nie jestem pewien, jak dokładnie znaleźć generatory dowolnej ukrytej podgrupy w SZK. Powodem, dla którego możemy zdecydować o wielkości ukrytej podgrupy jest to, że jeśli f: G-> S ma ukrytą podgrupę H, a my wybieramy g równomiernie losowo z G, to f (g) jest jednorodnie losowy w stosunku do zestawu wielkości | G | / | H |. W szczególności f (g) ma log entropii | G | - log | H |. A ocena entropii jest w SZK.
Nie mam pojęcia, jak można by obalić takie twierdzenie, ale wątpię, czy to prawda. Mamy inne wykładnicze przyspieszenia algorytmów kwantowych, które nie opierają się na Abelian HSP. Co więcej, Abelian HSP nie jest znany jako BQP.
Z drugiej strony, problemy, o których wiadomo, że są kompletne w BQP, to problemy takie jak obliczanie niezmienników węzłów, innych niezmienników różnorodnych, funkcji podziału i przeprowadzania symulacji Hamiltona. Z wyrocznią na którykolwiek z tych problemów BPP byłby tak potężny jak BQP.
Wreszcie jestem pewien, że można zbudować separację wyroczni między dwiema wspomnianymi klasami, ale nie byłby to uczciwy sposób na porównanie ich, ponieważ jedna klasa może zadawać kwantowe kwerendy, a druga nie, więc separacja po prostu odzwierciedla ten fakt. .
Muszę zgodzić się z Robinem, że niekoniecznie jest to łatwe roszczenie do obalenia, chociaż prawie na pewno jest to nieprawda. Bezpośrednim powodem, dla którego wątpię, jest to, że wybrane obliczenia kwantowe są równe PP i wydaje się to sugerować, że statystyki byłyby trudne do odtworzenia. Scott Aaronson ma artykuł w STOC pokazujący, że istnieje problem relacji z wyrocznią, który można rozwiązać w BQP, ale nie w PH.