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:1909.10303 · Journal of the ACM

On the Need for Large Quantum Depth

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

Published Nov 23, 2022• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/3570637

Related papers

Oracle separations of hybrid quantum-classical circuits

Atul Singh Arora, Alexandru Gheorghiu, Singh, Uttam

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.

arXiv:2201.01904•Jan 6, 2022•3 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•4 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•0 citations

Improved Circuit Lower Bounds and Quantum-Classical Separations

Sabee Grewal, Vinayak M. Kumar

We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters. We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-$d$ GC^0[p] circuits of size $2^{Ω(n^{1/2(d-1)})}$, matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014). Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).

arXiv:2408.16406•Aug 29, 2024•1 citation

IQP circuits for 2-Forrelation

Quentin Buzet, André Chailloux

The $2$-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating $\mathsf{BQP}$ and $\mathsf{PH}$ relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that $2$-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($\mathsf{IQP}$) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed $2$-Forrelation can be solved by a classical random choice between two one-query $\mathsf{IQP}$ circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle $O$ such that $\mathsf{IQP}^O \not\subseteq \mathsf{PH}^O$, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between $\mathsf{IQP}$ and $\mathsf{DQC}_1$. We prove Fourier growth bounds for multi-query $\mathsf{IQP}$ circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted $\mathsf{IQP}$ model. The key ingredient is an algebraic identity of the quadratic function $Q(x) = \sum_{i < j} x_ix_j$ that allows extracting inner-product phases within an $\mathsf{IQP}$ circuit.

quant-pharXiv:2604.15248•Apr 17, 2026•0 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•2 citations
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.
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.
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.
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.
We continue the study of the circuit class GC^0, which augments AC^0 with unbounded-fan-in gates that compute arbitrary functions inside a sufficiently small Hamming ball but must be constant outside it. While GC^0 can compute functions requiring exponential-size circuits, Kumar (CCC 2023) showed that switching-lemma lower bounds for AC^0 extend to GC^0 with no loss in parameters. We prove a parallel result for the polynomial method: any lower bound for AC^0[p] obtained via the polynomial method extends to GC^0[p] without loss in parameters. As a consequence, we show that the majority function MAJ requires depth-ddd GC^0[p] circuits of size 2Ω(n1/2(d−1))2^{Ω(n^{1/2(d-1)})}2Ω(n1/2(d−1)), matching the best-known lower bounds for AC^0[p]. This yields the most expressive class of non-monotone circuits for which exponential-size lower bounds are known for an explicit function. We also prove a similar result for the algorithmic method, showing that E^NP requires exponential-size GCC^0 circuits, extending a result of Williams (JACM 2014). Finally, leveraging our improved classical lower bounds, we establish the strongest known unconditional separations between quantum and classical circuit classes. We separate QNC^0 from GC^0 and GC^0[p] in various settings and show that BQLOGTIME is not contained in GC^0. As a consequence, we construct an oracle relative to which BQP lies outside uniform GC^0, extending the Raz-Tal oracle separation between BQP and PH (STOC 2019).
The 222-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP\mathsf{BQP}BQP and PH\mathsf{PH}PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 222-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP\mathsf{IQP}IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 222-Forrelation can be solved by a classical random choice between two one-query IQP\mathsf{IQP}IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle OOO such that IQPO⊈PHO\mathsf{IQP}^O \not\subseteq \mathsf{PH}^OIQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP\mathsf{IQP}IQP and DQC1\mathsf{DQC}_1DQC1​. We prove Fourier growth bounds for multi-query IQP\mathsf{IQP}IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP\mathsf{IQP}IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixjQ(x) = \sum_{i < j} x_ix_jQ(x)=∑i<j​xi​xj​ that allows extracting inner-product phases within an IQP\mathsf{IQP}IQP circuit.
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.