Separacja BQP i PH
Czytałem tutaj artykuł Quanty, który pokazuje, że istnieje problem, który prowadzi do „rozdzielenia wyroczni między BQP i PH”. Mówiąc prościej, istnieje problem, który komputer kwantowy może rozwiązać przy znacznie mniejszej liczbie wezwań do wyroczni niż mógłby to zrobić klasyczny komputer (nawet w dziedzinie, w której P = NP).
Dlaczego jest to lepszy wynik niż dobrze znany algorytm Deutsch-Jozsa do decydowania, czy funkcja jest stała, czy zrównoważona? W tym przypadku też musiał zrobić klasyczny komputer$O(n)$wywołania wyroczni (funkcji), podczas gdy komputer kwantowy mógłby to zrobić za pomocą jednego zapytania. Czy to nie dowodzi, że komputery kwantowe różnią się od wszelkich możliwych komputerów klasycznych, nawet jeśli P = NP?
Odpowiedzi
Problem Deutsch-Josza zapewnia wyrocznię między $\mathsf{EQP}$ (dokładny czas kwantowo-wielomianowy) i $\mathsf{P}$, ale nie ma wykluczenia przed dodaniem randomizacji w celu uzyskania wydajnego klasycznego algorytmu.
Na przykład problem Deutsch-Josza jest trywialny $\mathsf{BPP}$. Można było po prostu wykonać niewielką liczbę telefonów do wyroczni; Jeśli kiedykolwiek zobaczysz dwa różne wyniki, wiesz, że wyrocznia jest zrównoważona, ale jeśli zawsze widzisz ten sam wynik, możesz wywnioskować, że wyrocznia jest stała z dużym prawdopodobieństwem.
Ponadto istnieje uzasadnione przypuszczenie o derandomizacji, że $\mathsf{BPP}$ jest równe $\mathsf{P}$. Stąd problem Deutsch-Josza$\mathsf{P}$, modulo taka hipoteza derandomizacji.
Jednak „problem dotyczący relacji” rozważany w artykule Raz-Tal i omawiany w artykule Quanty zapewnia wyrocznię między $\mathsf{BQP}$ i $\mathsf{PH}$. Ten problem związany z relacjami nie jest prawdopodobny w$\mathsf{BPP}$.
Na przykład, nie możesz z dużym prawdopodobieństwem uruchomić swojej wyroczni z klasycznym komputerem w czasie wielomianowym, a następnie użyć czegoś podobnego do powiązania Chernoffa na wyjściach, aby określić, czy dany rozkład jest rozkładem jednostajnym, czy też rozkładem zależności.