Source-linked AI summary
Universal computation by quantum walk
Andrew M. Childs
TL;DR
The paper asks whether universal quantum computation can be realized with a highly restricted, time-independent Hamiltonian. It constructs quantum circuits from scattering processes on sparse, unweighted graphs and concludes that quantum walk is a universal computational primitive.
Problem
The paper investigates whether universal quantum computation remains possible when the Hamiltonian is restricted to the adjacency matrix of a low-degree graph with entries only 0 or 1.
Method
The construction represents computational basis states by quantum wires and implements quantum gates through scattering widgets attached to and connecting those wires.
Results
Quantum computation can be efficiently simulated by quantum walk on a sparse, unweighted graph, with gate widgets composed into circuits.
Takeaways & Limitations
Quantum walk can serve as a universal computational primitive, with quantum computations encoded entirely in an underlying graph.
Abstract
from arXiv · showhide
In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.
I. INTRODUCTION
The paper develops quantum walk as a universal computational model, motivated by quantum walks’ speedups and by Hamiltonian-based universality. Its construction uses unweighted, maximum-degree-3 graphs whose wires and scattering widgets encode quantum circuits.
- Quantum walks exploit interference and can provide exponential speedups for some black-box problems and polynomial speedups for many practical problems.
- A continuous-time quantum walk is generated by a graph’s adjacency matrix, with evolution e^-iAt on vertex-basis states.
- The paper shows that a restricted quantum walk is universal, so any computation achievable by a general-purpose quantum computer can be simulated by quantum walk.
- The construction uses unweighted edges, maximum degree 3, quantum wires for basis states, and scattering widgets for quantum gates.
- For an n-qubit circuit, the graph has 2n wires, with computation entering on one wire and the output identified by the wire reached on the far right.
II. SCATTERING ON GRAPHS
The section develops scattering analysis for quantum walks on graphs by combining line momentum states, graph-induced scattering coefficients, and stationary-phase propagation. It then shows that semi-infinite scattering lines can be truncated to finite lengths with negligible dynamical effect under a time-scale condition.
- Line states: On an infinite line, momentum states indexed by k ∈ [−π, π) have adjacency eigenvalues 2 cos k.The basis is normalized by ⟨k̃|k̃′⟩ = 2πδ(k − k′).
- Scattering states: Attaching semi-infinite lines to selected vertices of a finite graph produces scattering states whose reflection and transmission coefficients are fixed by boundary equations on G.For fixed momentum, these coefficients can be obtained by solving |G| linear equations, alongside equations for bound states.
- Propagator asymptotics: For propagation between distinct lines, stationary phase selects momenta where the phase k(x + y) + arg Tj,j′(k) − 2t cos k is stationary.The analysis interprets the resulting group velocity and effective path length through G to characterize large-distance propagation; bound-state contributions are argued to be negligible.
- Scattering matrix: The incoming and outgoing scattering bases are related by a unitary S-matrix, whose diagonal entries are reflection coefficients and off-diagonal entries are transmission coefficients.Column orthogonality yields cancellations involving transmission and reflection amplitudes in the propagator analysis.
- Finite-graph implementation: 13: The line walk has a wavefront moving with speed 2, so attached lines can be truncated when their lengths are large compared with twice the total evolution time.This follows from the maximum group velocity and exponential decay of the Bessel-function propagator beyond the wavefront.
III. UNIVERSAL GATE SET
The construction implements a universal set of quantum gates through scattering on graph widgets, with computation encoded by concatenated quantum wires. Gate widgets realize controlled-not, phase, and basis-changing operations, while suitable momentum selection enables circuit-wide composition.
- Gate widgets: The construction uses controlled-not, phase, and basis-changing widgets to implement a universal gate set through scattering on graph wires.The controlled-not exchanges appropriate wires; the phase widget acts on the |1⟩ wire; and the basis-changing widget couples quantum wires.
- Gate widgets: At k = −π/4, the phase widget transmits perfectly and adds a phase of eiπ/4 relative to a straight wire of length 1.For momenta near −π/4, combining this widget on the |1⟩ wire with a straight |0⟩ wire implements the phase gate.
- Gate widgets: At k = −π/4, the basis-changing widget produces an equal superposition of output amplitudes with no reflection back to the input channels.The widget’s forward transmission effectively lengthens the relevant wires by two units.
- Universality: The phase and basis-changing gates generate a dense subset of SU(2), with the latter’s associated gate being the Hadamard gate up to a global phase.Together with the controlled-not widget, these operations provide the universal gate construction described in the section.
- Circuit embedding: For an n-qubit circuit, widgets are replicated across computational-basis settings, producing a graph that is exponentially large but succinctly described by the original circuit.The controlled-not widget is included 2n−2 times and single-qubit widgets 2n−1 times.
- Circuit embedding: Using only three gate widgets, arbitrary quantum circuits can be implemented when the input is a narrow wave packet concentrated near k = −π/4.At this momentum there is no reflection, so transmission coefficients compose multiplicatively through concatenated widgets.
IV. MOMENTUM FILTERING
The filtering construction isolates momenta near k = −π/4 using repeated filter widgets and separates the unwanted k = −3π/4 component temporally.
- Filter construction: The basic filter widget transmits desired and undesired momentum components near k = −π/4 and k = −3π/4, respectively.It includes a semi-infinite line that carries unwanted components away.
- Momentum separation: The filter widget’s transmission sends all amplitude forward at k = −π/4 and k = −3π/4, while other momenta are partly transmitted upward and partly reflected.The solid and dashed curves represent the forward and upward outputs, respectively.
- Filter construction: Repeated filter widgets make transmission exponentially small for momenta away from neighborhoods of k = −π/4 and k = −3π/4.The transfer-matrix eigenvalue analysis gives this suppression as the number of widgets increases.
- Filter construction: At k = −π/4, the filter has perfect transmission, while the effective wire length is increased by two units per widget.The corresponding effective length is also relevant when composing the filtering and gate stages.
- Momentum separation: The momentum separator has perfect transmission at k = −π/4 and k = −3π/4 but different effective lengths, enabling temporal separation of the two components.It also has perfect transmission at k = −π/2.
V. COMPOSING WIDGETS
The paper composes scattering widgets into circuits by tracking transmission and reflection matrices, showing that near k = −π/4 the resulting circuit behaves nearly ideally.
- Circuit construction: For an m-gate circuit, the transmission coefficients at k = −π/4 exactly implement the desired circuit, while effective lengths and curvatures add across widgets.Both quantities therefore scale proportionally to m for the overall graph.
- Scattering composition: Widgets are composed by treating their channels with forward and backward transmission and reflection matrices.The composite scattering expressions arise from summing repeated reflections between widgets.
- Scattering composition: Two widgets with small reflection retain small reflection when combined, and compound forward transmission is nearly the product of the individual transmissions.The paper derives corresponding bounds for both forward and backward reflection.
- Circuit construction: For momenta satisfying |k + π/4| = O(1/m^2), the combined reflection of m gate widgets is O(1/m), so transmission is nearly perfect.The bound applies recursively across the gate-widget sequence.
- Circuit construction: Using md = log Θ(m^2) filter widgets before the gates leaves exponentially small output except near k = −π/4 and k = −3π/4.The filtering stage narrows the momentum support to O(1/m^2) neighborhoods of those points.
VI. BOUND STATES
The analysis shows that bound-state contributions can be neglected with suitable initialization and timing, at the cost of only polynomially increasing the simulation time.
- Neglecting bound states: Starting the walk a distance x = Θ(m^4) from the first widget suppresses bound states with κ = Ω(1/m^4), increasing the running time only polynomially.The suppression follows from exponential decay of bound states as e^−κx.
- Neglecting bound states: Very weakly bound states have nearly identical energies, ±(2 + O(1/m^8)), when κ = O(1/m^4).For t = O(m^4), their phases differ only by O(1/m^4) within each sign class.
- Neglecting bound states: Choosing the evolution time so the phases of the two weakly bound-state types coincide makes their combined phase approximately independent of κ.The stationary scattering momentum remains k⋆ = −π/4 + O(1/m^4).
- Neglecting bound states: The amplitude error from neglecting bound states is O(1/m^4), because their initial contribution is negligible and their relative phases change by only O(1/m^4).The paper states that this error is dominated by the scattering-state contribution.
VII. UNIVERSAL COMPUTER
The construction simulates an arbitrary quantum circuit using quantum walk on a graph, with filtering, momentum separation, and gate widgets arranged along truncated wires. After evolution and measurement, valid outputs reproduce the circuit’s statistics up to the construction’s stated amplitude scaling.
- Circuit implementation: The graph encodes the circuit with filter, momentum-separation, and gate widgets connected by truncated input, output, and filter wires.The circuit uses 2n computational wires, while each gate widget has 2n inputs and 2n outputs.
- Evolution and measurement: The initial state is placed at vertex x on input wire 0in, with x = Θ(m^4), and the graph evolves for time t = O(m^4).The construction initializes |x, 0in⟩ and evolves under the graph’s adjacency-matrix Hamiltonian.
- Evolution and measurement: The procedure measures in the vertex basis and retains an output s only when the result lies on an output wire.A valid output occurs with probability Ω(1/m^4); otherwise, the run is discarded and restarted.
- Simulation fidelity: Conditioned on a valid output, the simulation’s statistics closely reproduce those of the original quantum circuit.The output amplitude is approximately ⟨s|U|0⟩ × Ω(1/m^2).
VIII. DISCUSSION
The construction establishes quantum walk as a universal computational primitive and points to applications in graph-scattering algorithms, quantum complexity theory, and quantum-computer architectures. These applications are presented as potential directions arising from the construction.
- Conclusion: Quantum walk on a sparse, unweighted graph can efficiently simulate any quantum computation.This establishes quantum walk as a universal computational primitive.
- Quantum algorithms: Scattering on graphs can serve as a generic method for transforming quantum states, supporting algorithms for decision trees, game trees, and broad formula classes.The approach need not directly implement one- or two-qubit gates.
- Quantum complexity theory: The construction could potentially support new complete problems in quantum complexity theory or adiabatic quantum computers with desirable properties.The discussion connects this possibility to prior Hamiltonian constructions yielding QMA-complete and BQP-complete problems.
- Quantum architectures: The graph construction might also contribute to developing new architectures for quantum computers.The paper notes this as a possible application without specifying a physical representation.