## Robust Implementation of Discrete-time Quantum Walks in Any Finite-dimensional Quantum System

Biswayan Nandi , Sandipan Singha , Ankan Datta , Amit Saha 1 1 2 3 4 , , ∗ and Amlan Chakrabarti 1 1 A. K. Choudhury School of Information Technology, University of Calcutta, India 2 Institute of Radiophysics and Electronics, University of Calcutta, Kolkata, India 3 Institut National de Recherche en Informatique et en Automatique (Inria), Paris, France 4 ´ cole E Normale Sup´ erieure (ENS), PSL University, Paris, France (Dated: August 6, 2024)

Research has shown that quantum walks can accelerate certain quantum algorithms and act as a universal paradigm for quantum processing. The discrete-time quantum walk (DTQW) model, owing to its discrete nature, stands out as one of the most suitable choices for circuit implementation. Nevertheless, most current implementations are characterized by extensive, multi-layered quantum circuits, leading to higher computational expenses and a notable decrease in the number of confidently executable time steps on current quantum computers. Since quantum computers are not scalable enough in this NISQ era, we also must confine ourselves to the ancilla-free frontier zone. Therefore, in this paper, we have successfully cut down the circuit cost concerning gate count and circuit depth by half through our proposed methodology in qubit systems as compared to the state-of-the-art increment-decrement approach. Furthermore, for the engineering excellence of our proposed approach, we implement DTQW in any finite-dimensional quantum system with akin efficiency. To ensure an efficient implementation of quantum walks without requiring ancilla, we have incorporated an intermediate qudit technique for decomposing multi-qubit gates. Experimental outcomes hold significance far beyond the realm of just a few time steps, laying the groundwork for dependable implementation and utilization on quantum computers.

## I. INTRODUCTION

The field of quantum computing [1, 2] is in rapid development in the current era. Quantum computers are far more efficient in doing certain tasks than our best state-of-the-art classical computing algorithms. They can leverage quantum mechanical phenomena like superposition, entanglement, and measurement giving them a significant edge over classical computers. For example, Grover's search [3] can search in O ( √ N ) time where N is the size of the input space. In 1994, Peter Shor showed that we can prime factor a number much more efficiently using quantum computers [4]. Like these quantum algorithms, quantum walk algorithms have also applications in various fields such as quantum simulation, quantum search algorithms, and quantum cryptography. They also offer potential advantages over classical algorithms in certain scenarios, particularly in tasks that involve searching through large databases or graphs.

the state from which the walker starts walking has the highest probability, or in other words, the walker is most likely to return to where it started. In contrast, a quantum walker is the exact opposite. In a quantum walk, the probability of finding the walker around the state it started is the lowest. It is highest on the states farthest from the starting position. Therefore, we can say that, quantum walks move faster than their classical counterparts [9], which can be useful for certain applications such as in developing cryptographic applications [10].

Quantum walks [5] is the quantum mechanical counterpart of classical random walks. Random walks have been used to simulate the motion of molecules in gas or liquid, also known as Brownian motion [6], unpredictable fluctuating stock prices [7], PageRank [8] algorithms in search engines like Google, and recommendation algorithms also make use of it. Therefore, there is a significant amount of use cases for random walk algorithms but how is quantum walk different from classical random walk? We get a normal distribution of the probability of finding the walker in different states of the space. Therefore, around

∗ abamitsaha@gmail.com

Two types of quantum walks are proposed in the literature: discrete-time quantum walks (DTQW) [11] and continuous-time quantum walks (CTQW) [12]. In the first model, we have a walker, a coin, and an evolution operator which is applied to both the walker and the coin in discrete time steps. On the other hand, in the second model, we have a walker and an evolution that can be applied to the walker with no timing restrictions. In this article, we have only worked with the first model i.e., DTQW. Before we discuss our motivation for implementing a scalable generalized quantum walk algorithm, we address why one should study quantum walks in the first place i.e., its applications. Childs in his work showed that quantum walks can be considered a universal computational model [13, 14]. Ambainis showed that quantum walks can be used to efficiently solve the element distinctness problem which is a problem of finding two distinct items among N given ones [15]. The application domain of quantum walks is not bounded by theoretical computer science only. We can use quantum walks to simulate natural processes like photosynthesis [16]. The primary challenge in quantum computing lies in optimizing qubit utilization and circuit depth to maximize the implemen-

tation of Discrete-Time Quantum Walks (DTQW) within the constraints of qubit quantity and coherence time for its applications.

Motivation: In the initial development of quantum walk algorithms [17] and in recent developments [18] also, for a general quantum walk implementation, without considering special cases such as quantum walks on complete graphs [19], the naive approach [20] is used in binary quantum systems. This is a generalized approach for implementing n -qubit quantum walks, albeit, this is inefficient concerning gate count and circuit depth. The noise level is also colossal because of its inefficient circuit structure. Our main motivation is to develop an efficient generalized approach to robust circuit implementation of DTQW that can also be scaled up to any finitedimensional quantum system to make it noise-resilient. In [21], the authors have proposed a generalized quantum walk implementation for 5-qubit quantum hardware, but not scalable to the n -qubit systems. Another efficient quantum circuit for the DTQW on the cycle has been presented as a notable advancement in [22]. By employing just one QFT and one IQFT, the approach in [22] markedly enhances the most efficient state-of-theart QFT-based implementation. Albeit, this QFT-based implementation is not efficient in this ancilla-free frontier zone [23] and is also difficult to scale to any finitedimensional quantum systems due to its complex circuit structure. In [24, 25], the authors have shown an efficient implementation for d -dimensional quantum walks in qudit systems where d is odd, but the circuit for even dimensions remains inefficient because it is still based on the increment-decrement approach due to engineering challenges.

Contribution: With the background of the implementation of DTQW, in this article, we have successfully cut down the circuit cost concerning gate count and circuit depth by half through our proposed methodology in qubit systems as compared to the naive incrementdecrement approach. Certainly, this is the first-of-itskind approach apart from naive increment-decrement, which is generalized for any n -qubit systems. Because of its engineering excellence, we also show that with slight modification, the proposed approach is generalized for any finite-dimensional quantum system.

Our key contributions are as follows:

- · We optimize the circuit for DTQW by reducing the circuit depth and gate count. We have developed a generalized algorithm that is theoretically twice as efficient as the naive increment-decrement approach. From now on we will call it the Enhanced Increment-Decrement approach.
- · Our proposed algorithm is generalized in the binary space, meaning it works for any number of qubits. However, our further aim is to extend this generalization to higher dimensions as well. Through our proposed approach, by setting the Least Significant Bit (LSB) as any even dimension when d ≥ 4 and

adjusting the dimensionality of the other Most Significant Bits (MSB) for any qudits, our proposed algorithm can be generalized for any d -dimensional space.

- · We have further compared the naive approach and our proposed approach in terms of gate count, circuit depth, and effect of noise after Toffoli decomposition and we have observed that in every comparison, our proposed approach has outperformed the naive approach significantly.

In this paper, first, we discuss some basic concepts and gates in quantum computing in section II. Then we discuss the mathematical foundation and implementation of the naive quantum walk approach in section II B. Next, we explain our proposed methodology in binary systems in detail in section III and compare our approach with the naive approach in section III C. We then discuss the implementation of our approach in higher dimensions in section IV. Finally, we conclude our remarks in V.

## II. BACKGROUND

In this section, our discussion will focus on some basics of quantum computing and quantum walks.

## A. Quantum computing

