This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting U ( 2 ) gates as S U ( 2 ) gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from O ( n 2 ) to at most 32 n . Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from 16 n to 12 n and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting U ( 2 ) gates as S U ( 2 ) gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from O ( n 2 ) to at most 32 n . Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from 16 n to 12 n and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.

arXiv:2406.05581QuantumMar 12, 202512 citations

Qudits and High-Dimensional Quantum Computing

Yuchen Wang, Zixuan Hu, Barry C. Sanders +1 more

Qudit is a multi-level computational unit alternative to the conventional 2-level qubit. Compared to qubit, qudit provides a larger state space to store and process information, and thus can provide reduction of the circuit complexity, simplification of the experimental setup and enhancement of the algorithm efficiency. This review provides an overview of qudit-based quantum computing covering a variety of topics ranging from circuit building, algorithm design, to experimental methods. We first discuss the qudit gate universality and a variety of qudit gates including the pi/8 gate, the SWAP gate, and the multi-level-controlled gate. We then present the qudit version of several representative quantum algorithms including the Deutsch-Jozsa algorithm, the quantum Fourier transform, and the phase estimation algorithm. Finally we discuss various physical realizations for qudit computation such as the photonic platform, iron trap, and nuclear magnetic resonance.Qudit is a multi-level computational unit alternative to the conventional 2-level qubit. Compared to qubit, qudit provides a larger state space to store and process information, and thus can provide reduction of the circuit complexity, simplification of the experimental setup and enhancement of the algorithm efficiency. This review provides an overview of qudit-based quantum computing covering a variety of topics ranging from circuit building, algorithm design, to experimental methods. We first discuss the qudit gate universality and a variety of qudit gates including the pi/8 gate, the SWAP gate, and the multi-level-controlled gate. We then present the qudit version of several representative quantum algorithms including the Deutsch-Jozsa algorithm, the quantum Fourier transform, and the phase estimation algorithm. Finally we discuss various physical realizations for qudit computation such as the photonic platform, iron trap, and nuclear magnetic resonance.

arXiv:2008.00959Frontiers in PhysicsNov 10, 2020487 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.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.08200Jul 10, 20260 citations

Quantum Logic Gates

WORLD SCIENTIFIC eBooksJul 1, 19981 citation

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

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.