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:2211.01252

Quantum algorithms for classical Boolean functions via adaptive measurements: Exponential reductions in space-time resources

Austin K. Daniel, Akimasa Miyake

Published Nov 2, 2022• 1 citation
arXivHTMLPDF

Abstract

The limited computational power of constant-depth quantum circuits can be boosted by adapting future gates according to the outcomes of mid-circuit measurements. We formulate computation of a variety of Boolean functions in the framework of adaptive measurement-based quantum computation using a cluster state resource and a classical side-processor that can add bits modulo 2, so-called $l2$-MBQC. Our adaptive approach overcomes a known challenge that computing these functions in the nonadaptive setting requires a resource state that is exponentially large in the size of the computational input. In particular, we construct adaptive $l2$-MBQC algorithms based on the quantum signal processing technique that compute the mod-$p$ functions with the best known scaling in the space-time resources (i.e., qubit count, quantum circuit depth, classical memory size, and number of calls to the side-processor). As the subject is diverse and has a long history, the paper includes reviews of several previously constructed algorithms and recasts them as adaptive $l2$-MBQCs using cluster state resources. Our results constitute an alternative proof of an old theorem regarding an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits with unbounded fan-in NAND and mod-$p$ gates for any prime $p$.

DOI
10.48550/arxiv.2211.01252

Related papers

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

quant-pharXiv:2609.40294•Oct 1, 2026•0 citations

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham +1 more

The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, 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. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice \(\mathsf {QNC}^0/\mathsf {qpoly} \) , and \(\mathsf {AC}^0[p] \) , which is the class of classical constant-depth circuits with unbounded-fan in and \(\mathsf {MOD}_{p} \) gates. Additionally, we show a separation between \(\mathsf {QAC}^0 \) , the circuit class containing Toffoli gates with unbounded control, and \(\mathsf {AC}^0[p] \) , when \(\mathsf {QAC}^0 \) is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between \(\mathsf {AC}^0[p] \) and \([\mathsf {QNC}^0, \mathsf {AC}^0]^2 \) , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider \(\mathsf {QNC}^0 \) circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that \(\mathsf {QNC}^0[p]=\mathsf {QTC}^0 \) . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.

arXiv:2404.18104•ACM Transactions on Quantum Computing•May 18, 2026•3 citations

Mapping quantum circuits to shallow-depth measurement patterns based on graph states

Thierry N. Kaldenbach, Heller, Matthias

The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions, a so-called standard form, which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus enabling a significant decrease in circuit depth for certain applications. We show that groups of fully commuting operators can be implemented using fully-parallel, i.e., non-adaptive, measurements within our protocol. In addition, we discuss how such circuits can be implemented in constant quantum depths by employing quantum teleportation. Finally, we demonstrate the utility of our technique on two examples of high practical relevance: the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE).

arXiv:2311.16223•Nov 27, 2023•0 citations

Hierarchies of resources for measurement-based quantum computation

Markus Frembs, Sam Roberts, Earl T. Campbell +1 more

Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.

arXiv:2203.09965•New Journal of Physics•Dec 28, 2022•11 citations

Mapping quantum circuits to shallow-depth measurement patterns based on graph states

Thierry N. Kaldenbach, Matthias Heller

Abstract The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions—a so-called standard form—which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus, enabling a significant decrease in circuit depth for certain applications. We show that groups of mutually-commuting operators can be implemented using fully-parallel, i.e. non-adaptive, measurements within our protocol. In addition, we discuss how groups of mutually commuting observables can be simulatenously measured by adjusting the resource state, rather than performing a costly basis transformation prior to the measurement as it is done in the circuit model. Finally, we demonstrate the utility of our technique on two examples of high practical relevance—the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver (VQE) for the ground-state energy estimation of the water molecule. For the VQE, we find a reduction of the depth by a factor of 4 to 5 using measurement patterns vs. the standard circuit model. At the same time, since we incorporate the simultaneous measurements, our patterns allow us to save shots by a factor of at least 3.5 compared to measuring Pauli strings individually in the circuit model.

Quantum Science and Technology•Sep 26, 2024•7 citations

Quantum circuit compilation and hybrid computation using Pauli-based computation

