Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware

Quantum walks are a promising framework for developing quantum algorithms and quantum simulations. They represent an important test case for the application of quantum computers. Here we present different forms of discrete-time quantum walks (DTQWs) and show their equivalence for physical realizations. Using an appropriate digital mapping of the position space on which a walker evolves to the multiqubit states of a quantum processor, we present different configurations of quantum circuits for the implementation of DTQWs in one-dimensional position space. We provide example circuits for a five-qubit processor and address scalability to higher dimensions as well as larger quantum processors.

Figure 1

Probability distribution after 100 time steps of a standard DTQW (SQW) for different initial states with the coin parameter $\theta =\pi /4$. Initial states are $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =|\uparrow \rangle \otimes |x=0\rangle$ for (a), $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =|\downarrow \rangle \otimes |x=0\rangle$ for (b), and $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =\frac{1}{\sqrt{2}}(|\uparrow \rangle +|\downarrow \rangle )\otimes |x=0\rangle$ for (c). Alternate sites will have zero probability in a SQW irrespective of the initial state.

Figure 2

Probability distribution for standard DTQW (SQW), directed DTQW (DQW), and a split-step quantum walk (SSQW) with the coin parameter $\theta =\pi /4$ after 100 steps. In the plot, the zero-probability values at alternate positions are discarded from the SQW. The spread in position space for the SQW and SSQW are identical, but the peak values of the distribution are different. The spread is different for SQW and DQW, but their peak values are identical. The initial state is $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =\frac{1}{\sqrt{2}}(|\uparrow \rangle +|\downarrow \rangle )\otimes |x=0\rangle$ for all cases.

Figure 3

Systematic presentation of the equivalence of the three forms of DTQWs.

Figure 4

Equivalence of the probability distribution for different forms of DTQWs, i.e., the SQW and DQW for 100 steps and the SSQW for 50 steps, with the coin parameter $\theta =\pi /4$. Alternate sites of the SQW have zero probability, and thus 100 steps of SQW are equivalent to 50 time steps of the SSQW. The initial state is $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =\frac{1}{\sqrt{2}}(|\uparrow \rangle +|\downarrow \rangle )\otimes |x=0\rangle$.

Figure 5

Generic quantum circuit to implement one step of the SQW on a five-qubit system for the mapping given in Table 1. Repetition of this circuit will give us the SQW on the position Hilbert space with 16 sites. The shift operation $S$ is performed using the increment and decrement circuit.

Figure 6

Generic quantum circuit for two steps of the SQW on a five-qubit system for the mapping given in Table 2. It can be used to implement up to seven steps of the SQW by alternating the circuits in (a) and (b). If the initial position state is even, the circuit in (a) is applied first, and if the initial position state is odd, the circuit in (b) is applied first.

Figure 7

Generic quantum circuit for a DQW on a five-qubit system for the mapping given in Table 2. Concatenation of this circuit will give the probability distribution of the DQW for up to 15 steps.

Figure 8

Quantum circuit for the first seven steps of the SQW on a five-qubit system with the fixed initial state $|\uparrow \rangle \otimes |x=0\rangle \equiv |0\rangle \otimes |0000\rangle$ for the mapping given in Table 2. This circuit has a reduced gate count compared to the generic circuit shown in Fig. 6. We note that the sequence of ${\sigma }_x$ in the last qubit can be replaced by classically tracking the number of steps.

Figure 9

Quantum circuit for the first seven steps of the DQW on a five-qubit system with the fixed initial state $|\uparrow \rangle \otimes |x=0\rangle \equiv |0\rangle \otimes |0000\rangle$ for the mapping given in Table 2. It has a reduced gate count compared to the generic circuit shown in Fig. 7.

Figure 10

Quantum circuit for the SQW for the first seven steps on a five-qubit system for the fixed initial state $|\uparrow \rangle \otimes |x=0\rangle \equiv |0\rangle \otimes |0000\rangle$ for the mapping given in Table 3. Here also the sequence of ${\sigma }_x$ in the last qubit can be completely replaced by classically tracking the step number.

Figure 11

Quantum circuit for the first seven steps of the DQW on a five-qubit system with the fixed initial state $|\uparrow \rangle \otimes |x=0\rangle \equiv |0\rangle \otimes |0000\rangle$ for the mapping given in Table 3.

Figure 12

Quantum circuit for the DQW for the first five steps with the fixed initial state $|{\mathrm{\Psi }}_{\mathrm{in}}\rangle =|\uparrow \rangle \otimes |x=0\rangle \equiv |0\rangle \otimes |0000\rangle$ for the naive mapping shown in Table 5. This circuit has a simple structure, but it consists of many additional higher-order Toffoli gates compared to the circuits shown in Sec. 3 and the Appendix.

Figure 13

Quantum circuit for the DQW for the first four steps without interference. Each step of this quantum circuit is given by a cnot gate because of the mapping chosen (see Table 6). To include interference in the circuit, ancilla operations are needed before the measurement (see Fig. 14).

Figure 14

Quantum circuit for the DQW with the ancilla operation to include interference after the first three steps. The ancilla qubit is left unobserved in the circuit. Here $C_1=C_2=C_3=C_{\theta }$.

Figure 15

Quantum circuit for the DQW with the ancilla operation to include interference after the first four steps. The ancilla qubits are left unobserved in the circuit. With a larger number of steps, the number of ancilla qubits also increases. Here $C_1=C_2=C_3=C_4=C_{\theta }$.