Efficient implementation of discrete-time quantum walks on quantum
  computers
Quantum walks have proven to be a universal model for quantum computation and
to provide speed-up in certain quantum algorithms. The discrete-time quantum
walk (DTQW) model, among others, is one of the most suitable candidates for
circuit implementation, due to its discrete nature. Current implementations,
however, are usually characterized by quantum circuits of large size and depth,
which leads to a higher computational cost and severely limits the number of
time steps that can be reliably implemented on current quantum computers. In
this work, we propose an efficient and scalable quantum circuit implementing
the DTQW on the $2^n$-cycle based on the diagonalization of the conditional
shift operator. For $t$ time-steps of the DTQW, the proposed circuit requires
only $O(n^2 + nt)$ two-qubit gates compared to the $O(n^2 t)$ of the current
most efficient implementation based on quantum Fourier transforms. We test the
proposed circuit on an IBM quantum device for a Hadamard DTQW on the $4$- and
$8$-cycle characterized by periodic dynamics and recurrent generation of
maximally entangled single-particle states. Experimental results are meaningful
well beyond the regime of few time steps, paving the way for reliable
implementation and use on quantum computers.
Luca Razzoli Gabriele Cenedese Maria Bondani Giuliano Benenti