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

Fast Cliffords When Your Quantum Memory Is Full

Marten Folkertsma, Ian Mertz, Sergii Strelchuk, Sathyawageeswar Subramanian

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

Related papers

Quantum Catalytic Space

Harry Buhrman, Folkertsma, Marten, Ian Mertz +4 more

Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.

arXiv:2506.16324•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

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

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

Emile Anand, Elia Gorokhovsky, Jennifer Hritz +1 more

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

quant-pharXiv:2608.18536•Aug 20, 2026•0 citations

Semi-Cliffordness of the Clifford hierarchy for a single qudit in composite dimensions

Yifei Qi, Rahul Sarkar

An important question in quantum information theory asks whether every gate in the Clifford hierarchy is semi-Clifford or not, as such gates admit resource-efficient implementations via gate teleportation. Extending recent results for prime dimensions~\cite{silva_clifford_2025}, we prove that every hierarchy gate on a single qudit of dimension \(d\) is semi-Clifford, if and only if \(d\) is square-free. In composite dimensions, \(\mathbb{Z}_d^2\) is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates ($\mathcal{SC}$) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class $\mathcal{N}$ admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates ($\mathcal{LSC}$) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates ($\mathcal{GSC}$) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have \(\mathcal{SC}=\mathcal{LSC}\) and \(\mathcal{N}=\mathcal{GSC}\), but when \(d\) is not square-free, these equivalences can fail, as Lagrangian submodules can become non-free. We also show that every third-level gate of the one-qudit Clifford hierarchy is a generalized semi-Clifford in arbitrary dimensions.

quant-pharXiv:2610.06836•Oct 6, 2026•0 citations

Catalytic Embeddings of Quantum Circuits

Matthew Amy, Crawford, M., Andrew N. Glaudell +3 more

If a set $\mathbb{G}$ of quantum gates is countable, then the operators that can be exactly represented by a circuit over $\mathbb{G}$ form a strict subset of the collection of all unitary operators. When $\mathbb{G}$ is universal, one circumvents this limitation by resorting to repeated gate approximations: every occurrence of a gate which cannot be exactly represented over $\mathbb{G}$ is replaced by an approximating circuit. Here, we introduce catalytic embeddings, which provide an alternative to repeated gate approximations. With catalytic embeddings, approximations are relegated to the preparation of a fixed number of reusable resource states called catalysts. Because the catalysts only need to be prepared once, when catalytic embeddings exist they always produce shorter circuits, in the limit of increasing gate count and target precision. In the present paper, we lay the foundations of the theory of catalytic embeddings and we establish several of their structural properties. In addition, we provide methods to design catalytic embeddings, showing that their construction can be reduced to that of a single fixed matrix when the gates involved have entries in well-behaved rings of algebraic numbers. Finally, we showcase some concrete examples and applications. Notably, we show that catalytic embeddings generalize a technique previously used to implement the Quantum Fourier Transform over the Clifford+$T$ gate set with $O(n)$ gate approximations.

arXiv:2305.07720•May 12, 2023•1 citation

Any Clifford+T circuit can be controlled with constant T-depth overhead

Isaac H. Kim, Tuomas Laakkonen

Since an n-qubit circuit consisting of CNOT gates can have up to $Ω(n^2/\log{n})$ CNOT gates, it is natural to expect that $Ω(n^2/\log{n})$ Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision $ε$ in T-depth exactly 1 using a universal $\lceil\log_2(8/ε)\rceil$-qubit catalyst state.