The bit is the fundamental concept of classical computation and classical information. Quantum computation and quantum information are built upon an analogous concept, the quantum bit or qubit for short [2]. As classical bits can be either 0 or 1, a qubit can be in a continuum of states between 0 and 1 until it is observed or measured which is called superposition. For example, a qubit can be in the probabilistic state α | 0 ⟩ + β | 1 , where ⟩ α and β can be complex numbers. Changes occurring in a quantum state can be described using the language of quantum computation. Analogous to the way a classical computer is built from an electrical circuit containing wires and logic gates, a quantum computer is built from a quantum circuit containing wires and elementary quantum gates to carry around and manipulate the quantum information [2]. We have used the following gates for our proposed approach: Pauli X (NOT) Gate, Hadamard Gate, Controlled NOT (CX) Gate, Toffoli (CCX) Gate, and Multi-controlled Toffoli (C n X) Gate and its generalized versions. A decomposition using the Clifford+T gate set of the Toffoli gate in binary systems is shown in Figure 1, which is used to estimate the gate resources in this paper in binary quantum systems.

FIG. 1: 2-controlled Toffoli decomposition using Clifford+T gate set

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-e77d4f89-80d7-44c0-8bde-2197aa0dfa09.jpg)

## B. Discrete-time quantum walks (DTQW)

## 1. Mathematical background of DTQW

As a mathematical illustration, DTQW is applied over 1D space which is an Integer line. A coin is tossed, and according to that, the walker shifts its position to the right or left. Let H c be the Hilbert space of the coin spanned by the basis set {|↑⟩ , |↓⟩} and H x be the Hilbert space of the position states spanned by the basis set {| x ⟩} x ∈ Z . The unitary operator for a single step of the quantum walk is given by

$$U = S ( C \otimes I )$$

where C is the coin toss operator and S is the shift operator that is applied to the walker after the toss. ⊗ is tensor product. In the case of a general coin,

$$C = \cos \theta | \uparrow \rangle \langle \uparrow | + e ^ { i \phi _ { 1 } } s i n \theta | \uparrow \rangle \langle \downarrow | + e ^ { i \phi _ { 2 } } s i n \theta | \downarrow \rangle \langle \uparrow | - e ^ { i ( \phi _ { 1 } + \phi _ { 2 } ) } \cos \theta | \downarrow \rangle \langle \downarrow | \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

where θ ∈ [0 , 2 π ) and ϕ , ϕ 1 2 ∈ [0 , π ). We refer to θ as rotation and ϕ , ϕ 1 2 as phase parameters of the general coin [26]. But here we have considered only the Haramard coin for simplicity. So having θ = π 4 and ϕ , ϕ 1 2 = 0 we get,

$$C = \frac { 1 } { \sqrt { 2 } } \begin{bmatrix} 1 & 1 \\ 1 & - 1 \end{bmatrix}$$

Finally, the unitary operator for shifting the walker is defined as [25],

$$S = \sum _ { x \in \mathbb { Z } } \left ( | \uparrow \rangle \left \langle \uparrow | \otimes | x + 1 \right \rangle \left \langle x | + | \downarrow \right \rangle \left \langle \downarrow | \otimes | x - 1 \right \rangle \left \langle x | \right ) \ ( 4 ) \quad \text{the H} \\ \quad \text{like } | a$$

## 2. Implementation of quantum walks in naive approach

The components for increment and decrement in a 3qubit system in the naive implementation of DTQW are shown in Figure 2. After a coin toss, which is a simple Hadamard transform in this case, we need to do both increment and decrement operations based on the state of the coin. The circuit for a single step of DTQW in this naive setting is shown in Figure 3. For n qubits, we can have 2 n -1 -1 steps of DTQW. The position state mapping for the circuit shown in Figure 3, after it is applied 3 times is as Table I.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-136f8bdb-8f2d-4a22-984d-12f76f8d59a0.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-81f86283-faa3-4d33-99c8-62fdbdb9d461.jpg)

FIG. 2: The circuit on the left, is the increment circuit and the circuit on the right is the decrement circuit. After a coin toss, both circuits need to be employed. We need an increment for a rightwards shift and a decrement for a leftwards shift.

FIG. 3: Naive circuit for a single step of DTQW.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-610d223f-f2ce-40b1-a189-187ab31d535e.jpg)

TABLE I: Position state mapping for naive implementation of DTQW shown in Figure 3.

| | x = 0 ⟩ = | 000 ⟩                        |
|--------------------------------------------|
| | x = - 1 ⟩ = | 111 ⟩ | x = +1 ⟩ = | 001 ⟩ |
| | x = - 2 ⟩ = | 110 ⟩ | x = +2 ⟩ = | 010 ⟩ |
| | x = - 3 ⟩ = | 101 ⟩ | x = +3 ⟩ = | 011 ⟩ |

## III. OUR PROPOSED APPROACH: ENHANCED INCREMENT-DECREMENT APPROACH FOR DTQW IN BINARY QUANTUM SYSTEMS

## A. Mathematical formulation of our proposed approach

As an instance, DTQW is applied over a 1D integer line. A coin is tossed and according to that, the walker shifts its position. Let H c be the Hilbert space of the coin spanned by the basis set {|↑⟩ , |↓⟩} and H x be the Hilbert space of the position state by the basis set {| x ⟩} x ∈ Z . | x ⟩ . | x ⟩ can be represented by multiple qubits like | q n q n -1 ...q 0 ⟩ where q n is the MSB and q 0 is the LSB. In this approach two unitary operators are needed for the walk, unlike the naive approach, one operator is used for the even position state and another one is used for the odd position state. The operators are

$$U _ { e v e n } = S _ { e v e n } ( C \otimes I ) \text{ \quad \ \ } ( 5 )$$

$$U _ { o d d } = S _ { o d d } ( C \otimes I )$$

where C is the coin toss operator and S even and S odd are the shift operators that are applied to the walker after the toss. A tensor product is denoted by ⊗ .

The unitary operator for shifting the walker to an even

position state is defined as

$$S _ { e v e n } = \sum _ { x \in \mathbb { Z } } \left ( | \uparrow \rangle \left \langle \uparrow \right | \otimes | x _ { e 1 } \right \rangle \left \langle x | + | \downarrow \right \rangle \left \langle \downarrow \right | \otimes | x _ { e 2 } \right \rangle \left \langle x | \right ) \ ( 7 ) \quad \ \ & -$$

where | x e 1 ⟩ consists of q n q n -1 ...q 0 . It can be written as | x n -1 +1 ⟩ | x 0 +1 where ⟩ x n -1 consists of q n q n -1 ...q 1 and x 0 consists of q 0 . | x e 2 ⟩ consists of q n q n -1 ...q 0 . It can be written as | x n -1 ⟩ | x 0 +1 where ⟩ x n -1 consists of q n q n -1 ...q 1 and x 0 consists of q 0 .

The unitary operator for shifting the walker to an odd position state is defined as

$$S _ { o d d } = \sum _ { x \in \mathbb { Z } } \left ( | \uparrow \rangle \left \langle \uparrow \right | \otimes | x _ { o 1 } \right \rangle \left \langle x | + | \downarrow \right \rangle \left \langle \downarrow \right | \otimes | x _ { o 2 } \right \rangle \left \langle x | \right ) \ \ ( 8 ) \quad \overline { \text{Algo} } \,.$$

where | x o 1 ⟩ consists of q n q n -1 ...q 0 . It can be written as | x n -1 ⟩ | x 0 - ⟩ 1 where x n -1 consists of q n q n -1 ...q 1 and x 0 consists of q 0 .

| x o 2 ⟩ consists of q n q n -1 ...q 0 . It can be written as | x n -1 - ⟩| 1 x 0 - ⟩ 1 where x n -1 consists of q n q n -1 ...q 1 and x 0 consists of q 0 .

