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

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

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

Published Dec 8, 2020• 3 citations
OpenAlex

Abstract

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.

Related papers

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 +2 more

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.

arXiv:2012.04447•Physical Review A•Jun 28, 2022•28 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

Asymptotic improvements to quantum circuits via qutrits

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

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qutrits. 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 depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla-a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation.

arXiv:1905.10481•Proceedings - International Symposium on Computer Architecture/Proceedings•Jun 14, 2019•120 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

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

Exact and Fixed-Point Grover Search with Qudits

Tanay Roy

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

quant-pharXiv:2607.24658•Jul 28, 2026•0 citations
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 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{\ge}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.
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.
Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qutrits. 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 depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla-a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation.
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.
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.
Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.