Quantum Depth in the Random Oracle Model
- URL: http://arxiv.org/abs/2210.06454v1
- Date: Wed, 12 Oct 2022 17:54:02 GMT
- Title: Quantum Depth in the Random Oracle Model
- Authors: Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and
Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner
- Abstract summary: We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
- Score: 57.663890114335736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a comprehensive characterization of the computational power of
shallow quantum circuits combined with classical computation. Specifically, for
classes of search problems, we show that the following statements hold,
relative to a random oracle:
(a) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{BQP}$. This
refutes Jozsa's conjecture [QIP 05] 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) $\mathsf{BPP}^{\mathsf{QNC}} \nsubseteq \mathsf{QNC}^{\mathsf{BPP}}$ and
$\mathsf{QNC}^{\mathsf{BPP}} \nsubseteq \mathsf{BPP}^{\mathsf{QNC}}$. 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 [STOC 22].
Related papers
- The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically.
We prove new separations between classical and quantum constant-depth circuits.
In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
arXiv Detail & Related papers (2024-04-28T07:44:27Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
We construct a classically succinct interactive argument for quantum computation (BQP)
Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
arXiv Detail & Related papers (2022-06-29T22:19:12Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - An optimal oracle separation of classical and quantum hybrid schemes [0.0]
We show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when computation-time classical is allowed.
This gives an optimal oracle separation of classical and quantum hybrid schemes.
arXiv Detail & Related papers (2022-05-10T02:31:19Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
Two models of quantum computation: CQ_d and QC_d.
CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation.
We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
arXiv Detail & Related papers (2022-01-06T03:10:53Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
We establish the first general connection between the design of quantum algorithms and circuit lower bounds.
Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
arXiv Detail & Related papers (2020-12-03T14:03:20Z) - Simpler Proofs of Quantumness [16.12500804569801]
A proof of quantumness is a method for provably demonstrating that a quantum device can perform computational tasks that a classical device cannot.
There are currently three approaches for exhibiting proofs of quantumness.
We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function.
arXiv Detail & Related papers (2020-05-11T01:31:18Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.