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:2303.12979 · ACM/IEEE Design Automation Conference (DAC)

Optimal Synthesis of Multi-Controlled Qudit Gates

Wei Zi, Qian Li, Xiaoming Sun

Published Jul 9, 2023• 12 citations
arXivHTMLPDF

Abstract

We propose a linear-size synthesis of the multi-controlled Toffoli gate on qudits with at most one borrowed ancilla. This one ancilla can even be saved when the qudit dimension is odd. Our synthesis leads to improvements in various quantum algorithms implemented on qudits. In particular, we obtain (i) a linear-size and one-clean-ancilla synthesis of multi-controlled qudit gates; (ii) an optimal-size and one-clean-ancilla synthesis of unitaries on qudits; (iii) a near-optimal-size and ancilla-free/one-borrowed-ancilla implementation of classical reversible functions as qudit gates.

DOI
10.1109/dac56929.2023.10247925

Related papers

Efficient circuits for exact-universal computation with qudits

Gavin K. Brennen, Stephen S. Bullock, Dianne Prost O’Leary

This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, $\CINC$, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d^n) two-qudit gates for state synthesis and O(d^{2n}) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the (n-2)/(d-2) ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.

arXiv:quant-ph/0509161•Quantum Information and Computation•Jul 1, 2006•39 citations

Optimal Multi-Bit Toffoli Gate Synthesis

Young-Min Jun, In-Chan Choi

Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.

IEEE Access•Jan 1, 2023•3 citations

Efficient implementation of multicontrolled quantum gates

Ben Zindorf, Sougato Bose

We present an implementation of multicontrolled () quantum gates that provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (multicontrolled Toffoli), and requires one clean ancilla, no ancilla, or one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor (LNN) connectivity. All of the methods use a linear cost of gates from the Clifford+ T (fault-tolerant) set. In the context of LNN architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, the quadratic-to-linear controlled- count for LNN, they will naturally result in a large reduction of errors.

arXiv:2404.02279•Physical Review Applied•Sep 15, 2025•50 citations

Efficient High-Dimensional Quantum Circuit Synthesis: From Multi-Controlled Gates to Isometries and Quantum Channels

Gui-Long Jiang

Circuit synthesis of multi-controlled gates is crucial for qudit ($d$-level) quantum computing. This paper presents efficient synthesis schemes that reduce the elementary gate count for multi-controlled single-qudit gates. For synthesizing general $(n-1)$-controlled unitaries on $n$ qudits, we reduce the controlled-increment (CINC) and generalized controlled-$X$ (GCX) gate counts to $O(n^2)$, improving upon existing $O(n^{2+\log_2 d})$ CINC and $O(n^3)$ GCX bounds. For $(n-1)$-controlled special unitaries, this complexity is further reduced to $O(n)$. Furthermore, we present a method for approximately synthesizing multi-controlled unitary gates with a linear complexity in the number of control qudits. By utilizing the proposed circuit, we present qudit-based circuit constructions for isometries and quantum channels from $n$ to $m$ qudits. Moreover, for the first time, we present a circuit synthesis scheme for single-controlled gates using SUM gates and single-qudit gates when $d$ is prime. This enables all CINC-based circuits for various quantum operations to be converted into SUM-gate circuits while preserving the same asymptotic complexity. Finally, we establish a theoretical lower bound on the number of SUM and CINC gates required to synthesize general $n$-qudit unitaries.

quant-pharXiv:2607.08200•Jul 10, 2026•0 citations

Reversible Logic Synthesis with Minimal Usage of Ancilla Bits

Siyao Xu

Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.

arXiv:1506.03777•Jun 10, 2015•16 citations

Almost Optimal Synthesis of Reversible Function in Qudit Model

Boqian Xu, Junhong Nie, Xiaoming Sun

Quantum oracles are widely adopted in problems, like query oracle in Grover’s algorithm, cipher in quantum cryptanalytic and data encoder in quantum machine learning. Notably, the bit-flip oracle, capable of flipping the state based on a given classical function, emerges as a fundamental component in the design and construction of quantum algorithms. Devising methods to optimally implement the bit-flip oracle essentially translates to the efficient synthesis of reversible functions. Prior research has primarily focused on the qubit model, leaving the higher dimensional systems, i.e. qudit model, largely unexplored. By allowing more than two computational bases, qudit model can fully utilize the multi-level nature of the underlying physical mechanism. We propose a method to synthesize even permutations inAdnusing Θ(d) (n− 1)-qudit sub-circuits, which achieve asymptotic optimality in the count of sub-circuits. Moreover, we introduce a technique for synthesizing reversible functions employingO(ndn) two-qudit gates and only a single ancilla. This is asymptotically tight in terms of d and asymptotically almost tight in terms ofn.

