Wyraźne separacje między obwodami kwantowymi o głębokości poli- i logarytmicznej

Następujący problem pojawia się na liście Aaronsona Dziesięć pół-wielkich wyzwań dla teorii obliczeń kwantowych .

Jest $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ Innymi słowy, i „kwantową” część dowolnego algorytmu kwantowej być skompresowane do $\mathrm{polylog}(n)$ głębokości, pod warunkiem, że jesteśmy gotowi do polynomial- czas klasyczne postprocessing? (Jest to znane z algorytmu Shora.) Jeśli tak, zbudowanie komputera kwantowego ogólnego przeznaczenia byłoby znacznie łatwiejsze niż się powszechnie uważa! Nawiasem mówiąc, nie jest trudno dać wyrocznię między $\mathsf{BQP}$ a $\mathsf{BPP}^{\mathsf{BQNC}}$ , ale pytanie brzmi, czy jest jakaś konkretna funkcja „inicjująca” taką wyrocznię.

Został on przypuszczał przez Józsa , że odpowiedź na to pytanie jest twierdząca w „” modelu pomiaru oparte obliczeń kwantowych. ": Gdzie dozwolone są pomiary lokalne, adaptacyjne lokalne bramy i wydajny klasycznego post-processing Zobacz także ten Related Post .

Pytanie . Chciałbym wiedzieć o znanych obecnie podziałach wyroczni między tymi klasami (a przynajmniej separacji wyroczni, o których mówi Aaronson).

— Juan Bermejo Vega
źródło

Domyślam się, że problem sklejonych drzew jest dobrym kandydatem do separacji. Intuicja polega na tym, że klasyczny komputer jest zasadniczo bezużyteczny do tego zadania, a obwód kwantowy o głębokości polilogu może dotrzeć do polilogu tylko głęboko w sklejonych drzewach, ale musisz dotrzeć do wierzchołka wyjściowego, który jest wielomianowo daleko od wierzchołka wejściowego.

— Robin Kothari,

$BQP$ $BPP^{BQNC}$

— Scott Aaronson
źródło

Rozumiem, dziękuję Scott. Cóż, osobiście podoba mi się ten BQP = BPP ^ BQNC? pytanie, ze względu na jego przydatność do budowy komputerów kwantowych. Myślę, że warto zastanowić się nad tym.

— Juan Bermejo Vega

To pytanie wydaje się rozwiązane: patrz arXiv: 1909.10303 i arXiv: 1909.10503 .

— Sanketh Menda