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

Decomposing the generalized Toffoli gate with qutrits

Anastasiia S. Nikolaeva, Evgeniy O. Kiktenko, Aleksey K. Fedorov

Published Mar 31, 2022• 41 citations
arXivHTMLPDF

Abstract

The problem of finding efficient decompositions of multiqubit gates is of importance for quantum computing, especially, in application to existing noisy intermediate-scale quantum devices, whose resources are substantially limited. Here we propose a decomposition scheme for a generalized $N$-qubit Toffoli gate with the use of $2N\ensuremath{-}3$ two-qutrit gates for arbitrary connectivity. The fixed number of the required additional levels (the choice of qutrits is optimal) and the use of the iSWAP gate as a native operation make our approach directly applicable for ongoing experiments with superconducting quantum processors. Specifically, we present a blueprint of the realization of the proposed scheme for the Aspen-9 processor supporting quantum operations with qutrits.

DOI
10.1103/physreva.105.032621

Related papers

Generalized Toffoli Gate Decomposition Using Ququints: Towards Realizing Grover’s Algorithm with Qudits

Anastasiia S. Nikolaeva, Evgeniy O. Kiktenko, Aleksey K. Fedorov

Qubits, which are the quantum counterparts of classical bits, are used as basic information units for quantum information processing, whereas underlying physical information carriers, e.g., (artificial) atoms or ions, admit encoding of more complex multilevel states—qudits. Recently, significant attention has been paid to the idea of using qudit encoding as a way for further scaling quantum processors. In this work, we present an efficient decomposition of the generalized Toffoli gate on five-level quantum systems—so-called ququints—that use ququints’ space as the space of two qubits with a joint ancillary state. The basic two-qubit operation we use is a version of the controlled-phase gate. The proposed N-qubit Toffoli gate decomposition has O(N) asymptotic depth and does not use ancillary qubits. We then apply our results for Grover’s algorithm, where we indicate on the sizable advantage of using the qudit-based approach with the proposed decomposition in comparison to the standard qubit case. We expect that our results are applicable for quantum processors based on various physical platforms, such as trapped ions, neutral atoms, protonic systems, superconducting circuits, and others.

arXiv:2212.12505•Entropy•Feb 20, 2023•23 citations

Device-Aware Decomposition and Mapping of Multiple-Control Toffoli Circuits in Quantum Computing Systems

Yibo Jiang, Xueyun Cheng, Pengcheng Zhu +2 more

Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.

•Sep 13, 2024•0 citations

Stable Toffoli Gate on Fixed-Frequency Superconducting Qutrits

Wonho Jang, Y. Iiyama, Naoki Kanazawa +4 more

Entangling gates in superconducting quantum computers suffer from imperfection of control and relaxation of qubits. The Toffoli gate, essential to various quantum algorithms and to certain fast error correction schemes, represents a particular challenge, as it is decomposed into at least six two-qubit gates, whose errors accrue on top of the increased probability of qubit relaxation due to the long gate time. While it is possible to significantly reduce the depth of the Toffoli gate by exploiting three-level, i.e., qutrit states internally, existing methods are susceptible to errors arising from frequency drifts due to charge fluctuation effects in the second excited state of the transmon. In this poster, we propose a novel qutrit-based implementation of the Toffoli gate that is inherently robust against such errors. The method is extensively validated through a pulse-level simulation and experiments performed on IBM Quantum machines. On one device, where the total Toffoli gate time is 2.510μs, we obtained average gate fidelity values of 0.928 ± 0.007 and 0.896 ± 0.036 from multiple measurements performed during the first one and twenty-four hours after calibrations, respectively, where the errors represent the standard deviations of the measurement results.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•1 citation

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

Orchestrated trios: compiling for efficient communication in Quantum programs with 3-Qubit gates

Casey Duckering, Jonathan M. Baker, Andrew Litteken +1 more

Current quantum computers are especially error prone and require high levels of optimization to reduce operation counts and maximize the probability the compiled program will succeed. These computers only support operations decomposed into one- and two-qubit gates and only two-qubit gates between physically connected pairs of qubits. Typical compilers first decompose operations, then route data to connected qubits. We propose a new compiler structure, Orchestrated Trios, that first decomposes to the three-qubit Toffoli, routes the inputs of the higher-level Toffoli operations to groups of nearby qubits, then finishes decomposition to hardware-supported gates.

arXiv:2102.08451•International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Apr 11, 2021•30 citations

Implementing a Ternary Decomposition of the Toffoli Gate on Fixed-FrequencyTransmon Qutrits

Alexey Galda, Michael Cubeddu, Naoki Kanazawa +2 more

