Oracle Separation of BQP and the Polynomial Hierarchy

on YouTube ↗01h 03m

" summary

Proves an oracle separating BQP from PH by building a boolean distribution D from a 2N‑dimensional multivariate Gaussian (identity and Hadamard blocks), truncating to coin biases and sampling signs. A quantum algorithm runs in O(log N) time with one quantum query and distinguishes D from uniform with advantage 1/log N. Any constant‑depth AC0 circuit of quasi‑polynomial size has advantage ≤ 1/√N. Proof uses sparse low‑degree approximations plus a fractional‑PRG hybrid argument.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 2:27Where does BQP fit in the landscape? BQP: Bounded Error Quantum Polynomial Time
3. 4:00Our Main Result: BQP vs. PH
4. 5:56The Black-Box/Query Model
5. 8:57The Pseudorandomness Setting
6. 13:46The Separating Distribution D (Based on Aaronson's Forrelation distribution)
7. 24:07D is Pseudorandom for AC
8. 25:26Bounded Depth Circuits
9. 29:13The Difference between BQLogTime and AC
10. 35:34Fourier Analytical Approach - First Attempt
11. 39:19Main Technical Lemma
12. 42:47Viewing 2-G as a result of a random walk
13. 44:41Viewing Z-G as a result of a random walk
14. 46:42Claim - Base Case
15. 48:57Reducing the General Case to the Base Case
16. 55:00Recap: Proof by Picture
17. 57:04Open Problems & New results
18. 58:57Open Problems 2: Pseudorandomness Separate BQLogTime and ACO .