Efficient implementation of discrete-time quantum walks on quantum computers

Abstract

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.

Accepted version: 24 pages, 12 figures

References in corpus (13)

• Universal computation by quantum walk
• Spatial search by quantum walk
• Experimental Comparison of Two Quantum Computing Architectures
• A random walk approach to quantum algorithms
• Relationship Between Quantum Walk and Relativistic Quantum Mechanics
• Classical approach to the graph isomorphism problem using quantum walks
• Perfect state transfer and efficient quantum routing: a discrete-time quantum walk approach
• Discrete-time quantum walk on complex networks for community detection
• Qubit state transfer via discrete-time quantum walks
• Quantum state revivals in quantum walks on cycles
• Photonic Discrete-time Quantum Walks and Applications
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method