Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P9 Gates
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=2h−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 P9 injections and (n−3)/4 clean ancillary qutrits. It matches the direct P9 count of a recursively extended Clifford+P9 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 P9 count but has depth O(log m+n−m) for a balanced core m=2h−1≤ 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.
Related
- Structure-Aware Placement and Routing of Multi-Controlled Toffoli on Bivariate Bicycle Code Architectures
- Efficient Learning of Clifford-Scrambled Product States
- Efficient Fidelity Estimation of General Quantum Resource States via Clifford Circuits
- Efficient learning of Clifford disentanglers and typical t-doped unitaries with exponentially more T gates
- Exact efficient simulation of noisy logical magic states using Clifford stabilizers
BibTeX
@misc{saha2026efficient,
title = {{Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates}},
author = {Amit Saha and Francesco Arzani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29884},
eprint = {2609.29884},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29884},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P_9 Gates
AU - Amit Saha
AU - Francesco Arzani
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29884
UR - https://arxiv.org/abs/2609.29884
AB - 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 (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≤ 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.
ER -