arXiv:2609.29884
Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates
Amit Saha, Francesco Arzani
Abstract
Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths $n=2^h-1$, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires $6n+3$ logical $P_9$ injections and $\frac{n-3}{4}$ clean ancillary qutrits. It matches the direct $P_9$ count of a recursively extended Clifford+$P_9$ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the $6n+3$ $P_9$ count but has depth $O(\log m+n-m)$ for a balanced core $m=2^h-1\leq n$, which is linear in the worst case over $n$. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.
AI Summary
The paper studies exact multi-controlled Toffoli synthesis with binary-subspace inputs and outputs in the ternary Clifford+$P_9$ model. It uses temporary occupation of $|2\rangle$ to encode conjunctions of controls, arranging their evaluation as a balanced tree rather than a sequential recursion. For $n=2^h-1$ controls, three-control leaf blocks use a Clifford SUM and one state-selective increment. Internal merges combine two subtree markers with another control using three state-selective increments and one clean ancillary qutrit. A single strict controlled target toggle is followed by reversal of the predicate computation. Local marker identities and induction establish correctness, including restoration of controls and ancillas. Counting $2n-4$ state-selective increments at three $P_9$ injections each, plus a 15-injection target toggle, gives $6n+3$ injections and $(n-3)/4$ clean ancillas. Primitive-gate depth is at most $6\log_2(n+1)-7$. This matches the injection count of one recursively extended ternary baseline while asymptotically quartering its ancillary requirement and replacing linear depth with logarithmic depth. Ancilla reuse gives a constructive tradeoff $N_{P_9}(n,A)=9n-6-12A$, with stated depth $O(\log n+n/A)$. For arbitrary widths, sequentially extending a balanced core of size $m$ preserves $6n+3$ injections but gives depth $O(\log m+n-m)$, linear in the worst case. The tradeoff is not claimed globally optimal. Reported depth counts declared primitives, not an explicit injection schedule. Physical advantages remain conditional on error correction, magic-state factories, routing, connectivity, and noise; comparisons with binary circuits do not establish hardware-independent savings.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 15 pages, 3 figures