A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$

by Xinyu Wu

Theory of Computing, Volume 18(17), pp. 1-11, 2022

Bibliography with links to cited articles

[1]   Scott Aaronson: BQP and the Polynomial Hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. [doi:10.1145/1806689.1806711]

[2]   Scott Aaronson and Andris Ambainis: Forrelation: a problem that optimally separates quantum from classical computing. SIAM J. Comput., 47(3):982–1038, 2018. Preliminary version in STOC’15. [doi:10.1137/15M1050902]

[3]   Boaz Barak and Jarosław Błasiok: On the Raz-Tal oracle separation of BQP and PH, 2018. windowsontheory.org.

[4]   Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett: Pseudorandom generators from polarizing random walks. Theory of Computing, 15(10):1–26, 2019. Preliminary version in CCC’18. [doi:10.4086/toc.2019.v015a010]

[5]    Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal: Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 22:1–22:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.22, ECCC:TR18-155]

[6]   Merrick Lee Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17(1):13–27, 1984. Preliminary version in FOCS’81. [doi:10.1007/BF01744431]

[7]   Bernt ├śksendal: Stochastic Differential Equations. Universitext. Springer, 6th edition, 2003. [doi:10.1007/978-3-642-14394-6]

[8]   Ran Raz and Avishay Tal: Oracle separation of BQP and PH. In Proc. 51st STOC, pp. 13–23. ACM Press, 2019. [doi:10.1145/3313276.3316315, ECCC:TR18-107]

[9]   Daniel Revuz and Marc Yor: Continuous Martingales and Brownian Motion. Volume 293 of Grundlehren der Math. Wiss. Springer, 3rd edition, 1999. [doi:10.1007/978-3-662-06400-9]

[10]   Avishay Tal: Tight bounds on the Fourier spectrum of AC0. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 15:1–15:31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.15, ECCC:TR14-174]