## B. Implementation of the proposed approach

In the naive implementation of the quantum walk, two components were required for increment and decrement in each coin toss. Inspired by the work in [27], in our proposed algorithm, only one component is required in each coin toss. Figure 4 shows both components for a 3-qubit system. Extending the circuit for more than 3 qubits requires more multi-controlled Toffoli gates similar to the naive approach. Figure 5 shows the generalized circuit diagram. It can be easily observed that, in our proposed algorithm, Algorithm 1, we can cut down the depth of the circuit for a single step of DTQW by half.

FIG. 4: Circuit implementing DTQW in a 3-qubit system. The circuit on the left is for when the walker is in some even position state and the circuit on the right is for when the walker is in some odd position state.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-2e7d7200-e81a-4a6a-b92d-a65217cd07ad.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-ba0f2e3b-8b07-4d52-9b1f-1220b6cdd573.jpg)

FIG. 5: Generalized circuit diagram of our proposed enhanced increment decrement quantum walk for n qubits. The circuit on the left is to be used when the walker is in some even position state and the circuit on the right is to be used in case the walker on some odd position state.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-4d66bdca-20ee-4209-a12d-3765a8e3b48d.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-e1adf42a-31f2-4ce8-a412-52fb01332764.jpg)

## Algorithm 1 Our proposed approach of DTQW for binary systems

1: X ← n +1 qubit register ▷ Where the first n qubits are to represent the walker's position state and the remaining one MSB is for the coin

2: C ← A single qubit coin operator (Hadamard in our case)

3: S even ← Shift operator as per Eq. 7

4: S odd ← Shift operator as per Eq. 8

5: N ← 2 n - 1 - 1 ▷ Total number of possible steps for a n -qubit quantum system

6: i ← 0

7: while i &lt; N do

8:

X

←

(

C

⊗

I

⊗

(

n

-

1)

)

×

X

▷

Coin toss

9: if i is even then conditionally

▷

Applying shift operation

10: X ← ( I ⊗ S even ) × X

11: else

$$1 2 \colon \quad X \leftarrow ( I \otimes S _ { o d d } ) \times X$$

13: end if

i

←

i

+1

14: end while

## 1. Explanation

In our approach, the basic concept of increment and decrement (shown in Figure 2) is used with some modification. Indeed, it's widely understood that the increment and decrement circuit can be extended to n qubits. In our proposed approach, each step incorporates either the enhanced increment or the enhanced decrement circuit (Shown in Figure 5).

- · The enhanced increment operation: The walk starts at the initial state of | 0 ⟩ ⊗ n . Following the coin toss, executed through a simple Hadamard transform, we proceed to select a single shift operator. Referring back to our discussion in Figure 5, since the walker currently resides in an even position state, our selection will be the enhanced increment circuit. This circuit performs an increment operation on every qubit except for the least sig-

nificant bit (LSB) when the coin state happens to be | 1 . ⟩ As an example, if we consider a 3 qubit system, then from | 000 ⟩ we get two states, | 001 ⟩ when the coin is | 0 , and ⟩ | 011 ⟩ when the coin is | 1 . ⟩ We can consider | 011 ⟩ as +1 state and | 001 ⟩ as -1 state. From this example, it's evident that for even position states, the least significant bit (LSB) will always be | 0 , while for odd position states, it will ⟩ be | 1 . ⟩

- · The enhanced decrement operation: After the first toss, the walker is on | 001 ⟩ and | 011 . ⟩ Now we choose the enhanced decrement circuit as the shift operator. Akin to the enhanced increment circuit, it decrements all the qubits except for the LSB. So, from | 001 , ⟩ we get | 110 ⟩ (a new state) when the coin is | 0 ⟩ and | 000 ⟩ (the previous state) when the coin is | 1 . ⟩ We can consider the new state | 110 ⟩ as the -2 state. Similarly, from | 011 , ⟩ we get | 000 ⟩ (the previous state) when the coin is | 0 ⟩ and | 010 ⟩ (a new state) when the coin is | 1 . ⟩ We can consider the new state | 010 ⟩ as the +2 state.

The position state mapping employing the naive approach, shown in Table I, uses binary 2's complement counting scheme. Similarly, in our proposed approach, for all even position states, the LSB is always | 0 , and ⟩ | 1 ⟩ for all odd position states. This implies that the value of LSB always flips at every step of the DTQW. We have exploited this fact in our proposed approach and removed the flipping of the LSB in control with the coin state. In our approach, as it is also portrayed by the diagram (Fig. 5), the LSB is flipped irrespective of the coin state. For a 3-qubit system, the position state mapping employing our approach is shown in Table II.

TABLE II: Position state mapping employing our proposed approach for a 3-qubit system.

| | x = 0 ⟩ = | 000 ⟩   | | x = 0 ⟩ = | 000 ⟩   | | x = 0 ⟩ = | 000 ⟩   |
|-----------------------|-----------------------|-----------------------|
| | x = - 1             | | x = +1 ⟩ =          | | 011 ⟩               |
| | x = - 2             | | x = +2 ⟩ =          | | 010 ⟩               |
| | x = - 3             | | x = +3 ⟩ =          | | 101 ⟩               |

## 2. Mathematical steps for a 3-qubit DTQW using our proposed approach

We have taken | 000 ⟩ as the initial position state of the walker. A total of three steps are as follows: a 0 | 0 ⟩| 000 . ⟩

↓ U even a 1 | 0 ⟩| 001 ⟩ + b 1 | 1 ⟩| 011 . ⟩ ↓ U odd a 2 | 0 ⟩| 110 ⟩ + c 0 | 1 ⟩| 000 ⟩ + c 1 | 0 ⟩| 000 ⟩ + b 2 | 1 ⟩| 010 . ⟩ ↓ U even a 3 | 0 ⟩| 111 ⟩ + c 30 | 1 ⟩| 001 ⟩ + c 10 | 0 ⟩| 001 ⟩ + c 11 | 1 ⟩| 011 ⟩ + c 20 | 0 ⟩| 001 ⟩ + c 21 | 1 ⟩| 011 ⟩ + c 31 | 0 ⟩| 011 ⟩ + b 3 | 1 ⟩| 101 . ⟩ where a , b , and c are the amplitudes.

## C. Experimental results in binary systems

- 1. Comparative study between naive approach and our proposed approach

We consider three metrics for the comparison, which are as follows:

- 1. Circuit depth: It is an important property of a quantum circuit. The circuit depth of a quantum circuit is the measure of how many layers of quantum gates, executed in parallel, it takes to complete the total computation. The depth of a circuit roughly corresponds to the amount of time it takes the quantum computer to execute the circuit. Therefore, we always want to reduce the depth of our quantum circuits as much as possible.
- 2. Gate count: In Figure 3 and Figure 5, we observe that multi-controlled Toffoli gates are used in abundance and for circuits with increasing number of qubits, this number of multi-controlled Toffoli's will increase substantially. However, these gates are not directly implementable on any quantum hardware. We need to decompose these gates into single and two-qubit gates before implementing them on real hardware. Gate count is the total number of gates after decomposing Toffoli gates. We also want to minimize the gate count of our circuits as much as possible. It is also possible to use intermediate qudits to decompose the Toffoli gates as suggested by the authors in [28] for ancilla-free decomposition, which is thoroughly discussed in the next section.
- 3. Probability of success: After the multicontrolled Toffoli gates are decomposed, certainly the depth and gate count of the circuit increase because we are replacing one gate with more than one other gate. We want a higher probability of success for our circuits. Small errors in the gates employed in quantum circuits are frequently present; these errors can be represented as an ideal gate followed by an unwanted Pauli operator. Instead of comparing the probability of small circuit errors, we compare the probability that the circuit will stay error-free (probability of success) in this comparison, maintaining the same level of generality as in [29]. The product that each component fails independently is the generalized formula for the probability of success ( P success ) for any decomposition. The general equation for calculating success probability is,

