BQP 및 PH 분리

Question

나는 여기에서 "BQP와 PH 사이의 오라클 분리"를 달성하는 문제가 있음을 보여주는 Quanta 기사를 읽고 있었습니다. 간단히 말해, 양자 컴퓨터가 기존 컴퓨터보다 훨씬 적은 수의 오라클 호출로 해결할 수있는 문제가 있습니다 (P = NP 영역에서도).

함수가 상수인지 균형인지를 결정하는 데 잘 알려진 Deutsch-Jozsa 알고리즘보다 더 강력한 결과 인 이유는 무엇입니까? 이 경우에도 고전적인 컴퓨터는$O(n)$양자 컴퓨터는 단일 쿼리로 그렇게 할 수있는 동안 오라클 (함수)을 호출합니다. 이것은 양자 컴퓨터가 P = NP라고하더라도 가능한 기존 컴퓨터와 구별된다는 것을 증명하지 않습니까?

Answer 1

Deutsch-Josza 문제는 $\mathsf{EQP}$ (정확한 양자 다항식 시간) 및 $\mathsf{P}$하지만 효율적인 클래식 알고리즘을 얻기 위해 무작위 화를 추가하는 것에 대한 배제는 없습니다.

예를 들어, Deutsch-Josza 문제는 $\mathsf{BPP}$. 누군가는 오라클에 대해 적은 수의 호출을 할 수 있습니다. 두 개의 다른 출력을 본 적이 있다면 오라클이 균형을 이루고 있다는 것을 알지만 항상 동일한 결과를 본다면 오라클이 높은 확률로 일정하다는 결론을 내릴 수 있습니다.

또한 합리적인 비 무작위 화 추측이 있습니다. $\mathsf{BPP}$ 동일하다 $\mathsf{P}$. 따라서 Deutsch-Josza 문제는$\mathsf{P}$, 모듈로 그러한 derandomization 추측.

그러나 Raz-Tal 논문에서 고려되고 Quanta 기사에서 논의 된 "forrelation problem"은 $\mathsf{BQP}$ 과 $\mathsf{PH}$. 이 forrelation 문제는$\mathsf{BPP}$.

예를 들어, 높은 확률로 다항식 시간에 고전적인 컴퓨터로 오라클을 실행 한 다음 출력에서 ​​Chernoff의 경계와 유사한 것을 사용하여 주어진 분포가 균일 분포인지 관계 분포인지 여부를 결정할 수 없습니다.