Fast Cliffords When Your Quantum Memory Is Full

arXiv:2609.40144 · quant-ph · Submitted 2026-09-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Fast Cliffords When Your Quantum Memory Is Full".

Mira: Every n-qubit Clifford circuit admits a catalytic implementation of depth O(log n) using O(n squared / log2 n) catalytic qubits and no clean qubits,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So, we're here discussing "Fast Cliffords When Your Quantum Memory Is Full," and what this paper claims about implementing Clifford circuits. The main thrust seems to be that you don't need clean auxiliary qubits for parallel computation; instead, you can use catalytic qubits instead.

Mira: I see. So the core thesis is that every n-qubit Clifford circuit has a way to be implemented catalytically with depth O(log n) using O(n squared / log2 n) catalytic qubits, which matches what we expect when clean workspace is available. That's a big statement about the resource requirements for these circuits.

Lev: From an error correction standpoint, that moves things closer to what we might actually need for fault tolerance; if you can do this with no clean state assumptions, it simplifies the hardware architecture immensely because you don't need to prepare specific initial states on those ancillas.

Kai: Exactly. The paper claims this catalytic implementation works for every n-qubit Clifford circuit, which is a very broad claim covering all these fundamental gates we use in quantum computation.

Mira: And they achieve this by cycling the work register through linear transformations whose contributions cancel out the dependence on its unknown initial state, which is a clever way to handle that uncertainty.

Lev: If you're talking about real hardware, I wonder how reliably that cycling of linear transformations translates into actual gate operations without accumulating errors from those catalytic qubits.

Kai: That's a fair point, Lev. The paper mentions they use this approach and then apply a factorization due to Urschel along with the Clifford normal form of Aaronson and Gottesman to eliminate the clean output register entirely.

Mira: Eliminating that clean output register is significant because it removes another major source of resource overhead that we usually deal with when managing intermediate states in quantum algorithms.

Lev: So, if we consider running this on actual hardware, the main concern shifts from state preparation to maintaining coherence during the cycle through those transformations.

Kai: That's right. The paper then shows that they can extend this approach to diagonal elements of any fixed level Ck of the Clifford hierarchy, achieving a depth of O(log(n + one)) with O(n k / log(n)) gates and O(n k / log2 (n)) catalytic qubits.

Mira: That extension is interesting because it shows the catalytic concept isn't just for the basic Clifford circuits; it applies to a whole family of related operations within that hierarchy.

Lev: For running these on real quantum hardware, if we consider an arbitrary level k, the resource scaling with n seems manageable, but we still have to worry about the exact complexity of those diagonal elements themselves.

Kai: The implication here is that for these specific gate classes, the catalytic implementation matches the asymptotic depth achievable even when clean workspace is present.

Mira: That suggests a fundamental property of Clifford circuits regarding their depth-workspace trade-off that we might not have fully appreciated before this work.

Lev: It gives us a concrete complexity bound to aim for when designing quantum algorithms that rely heavily on these structures, assuming we can manage the required catalytic qubit count.

Kai: Moving into the conclusion of "Fast Cliffords When Your Quantum Memory Is Full," it seems like they are really driving home how this catalytic approach fits into the broader landscape of Clifford circuit implementations.

Mira: The title itself suggests a practical concern—that your quantum memory might be full, and this paper offers a way around that using catalytic resources instead of clean ones.

Lev: If we translate this to error correction hardware design, it means we have a more efficient blueprint for how to structure the computation layers without needing massive amounts of ancillary qubits just for storage.

Kai: The authors are pointing toward a path where we can achieve logarithmic depth implementations that are resource-efficient in terms of clean versus catalytic resources.

Mira: This work implies that the efficiency gain comes not just from reducing gate count, but from changing *what* we use for the intermediate storage mechanism entirely.

Lev: For future hardware development, this suggests a design philosophy where we prioritize the catalytic qubit count as a primary constraint when designing systems for Clifford operations.

Kai: So, to wrap up this discussion on "Fast Cliffords When Your Quantum Memory Is Full," it seems the authors have established a robust method for implementing these circuits with minimal clean resources and logarithmic depth using catalytic ones.

Mira: This is important because it validates the idea that we can bypass some of the standard assumptions about workspace initialization when dealing with these specific gates.

Lev: It provides a solid theoretical foundation for what kind of resource efficiency we can expect to achieve in larger, more complex quantum circuits relying on Clifford operations.

Conclusion: Kai: So we've been looking at how this paper tackles implementing Clifford circuits without needing clean workspace qubits and instead using catalytic ones for depth O(log n).

Mira: I think the title itself really captures the essence of what they're showing, suggesting a solution for when your quantum memory is running out of clean states.

Lev: From my side, if you can manage this resource trade-off, it means we might be able to build much deeper circuits without needing exponentially more qubits just for storage.

Kai: Exactly, and the authors are focused on proving that this catalytic approach matches the asymptotic depth you'd expect even with clean workspace available.

Mira: The authors use a clever technique involving cycling registers through linear transformations to handle the state uncertainty, which is a pretty neat way to manage those intermediate steps without needing extra clean qubits.