$$P _ { s u c c e s s } = \prod _ { \ g a t e s } \left ( ( P _ { \text{success of gate} } ) ^ { \# g a t e s } \times e ^ { - d e p t h / T _ { 1 } } \right ) \\ \vdots \quad \text{--show $D$} \quad \colon + \theta \, \underset { \theta \, \infty \, \infty } { \dots } \, \text{--do-hidden} \, \text{--if $d$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$ } \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \. \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \text{--do$} \, \colon$$

where P success is the success probability of the decomposed circuit, P success of gate is the success probability of each type of gate (single qubit/qudit

or multi-qubit/qudit) as per the given hardware, depth is the depth of the circuit after decomposition and T 1 is the relaxation time of quantum hardware. For further experiments, we take the value of T 1 as per [30].

The comparative resource estimation for the naive approach and our proposed approach is exhibited in Table III.

TABLE III: Generalized formulation ( n - no. of qubit, t - no. of steps) [Toffoli decomposition using 1-qubit and 2-qubit gates [31]].

| Topic              | Our proposed approach                                             | Naive approach [19]                    |
|--------------------|-------------------------------------------------------------------|----------------------------------------|
| 1-qubit Gate Count | 3 t                                                               | 3 t                                    |
| 2-qubit Gate Count | t ( ∑ n x =3 (2 n 2 - 6 n +5) +1)                                 | 2 t ( ∑ n +1 x =3 (2 n 2 - 6 n +5) +2) |
| Circuit Depth      | t 2 ( ∑ n x =3 (8 n - 20) +1+1) + t 2 ( ∑ n x =3 (8 n - 20) +1+3) | t (2( ∑ n +1 3 (8 n - 20)) +3)         |
| Highest Control    | ( n - 1)-control                                                  | n -control                             |

If we roughly estimate, the naive approach requires around 2 n multi-controlled Toffoli gates for n qubits, whereas our proposed approach requires roughly half that amount. Not only is the gate count approximately halved compared to the naive approach, but the circuit depth is also roughly halved.

Compared to the naive approach, our proposed approach provides a better probability of success. The result is as Figure 6.

FIG. 6: Success probability analysis between our proposed approach and the naive approach of DTQW.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-6539e99e-30de-417b-b865-c5ed31d91547.jpg)

## 2. Runs and Simulations

We use IBM's Qiskit package and the BasicAer backend to simulate and validate our approach. We decompose the circuit into 1-qubit and 2-qubit gates. We use Qiskit's 'transpile' function for decomposition. For decomposition, the basic gate set is ['cx', 'u1', 'u2', 'h', 'x', 'p']. In this set, only 'cx'(CNOT) is the 2-qubit gate, others are 1-qubit gates. The optimization level is set to 1. We also use ancilla qubits to decompose multi-qubit

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-8baf4035-975f-4698-957c-6201011534cd.jpg)

States

FIG. 7: Probability distribution of the simulated result for 3-qubit DTQW using our proposed approach.

gates for better circuit depth. The total number of shots considered is 1024.

The results of DTQW using our proposed approach are as follows:

- a. 3-qubit quantum walks using our proposed approach We have implemented a 3-qubit quantum walk using our proposed approach. The circuits are shown in Figure 4 and the corresponding position state mapping is as Table II. The probability distribution after three steps of quantum walks is portrayed in Figure 7.
- b. 4-qubit Quantum Walk Using Our Proposed approach For a 4-qubit system, the circuits of the DTQW are shown in Figure 8 and the corresponding position state mapping is as Table IV. The probability distribution after seven steps of quantum walks is portrayed in Figure 9.

FIG. 8: Circuit implementing DTQW in a 4-qubit system. The circuit on the left is for when the walker is in some even position state and the circuit on the right is for when the walker is in some odd position state.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-95584ddc-c387-4b22-813f-8c17186df25f.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-5c856217-34f5-4da5-b54e-14432c45bdc6.jpg)

TABLE IV: Position state mapping employing our proposed approach for a 4-qubit system.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-a3f4ad7e-61d0-4d83-9942-d31eaf8a4318.jpg)

| | x = 0 ⟩ = | 0000 ⟩   | | x = 0 ⟩ = | 0000 ⟩   | | x = 0 ⟩ = | 0000 ⟩   | | x = 0 ⟩ = | 0000 ⟩   |
|------------------------|------------------------|------------------------|------------------------|
| | x = - 1 ⟩ =          | | 0001 ⟩               | | x = +1 ⟩ =           | | 0011 ⟩               |
| | x = - 2 ⟩ =          | | 1110 ⟩               | | x = +2 ⟩ =           | | 0010 ⟩               |
| | x = - 3 ⟩ =          | | 1111 ⟩               | | x = +3 ⟩ =           | | 0101 ⟩               |
| | x = - 4 ⟩ =          | | 1100 ⟩               | | x = +4 ⟩ =           | | 0100 ⟩               |
| | x = - 5 ⟩ =          | | 1101 ⟩               | | x = +5 ⟩ =           | | 0111 ⟩               |
| | x = - 6 ⟩ =          | | 1010 ⟩               | | x = +6 ⟩ =           | | 0110 ⟩               |
| | x = - 7 ⟩ =          | | 1011 ⟩               | | x = +7 ⟩ =           | | 1001 ⟩               |

FIG. 9: Probability distribution of the simulated result for 4-qubit DTQW using our proposed approach.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-a37cf142-abc5-40c3-aa33-86c3fef0fa5f.jpg)

These results validate our proposed approach and exhibit efficiency as compared to the naive approach.

## IV. ENHANCED INCREMENT-DECREMENT APPROACH FOR DTQW IN HIGHER DIMENSIONAL QUANTUM SYSTEMS

In this section, at first, we try to map our proposed binary method to higher dimensional quantum systems by considering LSB is in the binary system. Therefore, for n qudits with dimension d , we can have a total of 2 d ( n -1) number of state spaces and we can implement a total of d n -1 number of steps. Thus implementing our proposed methodology in higher dimensions is limiting us from leveraging the whole state space of higher dimensions because of the LSB which is set to d = 2.

As an instance, in a ququad system (Four-dimensional quantum systems), the circuit for the 3-ququad DTQW is as Figure 10, and the corresponding position state mapping is shown in Table V. In the last step of Table V, we get the states | 200 ⟩ as the mid-state of the total state set in both directions, which restricts the walker to use the rest of the 32 number of state spaces further. We also check upto 8-dimensional quantum systems and observe that this direct mapping technique in higher dimensions can not be generalized for all n -qudit systems since it can not use all possible state spaces. Therefore, we need some changes in our proposed technique of binary systems while applying in higher dimensions so that it also utilizes all the state spaces in the higher dimensional quantum systems.

To solve the state-space issue in higher dimensions, with a slight modification of the proposed binary-only approach, we propose a modified technique where we set the Least Significant Bit (LSB) as any even dimension when d ≥ 4. We propose modified circuits for both the even and odd dimensions when d &gt; 2, which are portrayed in Figures 11 and 12 respectively.

In our modified circuit, as shown in Figures 11 and 12, instead of applying only a NOT/Pauli-X gate on the LSB,

