Efficient quantum walk on a quantum processor

Abstract

Quantum walks are a potential framework for developing quantum algorithms, but have so far been limited to analogue quantum-simulation approaches that do not scale. Here, the authors provide a protocol for simulating exponentially large quantum walks using a polynomial number of quantum gates and qubits.