Universal computation by quantum walk.

By Andrew M. Childs. Physical Review Letters, 2008

888 citations recorded by the source corpus.

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/b8546f5212d9ecf8361d9bef16b47c2a2f009c84

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 Atomic and Molecular Physics, and Optics

Citations in the corpus

Simulating chemistry using quantum computers. (2010, background): “Although we focused on the adiabatic and circuit models, these are not the only universal models of quantum computation and it may be possible to make further algorithmic progress with models such as topological quantum computing (69, 90), one-way quantum computing (108,109), and quantum walks (65,2”
Limits of quantum speedup in photosynthetic light harvesting (2009, background): “Quantum walks even provide a universal implementation for quantum computing [24].”
Anderson localization of entangled photons in an integrated quantum walk (2013, background): “At the quantum level, interference and superposition phenomena lead to a non-classical behavior of the walker giving rise to new interesting effects, which can be harnessed to exponentially speed up search algorithms [21] and to realize universal quantum computation [22].”
Hamiltonian simulation using linear combinations of unitary operations (2012, methodology): “Even before a fault-tolerant quantum computer is built, quantum simulation techniques can be used to prove equivalence between Hamiltonian-based models of quantum computing (such as adiabatic quantum computing [1] and continuous-time quantum walks [2]) and to develop novel quantum algorithms [3–7].”
Exploring topological phases with quantum walks (2010, background): “[4] Childs, A.”
Quantum walks: a comprehensive review (2012, background): “In particular, [151] plays an increasingly important role on the foundations of the field of quantum walks for being an alternative formulation for discrete quantum walks as well as a key tool to describe and understand the proof of computational universality delivered by Childs in [113], this latte”
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.”
Twisted photons: new quantum perspectives in high dimensions (2017, background): “It has been demonstrated that QW allows for dynamic simulation of complex quantum systems, for the implementation of quantum search algorithms [88] and even universal quantum computation [89].”
Geometric phase from Aharonov–Bohm to Pancharatnam–Berry and beyond (2019, background): “sponds to the number of steps in the quantum walk and scales linearly with the number of elements. Quantum walks have been shown to be promising tools for quantum simulations and quantum computations (151,152). Thus, one can appreciate the breadth and impact that geometric phases currently may have ”
Harnessing the Power of the Second Quantum Revolution (2020, background): “Other continuous-time and thus formally analog models include adiabatic quantum computing [85,101], quantum annealing [102], and Hamiltonian quantum walks [103].”
Universal Computation by Multiparticle Quantum Walk (2012, methodology): “Notable previous applications of such scattering include the quantum algorithm for the Hamiltonian NAND tree [8] and the single-particle universality construction [5].”