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).

$BQP$$BPP^{BQNC}$