An optimal oracle separation of classical and quantum hybrid schemes
- URL: http://arxiv.org/abs/2205.04633v2
- Date: Mon, 8 Aug 2022 05:23:10 GMT
- Title: An optimal oracle separation of classical and quantum hybrid schemes
- Authors: Atsuya Hasegawa and Fran\c{c}ois Le Gall
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020)
have shown that there exists an oracle $\mathcal{O}$ such that
$\mathsf{BQP}^\mathcal{O} \neq (\mathsf{BPP^{BQNC}})^\mathcal{O} \cup
(\mathsf{BQNC^{BPP}})^\mathcal{O}$. In fact, Chia et al. proved a stronger
statement: for any depth parameter $d$, there exists an oracle that separates
quantum depth $d$ and $2d+1$, when polynomial-time classical computation is
allowed. This implies that relative to an oracle, doubling quantum depth gives
classical and quantum hybrid schemes more computational power.
In this paper, we show that for any depth parameter $d$, there exists an
oracle that separates quantum depth $d$ and $d+1$, when polynomial-time
classical computation is allowed. This gives an optimal oracle separation of
classical and quantum hybrid schemes. To prove our result, we consider
$d$-Bijective Shuffling Simon's Problem (which is a variant of $d$-Shuffling
Simon's Problem considered by Chia et al.) and an oracle inspired by an
"in-place" permutation oracle.
Related papers
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
We show that the entangled quantum quantum hierarchy $mathsfQEPH$ collapses to its second level.
We also show that only quantum superposition (not classical probability) increases the computational power of these hierarchies.
arXiv Detail & Related papers (2024-01-02T22:25:56Z) - A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
It is a long-standing open question in quantum complexity theory whether the definition of $textitnon-deterministic$ quantum computation requires quantum witnesses.
We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes.
arXiv Detail & Related papers (2022-10-27T12:43:56Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
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.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - 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) - The Acrobatics of BQP [1.7136832159667206]
We show that in the black-box setting the behavior of quantum-time ($mathsfBQP$) can be remarkably decoupled from that of classical complexity classes like $mathsfNP$.
We also introduce new tools that might be of independent interest.
These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $mathsfAC0$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
arXiv Detail & Related papers (2021-11-19T19:40:05Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
We show that a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state.
We also show that there exists a quantum-time algorithm that can generate a witness for a $mathsfQMA$ problem up to inverse precision.
We also explore the more general $textitstate synthesis problem$, in which the goal is to efficiently synthesize a target state.
arXiv Detail & Related papers (2021-11-04T16:52:58Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z)
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.