PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal computation by multi-particle quantum walk

Andrew M. Childs, David Gosset, Zak Webb

arXiv:1205.3782v2quant-ph

TL;DR

The paper asks whether interacting multi-particle quantum walks can overcome implementation limits of single-particle quantum-walk universality. It constructs a time-independent multi-particle walk that efficiently simulates quantum circuits, establishing universal quantum computation within stated interaction assumptions.

  • Problem

    Single-particle quantum-walk universality does not directly provide an efficiently implementable architecture because the required graph is exponentially large in the number of qubits.

  • Method

    The paper encodes computational qubits in particle locations and uses a time-independent graph Hamiltonian with particle interactions, analyzed through multi-particle scattering.

  • Results

    Multi-particle quantum walk efficiently simulates any n-qubit circuit with g gates using O(n) particles, polynomial interaction time, and polynomial-size unweighted planar graphs of maximum degree 4.

  • Takeaways & Limitations

    The construction establishes universal quantum computation for interacting multi-particle quantum walks and motivates their investigation as a possible scalable architecture without time-dependent control.

  • Takeaways & Limitations

    The construction assumes interaction terms have constant range and norms polynomially bounded in the number of particles.

Abstract

from arXiv · show

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. Here we consider a generalization of quantum walk to systems with more than one walker. A continuous-time multi-particle quantum walk is generated by a time-independent Hamiltonian with a term corresponding to a single-particle quantum walk for each particle, along with an interaction term. Multi-particle quantum walk includes a broad class of interacting many-body systems such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions. We show that multi-particle quantum walk is capable of universal quantum computation. Since it is also possible to efficiently simulate a multi-particle quantum walk of the type we consider using a universal quantum computer, this model exactly captures the power of quantum computation. In principle our construction could be used as an architecture for building a scalable quantum computer with no need for time-dependent control.

Introduction

The paper addresses the implementation gap in single-particle quantum-walk universality by using interacting multi-particle walks to realize universal quantum computation with a time-independent Hamiltonian.

  • Prior quantum-walk universality: Single-particle continuous-time quantum walk on sparse unweighted graphs is computationally equivalent to the quantum circuit model.
  • Implementation gap: That universality construction does not directly yield a scalable architecture because its graph has exponentially many vertices for n-qubit computations.
  • Implementation gap: Existing physical implementations typically use non-scalable encodings with overhead that prevents efficient universal quantum computation.
  • Multi-particle construction: Multi-particle quantum walk simulates an n-qubit, g-gate circuit using O(n) interacting particles for polynomial time on an unweighted planar graph of maximum degree 4 with poly(n, g) vertices.
  • Multi-particle construction: The construction encodes quantum data differently from the single-particle approach, using particle interactions to implement two-qubit gates and supporting Bose-Hubbard, fermionic, and distinguishable-particle models.
  • Time-independent control: Unlike earlier time-dependent interacting-particle schemes, this approach encodes the computation entirely in a time-independent Hamiltonian and graph.

Multi-particle quantum walk

A continuous-time multi-particle quantum walk describes particles moving on a graph under single-particle hopping terms and local interactions, including bosonic, fermionic, and distinguishable-particle systems.

  • Model definition: The framework allows distinguishable particles and indistinguishable bosons or fermions moving on a simple graph with local interactions.
  • Model definition: For m distinguishable particles, basis states record the vertex location of every particle.
  • Hamiltonian: The continuous-time walk is generated by a time-independent Hamiltonian whose first term moves particles between adjacent sites and whose second term describes particle interactions.
  • Interaction assumptions: Interactions act between two or more particles, have constant range C, and vanish when particles are separated by more than C graph edges.
  • Interaction assumptions: Each interaction term Uij is assumed to have norm bounded by a polynomial in the particle number m.
  • Included models: The framework includes the Bose-Hubbard model and nearest-neighbor interaction models, while its single-particle limit reduces to the standard continuous-time walk generated by the graph adjacency matrix.

Single-particle and two-particle scattering

