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:1506.04394 · Physical Review A

Optimal synthesis of multivalued quantum circuits

Yao-Min Di, Hai‐Rui Wei

Published Dec 9, 2015• 25 citations
arXivHTMLPDF

Abstract

Although much work has been devoted to multivalued quantum logic synthesis, the question of whether multivalued quantum circuits are more efficient than conventional binary quantum circuits is still open. This article is devoted to the optimization of generic multivalued quantum circuits. Multivalued quantum Shannon decompositions are improved so that the circuits obtained are asymptotically optimal for all dimensionality $d$. The syntheses of uniformly multifold controlled ${R}_{y}$ rotations are also optimized to make the circuits further simplified. Moreover, the theoretical lower bound of complexity for multivalued quantum circuits is investigated, and a quantity known as the efficiency index is proposed to evaluate the efficiency of the synthesis of various quantum circuits. The algorithm for qudit circuits given here is an efficient synthesis routine which produces improved results for all dimensionality $d$, whether the number of qudits $n$ is small or large. The two facts, the leading factor of the lower bound of complexity for qudit circuits is small by a factor of $d\ensuremath{-}1$ in comparison to that for qubit circuits and the asymptotic efficiency index is increased with an increase of dimensionality $d$, reveal the potential advantage of qudit circuits over generic qubit circuits. Generic $n$-qudit circuits with $d\ensuremath{\ge}5$ and generic two-ququart circuits synthesized by the algorithm given here are practical circuits which are more efficient than the most efficient qubit circuits.

DOI
10.1103/physreva.92.062317

Related papers

Synthesis of quantum-logic circuits

Vivek Shende, Stephen S. Bullock, Igor L. Markov

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.

arXiv:quant-ph/0406176•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 12, 2006•794 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

Synthesis of multivalued quantum logic circuits by elementary gates

Yao-Min Di, Hai‐Rui Wei

We propose the generalized controlled $X$ (gcx) gate as the two-qudit elementary gate, and based on Cartan decomposition, we also give the one-qudit elementary gates. Then we discuss the physical implementation of these elementary gates and show that it is feasible with current technology. With these elementary gates many important qudit quantum gates can be synthesized conveniently. We provide efficient methods for the synthesis of various kinds of controlled qudit gates and greatly simplify the synthesis of existing generic multi-valued quantum circuits. Moreover, we generalize the quantum Shannon decomposition (QSD), the most powerful technique for the synthesis of generic qubit circuits, to the qudit case. A comparison of ququart ($d=4$) circuits and qubit circuits reveals that using ququart circuits may have an advantage over the qubit circuits in the synthesis of quantum circuits.

arXiv:1302.0056•Physical Review A•Jan 22, 2013•78 citations

Synthesis of Ternary Quantum Logic Circuits by Decomposition

Khan, Faisal Shah, Perkowski, Marek

Recent research in multi-valued logic for quantum computing has shown practical advantages for scaling up a quantum computer. Multivalued quantum systems have also been used in the framework of quantum cryptography, and the concept of a qudit cluster state has been proposed by generalizing the qubit cluster state. An evolutionary algorithm based synthesizer for ternary quantum circuits has recently been presented, as well as a synthesis method based on matrix factorization.In this paper, a recursive synthesis method for ternary quantum circuits based on the Cosine-Sine unitary matrix decomposition is presented.

arXiv:quant-ph/0511041•Nov 4, 2005•28 citations

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

Beyond quantum Shannon decomposition: Circuit construction for n -qubit gates based on block- Z X Z decomposition

Anna M. Krol, Zaid Al-Ars

This paper proposes an optimized quantum block-$ZXZ$ decomposition method that results in more optimal quantum circuits than the quantum Shannon decomposition, which was presented in 2005 by M. M\"ott\"onen, and J. J. Vartiainen [in Trends in quantum computing research, edited by S. Shannon (Nova Science Publishers, 2006) Chap. 7, p. 149, arXiv:quant-ph/0504100]. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only single-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general three-qubit gate can be decomposed using 19 cnot gates (rather than 20). For general $n$-qubit gates, the proposed decomposition generates circuits that have $\frac{22}{48}{4}^{n}\ensuremath{-}\frac{3}{2}{2}^{n}+\frac{5}{3}$ cnot gates, which is less than the best-known exact decomposition algorithm by $({4}^{n\ensuremath{-}2}\ensuremath{-}1)/3$ cnot gates.

