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• 39 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•16 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

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

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

Scalable Improvement of the Generalized Toffoli Gate Realization Using Trapped-Ion-Based Qutrits

Anastasiia S. Nikolaeva, Ilia V. Zalivako, Alexander S. Borisenko +8 more

An efficient implementation of the Toffoli gate is of conceptual importance for running various quantum algorithms, including Grover's search and Shor's integer factorization. However, direct implementation of the Toffoli gate either entails a prohibitive increase in the number of two-qubit gates or requires ancilla qubits, whereas both of these resources are limited in the current generation of noisy intermediate-scale quantum devices. Here, we experimentally demonstrate a scalable N-qubit Toffoli gate improvement using ^{171}Yb^{+} trapped-ion-based optical-metastable-ground encoded qutrits for the cases of up to N=10. With the use of the Mølmer-Sørensen gate as a basic entangling operation, we compare the standard qubit decomposition with the qutrit approach, where upper levels are used as ancillae. The presented decomposition requires only global control of the ancilla levels, which simplifies experimental implementation of the proposed approach. Using the example of a three-qubit Grover's search, we also demonstrate an increase in the algorithm's accuracy by monitoring the leakage from the qubit subspace during a qutrit-based Toffoli gate implementation.

arXiv:2407.07758•Physical Review Letters•Jul 14, 2025•14 citations

Extending the Frontier of Quantum Computers With Qutrits

Pranav Gokhale, Jonathan M. Baker, Casey Duckering +3 more

We advocate for a fundamentally different way to perform quantum computation by using three-level qutrits instead of qubits. In particular, we substantially reduce the resource requirements of quantum computations by exploiting a third state for temporary variables (ancilla) in quantum circuits. Past work with qutrits has demonstrated only constant factor improvements, owing to the log2(3) binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic runtime decomposition of the Generalized Toffoli gate using no ancilla---an exponential improvement over the best qubit-only equivalent. Our approach features a 70x improvement in total two-qudit gate count over the qubit-only decomposition. This results in improvements for important algorithms for arithmetic and QRAM. Simulation results under realistic noise models indicate over 90% mean reliability (fidelity) for our circuit, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path toward extending the frontier of quantum computers.

IEEE Micro•Apr 16, 2020•35 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.
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.
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.
An efficient implementation of the Toffoli gate is of conceptual importance for running various quantum algorithms, including Grover's search and Shor's integer factorization. However, direct implementation of the Toffoli gate either entails a prohibitive increase in the number of two-qubit gates or requires ancilla qubits, whereas both of these resources are limited in the current generation of noisy intermediate-scale quantum devices. Here, we experimentally demonstrate a scalable N-qubit Toffoli gate improvement using ^{171}Yb^{+} trapped-ion-based optical-metastable-ground encoded qutrits for the cases of up to N=10. With the use of the Mølmer-Sørensen gate as a basic entangling operation, we compare the standard qubit decomposition with the qutrit approach, where upper levels are used as ancillae. The presented decomposition requires only global control of the ancilla levels, which simplifies experimental implementation of the proposed approach. Using the example of a three-qubit Grover's search, we also demonstrate an increase in the algorithm's accuracy by monitoring the leakage from the qubit subspace during a qutrit-based Toffoli gate implementation.
We advocate for a fundamentally different way to perform quantum computation by using three-level qutrits instead of qubits. In particular, we substantially reduce the resource requirements of quantum computations by exploiting a third state for temporary variables (ancilla) in quantum circuits. Past work with qutrits has demonstrated only constant factor improvements, owing to the log2(3) binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic runtime decomposition of the Generalized Toffoli gate using no ancilla---an exponential improvement over the best qubit-only equivalent. Our approach features a 70x improvement in total two-qudit gate count over the qubit-only decomposition. This results in improvements for important algorithms for arithmetic and QRAM. Simulation results under realistic noise models indicate over 90% mean reliability (fidelity) for our circuit, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path toward extending the frontier of quantum computers.