Atul Singh Arora

We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, we show that the following statements hold relative to a random oracle: (a) latex mathsfBPP^QNC^BPP neq mathsfBQP. This refutes Jozsa's conjecture [Joz05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing. (b) latex mathsfQNC^BPP notsubseteq mathsfBPP^QNC and latex mathsfBPP^QNC notsubseteq mathsfQNC^BPP This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements. (c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [YZ22]. [Joz05] - Richard Jozsa. ""An introduction to measurement based quantum computation."" In: Quantum Information Processing 199 (Sept. 2005). [YZ22] - Takashi Yamakawa and Mark Zhandry. ""Verifiable quantum advantage without structure."" In: 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.

Abstract Weak coin flipping (WCF) is a fundamental cryptographic primitive for two-party secure computation, where two distrustful parties need to remotely establish a shared random bit whilst having opposite preferred outcomes. It is the strongest known primitive with arbitrarily close to perfect security quantumly while classically, its security is completely compromised (unless one makes further assumptions, such as computational hardness). A WCF protocol is said to have bias \epsilon if neither party can force their preferred outcome with probability greater than 1/2 + \epsilon. Classical WCF protocols are shown to have bias 1/2, i.e., a cheating party can always force their preferred outcome. On the other hand, there exist quantum WCF protocols with arbitrarily small bias, as Mochon showed in his seminal work in 2007 [arXiv:0711.4114]. In particular, he proved the existence of a family of WCF protocols approaching bias \epsilon(k)=1/(4k + 2) for arbitrarily large k and proposed a protocol with bias 1/6. Last year, Arora, Roland and Weis presented a protocol with bias 1/10 and to go below this bias, they designed an algorithm that numerically constructs unitary matrices corresponding to WCF protocols with arbitrarily small bias [STOC'19, p.205-216]. In this work, we present new techniques which yield a fully analytical construction of WCF protocols with bias arbitrarily close to zero, thus achieving a solution that has been missing for more than a decade. Furthermore, our new techniques lead to a simplified proof of existence of WCF protocols by circumventing the non-constructive part of Mochon's proof. As an example, we illustrate the construction of a WCF protocol with bias 1/14.