FIG. 10: The enhanced increment decrement approach for a 3-ququad system.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-9a1bd129-915e-4fa9-8aa3-7913c9bd38de.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-4160cafb-3135-4d50-8124-0e5cfd635037.jpg)

TABLE V: Position state mapping of the enhanced increment decrement approach in a 3-ququad system shown in Figure 10.

| | x = 0 ⟩ =    | | 000 ⟩   |               |         |
|----------------|-----------|---------------|---------|
| | x = - 1 ⟩ =  | | 001 ⟩   | | x = +1 ⟩ =  | | 011 ⟩ |
| | x = - 2 ⟩ =  | | 330 ⟩   | | x = +2 ⟩ =  | | 010 ⟩ |
| | x = - 3 ⟩ =  | | 331 ⟩   | | x = +3 ⟩ =  | | 021 ⟩ |
| | x = - 4 ⟩ =  | | 320 ⟩   | | x = +4 ⟩ =  | | 020 ⟩ |
| | x = - 5 ⟩ =  | | 321 ⟩   | | x = +5 ⟩ =  | | 031 ⟩ |
| | x = - 6 ⟩ =  | | 310 ⟩   | | x = +6 ⟩ =  | | 030 ⟩ |
| | x = - 7 ⟩ =  | | 331 ⟩   | | x = +7 ⟩ =  | | 101 ⟩ |
| | x = - 8 ⟩ =  | | 300 ⟩   | | x = +8 ⟩ =  | | 100 ⟩ |
| | x = - 9 ⟩ =  | | 301 ⟩   | | x = +9 ⟩ =  | | 111 ⟩ |
| | x = - 10 ⟩ = | | 230 ⟩   | | x = +10 ⟩ = | | 110 ⟩ |
| | x = - 11 ⟩ = | | 231 ⟩   | | x = +11 ⟩ = | | 121 ⟩ |
| | x = - 12 ⟩ = | | 220 ⟩   | | x = +12 ⟩ = | | 120 ⟩ |
| | x = - 13 ⟩ = | | 221 ⟩   | | x = +13 ⟩ = | | 131 ⟩ |
| | x = - 14 ⟩ = | | 210 ⟩   | | x = +14 ⟩ = | | 130 ⟩ |
| | x = - 15 ⟩ = | | 211 ⟩   | | x = +15 ⟩ = | | 201 ⟩ |
| | x = - 16 ⟩ = | | 200 ⟩   | | x = +16 ⟩ = | | 200 ⟩ |

a conditional increment or decrement gate is applied on the LSB for both the increment and decrement circuits so that the same mid-state of the total state set can be avoided in both directions of DTQW. With the modified logic as per Algorithm 2, when the walker reaches the middle point, it increments the value of LSB by 2 because of the increment circuit and decrements the value of LSB by 2 because of the decrement circuit. Hence, with this modified circuit, all possible states can be traversed using the even-dimensional circuit, which is d n and the total number of steps that can be implemented is ( d n / 2) -1. In our modified circuit, the LSB is not only dependent on control operations from other qudits for a conditional increment or decrement operation, but also it must increment the value of LSB at one step, and in the very next step, it decrements the value of LSB. For that reason, we need to restrict the LSB as an even dimension, but the other qudits can be in any dimension. Henceforth, the total number of states that can be traversed using the odd-dimensional circuit is d even ∗ d n -1 and the total number of steps that can be implemented is (( d even ∗ d n -1 ) / 2) -1, where d even represents the LSB.

FIG. 11: Generalized modified DTQW circuit for all even dimensions of qudits. After the binary generic coin toss, the circuit on the top is to be applied when the walker is in an even position state. Otherwise, when the walker is in an odd position state, the circuit below is to be applied.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-334d98a1-32e8-4e7d-8ac8-0f3a3c3edd95.jpg)

FIG. 12: Generalized modified DTQW circuit for all odd dimensions of qudits. After the binary generic coin toss, the circuit on the top is to be applied when the walker is in an even position state. Otherwise, when the walker is in an odd position state, the circuit below is to be applied.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-e1752f12-7b2b-43c4-9db6-cddbb039229e.jpg)

Algorithm 2 Implementing DTQW in higher dimensional ( &gt; 2) quantum systems using our proposed approach

X ← Position State ( n -qudit of d dimension)

S even ← Shift Operator as per Eq. 7

S odd ← Shift Operator as per Eq. 8

C ← Coin Operator ( 1-qubit Hadamard Coin)

steps ← Half of the total number of possible states for X step ← 0

while step ≤ steps do

Apply C over X i.e., C ⊗ X

if step is even then

Apply S even over C ⊗ X

Operator and it works over X

else if step is odd then

Apply S odd over C ⊗ X ▷ C controls Shift Operator and it works over X

end if if X = midpoint excluding LSB ( ) and step is odd then Apply conditional decrement operator. ▷ Fig [11] or [12] according to d

else if X = midpoint excluding LSB ( ) and step is even then

Apply conditional increment operator. ▷ Fig [11] or [12] according to d end if

step ← step +1

end while

For better understanding, we take two separate example circuits, (i) an even dimension (3-ququad DTQW) circuit and (ii) an odd dimension (3-qutrit DTQW) circuit.

a. Implementation of 3-ququad (even dimension) DTQW with a Hadamard coin: As an example, we again take ququad systems, but this time with 3 ququads, including the LSB as ququad as per the modified circuit. Earlier, we observed in Table V, at step 16, we get | 200 ⟩ in both the directions of DTQW. As per the circuit in Figure 10, we get these states because we have used only binary ( 0 | ⟩ and | 1 ) for the LSB. Since the modified en-⟩ hanced increment-decrement approach for DTQW can utilize | 2 ⟩ and | 3 ⟩ states in the LSB as shown in Figure 13, we get the following states in Table VI. In Table VI, We observe that at step 16, | x = +16 ⟩ = 200 | ⟩ becomes | x = +16 ⟩ = 202 | ⟩ by incrementing the value of LSB by 2 with the help of controlled increment operator as per modified circuit's logic. After this step, the previous process of DTQW again starts working and we get all possible state spaces as required.

b. Implementation of 3-qutrit (odd dimension) DTQW with a Hadamard coin: We have also shown an example of our modified enhanced increment decrement approach for DTQW in a 3-qutrit system (Figure 14) and we get the results shown in Table VII by considering LSB as in ququad system. If we had used only our enhanced increment decrement circuit, we could get up to step 9, where we have to stop the DTQW with | x = +9 = 121 ⟩ | ⟩ and | x = - ⟩ 9 = 121 . | ⟩ Because of our modified circuit, it can be well-avoided. The

▷ C controls Shift

FIG. 13: Implementation of the modified enhanced increment decrement approach for DTQW in a 3-ququad system.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-c1eaf430-2a2d-456d-8146-c8c0247892f7.jpg)

TABLE VI: Position state mapping of modified DTQW in a 3-ququad system shown in Figure 13.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-b6021344-26b1-45a7-81af-3e21199ef593.jpg)

