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

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\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.

Figure 1

Decomposition of an eight-qubit Toffoli gate with intermediate qutrit [23]. Inputs and outputs are qubits. The control qubits in red (gray in grayscale) circles activate on $|1\rangle$ and those in blue (gray in grayscale) dotted-circles activate on $|2\rangle$. $X_3^{+1}$ and $X_3^{-1}$ inside rectangles denote $modulo3$ increment and decrement on target qubits, respectively.

Figure 2

Decomposition of ternary Toffoli gate into 13 one-qutrit and two-qutrit gates [33].

Figure 3

Generalized circuit for Grover's operator in $d$-ary quantum systems [36].

Figure 4

Generalized Toffoli in $d$-ary quantum systems: the control qudits in red (gray in grayscale) circles activate on $|d-1\rangle$ and those in the blue (gray in grayscale) dotted-circles activate on $|d\rangle$.

Figure 5

(a) An eight-qudit Toffoli gate, (b) its decomposition which follows [23], (c) our proposed decomposition using a few $d+1$-ary and/or $d+2$-ary cnot gates, and (d) our proposed optimized decomposition.

Figure 6

(a) An eight-qubit Toffoli gate, (b) its decomposition in [23], (c) our proposed decomposition using a few ternary and/or quaternary cnot gates, and (d) our proposed optimized decomposition.

Figure 7

Decomposition of 16-qudit Toffoli gate.

Figure 8

Effect of generalized amplitude damping channel when $p=0.5$. Here Meas $i$, Prep $i$, $i\in \{0,1\}$, denotes the probability of measuring a quantum state as $i$ when it was prepared as $|i\rangle$. We observe that the probability of measuring $|1\rangle$ decreases gradually with time (lower curve), while that of $|0\rangle$ increases (upper curve).

Figure 9

Probability of success for the decomposition of an $n$-qubit Toffoli gate using our proposed method (upper curve) versus the method in [23] (lower curve).