Universal Computation by Multiparticle Quantum Walk

By Andrew M. Childs, David Gosset, Zak Webb. Science, 2012

450 citations recorded by the source corpus.

Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson). Broome et al. (p. 794, published online 20 December) and Spring et al. (p. 798, published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation. A scalable quantum computer architecture based on multiple interacting quantum walkers is proposed. [Also see Perspective by Franson] A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. We consider a generalization to interacting systems with more than one walker, such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions, and show that multiparticle quantum walk is capable of universal quantum computation. Our construction could, in principle, be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/9afeb3e80d6166b4f477c090836615c842ab2766

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Integrated Source of Spectrally Filtered Correlated Photons for Large-Scale Quantum Photonic Systems (2014, background): “[65] A.”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, background): “algorithm [2, 3] inspired by adiabaticity, and quantum walks [4, 5] inspired by locality, are prominent examples.”