| | x = 0 ⟩ =    | | 000 ⟩   |       |          |         |
|----------------|-----------|-------|----------|---------|
| | x = - 1 ⟩ =  | | 001 ⟩   | | x = | +1 ⟩ =   | | 011 ⟩ |
| | x = - 2 ⟩ =  | | 330 ⟩   | | x = | +2 ⟩ =   | | 010 ⟩ |
| | x = - 3 ⟩ =  | | 331 ⟩   | | x = | +3 ⟩ =   | | 021 ⟩ |
| | x = - 4 ⟩ =  | | 320 ⟩   | | x = | +4 ⟩ =   | | 020 ⟩ |
| | x = - 5 ⟩ =  | | 321 ⟩   | | x = | +5 ⟩ =   | | 031 ⟩ |
| | x = - 6 ⟩ =  | | 310 ⟩   | | x = | +6 ⟩ =   | | 030 ⟩ |
| | x = - 7 ⟩ =  | | 331 ⟩   | | x = | +7 ⟩ =   | | 101 ⟩ |
| | x = - 8 ⟩ =  | | 300 ⟩   | | x = | +8 ⟩ =   | | 100 ⟩ |
| | x = - 9 ⟩ =  | | 301 ⟩   | | x = | +9 ⟩ = | | 111 ⟩   |
| | x = - 10 ⟩ = | | 230 ⟩   | | x = | +10 ⟩ =  | | 110 ⟩ |
| | x = - 11 ⟩ = | | 231 ⟩   | | x = | +11 ⟩ =  | | 121 ⟩ |
| | x = - 12 ⟩ = | | 220 ⟩   | | x = | +12 ⟩ =  | | 120 ⟩ |
| | x = - 13 ⟩ = | | 221 ⟩   | | x = | +13 ⟩ =  | | 131 ⟩ |
| | x = - 14 ⟩ = | | 210 ⟩   | | x = | +14 ⟩ =  | | 130 ⟩ |
| | x = - 15 ⟩ = | | 211 ⟩   | | x = | +15 ⟩ =  | | 201 ⟩ |
| | x = - 16 ⟩ = | | 200 ⟩   | | x = | +16 ⟩ =  | | 202 ⟩ |
| | x = - 17 ⟩ = | | 203 ⟩   | | x = | +17 ⟩ =  | | 213 ⟩ |
| | x = - 18 ⟩ = | | 132 ⟩   | | x = | +18 ⟩ =  | | 212 ⟩ |
| | x = - 19 ⟩ = | | 133 ⟩   | | x = | +19 ⟩ =  | | 223 ⟩ |
| | x = - 20 ⟩ = | | 122 ⟩   | | x = | +20 ⟩ =  | | 222 ⟩ |
| | x = - 21 ⟩ = | | 123 ⟩   | | x = | +21 ⟩ =  | | 233 ⟩ |
| | x = - 22 ⟩ = | | 112 ⟩   | | x = | +22 ⟩ =  | | 232 ⟩ |
| | x = - 23 ⟩ = | | 113 ⟩   | | x = | +23 ⟩ =  | | 303 ⟩ |
| | x = - 24 ⟩ = | | 102 ⟩   | | x = | +24 ⟩ =  | | 302 ⟩ |
| | x = - 25 ⟩ = | | 103 ⟩   | | x = | +25 ⟩ =  | | 313 ⟩ |
| | x = - 26 ⟩ = | | 032 ⟩   | | x = | +26 ⟩ =  | | 312 ⟩ |
| | x = - 27 ⟩ = | | 033 ⟩   | | x = | +27 ⟩ =  | | 323 ⟩ |
| | x = - 28 ⟩ = | | 022 ⟩   | | x = | +28 ⟩ =  | | 322 ⟩ |
| | x = - 29 ⟩ = | | 023 ⟩   | | x = | +29 ⟩ =  | | 333 ⟩ |
| | x = - 30 ⟩ = | | 012 ⟩   | | x = | +30 ⟩ =  | | 332 ⟩ |
| | x = - 31 ⟩ = | | 013 ⟩   | | x = | +31 ⟩ =  | | 003 ⟩ |
| | x = - 32 ⟩ = | | 002 ⟩   | | x = | +32 ⟩ =  | | 002 ⟩ |

| x = - ⟩ 9 = 121 | ⟩ now becomes | 123 ⟩ since the conditional increment activates at the midpoint as per the logic to get access to the full state spaces.

FIG. 14: Implementation of the modified enhanced increment decrement approach for DTQW in a 3-qutrit system.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-8ea6ef5b-5942-43e6-9d2d-866fb2dc3830.jpg)

TABLE VII: Position state mapping of modified DTQW in a 3-qutrit system shown in Figure 14.

| | x = 0 ⟩ =    | | 000 ⟩   |               |         |
|----------------|-----------|---------------|---------|
| | x = - 1 ⟩ =  | | 001 ⟩   | | x = +1 ⟩ =  | | 011 ⟩ |
| | x = - 2 ⟩ =  | | 220 ⟩   | | x = +2 ⟩ =  | | 010 ⟩ |
| | x = - 3 ⟩ =  | | 221 ⟩   | | x = +3 ⟩ =  | | 021 ⟩ |
| | x = - 4 ⟩ =  | | 210 ⟩   | | x = +4 ⟩ =  | | 020 ⟩ |
| | x = - 5 ⟩ =  | | 211 ⟩   | | x = +5 ⟩ =  | | 101 ⟩ |
| | x = - 6 ⟩ =  | | 200 ⟩   | | x = +6 ⟩ =  | | 100 ⟩ |
| | x = - 7 ⟩ =  | | 201 ⟩   | | x = +7 ⟩ =  | | 111 ⟩ |
| | x = - 8 ⟩ =  | | 120 ⟩   | | x = +8 ⟩ =  | | 110 ⟩ |
| | x = - 9 ⟩ =  | | 123 ⟩   | | x = +9 ⟩ =  | | 121 ⟩ |
| | x = - 10 ⟩ = | | 112 ⟩   | | x = +10 ⟩ = | | 122 ⟩ |
| | x = - 11 ⟩ = | | 113 ⟩   | | x = +11 ⟩ = | | 203 ⟩ |
| | x = - 12 ⟩ = | | 102 ⟩   | | x = +12 ⟩ = | | 202 ⟩ |
| | x = - 13 ⟩ = | | 103 ⟩   | | x = +13 ⟩ = | | 213 ⟩ |
| | x = - 14 ⟩ = | | 022 ⟩   | | x = +14 ⟩ = | | 212 ⟩ |
| | x = - 15 ⟩ = | | 023 ⟩   | | x = +15 ⟩ = | | 223 ⟩ |
| | x = - 16 ⟩ = | | 012 ⟩   | | x = +16 ⟩ = | | 222 ⟩ |
| | x = - 17 ⟩ = | | 013 ⟩   | | x = +17 ⟩ = | | 003 ⟩ |
| | x = - 18 ⟩ = | | 002 ⟩   | | x = +18 ⟩ = | | 002 ⟩ |

## A. Decomposition of Multi-controlled Toffoli Gates with Intermediate Qudit

To achieve more improvement, we use multi-controlled Toffoli decomposition using intermediate qudits [28, 32] in our proposed quantum walk circuit, where momentarily the binary system goes into higher dimensions, and using this concept, after the decomposition, gate count and circuit depth are reduced. No ancilla bits are required for this decomposition. In [32], the authors have shown how we can efficiently decompose a multi-

controlled Toffoli gate in the binary system by employing qutrits (3-ary quantum systems). In [28], the authors have extended and generalized the previous work to decompose n -qubit Toffoli gates by considering both the intermediate-qutrit and the intermediate-ququad (4ary quantum systems). For instance, in Figure 15, a 2controlled Toffoli gate is decomposed into 2-qutrit gates. We have also portrayed 7-controlled Toffloi gate decomposition into 2-qutrit gates and 2-ququad gates in Figure 16.

FIG. 15: 2-controlled Toffoli decomposition using intermediate qutrits.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-d3514813-baa3-45e2-b5d0-eaba12add37d.jpg)

FIG. 16: 7-controlled Toffoli decomposition using intermediate-qutrit and intermediate-ququad.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-dad33720-9eec-42fc-8e60-9dedfcfd14f0.jpg)

