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

Asymptotically improved circuit for a d -ary Grover's algorithm with advanced decomposition of the n -qudit Toffoli gate

Amit Saha, Ritajit Majumdar, Debasri Saha, Amlan Chakrabarti, Susmita Sur‐Kolay

Published Jun 28, 2022• 28 citations
arXivHTMLPDF

Abstract

The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides a considerable speed-up over the classical paradigm. It can be extended to a $d$-ary (qudit) quantum system also for utilizing the advantage of larger state space, which helps to reduce the runtime of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an $n$-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized $n$-qudit Toffoli gate is realized using higher-dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any $d$-ary quantum system, where $d\ensuremath{\ge}2$, with the proposed $n$-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an $n$-qudit Toffoli gate requires access to two immediately higher-energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant with both gate count and circuit depth reduced as compared to that in state-of-the-art works.

DOI
10.1103/physreva.105.062453

Related papers

Asymptotically Improved Grover's Algorithm in any Dimensional Quantum System with Novel Decomposed n-qudit Toffoli Gate.

Amit Saha, Ritajit Majumdar, Debasri Saha +2 more

As the development of Quantum computers becomes reality, the implementation of quantum algorithms is accelerating in a great pace. Grover's algorithm in a binary quantum system is one such quantum algorithm which solves search problems with numeric speed-ups than the conventional classical computers. Further, Grover's algorithm is extended to a $d$-ary quantum system for utilizing the advantage of larger state space. In qudit or $d$-ary quantum system n-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this paper, a generalized $n$-qudit Toffoli gate has been realized using qudits to attain a logarithmic depth decomposition without ancilla qudit. Further, the circuit for Grover's algorithm has been designed for any d-ary quantum system, where d >= 2, with the proposed $n$-qudit Toffoli gate so as to get optimized depth as compared to state-of-the-art approaches. This technique for decomposing an n-qudit Toffoli gate requires access to higher energy levels, making the design susceptible to leakage error. Therefore, the performance of this decomposition for the unitary and erasure models of leakage noise has been studied as well.

•Dec 8, 2020•3 citations

Intermediate-qudit assisted Improved quantum algorithm for string matching with an Advanced Decomposition of Fredkin gate

Amit Kumar Saha, Om Khanna

The circuit-level implementation of a quantum string-matching algorithm, which matches a search string (pattern) of length $M$ inside a longer text of length $N$, has already been demonstrated in the literature to outperform its classical counterparts in terms of time complexity and space complexity. Higher-dimensional quantum computing is becoming more and more common as a result of its powerful storage and processing capabilities. In this article, we have shown an improved quantum circuit implementation for the string-matching problem with the help of higher-dimensional intermediate temporary qudits. It is also shown that with the help of intermediate qudits not only the complexity of depth can be reduced but also query complexity can be reduced for a quantum algorithm, for the first time to the best of our knowledge. Our algorithm has an improved query complexity of $O(\sqrt{N-M+1})$ with overall time complexity $O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)$ as compared to the state-of-the-art work which has a query complexity of $O(\sqrt{N})$ with overall time complexity $O\left(\sqrt{N}\left((\log N)^{2}+\log (M)\right)\right)$, while the ancilla count also reduces to $\frac{N}{2}$ from $\frac{N}{2}+M$. The cost of state-of-the-art quantum circuit for string-matching problem is colossal due to a huge number of Fredkin gates and multi-controlled Toffoli gates. We have exhibited an improved gate cost and depth over the circuit by applying a proposed Fredkin gate decomposition with intermediate qutrits (3-dimensional qudits or ternary systems) and already existing logarithmic-depth decomposition of $n$-qubit Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts (4-dimensional qudits or quaternary systems). We have also asserted that the quantum circuit cost is relevant instead of using higher dimensional qudits through error analysis.

arXiv:2304.03050•Apr 6, 2023•1 citation

Asymptotically Optimal Quantum Circuits for Comparators and Incrementers

Vivien Vandaele

We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of $Θ(n)$ and depth of $Θ(\log n)$ over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 \log^2 n)$ without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.

quant-pharXiv:2603.12917•Mar 16, 2026•0 citations

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

Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Amit Saha, Francesco Arzani

Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths $n=2^h-1$, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires $6n+3$ logical $P_9$ injections and $\frac{n-3}{4}$ clean ancillary qutrits. It matches the direct $P_9$ count of a recursively extended Clifford+$P_9$ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the $6n+3$ $P_9$ count but has depth $O(\log m+n-m)$ for a balanced core $m=2^h-1\leq n$, which is linear in the worst case over $n$. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.

quant-pharXiv:2609.29884•Sep 25, 2026•0 citations

Improved Quantum Circuits via Intermediate Qutrits

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

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.

