A Comparison of Quantum Walk Implementations on NISQ Computers
arXiv:1911.00305 · doi:10.1103/PhysRevA.103.022408
Abstract
This paper explores two circuit approaches for quantum walks: the first consists of generalised controlled inversions, whereas the second one effectively replaces them with rotation operations around the basis states. We show the theoretical foundation of the rotational implementation. The rotational approach nullifies the large amount of ancilla qubits required to carry out the computation when using the inverter implementation. Our results concentrate around the comparison of the two architectures in terms of structure, benefits and detriments, as well as the computational resources needed for each approach. We show that the inverters approach requires exponentially fewer gates than the rotations but almost half the number of qubits in the system. Finally, we execute a number of experiments using an IBM quantum computer. The experiments show the effects of noise in our circuits. Small two-qubit quantum walks evolve closer to our expectations, whereas for a larger number of steps or state space the evolution is severely affected by noise.
arXiv commentFormatting changes post-acceptance (PRA); added an appendix on quantum volum
References in corpus (28)
- Quantum Computing in the NISQ era and beyond
- Elementary gates for quantum computation
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Validating quantum computers using randomized model circuits
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Quantum optimization using variational algorithms on near-term quantum devices
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
- Quantum walk of a trapped ion in phase space
- Discrete single-photon quantum walks with tunable decoherence
- Quantum speedup of Monte Carlo methods
- Quantum Metropolis Sampling
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Ideal negative measurements in quantum walks disprove theories based on classical trajectories
- Quantum speedup of classical mixing processes
- Localization, delocalization, and topological phase transitions in the one-dimensional split-step quantum walk
- Towards Pricing Financial Derivatives with an IBM Quantum Computer
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- Quantum Walks
- Topological bound states of a quantum walk with cold atoms
- Experimental simulation of quantum tunneling in small systems
- Identification of networking quantum teleportation on 14-qubit IBM universal quantum computer
- Quantum Markov chains associated with open quantum random walks
- Experimental Demonstration of Quantum Tunneling in IBM Quantum Computer
- On the spreading of quantum walks starting from local and delocalized states
Cited by in corpus (10)
- Modelling and Simulating the Noisy Behaviour of Near-term Quantum Computers
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- Efficient implementation of discrete-time quantum walks on quantum computers
- Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware
- Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
- Feynman checkers: towards algorithmic quantum theory
- Implementation of hitting times of discrete time quantum random walks on Cubelike graphs
- Implementation of Continuous-Time Quantum Walks on Quantum Computers
- Monte Carlo particle transport on quantum computers
- Qubit encodings for lattices of dipolar planar rotors