For the sake of better understandability, we have divided the steps of decomposition into three steps -

- · Preparation: In this step, the controls are prepared for the operation on the target. We must use only 2-qudit gates, and in the original circuit, we had multiple controls (more than 1). Therefore, based on the state of all those controls, we need to manipulate a single control in such a way that if all the other controls are set to | 1 , ⟩ then only the last single control will be set to | 2 . ⟩ However, in the process of setting a single control to | 2 , the state of ⟩ the other controls may get disturbed. Thus, in the final step, we need to correct those disturbances. We have highlighted this step with purple color.
- · Target Operation: Following the initial step, where a single control is set to | 2 ⟩ if all other con-

trols were | 1 , this step involves simply applying a ⟩ CNOT gate. The control for this gate is the single control that was set to | 2 ⟩ in the previous step, while the target remains the original target. We have highlighted this step with green color.

- · Correction: As previously discussed, this final step aims to correct the states of the controls. We need to reverse the operation performed in the first step, ensuring that only the target changes if all the controls were set to | 1 . ⟩ We have highlighted this step with red color.

Using this logic, we can decompose binary multicontrolled Toffoli gates of any size using intermediate qudits. This can be generalized for any finite d -dimensional quantum system as per [28] using two higher dimensions i.e., | d +1 and ⟩ | d +2 , which is thoroughly discussed in ⟩ Appendix A.

We further observe that by using intermediate qudit decomposition, we have acutely reduced the gate count and circuit depth. For the N -controlled Toffoli gate, we get a circuit depth of log N [28]. By considering that we can formulate a generalized formulation for our proposed quantum walk circuit. Thus, the total circuit depth for a N qubit circuit is 2 N -1 ( ∑ N -1 x =2 (log x ) + 1) + 3 ∗ 2 N -2 + 2 N -2 . Similarly the total gate count for a N qubit circuit is 2 N -1 ( ∑ N -1 x =2 (2 x -3)+1)+2 ∗ 2 N -2 +4 2 ∗ N -2 . We have compared circuit depth among naive approach [25] with intermediate qudits, enhanced increment decrement with intermediate qudits, and increment decrement without using intermediate qudits. The comparative analysis is shown in Figure 17.

## Circuit depth vs No. of qubits

FIG. 17: Comparative analysis of circuit depth.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-8ed0c57a-5871-4029-ae8d-4ae5a0995307.jpg)

With these circuit costs, we have also compared the probability of success by considering Equation 9 among the naive approach, enhanced increment decrement approach using intermediate qudits, and increment decrement approach without using intermediate qudits. The comparative analysis is shown in Figure 18. Using intermediate qudit decomposition for our approach increases the probability of success. We have also simulated and

validated our proposed quantum walk circuits with intermediate qudits on the QuDiet platform [33].

FIG. 18: Comparative analysis of success probability.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-cfb81fc8-535e-4695-9084-f4270ae4167d.jpg)

- [1] R. P. Feynman, Simulating physics with computers, in Feynman and computation (CRC Press, 2018) pp. 133153.
- [2] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information , Vol. 10th Anniversary Edition (Cambridge University Press, 2010).
- [3] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996) pp. 212-219.
- [4] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th annual symposium on foundations of computer science (Ieee, 1994) pp. 124-134.
- [5] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Physical Review A 48 , 1687 (1993).
- [6] M. Kac, Random walk and the theory of brownian motion, The American Mathematical Monthly 54 , 369 (1947).
- [7] M. D. Godfrey, C. W. Granger, and O. Morgenstern, The random-walk hypothesis of stock market behavior a, Kyklos 17 , 1 (1964).
- [8] L. Page, S. Brin, R. Motwani, and T. Winograd, The pagerank citation ranking: Bring order to the web , Tech. Rep. (Technical report, Stanford University, 1998).
- [9] J. Kempe, Quantum random walks: an introductory overview, Contemporary Physics 44 , 307 (2003).
- [10] A. A. Abd El-Latif, B. Abd-El-Atty, M. Amin, and A. M. Iliyasu, Quantum-inspired cascaded discrete-time quantum walks with induced chaotic dynamics and cryptographic applications, Scientific reports 10 , 1930 (2020).
- [11] R. P. Feynman, A. R. Hibbs, and D. F. Styer, Quantum mechanics and path integrals (Courier Corporation, 2010).
- [12] E. Farhi and S. Gutmann, Quantum computation and decision trees, Physical Review A 58 , 915 (1998).

## V. CONCLUSION

This paper achieved a 50% reduction in circuit cost, including gate count and circuit depth, compared to the current increment-decrement method, through our proposed technique in qubit systems. The experimental results extended the significance beyond a few time steps, establishing a reliable foundation for quantum computer utilization. Furthermore, the engineering excellence of our proposed approach achieves the generalization for any finite-dimensional quantum system. Additionally, to ensure efficient implementation of quantum walks without ancillary requirements, we integrated an intermediate qudit technique for multi-qubit gate decomposition. This proposed approach can be easily employed for higher dimensional lattices as well. How this proposed circuit can enhance the applications of quantum walks [34, 35] remains a prospect outlined in this paper. The code for our proposed implementation of DTQW is available in https://github.com/Biswayan375/Discrete-TimeQuantum-Walk/tree/enh-enc-dec.

- [13] A. M. Childs, Universal computation by quantum walk, Physical review letters 102 , 180501 (2009).
- [14] A. M. Childs, D. Gosset, and Z. Webb, Universal computation by multiparticle quantum walk, Science 339 , 791 (2013).
- [15] A. Ambainis, Quantum walk algorithm for element distinctness, SIAM Journal on Computing 37 , 210 (2007).
- [16] G. S. Engel, T. R. Calhoun, E. L. Read, T.-K. Ahn, T. Manˇ cal, Y.-C. Cheng, R. E. Blankenship, and G. R. Fleming, Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems, Nature 446 , 782 (2007).
- [17] V. M. Kendon, A random walk approach to quantum algorithms, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 364 , 3407 (2006).
- [18] V. Wadhia, N. Chancellor, and V. Kendon, Cycle discrete-time quantum walks on a noisy quantum computer, The European Physical Journal D 78 , 29 (2024).
- [19] B. Douglas and J. Wang, Efficient quantum circuit implementation of quantum walks, Physical Review A 79 , 052335 (2009).
- [20] B. L. Douglas and J. B. Wang, Efficient quantum circuit implementation of quantum walks, Phys. Rev. A 79 , 052335 (2009).
- [21] S. Singh, C. H. Alderete, R. Balu, C. Monroe, N. M. Linke, and C. Chandrashekar, Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware, Physical Review A 104 , 062401 (2021).
- [22] L. Razzoli, G. Cenedese, M. Bondani, and G. Benenti, Efficient implementation of discrete-time quantum walks on quantum computers, Entropy 26 , 313 (2024).
- [23] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2 , 79 (2018).