The construction analyzes quantum-walk computation through single- and two-particle scattering, using graph-attached paths and wave-packet interactions to characterize propagation and gate effects.

  • Scattering framework: The analysis uses a discrete version of scattering theory for single- and two-particle quantum walks on suitable graphs.
  • Single-particle scattering: A single-particle walker approaching the finite subgraph along one semi-infinite path scatters into a superposition over all attached paths.
  • Single-particle scattering: Scattering states have definite incoming momentum, and the unitary S-matrix gives the amplitudes for outgoing paths.
  • Single-particle scattering: A wave packet with momentum near k moves at speed |2 sin k| and exits along each path with amplitude S_qj(k).
  • Single-particle scattering: The scattering description remains applicable to finite wave packets and long finite paths through the paper’s analysis.
  • Two-particle scattering: For two indistinguishable particles approaching each other on an infinite path, energy and momentum conservation preserve their momenta while interaction modifies the wave-function phase.

Computation by multi-particle quantum walk

The scheme encodes computational and mediator qubits in particle wave packets and implements a universal gate set through time-independent multi-particle quantum-walk dynamics. Scattering-based graph components realize single- and two-qubit operations with polynomial resources and arbitrarily small simulation error.

  • Encoding: n computational qubits are encoded by n particles with momentum −π/4, while an additional mediator particle uses momentum −π/2.Each qubit uses dual-rail encoding: |0⟩ occupies the top path and |1⟩ the bottom path.
  • Single-qubit gates: Single-qubit gates are implemented by scattering particles through subgraphs while they remain far apart and their interactions are negligible.The construction uses phase, basis-changing, identity, and Hadamard gates as graph components.
  • Two-qubit gates: For the Bose-Hubbard model, U = 2 + 2 gives e^iθ = −i, while nearest-neighbor fermionic interactions with U = −2 − 2 give e^iθ = i and CP = (Cθ)^3.For most interaction phases, the controlled phase can instead be approximated by repeating Cθ a times so that e^iaθ ≈ −i.
  • Two-qubit gates: The momentum switch routes particles according to momentum, enabling a subgraph to make computational and mediator particles interact only for selected logical states.The controlled interaction routes particles toward each other along a long path, implementing a controlled-phase operation.
  • Efficiency and refinements: An n-qubit, g-gate circuit is simulated with arbitrarily small error using polynomial wave-packet size, graph size, and evolution time.For the Bose-Hubbard and nearest-neighbor models, the stated bounds are O(n^12g^4) wave-packet size, O(n^13g^5) vertices, and O(n^12g^5) evolution time.
  • Efficiency and refinements: The construction can be refined to use an unweighted planar graph of maximum degree four and distinguishable particles with nearest-neighbor interactions.These refinements are intended to make the scheme more amenable to implementation.

B Two-particle scattering states

The paper derives two-particle scattering eigenstates by transforming to center-of-mass and relative coordinates, then uses reflection, transmission, and interaction-dependent phases to characterize scattering for several particle models.

  • Derivation: The two-particle Hamiltonian is analyzed in coordinates s = x + y and r = x − y, exploiting translation symmetry.Allowed coordinate pairs have matching parity, and the relative-coordinate problem becomes an effective single-particle scattering problem.
  • Derivation: For each p1 ∈(−π, π) and p2 ∈(0, π), the scattering eigenstate has incoming, interaction-region, and outgoing components governed by R, f, and T.Outside the finite interaction range C, the state consists of plane-wave terms; within |r| < C, amplitudes are determined by linear equations.
  • Eigenstates: The scattering states have eigenvalue 4 cos(p1/2) cos(p2) and are delta-function orthonormal over the allowed momenta.States for negative p2 and exchanged particle coordinates provide the corresponding additional descriptions.
  • Scattering: The outgoing wave acquires the relative phase T ± R, which arises from the interaction between the particles and satisfies |T ± R| = 1.The sign distinguishes the symmetrized and antisymmetrized constructions for bosons and fermions.
  • Examples: For the Bose-Hubbard interaction V(|r|) = Uδr,0, the scattering phase is eiθ+(p1,p2) = T(p1,p2) + R(p1,p2).At k1 = −π/2 and k2 = π/4, the specified parameters produce a phase e−iπ/2 = −i after scattering.
  • Examples: For nearest-neighbor interactions V(|r|) = Uδ|r|,1, solving the interaction-region equations yields scattering states for bosons, fermions, and distinguishable particles.Unlike the Bose-Hubbard case, 1 + R = T need not hold; one example gives R = 0 and T = i.

