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

Quantum circuit for multi-qubit Toffoli gate with optimal resource

Nie, Junhong, Wei Zi, Xiaoming Sun

Published Feb 7, 2024• 4 citations
arXivHTMLPDF

Abstract

Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the $n$-Toffoli gate and general multi-controlled unitary, which have only $O(\log n)$-depth and $O(n)$-size, and only require $1$ ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of $O(\log^2n)$ and size of $O(n)$ without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.

DOI
10.48550/arxiv.2402.05053

Related papers

Ancilla-free optimal quantum adder

Junhong Nie, Jialiang Tang, Xiaoming Sun +1 more

We construct an exact $n$-bit quantum adder with $O(n)$ gates and $O(\log n)$ depth that requires no ancillary qubits. The circuit uses only $X$, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with $O(n\log\log n)$ gates and $O(\log n)$ depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with $O(n)$ gates. Both the gate count and circuit depth are asymptotically optimal.

quant-pharXiv:2610.34446•Oct 27, 2026•0 citations

Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Amit Saha, Francesco Arzani

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.

quant-pharXiv:2609.29884•Sep 25, 2026•0 citations

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917•Mar 16, 2026•0 citations

Recursive Generation of Multi-Qubits Control Gate to Facilitate the Grover's Quantum Algorithm in Large Scale Database Search

Wen-Li Wang, Shahid Hussain, Nathaniel V. Rondinelli +2 more

Context: Grover's algorithm is a powerful tool in the realm of quantum computing because it offers exponential speedup over classical linear searching for unstructured / unsorted search problems. However, it is challenging to construct efficient and scalable circuits for a multi-input control gate in the algorithm, particularly with a huge number of qubit inputs. Problem: Traditional circuit construction methods often require manual composition for the multi-input gate from basic quantum gates, which can be time consuming and error prone, thus hindering practical implementation. Moreover, the number of simple gates in the composition grows exponentially with the addition of each qubit. Method: This research provides an approach to recursively generate the oracle using Toffoli gates as the fundamental units to enhance scalability and reusability while maintaining effectiveness. The methodology leverages IBM Qiskit and Quantum Lab to simulate quantum computation to prove the practicality and feasibility. Result: The findings from the experiments between recursively and non-recursively generated circuits suggest that our recursive approach can offer comparable accuracy and computational complexity compared to the non-recursive approach. However, it tends to require a larger number of basic quantum gates due to a lack of circuit optimization. Conclusion: The results showcase the applicability of utilizing recursion as a speedy and economical alternative to generate circuits when implementing the Grover's algorithm. It not only presents potential scalability benefits, but also creates an avenue for further research on test verification and performance improvement to the computing community when running in actual quantum hardware.

IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C)•Jul 1, 2024•0 citations

Spin-Based Simulation and Optimization of Multi-Qubit Quantum Gates

Dolananda Sri Naga Phani Sarma Mokkapati, V Ramesh Kumar, D. De +1 more

Spin-based quantum architectures offer a promising route toward scalable and practical quantum computing owing to their long coherence times, high-fidelity gate operations, and compatibility with established semiconductor fabrication processes. This work focuses on the design, decomposition, and simulation of fundamental multi-qubit logic gates on spin-based architectures. An optimized CNOT gate decomposition is presented, achieving a $36.36 \%$ reduction in elementary operations, verified through quantum circuit simulation. Furthermore, a resource-efficient Toffoli (CCNOT) gate is developed, yielding a $38 \%$ reduction in elementary gates and demonstrating improved T-depth efficiency. Finally, a four-qubit circuit example is presented, illustrating the scalability of the pseudocode and validating the correctness of the proposed approach.