- [24] A. Saha, S. B. Mandal, D. Saha, and A. Chakrabarti, One-dimensional lazy quantum walk in ternary system, IEEE Transactions on Quantum Engineering 2 , 1 (2021).
- [25] A. Saha, D. Saha, and A. Chakrabarti, Discretetime quantum walks in qudit systems, arXiv preprint arXiv:2207.04319 (2022).
- [26] M. N. Jayakody, C. Meena, and P. Pradhan, Onedimensional discrete-time quantum walks with general coin, arXiv preprint arXiv:2102.07207 (2021).
- [27] S. Singh, P. Chawla, A. Sarkar, and C. Chandrashekar, Universal quantum computing using singleparticle discrete-time quantum walk, Scientific Reports 11 , 11551 (2021).
- [28] A. Saha, R. Majumdar, D. Saha, A. Chakrabarti, and S. Sur-Kolay, Asymptotically improved circuit for a dary grover's algorithm with advanced decomposition of the n-qudit toffoli gate, Physical Review A 105 , 062453 (2022).
- [29] R. Majumdar, D. Madan, D. Bhoumik, D. Vinayagamurthy, S. Raghunathan, and S. Sur-Kolay, Optimized qaoa ansatz circuit design for two-body hamiltonian problems, in 2024 37th International Conference on VLSI Design and 2024 23rd International Conference on Embedded Systems (VLSID) (2024) pp. 396-401.
- [30] L. E. Fischer, D. Miller, F. Tacchino, P. K. Barkoutsos, D. J. Egger, and I. Tavernelli, Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space, Phys. Rev. Res. 4 , 033027 (2022).
- [31] M. Saeedi and M. Pedram, Linear-depth quantum circuits for n -qubit toffoli gates with no ancilla, Phys. Rev. A 87 , 062318 (2013).
- [32] P. Gokhale, J. M. Baker, C. Duckering, N. C. Brown, K. R. Brown, and F. T. Chong, Asymptotic improvements to quantum circuits via qutrits, in 2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA) (2019) pp. 554-566.
- [33] T. Chatterjee, A. Das, S. K. Bala, A. Saha, A. Chattopadhyay, and A. Chakrabarti, Qudiet: A classical simulation platform for qubit-qudit hybrid quantum systems, IET Quantum Communication 4 , 167-180 (2023).
- [34] S. Srikara and C. M. Chandrashekar, Quantum direct communication protocols using discrete-time quantum walk, Quantum Information Processing 19 , 10.1007/s11128-020-02793-4 (2020).
- [35] A. Saha, R. Majumdar, D. Saha, A. Chakrabarti, and S. Sur-Kolay, Faster search of clustered marked states with lackadaisical quantum walks, Quantum Information Processing 21 , 10.1007/s11128-022-03606-6 (2022).
- [36] P. Gokhale, J. M. Baker, C. Duckering, F. T. Chong, N. C. Brown, and K. R. Brown, Extending the frontier of quantum computers with qutrits, IEEE Micro 40 , 64 (2020).
- [37] M. Amy, D. Maslov, M. Mosca, and M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32 , 818-830 (2013).
- [38] A. Saha and O. Khanna, Intermediate-qudit assisted improved quantum algorithm for string matching with an advanced decomposition of fredkin gate, arXiv preprint arXiv:2304.03050 (2023).
- [39] T. Chatterjee, A. Das, S. K. Bala, A. Saha, A. Chattopadhyay, and A. Chakrabarti, Qudiet: A classical simulation platform for qubit-qudit hybrid quantum systems, IET Quantum Communication (2023).
- [40] Y.-M. Di and H.-R. Wei, Elementary gates for ternary quantum logic circuit, arXiv preprint arXiv:1105.5485 (2012).
- [41] B. P. Lanyon, M. Barbieri, M. P. Almeida, T. Jennewein, T. C. Ralph, K. J. Resch, G. J. Pryde, J. L. O'brien, A. Gilchrist, and A. G. White, Simplifying quantum logic using higher-dimensional hilbert spaces, Nature Physics 5 , 134 (2009).
- [42] T. Ralph, K. Resch, and A. Gilchrist, Efficient toffoli gates using qudits, Physical Review A 75 , 022313 (2007).
- [43] A. Shakeel, Efficient and scalable quantum walk algorithms via the quantum fourier transform. 10.1007/s11128-020-02834-y (2020).
- [44] A. Saha, R. Majumdar, D. Saha, A. Chakrabarti, and S. Sur-Kolay, Asymptotically improved circuit for a d -ary grover's algorithm with advanced decomposition of the n -qudit toffoli gate, Phys. Rev. A 105 , 062453 (2022).
- [45] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, Strengths and weaknesses of quantum computing, SIAM journal on Computing 26 , 1510 (1997).
- [46] P. Benioff, Space searches with a quantum robot, arXiv preprint quant-ph/0003006 (2000).
- [47] S. Aaronson and A. Ambainis, Quantum search of spatial regions, in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (IEEE, 2003) pp. 200-209.
- [48] A. M. Childs and J. Goldstone, Spatial search by quantum walk, Physical Review A 70 , 022314 (2004).
- [49] T. G. Wong, Faster search by lackadaisical quantum walk, Quantum Information Processing 17 , 10.1007/s11128-018-1840-y (2018).

## Appendix A: Generalization of intermediate qudit approach

The intermediate qudit approach is generalized and further optimized in [28] using two higher dimensions i.e., | d +1 and ⟩ | d +2 . First, we discuss how it is generalized ⟩ and then how it is optimized.

- 1. Generalization: The decomposition circuit for a d-ary 3-controlled Toffoli gate using the approach is shown in Figure 19. In this case, we are required to use only one higher-level state, | d +1 . ⟩ But to generalize the work of [36] for an n -controlled d -ary Toffoli gate, we need to use two higher-level states, | d +1 and ⟩ | d +2 , as in Figure 20. ⟩
- 2. Optimization: In Figure 20, we observe that there are some redundant gates. Hence, an optimization has been used, which is proposed in [28]. We now need to remove these redundant gates for a more optimized decomposition of the 7-controlled d -ary Toffoli gate, which is shown in Figure 21.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-f09bc5d6-3c82-4574-a913-4044e34c2946.jpg)

FIG. 19: 3-controlled d -ary Toffoli decomposition using intermediate qudits of dimension d and d +1. Here U d is used instead of ⊕ or X d to represent any unitary operation in general and not just Addition modulo d .

FIG. 20: 7-controlled Toffoli decomposition in d -dimensional systems. We have highlighted in yellow and labeled as I and II two 2-qudit gates to make it more visually understandable how the decomposition is done. By red color, redundant gates are highlighted which is further optimized.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-fcca153b-089e-477d-8731-c32cc9bd05ed.jpg)

FIG. 21: Optimized 7-controlled generalized Toffoli decomposition using intermediate-qudit in d -dimensional systems.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00530v2-figure-b61d16b0-3a22-4a57-ac3a-29f04793b0a5.jpg)
Biswayan Nandi Sandipan Singha Ankan Datta Amit Saha Amlan Chakrabarti
Robust Implementation of Discrete-time Quantum Walks in Any Finite-dimensional Quantum System
Research has shown that quantum walks can accelerate certain quantum
algorithms and act as a universal paradigm for quantum processing. The
discrete-time quantum walk (DTQW) model, owing to its discrete nature, stands
out as one of the most suitable choices for circuit implementation.
Nevertheless, most current implementations are characterized by extensive,
multi-layered quantum circuits, leading to higher computational expenses and a
notable decrease in the number of confidently executable time steps on current
quantum computers. Since quantum computers are not scalable enough in this NISQ
era, we also must confine ourselves to the ancilla-free frontier zone.
Therefore, in this paper, we have successfully cut down the circuit cost
concerning gate count and circuit depth by half through our proposed
methodology in qubit systems as compared to the state-of-the-art
increment-decrement approach. Furthermore, for the engineering excellence of
our proposed approach, we implement DTQW in any finite-dimensional quantum
system with akin efficiency. To ensure an efficient implementation of quantum
walks without requiring ancilla, we have incorporated an intermediate qudit
technique for decomposing multi-qubit gates. Experimental outcomes hold
significance far beyond the realm of just a few time steps, laying the
groundwork for dependable implementation and utilization on quantum computers.