Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2201.01904

Oracle separations of hybrid quantum-classical circuits

Atul Singh Arora, Alexandru Gheorghiu, Singh, Uttam

Published Jan 6, 2022• 13 citations
arXivHTMLPDF

Abstract

An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d $\nsubseteq$ QC_d and QC_d $\nsubseteq$ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.

DOI
10.3929/ethz-b-000584643

Related papers

On the Need for Large Quantum Depth

Nai-Hui Chia, Kai-Min Chung, Ching–Yi Lai

Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation. Indeed, Jozsa conjectured that “ Any quantum polynomial-time algorithm can be implemented with only O (log n ) quantum depth interspersed with polynomial-time classical computations. ” This can be formalized as asserting the equivalence of BQP and “ BQNC BPP .” However, Aaronson conjectured that “ there exists an oracle separation between BQP and BPP BQNC . ” BQNC BPP and BPP BQNC are two natural and seemingly incomparable ways of hybrid classical-quantum computation. In this work, we manage to prove Aaronson’s conjecture and in the meantime prove that Jozsa’s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter d , there exists an oracle that separates quantum depth d and 2 d +1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth does make the hybrid model more powerful, and this cannot be traded by classical computation.

arXiv:1909.10303•Journal of the ACM•Nov 23, 2022•17 citations

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Atsuya Hasegawa, François Le Gall

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.

arXiv:2205.04633•Leibniz international proceedings in informatics•Jan 1, 2022•8 citations

Classical verification of quantum depth

Nai-Hui Chia, Hung, Shih-Han

We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths even in the presence of classical computation. We show that a device with quantum circuit depth at most d will be rejected by the verifier even if the prover applies additional polynomial-time classical computation to cheat. On the other hand, the verifier accepts a device which has quantum circuit depth d' for some d'>d. In our first protocol, we introduce an additional untrusted quantum machine which shares entanglements with the target machine. Applying a robust self-test, our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation. The protocol relies on the oracle separation problem for quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an oracle separation problem to a two-player non-local game. Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors. The protocol relies on the noisy trapdoor claw-free function family and the idea of pointer chasing to force the prover to keep quantum coherence until all preceding message exchanges are completed. To our knowledge, we give the first constructions for distinguishing hybrid quantum-classical computers with different circuit depths in unrelativized models.

arXiv:2205.04656•May 10, 2022•13 citations

BQP and the Polynomial Hierarchy

Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.

arXiv:0910.4698•Oct 25, 2009•46 citations

Separating ClonableQMA and QCMA Relative to a Classical Oracle

Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung +1 more

Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.

cs.CCCross-listedarXiv:2610.06740•Oct 6, 2026•0 citations

The Space Just Above One Clean Qubit

Dale Jacobs, Saeed Adel Mehraban

Consider the model of computation where we start with two halves of a $2n$-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call $\frac12$BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, $\frac12$BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, $\frac12$BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, $\frac12$BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of $\frac12$BQP and show that similarly to DQC1, $\frac12$BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating $\frac12$BQP and BQP. Due to this limitation, $\frac12$BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that $\frac12$BQP cannot solve $3$-Forrelation.

arXiv:2410.08051•Oct 10, 2024•11 citations
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models, that combine poly-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a d-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a d-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung & Lai (STOC 2020) and Coudron & Menda (STOC 2020) showed that these models (with d=log^O(1) (n)) are strictly weaker than BQP (the class of problems solvable by poly-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. We show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d ⊈\nsubseteq⊈ QC_d and QC_d ⊈\nsubseteq⊈ CQ_d relative to an oracle. In other words, there exist problems that one model can solve but not the other and vice versa. We do this by considering new oracle problems that capture the distinctions between the two models and by introducing the notion of an intrinsically stochastic oracle, an oracle whose responses are inherently randomised, which is used for our second result. While we leave showing the second separation relative to a standard oracle as an open problem, we believe the notion of stochastic oracles could be of independent interest for studying complexity classes which have resisted separation in the standard oracle model. Our constructions also yield simpler oracle separations between the hybrid models and BQP, compared to earlier works.
Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation. Indeed, Jozsa conjectured that “ Any quantum polynomial-time algorithm can be implemented with only O (log n ) quantum depth interspersed with polynomial-time classical computations. ” This can be formalized as asserting the equivalence of BQP and “ BQNC BPP .” However, Aaronson conjectured that “ there exists an oracle separation between BQP and BPP BQNC . ” BQNC BPP and BPP BQNC are two natural and seemingly incomparable ways of hybrid classical-quantum computation. In this work, we manage to prove Aaronson’s conjecture and in the meantime prove that Jozsa’s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter d , there exists an oracle that separates quantum depth d and 2 d +1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth does make the hybrid model more powerful, and this cannot be traded by classical computation.
Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle O\mathcal{O}O such that BQPO≠(BPPBQNC)O∪(BQNCBPP)O\mathsf{BQP}^\mathcal{O} \neq (\mathsf{BPP^{BQNC}})^\mathcal{O} \cup (\mathsf{BQNC^{BPP}})^\mathcal{O}BQPO=(BPPBQNC)O∪(BQNCBPP)O. In fact, Chia et al. proved a stronger statement: for any depth parameter ddd, there exists an oracle that separates quantum depth ddd and 2d+12d+12d+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 ddd, there exists an oracle that separates quantum depth ddd and d+1d+1d+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 ddd-Bijective Shuffling Simon's Problem (which is a variant of ddd-Shuffling Simon's Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.
We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths even in the presence of classical computation. We show that a device with quantum circuit depth at most d will be rejected by the verifier even if the prover applies additional polynomial-time classical computation to cheat. On the other hand, the verifier accepts a device which has quantum circuit depth d' for some d'>d. In our first protocol, we introduce an additional untrusted quantum machine which shares entanglements with the target machine. Applying a robust self-test, our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation. The protocol relies on the oracle separation problem for quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an oracle separation problem to a two-player non-local game. Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors. The protocol relies on the noisy trapdoor claw-free function family and the idea of pointer chasing to force the prover to keep quantum coherence until all preceding message exchanges are completed. To our knowledge, we give the first constructions for distinguishing hybrid quantum-classical computers with different circuit depths in unrelativized models.
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.
Consider the model of computation where we start with two halves of a 2n2n2n-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call 12\frac1221​BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, 12\frac1221​BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, 12\frac1221​BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, 12\frac1221​BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of 12\frac1221​BQP and show that similarly to DQC1, 12\frac1221​BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating 12\frac1221​BQP and BQP. Due to this limitation, 12\frac1221​BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that 12\frac1221​BQP cannot solve 333-Forrelation.