International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN)•Dec 20, 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
Resource consumption is an important issue in quantum information processing, particularly during the present NISQ era. In this paper, we investigate resource optimization of implementing multiple controlled operations, which are fundamental building blocks in the field of quantum computing and quantum simulation. We design new quantum circuits for the nnn-Toffoli gate and general multi-controlled unitary, which have only O(log⁡n)O(\log n)O(logn)-depth and O(n)O(n)O(n)-size, and only require 111 ancillary qubit. To achieve these results, we explore the potential of ancillary qubits and discover a method to create new conditional clean qubits from existed ancillary qubits. These techniques can also be utilized to construct an efficient quantum circuit for incrementor, leading to an implementation of multi-qubit Toffoli gate with a depth of O(log⁡2n)O(\log^2n)O(log2n) and size of O(n)O(n)O(n) without any ancillary qubits. Furthermore, we explore the power of ancillary qubits from the perspective of resource theory. We demonstrate that without the assistance of ancillary qubit, any quantum circuit implementation of multi-qubit Toffoli gate must employ exponential precision gates. This finding indicates a significant disparity in computational power of quantum circuits between using and not using ancillary qubits. Additionally, we discuss the comparison of the power of ancillary qubits and extra energy levels in quantum circuit design.
We construct an exact nnn-bit quantum adder with O(n)O(n)O(n) gates and O(log⁡n)O(\log n)O(logn) depth that requires no ancillary qubits. The circuit uses only XXX, CNOT, and Toffoli gates under all-to-all connectivity and is classically reversible. Our construction accelerates the controlled ladder underlying addition. Grouping the data into blocks and use existing control qubits as conditional workspace gives a recursive construction with O(nlog⁡log⁡n)O(n\log\log n)O(nloglogn) gates and O(log⁡n)O(\log n)O(logn) depth. We then coordinate inter-block propagation via two short-path forest operations to cut the per-block workspace requirement, yielding a nonrecursive implementation with O(n)O(n)O(n) gates. Both the gate count and circuit depth are asymptotically optimal.
Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P9+P_9+P9​ Gates
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−1n=2^h-1n=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+36n+36n+3 logical P9P_9P9​ injections and n−34\frac{n-3}{4}4n−3​ clean ancillary qutrits. It matches the direct P9P_9P9​ count of a recursively extended Clifford+P9P_9P9​ 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+36n+36n+3 P9P_9P9​ count but has depth O(log⁡m+n−m)O(\log m+n-m)O(logm+n−m) for a balanced core m=2h−1≤nm=2^h-1\leq nm=2h−1≤n, which is linear in the worst case over nnn. 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.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.
Context: Grover's algorithm is a powerful tool in the realm of quantum computing because it offers exponential speedup over classical linear searching for unstructured / unsorted search problems. However, it is challenging to construct efficient and scalable circuits for a multi-input control gate in the algorithm, particularly with a huge number of qubit inputs. Problem: Traditional circuit construction methods often require manual composition for the multi-input gate from basic quantum gates, which can be time consuming and error prone, thus hindering practical implementation. Moreover, the number of simple gates in the composition grows exponentially with the addition of each qubit. Method: This research provides an approach to recursively generate the oracle using Toffoli gates as the fundamental units to enhance scalability and reusability while maintaining effectiveness. The methodology leverages IBM Qiskit and Quantum Lab to simulate quantum computation to prove the practicality and feasibility. Result: The findings from the experiments between recursively and non-recursively generated circuits suggest that our recursive approach can offer comparable accuracy and computational complexity compared to the non-recursive approach. However, it tends to require a larger number of basic quantum gates due to a lack of circuit optimization. Conclusion: The results showcase the applicability of utilizing recursion as a speedy and economical alternative to generate circuits when implementing the Grover's algorithm. It not only presents potential scalability benefits, but also creates an avenue for further research on test verification and performance improvement to the computing community when running in actual quantum hardware.
Spin-based quantum architectures offer a promising route toward scalable and practical quantum computing owing to their long coherence times, high-fidelity gate operations, and compatibility with established semiconductor fabrication processes. This work focuses on the design, decomposition, and simulation of fundamental multi-qubit logic gates on spin-based architectures. An optimized CNOT gate decomposition is presented, achieving a 36.36%36.36 \%36.36% reduction in elementary operations, verified through quantum circuit simulation. Furthermore, a resource-efficient Toffoli (CCNOT) gate is developed, yielding a 38%38 \%38% reduction in elementary gates and demonstrating improved T-depth efficiency. Finally, a four-qubit circuit example is presented, illustrating the scalability of the pseudocode and validating the correctness of the proposed approach.
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.