arXiv:2609.40144
Fast Cliffords When Your Quantum Memory Is Full
Marten Folkertsma, Ian Mertz, Sergii Strelchuk, Sathyawageeswar Subramanian
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.
AI Summary
Can arbitrary, information-bearing qubits replace initialized ancillas when parallelizing quantum circuits? This paper studies catalytic workspace: the implemented operation must be $U\otimes I_W$, restoring the workspace exactly, including entanglement with other registers. Every $n$-qubit Clifford admits an implementation with no clean ancillas, depth $O(n/(s\log n))$, and $O(sn)$ catalytic qubits for $1\le s\le n/\log^2 n$. Thus logarithmic depth requires $O(n^2/\log^2 n)$ catalytic qubits, matching the asymptotic clean-workspace tradeoff and reducing the workspace relative to a prior $O(n^2)$ dirty-ancilla construction. The construction adapts an existing parallel CNOT compiler: three executions interleaved with linear transformations cancel dependence on the unknown workspace. A six-factor binary-matrix decomposition removes the clean output register, and a Clifford normal form extends the result. For diagonal gates in any fixed hierarchy level $C_k$, and semi-Clifford gates supplied with a Clifford–diagonal decomposition, the depth is $O(\log(n+1)+n^{k-1}/(s\log(n+1)))$ with $O(sn)$ catalytic qubits and size $O(n^k/\log(n+1))$. Phase-polynomial normal forms, finite-field cycling, and quadratic-form reductions establish these bounds. Light-cone and counting arguments give matching worst-case depth–workspace lower bounds. An application parallelizes a randomized approximate multi-controlled Toffoli construction while retaining $O(\log(1/\epsilon))$ T gates, but still uses clean ancillas. The model assumes unrestricted connectivity and bounded-arity gates. Hierarchy-level constants depend on fixed $k$; semi-Clifford decompositions must be supplied. Replacement of clean workspace for general quantum circuits remains conjectural.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.