Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing

Abstract

In the present paper, the first in a series of two, we propose a model of universal quantum computation using a fermionic/bosonic multi-particle continuous-time quantum walk with two internal states (e.g., the spin-up and down states of an electron). A dual-rail encoding is adopted to convert information: a single-qubit is represented by the presence of a single quantum walker in either of the two parallel paths. We develop a roundabout gate that moves a walker from one path to the next, either clockwise or counterclockwise, depending on its internal state. It can be realized by a single-particle scattering on a directed weighted graph with the edge weights $1$ and $\pm i$. The roundabout gate also allows the spatial information of the quantum walker to be temporarily encoded in its internal states. The universal gates are constructed by appropriately combining several roundabout gates, some unitary gates that act on the internal states and two-particle scatterings on straight paths. Any ancilla qubit is not required in our model. The computation is done by just passing quantum walkers through properly designed paths. Namely, there is no need for any time-dependent control. A physical implementation of quantum random access memory compatible with the present model will be considered in the second paper (arXiv:2204.08709).

arXiv comment26 pages; ver. 3: improved presentation, expanded discussion, fixed typos. This is the first paper in a series of two. The second paper is arXiv:2204.08709

References in corpus (25)

• Quantum random walks - an introductory overview
• A Quantum Random Walk Search Algorithm
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Universal quantum computation using the discrete time quantum walk
• Universal computation by multi-particle quantum walk
• Controlling discrete quantum walks: coins and intitial states
• Decoherence in quantum walks - a review
• Entanglement in coined quantum walks on regular graphs
• Two-particle quantum walks applied to the graph isomorphism problem
• Classical approach to the graph isomorphism problem using quantum walks
• Universal quantum computation by discontinuous quantum walk
• Almost uniform sampling via quantum walks
• Electric-circuit simulation of the Schrödinger equation and non-Hermitian quantum walks
• Quantum walks of a phonon in trapped ions
• Quantum Walks
• Universal quantum computing using single-particle discrete-time quantum walk
• Quantum circuit for the fast Fourier transform
• Quantum random access memory via quantum walk
• Electric circuits for universal quantum gates and quantum Fourier transformation
• Levinson's theorem for graphs II
• Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine
• GPU-accelerated algorithms for many-particle continuous-time quantum walks
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Universal Quantum Computation by Scattering in the Fermi-Hubbard Model

Cited by in corpus (4)

• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Disorder-free localisation in continuous-time quantum walks : Role of symmetries
• Optimizing topology for quantum probing with discrete-time quantum walks
• Photon-Number Conserved Universal Quantum Logic Employing Continuous-Time Quantum Walk on Dual-Rail Qubit Arrays