Filipa C. R. Peres, Ernesto F. Galvão

Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. Any quantum circuit written in terms of the Clifford+ T gate set and having t T gates can be compiled into a PBC on t qubits. Here we propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing. Our schemes reduce the number of quantum gates to O ( t 2 ) (from a previous O ( t 3 / log ⁡ t ) scaling) and space/time trade-offs are discussed which lead to a reduction of the depth from O ( t log ⁡ t ) to O ( t ) within our schemes, at the cost of t additional auxiliary qubits. We compile examples of random and hidden-shift quantum circuits into adaptive PBC circuits. We also simulate hybrid quantum computation, where a classical computer effectively extends the working memory of a small quantum computer by k virtual qubits, at a cost exponential in k . Our results demonstrate the practical advantage of PBC techniques for circuit compilation and hybrid computation.

arXiv:2203.01789•Quantum•Oct 3, 2023•14 citations
The limited computational power of constant-depth quantum circuits can be boosted by adapting future gates according to the outcomes of mid-circuit measurements. We formulate computation of a variety of Boolean functions in the framework of adaptive measurement-based quantum computation using a cluster state resource and a classical side-processor that can add bits modulo 2, so-called l2l2l2-MBQC. Our adaptive approach overcomes a known challenge that computing these functions in the nonadaptive setting requires a resource state that is exponentially large in the size of the computational input. In particular, we construct adaptive l2l2l2-MBQC algorithms based on the quantum signal processing technique that compute the mod-ppp functions with the best known scaling in the space-time resources (i.e., qubit count, quantum circuit depth, classical memory size, and number of calls to the side-processor). As the subject is diverse and has a long history, the paper includes reviews of several previously constructed algorithms and recasts them as adaptive l2l2l2-MBQCs using cluster state resources. Our results constitute an alternative proof of an old theorem regarding an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits with unbounded fan-in NAND and mod-ppp gates for any prime ppp.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, 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. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice QNC0/qpoly\mathsf {QNC}^0/\mathsf {qpoly} QNC0/qpoly , and AC0[p]\mathsf {AC}^0[p] AC0[p] , which is the class of classical constant-depth circuits with unbounded-fan in and MODp\mathsf {MOD}_{p} MODp​ gates. Additionally, we show a separation between QAC0\mathsf {QAC}^0 QAC0 , the circuit class containing Toffoli gates with unbounded control, and AC0[p]\mathsf {AC}^0[p] AC0[p] , when QAC0\mathsf {QAC}^0 QAC0 is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between AC0[p]\mathsf {AC}^0[p] AC0[p] and [QNC0,AC0]2[\mathsf {QNC}^0, \mathsf {AC}^0]^2 [QNC0,AC0]2 , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider QNC0\mathsf {QNC}^0 QNC0 circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that QNC0[p]=QTC0\mathsf {QNC}^0[p]=\mathsf {QTC}^0 QNC0[p]=QTC0 . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions, a so-called standard form, which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus enabling a significant decrease in circuit depth for certain applications. We show that groups of fully commuting operators can be implemented using fully-parallel, i.e., non-adaptive, measurements within our protocol. In addition, we discuss how such circuits can be implemented in constant quantum depths by employing quantum teleportation. Finally, we demonstrate the utility of our technique on two examples of high practical relevance: the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE).
Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.
Abstract The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions—a so-called standard form—which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus, enabling a significant decrease in circuit depth for certain applications. We show that groups of mutually-commuting operators can be implemented using fully-parallel, i.e. non-adaptive, measurements within our protocol. In addition, we discuss how groups of mutually commuting observables can be simulatenously measured by adjusting the resource state, rather than performing a costly basis transformation prior to the measurement as it is done in the circuit model. Finally, we demonstrate the utility of our technique on two examples of high practical relevance—the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver (VQE) for the ground-state energy estimation of the water molecule. For the VQE, we find a reduction of the depth by a factor of 4 to 5 using measurement patterns vs. the standard circuit model. At the same time, since we incorporate the simultaneous measurements, our patterns allow us to save shots by a factor of at least 3.5 compared to measuring Pauli strings individually in the circuit model.
Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. Any quantum circuit written in terms of the Clifford+ T gate set and having t T gates can be compiled into a PBC on t qubits. Here we propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing. Our schemes reduce the number of quantum gates to O ( t 2 ) (from a previous O ( t 3 / log ⁡ t ) scaling) and space/time trade-offs are discussed which lead to a reduction of the depth from O ( t log ⁡ t ) to O ( t ) within our schemes, at the cost of t additional auxiliary qubits. We compile examples of random and hidden-shift quantum circuits into adaptive PBC circuits. We also simulate hybrid quantum computation, where a classical computer effectively extends the working memory of a small quantum computer by k virtual qubits, at a cost exponential in k . Our results demonstrate the practical advantage of PBC techniques for circuit compilation and hybrid computation.