C.1 Making the graph planar

The construction modifies the gate graphs and introduces mediator qubits so the entire computation can be implemented on a planar graph. Distinguishable particles require a specially tuned interaction to preserve the encoding while producing a nontrivial phase.

  • Planarity challenge: The original gate scheme may be nonplanar because mediator interactions can cross computational-qubit paths.The Hadamard and controlled-phase gate graphs can also become nonplanar when input and output paths are attached.
  • Planarity challenge: A planar Hadamard graph reduces maximum degree from 5 to 4 but increases the number of vertices.The modification preserves the required input and output face arrangement.
  • Planar construction: Additional mediator qubits are placed between neighboring computational qubits, restricting two-qubit interactions to adjacent encoded qubits.Mediator m(i) interacts only with computational qubits i and i + 1.
  • Planar construction: The planar entangling graph is formed by concatenating two Cθ graphs and uncrossing paths, implementing controlled phases between a mediator and a neighboring computational qubit.Interactions with the upper and lower encoded qubits produce X-conjugated (Cθ)^2 operations on the corresponding bottom qubit.
  • Planar construction: SWAP gates move encoded qubits so the nearest-neighbor controlled-phase gates can implement interactions between arbitrary encoded qubits.The information is moved next to the target qubit, the controlled phase is applied, and the information is returned.
  • Planar construction: Concatenating planar gate graphs preserves the relative ordering of input and output paths, making the overall computation graph planar.This follows because each individual graph is planar and preserves path positions at its boundaries.
  • Distinguishable particles: For distinguishable particles, the interaction must force zero reflection while retaining a nontrivial transmission phase.The construction chooses parameters so R = 0 and T ≠ 1; one choice yields T = i and enables a controlled-phase gate.

D.2 Initial state, final measurement, and error bound

The construction initializes encoded wave packets on the graph, evolves them under its time-independent Hamiltonian, and reads out the encoded state from particle locations. Polynomial choices of the path parameter make the simulation error arbitrarily small while keeping graph size and evolution time polynomial.

  • Initial state: The initial state consists of n + 1 spatially separated wave packets localized on input paths of the first graph block.Computational and mediator input paths are labeled separately for basis states and positions.
  • Initial state: The system starts at t = 0 in the computational basis state |00 . . . 0⟩ encoded across the particle wave packets.For indistinguishable particles, the encoded state is symmetrized or antisymmetrized according to particle statistics.
  • Evolution and measurement: The encoded state evolves for time T under the Hamiltonian H^(n+1)_G according to the Schrödinger equation.The final block defines the output locations used to represent the logical output state.
  • Error bound: The graph implementing a circuit is assembled by composing type I and type II blocks that represent circuit gates.The total evolution time is specified as a function of the circuit-block composition.
  • Evolution and measurement: A computational-basis measurement reads the logical output by measuring the particles’ locations at the end of the evolution.The measured locations are interpreted using the encoded output-path basis.
  • Error bound: For the considered models, ∥H^(n+1)_G∥ = O(n^2), and choosing L = O(n^12g^4) makes the simulation error arbitrarily small.The resulting construction has O(n^13g^5) vertices and total evolution time O(n^12g^5).

E Analysis of wave packet scattering