Lev: I'm curious about the practical implementation; if this works on paper, how does that translate to actual hardware running these specific O(log n) depth implementations?

Kai: That’s exactly what we need to figure out next, and it leads us into the broader implications of this work for quantum computation.

Mira: This could mean a significant reduction in the overhead required for certain types of quantum algorithms that heavily rely on Clifford operations.

Lev: If we can reduce those resource demands, it opens up possibilities for scaling up error-corrected systems much more efficiently.

Kai: We need to look closely at how this affects the overall architecture of future quantum processors and whether this catalytic qubit requirement is actually achievable in practice.

Marten Folkertsma, Ian Mertz, Sergii Strelchuk, Sathyawageeswar Subramanian

University of Amsterdam · Charles University, Prague, Czech Republic · Department of Computer Science, University of Oxford

quant-ph

Submitted: 2026-09-30

Updated: 2026-09-30

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: Every n-qubit Clifford circuit admits a catalytic implementation of depth O(log n) using O(n squared / log2 n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when

Key concepts

Catalytic Implementation
This approach replaces the need for auxiliary 'clean' qubits with 'catalytic' ones. These catalytic qubits are used to perform intermediate transformations that cancel out the dependency on an unknown initial state of the work register, allowing complex operations to be done without needing a separate clean workspace.
Clifford Normal Form
This is a specific mathematical representation of Clifford circuits derived from Aaronson and Gottesman. Using this form allows researchers to eliminate the need for a separate clean output register during the implementation process, simplifying the circuit structure.
Depth-Workspace Tradeoff
This refers to the relationship between how deep a quantum circuit can be (the number of sequential operations) and how much auxiliary workspace (extra qubits) is required. The paper proves that for Clifford circuits, this tradeoff can be optimized by using catalytic resources instead of traditional clean workspace.

Terminology

Summary

Every n-qubit Clifford circuit admits a catalytic implementation of depth O(log n) using O(n squared / log2 n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available.

The gist

Every n-qubit Clifford circuit admits a catalytic implementation of depth O(log n) using O(n squared / log2 n) catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available.

Catalytic Implementation for Clifford Circuits

The core finding demonstrates that the depth–workspace tradeoff for Clifford circuits can be achieved using catalytic workspace in place of clean auxiliary qubits. The approach involves cycling the work register through a fixed family of linear transformations whose contributions cancel the dependence on its unknown initial state, and then using a factorization due to Urschel [Urs23] along with the Clifford normal form of Aaronson and Gottesman [AG04] to eliminate the clean output register altogether. This method allows extension to diagonal gates in the Clifford hierarchy using classification by Cui, Gottesman, and Krishna [CGK17], as well as semi-Clifford Gates.

Key Results for Clifford Circuits

The paper establishes several key theorems regarding this catalytic implementation:

  1. Theorem 1 shows that for every n-qubit Clifford circuit C, there exists a catalytic Clifford circuit Cc of depth O(n s log n) using O(sn) catalytic qubits and no clean qubits, where 1 ≤ s ≤ n/log2 n.

  2. The construction achieves logarithmic depth using O(n squared / log2 n) catalytic qubits, showing that this degree of parallelization does not require clean workspace.

  3. Theorem 13 proves that every n-qubit Clifford circuit can be implemented with depth O(n s log n) using O(sn) catalytic qubits, up to the global phase convention for Clifford circuits.

Generalizations to Diagonal Gates and Semi-Clifford Unitaries

The results extend beyond standard Clifford circuits to other important classes of quantum operations. For diagonal elements of the Clifford hierarchy (fixed level Ck), Theorem 3 shows that there is a catalytic circuit CD over G using O(sn) catalytic qubits and no clean qubits of depth O(log(n + 1)) + n(k-1)s log(n+1). Specifically, achieving depth O(log(n + 1)) requires only O(n k / log2 (n + 1)) catalytic qubits. Furthermore, the diagonal construction applies to semi-Clifford unitaries U = C1DC2, yielding a catalytic implementation with the same asymptotic bounds.

Application to Approximate Toffoli Gates

The paper shows that these catalytic constructions can be applied to improve implementations of approximate multi-controlled Toffoli gates. Theorem 2 (Informal) suggests that an ε-approximate n-qubit Toffoli gate can be implemented in depth O(log n) using O(log(1/ϵ)) T gates, O(n log(1/ϵ)) catalytic qubits and O(log(1/ϵ)) clean qubits. The catalytic approach reduces the required depth to O(log n) log 1/epsilon s + log log 1/epsilon, which reduces to O(log n) depth when s = Θ(log n), making it optimal for the n-qubit Toffoli gate among circuits of two-qubit gates.

Lower Bounds and Optimality

The paper provides lower bounds to confirm the optimality of the results. Lemma 24 shows that for fixed k, any diagonal unitary in Ck requires a depth of at least h ≥ log2 n, and Theorem 23 confirms that logarithmic depth is necessary in the worst case. The counting argument for workspace also establishes that O(n k / log2 (n + 1)) catalytic qubits are required to implement every such diagonal element exactly with depth at most h.

Catalytic Binary Addition Construction

The technical overview details the construction based on binary linear maps. Lemma 10 provides a catalytic binary addition circuit CeM of depth O(n s log n) using O(sn) catalytic work qubits that implements CeM = [II 0 0; M IO B; 0 0 IW], which is equivalent to implementing Mx in the output register while restoring the work register. Lemma 12 extends this to arbitrary invertible binary matrices M, showing that a catalytic CNOT circuit Cc can implement Mx in depth O(n s log n) using O(sn) catalytic qubits. This construction forms the basis for extending results to Clifford circuits by applying it to the constant number of CNOT circuits in the Clifford normal form.

Phase Synthesis for Diagonal Gates

For diagonal gates, a specific cancellation technique is used.

Improvements for AI systems

As a fastidious researcher, I have analyzed this groundbreaking work on quantum computation, specifically focusing on how it addresses the resource bottlenecks in quantum circuit design—namely, workspace initialization versus catalytic memory.

The paper proves that for Clifford and semi-Clifford circuits, the depth of computation can be reduced from the clean-workspace benchmark (which requires initialized ancillas) to a logarithmic depth using only catalytic qubits (dirty ancillas) whose initial state is arbitrary but must be restored exactly at the end.

Here are the specific, high-value improvements we can implement in AI systems, categorized by application:

  1. Improved Circuit Synthesis and Compilation (Hardware/Software Co-Design)

The core contribution is a new synthesis paradigm that replaces expensive, state-dependent clean ancilla management with a more flexible catalytic model.

Specific Improvements:

  1. Catalytic Compiler Integration: Implement the construction described in Theorem 1 as the default synthesis strategy for Clifford circuits, rather than relying on traditional methods requiring initialized workspace. This allows compilers to utilize any available idle qubits as temporary scratch space, significantly increasing circuit depth reduction potential without needing dedicated clean registers.

  2. Diagonal Gate Optimization: Apply Theorem 3 (and its subsequent logarithmic-depth bound) directly to the synthesis of diagonal unitaries (common in quantum machine learning models like Variational Quantum Eigensolvers or Quantum Neural Networks). This allows for the efficient, resource-aware construction of complex phase gates, trading a polynomial increase in catalytic qubits for a guaranteed logarithmic depth improvement.

  3. Semi-Clifford Unitary Mapping: Use Corollary 25 to optimize the synthesis of semi-Clifford unitaries (common in hybrid quantum/classical algorithms). This ensures that even complex operations involving Clifford factors and diagonal elements maintain the optimal depth scaling, making hybrid quantum models more efficient on current noisy hardware.

What the Improved System Can Do:

The AI system (or a compiler) can generate significantly deeper, yet resource-efficient, quantum circuits for solving problems like molecular simulation or complex optimization tasks. It can achieve near-optimal logarithmic circuit depths for these problems by intelligently utilizing dirty qubits that are otherwise considered unusable due to their prior computation.

  1. Enhanced Quantum Algorithms (Algorithm Design)

The paper provides tools to make inherently resource-intensive algorithms more practical by reducing the required gate count and depth overhead.

Specific Improvements:

  1. Approximate Toffoli Gate Optimization: Leverage Theorem 2 and Lemma 14 to design approximate multi-controlled gates (like the approximate Toffoli gate) with significantly reduced T-gate counts and shallower depths when catalytic qubits are abundant. This is crucial for algorithms that rely on high-fanout multi-control structures.

  2. Efficient Random Parity OR Implementation: Use the ensemble construction in Lemma 14 to implement the random parity OR operation efficiently, reducing its required clean workspace overhead while maintaining a strong diamond-norm guarantee for approximate computation.

What the Improved System Can Do:

The system can execute quantum algorithms that require complex multi-control logic (e.g., certain Grover variants or complex counting problems) with fewer sequential layers and lower error accumulation, leading to faster convergence in variational quantum eigensolvers (VQE) or more robust approximate solutions in NISQ devices.

  1. Robust Resource Estimation and Complexity Analysis

The paper establishes rigorous, worst-case complexity bounds that are tighter than those based solely on clean ancilla assumptions.

Specific Improvements:

  1. Worst-Case Resource Scaling: Implement the lower bound proof in Lemma 24 to provide a rigorously proven floor for required catalytic qubits for any given depth bound. This prevents over-provisioning of physical hardware resources during circuit design, ensuring that the claimed logarithmic depth is actually achievable without needing an arbitrarily large (and impractical) number of catalytic qubits.

  2. Complexity Benchmarking: Use the derived size and depth bounds (Theorem 23) as a standard benchmark for evaluating quantum algorithm efficiency across different gate sets (Clifford vs. semi-Clifford).

What the Improved System Can Do:

The system can perform automated, rigorous complexity analysis on proposed quantum circuits, predicting whether a given circuit structure will meet the target depth and resource constraints based on the established catalytic complexity bounds. This shifts algorithm design from heuristic trial-and-error to provably optimized synthesis.

Sources

Related papers