Quantum computation is conventionally performed using quantum operations acting on two-level quantum bits, or qubits. Qubits in modern quantum computers suffer from inevitable detrimental interactions with the environment that cause errors during computation, with multi-qubit operations often being a primary limitation. Most quantum devices naturally have multiple accessible energy levels beyond the lowest two traditionally used to define a qubit. Qudits offer a larger state space to store and process quantum information, reducing complexity of quantum circuits and improving efficiency of quantum algorithms. Here, we experimentally demonstrate a ternary decomposition of a multi-qubit operation on cloud-enabled fixed-frequency superconducting transmons. Specifically, we realize an order-preserving Toffoli gate consisting of four two-transmon operations, whereas the optimal order-preserving binary decomposition uses eight \texttt{CNOT}s on a linear transmon topology. Both decompositions are benchmarked via truth table fidelity where the ternary approach outperforms on most sets of transmons on \texttt{ibmq\_jakarta}, and is further benchmarked via quantum process tomography on one set of transmons to achieve an average gate fidelity of 78.00\% $\pm$ 1.93\%.

arXiv:2109.00558•Sep 1, 2021•46 citations
The problem of finding efficient decompositions of multiqubit gates is of importance for quantum computing, especially, in application to existing noisy intermediate-scale quantum devices, whose resources are substantially limited. Here we propose a decomposition scheme for a generalized NNN-qubit Toffoli gate with the use of 2N\ensuremath−32N\ensuremath{-}32N\ensuremath−3 two-qutrit gates for arbitrary connectivity. The fixed number of the required additional levels (the choice of qutrits is optimal) and the use of the iSWAP gate as a native operation make our approach directly applicable for ongoing experiments with superconducting quantum processors. Specifically, we present a blueprint of the realization of the proposed scheme for the Aspen-9 processor supporting quantum operations with qutrits.
Qubits, which are the quantum counterparts of classical bits, are used as basic information units for quantum information processing, whereas underlying physical information carriers, e.g., (artificial) atoms or ions, admit encoding of more complex multilevel states—qudits. Recently, significant attention has been paid to the idea of using qudit encoding as a way for further scaling quantum processors. In this work, we present an efficient decomposition of the generalized Toffoli gate on five-level quantum systems—so-called ququints—that use ququints’ space as the space of two qubits with a joint ancillary state. The basic two-qubit operation we use is a version of the controlled-phase gate. The proposed N-qubit Toffoli gate decomposition has O(N) asymptotic depth and does not use ancillary qubits. We then apply our results for Grover’s algorithm, where we indicate on the sizable advantage of using the qudit-based approach with the proposed decomposition in comparison to the standard qubit case. We expect that our results are applicable for quantum processors based on various physical platforms, such as trapped ions, neutral atoms, protonic systems, superconducting circuits, and others.
Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.
Entangling gates in superconducting quantum computers suffer from imperfection of control and relaxation of qubits. The Toffoli gate, essential to various quantum algorithms and to certain fast error correction schemes, represents a particular challenge, as it is decomposed into at least six two-qubit gates, whose errors accrue on top of the increased probability of qubit relaxation due to the long gate time. While it is possible to significantly reduce the depth of the Toffoli gate by exploiting three-level, i.e., qutrit states internally, existing methods are susceptible to errors arising from frequency drifts due to charge fluctuation effects in the second excited state of the transmon. In this poster, we propose a novel qutrit-based implementation of the Toffoli gate that is inherently robust against such errors. The method is extensively validated through a pulse-level simulation and experiments performed on IBM Quantum machines. On one device, where the total Toffoli gate time is 2.510μs, we obtained average gate fidelity values of 0.928 ± 0.007 and 0.896 ± 0.036 from multiple measurements performed during the first one and twenty-four hours after calibrations, respectively, where the errors represent the standard deviations of the measurement results.
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.
Current quantum computers are especially error prone and require high levels of optimization to reduce operation counts and maximize the probability the compiled program will succeed. These computers only support operations decomposed into one- and two-qubit gates and only two-qubit gates between physically connected pairs of qubits. Typical compilers first decompose operations, then route data to connected qubits. We propose a new compiler structure, Orchestrated Trios, that first decomposes to the three-qubit Toffoli, routes the inputs of the higher-level Toffoli operations to groups of nearby qubits, then finishes decomposition to hardware-supported gates.
Quantum computation is conventionally performed using quantum operations acting on two-level quantum bits, or qubits. Qubits in modern quantum computers suffer from inevitable detrimental interactions with the environment that cause errors during computation, with multi-qubit operations often being a primary limitation. Most quantum devices naturally have multiple accessible energy levels beyond the lowest two traditionally used to define a qubit. Qudits offer a larger state space to store and process quantum information, reducing complexity of quantum circuits and improving efficiency of quantum algorithms. Here, we experimentally demonstrate a ternary decomposition of a multi-qubit operation on cloud-enabled fixed-frequency superconducting transmons. Specifically, we realize an order-preserving Toffoli gate consisting of four two-transmon operations, whereas the optimal order-preserving binary decomposition uses eight \texttt{CNOT}s on a linear transmon topology. Both decompositions are benchmarked via truth table fidelity where the ternary approach outperforms on most sets of transmons on \texttt{ibmq\_jakarta}, and is further benchmarked via quantum process tomography on one set of transmons to achieve an average gate fidelity of 78.00\% ±\pm± 1.93\%.