Właściwie jest sporo pracy nad nie-abelowskimi problemami ukrytej podgrupy w badaniach algorytmów kwantowych, więc z pewnością mam nadzieję, że tak nie jest!
Joe Fitzsimons,
@Joe: Myślałem, że większość pracy nad nie-Abelowskimi HSP dotyczy grup, które są w jakiś sposób „bliskie Abelianowi” - ale proszę mnie poprawić, jeśli się mylę, ponieważ nie jestem ekspertem w tej dziedzinie. Ale jeśli tak rzeczywiście jest, to pozytywna odpowiedź na to pytanie może nie być sprzeczna z pracami, do których się odwołujesz.
Joshua Grochow
Odpowiedzi:
25
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. .
@Joshua: Te separacje wyroczni są w porządku, ponieważ próbują wykazać moc kwantowych zapytań. Podam przykład tego, co mam na myśli. Jeśli istniałby algorytm czasu policy dla 3SAT, i niech ten algorytm będzie nazywał się X. Najwyraźniej P ^ X zawiera NP. Możemy jednak zbudować separację wyroczni między P ^ X i NP, ponieważ w pierwszym przypadku tylko maszyna P może uzyskać dostęp do wyroczni, a separacja ta jedynie odzwierciedla fakt, że zapytania niedeterministyczne są lepsze niż zapytania deterministyczne. Podobnie, nawet jeśli BPP ^ AHSP zawierał BQP, moglibyśmy dość łatwo oddzielić je wyrocznią.
Robin Kothari,
2
Dziękuję za wszystkie odpowiedzi. W szczególności dziękuję za przypomnienie mi o wielomianach Jonesa i HOMFLY, które nie mają nic wspólnego z HSP. Ocena wielomianu Jonesa dokładnie przy piątym pierwiastku jedności jest trudna do uzyskania w skali P, ale przybliżenie ich do pewnej części epsilonu z pewną probabilistyczną dokładnością jest w BQP.
Jason
10
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.
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.
źródło
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. .
źródło
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.
źródło