The analysis establishes scattering behavior for one- and two-particle wave packets, then transfers these results from infinite graphs to finite, connected constructions using a truncation lemma. The resulting single-qubit gate approximation error decreases polynomially with wave-packet length.

  • Single-particle scattering: Single-particle wave packets decompose into incoming and outgoing components and propagate at speed 2|sin k|.Before scattering, the packet is supported on its input path; afterward, it becomes a superposition of outgoing packets.
  • Two-particle scattering: Two-particle scattering produces an overall phase eiθ from the interaction between the particles.The phase appears in the outgoing wave-packet description after the particles pass one another.
  • Finite-graph truncation: The truncation lemma shows that these scattering results remain valid on finite graphs when wave packets stay far from path endpoints for evolution times T = O(L).For the finite-path constructions, the approximation error is bounded by O(L^-1/4).
  • Single-qubit gates: Single-qubit gates use four length-K paths attached to a finite subgraph, with wave-packet evolution approximating the desired output state.The construction analyzes scattering at specified momenta and obtains an error that decreases polynomially as L grows.

E.4 A two-qubit gate

The two-qubit Cθ gate is implemented by arranging two encoded particles to traverse a graph whose interaction changes only the joint logical |11⟩ state. The phase acquired during scattering supplies the controlled phase, while truncation bounds the finite-graph approximation error.

  • Gate action: The Cθ graph applies a phase eiθ when both particles occupy the logical state 1.The other logical input cases are analyzed through single-particle propagation on disconnected or piecewise-connected subgraphs.
  • Noninteracting cases: For inputs with at most one logical 1, the particles propagate through the switches without interacting and emerge in the corresponding logical output states.At momentum −π/4, the switches have the same scattering behavior as paths of length 4.
  • Interacting case: The graph separates the two particles during the initial segment by deleting an interval longer than the interaction range C.This makes the relevant components disconnected and permits separate single-particle analyses before the packets meet.
  • Interacting case: For the |11⟩ input, the interaction changes the final global phase by eiθ relative to the noninteracting evolution, up to O(L^-1/4) error.The analysis divides the evolution into three time segments and applies the truncation lemma on each segment.

E.5 Block-by-block analysis of the full graph for a circuit

The full circuit is assembled from single- and two-qubit blocks whose encoded wave packets move through successive graph regions. Blockwise truncation analysis shows that the intended unitaries compose with polynomially controlled total error.

  • Type-I blocks: Type-I blocks apply the intended single-qubit gates to encoded computational and mediator qubits, with per-block error O(nL^-1/4).The errors from the n + 1 encoded qubits add linearly.
  • Type-II blocks: Type-II blocks apply the intended two-qubit unitary to the selected computational qubit and mediator qubit.The isolated-block evolution is then related to the connected full graph using the truncation lemma.
  • Block composition: Concatenating blocks makes the output of one block serve as the input of the next, while preserving the encoded wave-packet form up to small error.Overlapping paths place each outgoing packet at the required distance inside the succeeding block.
  • Block composition: For g blocks in series, the total final-state error scales as O(g∥H^(n+1)_G∥nL^-1/4).The construction therefore controls circuit-level error by choosing the wave-packet length L sufficiently large.

G.1 Proof of Theorem 2

The proof of the two-particle scattering theorem approximates localized wave packets by momentum-space states and bounds the resulting error terms. Technical lemmas control normalization, separated supports, interaction-region contributions, and truncation estimates.

  • Momentum-space bounds: The proof isolates momentum regions near the chosen particle momenta and uses smoothness of the scattering phase to control deviations within those regions.The relevant momenta are centered at p1 = π/4 and p2 = 3π/8.
  • Wave-packet approximation: Lemma 3 bounds the difference between the exact two-particle state and its wave-packet approximation by O(L^-1/4) for times t ≤ c0L.This estimate is a central input to the proof of Theorem 2.
  • Interaction-region bounds: Interaction contributions are confined to configurations where the particles are within the finite interaction range C.Support and amplitude bounds on this region yield the required norm estimates.
  • Truncation: The truncation lemma compares evolution under the full and projected Hamiltonians when the initial state remains separated from the removed region for sufficiently many applications of the Hamiltonian.This transfers infinite-graph scattering estimates to finite graphs.
  • Truncation: The proof chooses η = 2 in the truncation estimate, while noting that a smaller value would slightly improve the bound without significantly improving the final result.The simpler choice is retained because it is sufficient for the construction.
Loading 1205.3782v2…