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).

26 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 (8)

• Universal computation by quantum walk
• Universal computation by multi-particle quantum walk
• Decoherence in quantum walks - a review
• Classical approach to the graph isomorphism problem using quantum walks
• Almost uniform sampling via quantum walks
• Quantum random access memory via quantum walk
• Levinson's theorem for graphs II
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM

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