Volume 18 (2022)
Article 17 pp. 1-11
[Note]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
Received: February 7, 2020
Revised: June 17, 2022
Published: June 23, 2022
Revised: June 17, 2022
Published: June 23, 2022
Keywords: quantum complexity, stochastic calculus
Categories: quantum computing, complexity, relativization, separation of complexity classes, polynomial-time hierarchy, circuit complexity, bounded-depth circuits, stochastic calculus, note
ACM Classification: F.1.3, G.3
AMS Classification: 68Q15, 81P68
Abstract: [Plain Text Version]
Recently, Ran Raz and Avishay Tal proved that in some relativized world, $\mathsf{BQP}$ is not contained in the polynomial-time hierarchy (STOC'19). It has been suggested that some aspects of the proof may be simplified by stochastic calculus. In this note, we describe such a simplification.
Licensed under a Creative Commons Attribution License (CC-BY)