arXiv:2501.05237•IEEE Transactions on Information Theory•Dec 4, 2025•0 citations
We propose a linear-size synthesis of the multi-controlled Toffoli gate on qudits with at most one borrowed ancilla. This one ancilla can even be saved when the qudit dimension is odd. Our synthesis leads to improvements in various quantum algorithms implemented on qudits. In particular, we obtain (i) a linear-size and one-clean-ancilla synthesis of multi-controlled qudit gates; (ii) an optimal-size and one-clean-ancilla synthesis of unitaries on qudits; (iii) a near-optimal-size and ancilla-free/one-borrowed-ancilla implementation of classical reversible functions as qudit gates.
This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, $\CINC$, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Lett. 94, 230502 (2005)] describes quantum circuits for qudits which require O(d^n) two-qudit gates for state synthesis and O(d^{2n}) two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state-synthesis circuit in much greater detail and prove that it is correct. Also, the (n-2)/(d-2) ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.
Multi-bit Toffoli gates form an essential quantum gate class for quantum algorithms. They should be efficiently decomposed into elementary single- or multi-qubit quantum gates, such as CNOT, T, and Hadarmard, for a scalable implementation of a quantum algorithm. We propose an engineering method for the practical synthesis of a multi-bit Toffoli gate. Two optimization models and their closed-form solutions are presented for optimal decomposition of the multi-bit Toffoli gate. These models are based on linearized multi-objective integer programming with parameters such as the number of target ancillae, ancillae states, and basis gates. The proposed method supports the systematic handling of quantum circuit constraints, including the total number of available qubits and maximum circuit depth, which depend on various quantum hardware specifications. Our approach exhibits promise in the noisy intermediate-scale quantum environment by providing a rapid and optimal method for synthesizing multi-bit Toffoli gates in diverse and unpredictable quantum hardware specifications.
We present an implementation of multicontrolled () quantum gates that provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (multicontrolled Toffoli), and requires one clean ancilla, no ancilla, or one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor (LNN) connectivity. All of the methods use a linear cost of gates from the Clifford+ T (fault-tolerant) set. In the context of LNN architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, the quadratic-to-linear controlled- count for LNN, they will naturally result in a large reduction of errors.
Circuit synthesis of multi-controlled gates is crucial for qudit (ddd-level) quantum computing. This paper presents efficient synthesis schemes that reduce the elementary gate count for multi-controlled single-qudit gates. For synthesizing general (n−1)(n-1)(n−1)-controlled unitaries on nnn qudits, we reduce the controlled-increment (CINC) and generalized controlled-XXX (GCX) gate counts to O(n2)O(n^2)O(n2), improving upon existing O(n2+log⁡2d)O(n^{2+\log_2 d})O(n2+log2​d) CINC and O(n3)O(n^3)O(n3) GCX bounds. For (n−1)(n-1)(n−1)-controlled special unitaries, this complexity is further reduced to O(n)O(n)O(n). Furthermore, we present a method for approximately synthesizing multi-controlled unitary gates with a linear complexity in the number of control qudits. By utilizing the proposed circuit, we present qudit-based circuit constructions for isometries and quantum channels from nnn to mmm qudits. Moreover, for the first time, we present a circuit synthesis scheme for single-controlled gates using SUM gates and single-qudit gates when ddd is prime. This enables all CINC-based circuits for various quantum operations to be converted into SUM-gate circuits while preserving the same asymptotic complexity. Finally, we establish a theoretical lower bound on the number of SUM and CINC gates required to synthesize general nnn-qudit unitaries.
Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3-bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.
Quantum oracles are widely adopted in problems, like query oracle in Grover’s algorithm, cipher in quantum cryptanalytic and data encoder in quantum machine learning. Notably, the bit-flip oracle, capable of flipping the state based on a given classical function, emerges as a fundamental component in the design and construction of quantum algorithms. Devising methods to optimally implement the bit-flip oracle essentially translates to the efficient synthesis of reversible functions. Prior research has primarily focused on the qubit model, leaving the higher dimensional systems, i.e. qudit model, largely unexplored. By allowing more than two computational bases, qudit model can fully utilize the multi-level nature of the underlying physical mechanism. We propose a method to synthesize even permutations inAdnusing Θ(d) (n− 1)-qudit sub-circuits, which achieve asymptotic optimality in the count of sub-circuits. Moreover, we introduce a technique for synthesizing reversible functions employingO(ndn) two-qudit gates and only a single ancilla. This is asymptotically tight in terms of d and asymptotically almost tight in terms ofn.