arXiv:2403.13692•Physical Review Applied•Sep 9, 2024•25 citations
Although much work has been devoted to multivalued quantum logic synthesis, the question of whether multivalued quantum circuits are more efficient than conventional binary quantum circuits is still open. This article is devoted to the optimization of generic multivalued quantum circuits. Multivalued quantum Shannon decompositions are improved so that the circuits obtained are asymptotically optimal for all dimensionality ddd. The syntheses of uniformly multifold controlled Ry{R}_{y}Ry​ rotations are also optimized to make the circuits further simplified. Moreover, the theoretical lower bound of complexity for multivalued quantum circuits is investigated, and a quantity known as the efficiency index is proposed to evaluate the efficiency of the synthesis of various quantum circuits. The algorithm for qudit circuits given here is an efficient synthesis routine which produces improved results for all dimensionality ddd, whether the number of qudits nnn is small or large. The two facts, the leading factor of the lower bound of complexity for qudit circuits is small by a factor of d\ensuremath−1d\ensuremath{-}1d\ensuremath−1 in comparison to that for qubit circuits and the asymptotic efficiency index is increased with an increase of dimensionality ddd, reveal the potential advantage of qudit circuits over generic qubit circuits. Generic nnn-qudit circuits with d\ensuremath≥5d\ensuremath{\ge}5d\ensuremath≥5 and generic two-ququart circuits synthesized by the algorithm given here are practical circuits which are more efficient than the most efficient qubit circuits.
The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts.
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.
We propose the generalized controlled XXX (gcx) gate as the two-qudit elementary gate, and based on Cartan decomposition, we also give the one-qudit elementary gates. Then we discuss the physical implementation of these elementary gates and show that it is feasible with current technology. With these elementary gates many important qudit quantum gates can be synthesized conveniently. We provide efficient methods for the synthesis of various kinds of controlled qudit gates and greatly simplify the synthesis of existing generic multi-valued quantum circuits. Moreover, we generalize the quantum Shannon decomposition (QSD), the most powerful technique for the synthesis of generic qubit circuits, to the qudit case. A comparison of ququart (d=4d=4d=4) circuits and qubit circuits reveals that using ququart circuits may have an advantage over the qubit circuits in the synthesis of quantum circuits.
Recent research in multi-valued logic for quantum computing has shown practical advantages for scaling up a quantum computer. Multivalued quantum systems have also been used in the framework of quantum cryptography, and the concept of a qudit cluster state has been proposed by generalizing the qubit cluster state. An evolutionary algorithm based synthesizer for ternary quantum circuits has recently been presented, as well as a synthesis method based on matrix factorization.In this paper, a recursive synthesis method for ternary quantum circuits based on the Cosine-Sine unitary matrix decomposition is presented.
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.
This paper proposes an optimized quantum block-ZXZZXZZXZ decomposition method that results in more optimal quantum circuits than the quantum Shannon decomposition, which was presented in 2005 by M. M\"ott\"onen, and J. J. Vartiainen [in Trends in quantum computing research, edited by S. Shannon (Nova Science Publishers, 2006) Chap. 7, p. 149, arXiv:quant-ph/0504100]. The decomposition is applied recursively to generic quantum gates, and can take advantage of existing and future small-circuit optimizations. Because our method uses only single-qubit gates and uniformly controlled rotation-Z gates, it can easily be adapted to use other types of multi-qubit gates. With the proposed decomposition, a general three-qubit gate can be decomposed using 19 cnot gates (rather than 20). For general nnn-qubit gates, the proposed decomposition generates circuits that have $\frac{22}{48}{4}^{n}\ensuremath{-}\frac{3}{2}{2}^{n}+\frac{5}{3}$ cnot gates, which is less than the best-known exact decomposition algorithm by $({4}^{n\ensuremath{-}2}\ensuremath{-}1)/3$ cnot gates.