quant-pharXiv:2512.24982•Jan 1, 2026•0 citations
Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every nnn-qubit Clifford circuit has a catalytic implementation of depth O(log⁡n)O(\log n)O(logn) using O(n2/log⁡2n)O(n^2/\log^2 n)O(n2/log2n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level CkC_kCk​ of the Clifford hierarchy, which admit catalytic implementations of depth O(log⁡(n+1))O(\log(n+1))O(log(n+1)) with O(nk/log⁡(n))O(n^k/\log(n))O(nk/log(n)) gates and O(nk/log⁡2(n))O(n^k/\log^2(n))O(nk/log2(n)) catalytic qubits, as well as to semi-Clifford Gates.
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.
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.
Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth O(log⁡3n)O(\log^3 n)O(log3n). We show that the same asymptotic tradeoff is attained in optimal O(log⁡n)O(\log n)O(logn) depth under a gate distribution with a more restricted support. For every fixed δ>0δ>0δ>0 and sufficiently large nnn, if kn<1−H(dn)−dnlog⁡23−δ\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δnk​<1−H(nd​)−nd​log2​3−δ, we can construct random circuits of depth O(log⁡n)O(\log n)O(logn) which define, with high probability, an [n,k][n,k][n,k] stabilizer code of distance at least d+1d+1d+1, which matches the Ω(log⁡n)Ω(\log n)Ω(logn) light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of TTT independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using n/2n/2n/2 CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.
An important question in quantum information theory asks whether every gate in the Clifford hierarchy is semi-Clifford or not, as such gates admit resource-efficient implementations via gate teleportation. Extending recent results for prime dimensions~\cite{silva_clifford_2025}, we prove that every hierarchy gate on a single qudit of dimension ddd is semi-Clifford, if and only if ddd is square-free. In composite dimensions, Zd2\mathbb{Z}_d^2Zd2​ is a symplectic module rather than a vector space, motivating a distinction between four types of gates. Semi-Clifford gates (SC\mathcal{SC}SC) are the ones that become diagonal under left and right multiplication by Clifford gates, while a broader class N\mathcal{N}N admits a permutation diagonal form, under left and right multiplication by Cliffords. Lagrangian semi-Clifford gates (LSC\mathcal{LSC}LSC) conjugate some maximal abelian Pauli subgroup to another, whereas generalized semi-Clifford gates (GSC\mathcal{GSC}GSC) map some maximal abelian Pauli subalgebra to another under conjugation. In square-free dimensions, we have SC=LSC\mathcal{SC}=\mathcal{LSC}SC=LSC and N=GSC\mathcal{N}=\mathcal{GSC}N=GSC, but when ddd is not square-free, these equivalences can fail, as Lagrangian submodules can become non-free. We also show that every third-level gate of the one-qudit Clifford hierarchy is a generalized semi-Clifford in arbitrary dimensions.
If a set G\mathbb{G}G of quantum gates is countable, then the operators that can be exactly represented by a circuit over G\mathbb{G}G form a strict subset of the collection of all unitary operators. When G\mathbb{G}G is universal, one circumvents this limitation by resorting to repeated gate approximations: every occurrence of a gate which cannot be exactly represented over G\mathbb{G}G is replaced by an approximating circuit. Here, we introduce catalytic embeddings, which provide an alternative to repeated gate approximations. With catalytic embeddings, approximations are relegated to the preparation of a fixed number of reusable resource states called catalysts. Because the catalysts only need to be prepared once, when catalytic embeddings exist they always produce shorter circuits, in the limit of increasing gate count and target precision. In the present paper, we lay the foundations of the theory of catalytic embeddings and we establish several of their structural properties. In addition, we provide methods to design catalytic embeddings, showing that their construction can be reduced to that of a single fixed matrix when the gates involved have entries in well-behaved rings of algebraic numbers. Finally, we showcase some concrete examples and applications. Notably, we show that catalytic embeddings generalize a technique previously used to implement the Quantum Fourier Transform over the Clifford+TTT gate set with O(n)O(n)O(n) gate approximations.
Since an n-qubit circuit consisting of CNOT gates can have up to Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) CNOT gates, it is natural to expect that Ω(n2/log⁡n)Ω(n^2/\log{n})Ω(n2/logn) Toffoli gates are needed to apply a controlled version of such a circuit. We show that the Toffoli count can be reduced to at most n. The Toffoli depth can also be reduced to O(1), at the cost of 2n Toffoli gates, even without using any ancilla or measurement. In fact, using a measurement-based uncomputation, the Toffoli depth can be further reduced to 1. From this, we give two corollaries: any controlled Clifford circuit can be implemented with O(1) T-depth, and any Clifford+T circuit with T-depth D can be controlled with T-depth O(D), even without ancillas. As an application, we show how to catalyze a rotation by any angle up to precision εεε in T-depth exactly 1 using a universal ⌈log⁡2(8/ε)⌉\lceil\log_2(8/ε)\rceil⌈log2​(8/ε)⌉-qubit catalyst state.