ACM Transactions on Quantum Computing•Oct 29, 2020•17 citations
The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides a considerable speed-up over the classical paradigm. It can be extended to a ddd-ary (qudit) quantum system also for utilizing the advantage of larger state space, which helps to reduce the runtime of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an nnn-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized nnn-qudit Toffoli gate is realized using higher-dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any ddd-ary quantum system, where d\ensuremath≥2d\ensuremath{\ge}2d\ensuremath≥2, with the proposed nnn-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an nnn-qudit Toffoli gate requires access to two immediately higher-energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant with both gate count and circuit depth reduced as compared to that in state-of-the-art works.
As the development of Quantum computers becomes reality, the implementation of quantum algorithms is accelerating in a great pace. Grover's algorithm in a binary quantum system is one such quantum algorithm which solves search problems with numeric speed-ups than the conventional classical computers. Further, Grover's algorithm is extended to a ddd-ary quantum system for utilizing the advantage of larger state space. In qudit or ddd-ary quantum system n-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this paper, a generalized nnn-qudit Toffoli gate has been realized using qudits to attain a logarithmic depth decomposition without ancilla qudit. Further, the circuit for Grover's algorithm has been designed for any d-ary quantum system, where d >= 2, with the proposed nnn-qudit Toffoli gate so as to get optimized depth as compared to state-of-the-art approaches. This technique for decomposing an n-qudit Toffoli gate requires access to higher energy levels, making the design susceptible to leakage error. Therefore, the performance of this decomposition for the unitary and erasure models of leakage noise has been studied as well.
The circuit-level implementation of a quantum string-matching algorithm, which matches a search string (pattern) of length MMM inside a longer text of length NNN, has already been demonstrated in the literature to outperform its classical counterparts in terms of time complexity and space complexity. Higher-dimensional quantum computing is becoming more and more common as a result of its powerful storage and processing capabilities. In this article, we have shown an improved quantum circuit implementation for the string-matching problem with the help of higher-dimensional intermediate temporary qudits. It is also shown that with the help of intermediate qudits not only the complexity of depth can be reduced but also query complexity can be reduced for a quantum algorithm, for the first time to the best of our knowledge. Our algorithm has an improved query complexity of O(N−M+1)O(\sqrt{N-M+1})O(N−M+1​) with overall time complexity O(N−M+1((log⁡(N−M+1)log⁡N)+log⁡(M)))O\left(\sqrt{N-M+1}\left((\log {(N-M+1)} \log N)+\log (M)\right)\right)O(N−M+1​((log(N−M+1)logN)+log(M))) as compared to the state-of-the-art work which has a query complexity of O(N)O(\sqrt{N})O(N​) with overall time complexity O(N((log⁡N)2+log⁡(M)))O\left(\sqrt{N}\left((\log N)^{2}+\log (M)\right)\right)O(N​((logN)2+log(M))), while the ancilla count also reduces to N2\frac{N}{2}2N​ from N2+M\frac{N}{2}+M2N​+M. The cost of state-of-the-art quantum circuit for string-matching problem is colossal due to a huge number of Fredkin gates and multi-controlled Toffoli gates. We have exhibited an improved gate cost and depth over the circuit by applying a proposed Fredkin gate decomposition with intermediate qutrits (3-dimensional qudits or ternary systems) and already existing logarithmic-depth decomposition of nnn-qubit Toffoli or multi-controlled Toffoli gate (MCT) with intermediate ququarts (4-dimensional qudits or quaternary systems). We have also asserted that the quantum circuit cost is relevant instead of using higher dimensional qudits through error analysis.
We present quantum circuits for comparison and increment operations that achieve an asymptotically optimal gate count of Θ(n)Θ(n)Θ(n) and depth of Θ(log⁡n)Θ(\log n)Θ(logn) over the Clifford+Toffoli gate set, while using a provably minimal number of qubits. We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count. Given the ubiquity of these operations as algorithmic building blocks, our constructions translate directly into reduced circuit complexity for many quantum algorithms. As a notable example, they can be used to improve a space-efficient circuit for Shor's factoring algorithm, reducing circuit depth from O(n3)\mathcal{O}(n^3)O(n3) to O(n2log⁡2n)\mathcal{O}(n^2 \log^2 n)O(n2log2n) without increasing either the qubit count or the asymptotic gate complexity. Underpinning these results is a general theorem demonstrating how to trade ancilla qubits for control qubits with low overhead in both depth and gate count, providing a broadly applicable tool for quantum circuit design.
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.
Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford+P9+P_9+P9​ Gates
Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths n=2h−1n=2^h-1n=2h−1, the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires 6n+36n+36n+3 logical P9P_9P9​ injections and n−34\frac{n-3}{4}4n−3​ clean ancillary qutrits. It matches the direct P9P_9P9​ count of a recursively extended Clifford+P9P_9P9​ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the 6n+36n+36n+3 P9P_9P9​ count but has depth O(log⁡m+n−m)O(\log m+n-m)O(logm+n−m) for a balanced core m=2h−1≤nm=2^h-1\leq nm=2h−1≤n, which is linear in the worst case over nnn. By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.
Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.