PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Walks

Daniel Reitzner, Daniel Nagaj, Vladimir Buzek

arXiv:1207.7283v2quant-ph

TL;DR

The paper surveys quantum walks as quantum counterparts to classical random walks and examines their algorithmic uses in graph search and sampling. It describes discrete- and continuous-time walks, quantized Markov chains, and quantum-walk mechanisms that yield speedups over classical approaches.

  • Problem

    The paper addresses how quantum walks differ from classical random walks and how those differences can support graph-searching and sampling algorithms.

  • Method

    The paper presents a tutorial survey of discrete-time and continuous-time quantum walks, graph-search applications, and quantized Markov chains.

  • Results

    Quantum walks can provide faster mixing and quadratic speedups for graph searches, while quantum Markov chains underlie quadratic speedups for sampling-related algorithms.

  • Takeaways & Limitations

    Quantum walks provide a framework for quantum algorithms based on unitary amplitude evolution, including graph searches and sampling algorithms.

  • Takeaways & Limitations

    Whether the speedup for mixing can be achieved in general for many quantized Markov chains remains open.

Abstract

from arXiv · show

This tutorial article showcases the many varieties and uses of quantum walks. Discrete time quantum walks are introduced as counterparts of classical random walks. The emphasis is on the connections and differences between the two types of processes (with rather different underlying dynamics) for producing random distributions. We discuss algorithmic applications for graph-searching and compare the two approaches. Next, we look at quantization of Markov chains and show how it can lead to speedups for sampling schemes. Finally, we turn to continuous time quantum walks and their applications, which provide interesting (even exponential) speedups over classical approaches.

1 Introduction

The introduction section is listed on page 607.

  • The introduction begins on page 607.

2 Classical Random Walks

The section records small post-processing corrections at four specified pages: 653, 700, 707, and 711.

  • Small post-processing corrections were made at page 653.
  • Small post-processing corrections were made at pages 700 and 707.
  • A small post-processing correction was made at page 711.

3 Quantum Walks: Using Coins

The quantum-walks section introduces analogies with classical walks, dispersion of the Hadamard walk, coined walks on general graphs, scattering walks, and coins.

  • The section draws an analogy from the classical case.
  • It examines dispersion of the Hadamard quantum walk on a line.
  • It develops coined quantum walks on general graphs.
  • It discusses scattering quantum walks and two-dimensional coins.

4 Quantum Walks and Searches

The quantum-walks-and-searches section covers Grover search, graph searches, symmetry considerations, and search on a complete graph.

  • The section includes Grover search.
  • It examines searches on graphs.
  • It treats symmetry considerations in quantum-walk searches.
  • It includes search on a complete graph.

5 Quantizing Markov Chains

The article situates quantum walks within sampling and Markov-chain methods, including quantum approaches to mixing, Monte Carlo, and related speedups.

  • 5 Quantizing Markov Chains: This section covers walks on two registers, the walk spectrum, faster searching for marked vertices, and walks for sampling.It also includes quantum mixing speedups and Markov chain Monte Carlo methods.
  • 5 Quantizing Markov Chains: The section also introduces continuous-time quantum walks and their roles in quantizing continuous random walks and spatial search.Topics include one-dimensional walking and mixing, symmetries, complete-graph search, and searches on hypercubes and lattices.

1 Introduction

Quantum walks replace stochastic probability evolution with unitary amplitude evolution, producing interference and distributions that differ from classical random walks. The tutorial develops these ideas through graph search, sampling-related methods, and dispersion results showing faster spreading in quantum walks.

  • 1 Introduction: Quantum walks transform probability amplitudes by unitary operations rather than probabilities by stochastic matrices, enabling interference effects.The article presents this as the computer-science and mathematical analogy to classical random walks.
  • 1 Introduction: The tutorial develops discrete-time quantum walks from classical random walks and notes that noise can return their dynamics to classical random processes.It then connects superposition-based walks to graph searching and other applications.
  • Graph Searching: Graph-search examples include hypercube and glued-tree traversal, where quantum walks can have exponentially faster hitting times than classical random walks.The comparison is made for graphs whose structure is supplied through an oracle.
  • Graph Searching: Classical random walks on the hypercube require O(2^n) hitting time, while a memory-based classical strategy can traverse it with polynomial efficiency and O(n) memory.The walk increases distance from the entrance and decreases distance from the exit at each step.
  • Graph Searching: For glued trees, memory enables classical traversal in O(n^2) steps, so the example does not itself yield a major quantum speedup.The text identifies graph symmetry as the source of efficient quantum traversal and points to a later example for exponential speedup.
  • Dispersion of the Hadamard Quantum Walk on Line: On a line, quantum-walk standard deviation grows as σ ∼ m, compared with σ ∼ √m classically, giving quadratically faster spreading.The Hadamard-walk distribution can also be asymmetric and is close to uniform within its accessible interval.
  • Dispersion of the Hadamard Quantum Walk on Line: Coined quantum-walk Shannon entropy exceeds the classical drunkard’s-walk entropy, although the quantum value depends on the initial coin state.The maximal entropy reachable by any walk is Smax(m) = ln(m + 1).

3.4 More on Coins

Quantum-walk behavior depends strongly on the initial coin state, coin choice, graph spectrum, and decoherence. These choices produce distributions and search dynamics that differ substantially from classical random walks, while graph symmetries can reduce analysis to small invariant subspaces.

  • Coin choices: The initial coin state can produce right-skewed, symmetric, or left-skewed Hadamard-walk distributions despite an unbiased coin.Under unitary evolution, information about the initial state is transferred to the final distribution.
  • Coin choices: The full range of unbiased-coin quantum-walk behavior on a line can be achieved with the Hadamard coin by choosing the initial coin state.Different coin operators are therefore not required to realize qualitatively distinct line-walk behaviors.
  • Limiting distributions: Unlike classical limiting distributions, general quantum limiting distributions can depend on the initial state; distinct eigenvalues on suitable Abelian Cayley graphs are an exception.Quantum mixing-time behavior is also governed differently because unitary eigenvalues all have amplitude one.
  • Limiting distributions: On cycles, the limiting Hadamard-walk distribution depends on the parity of N and is uniform only when N is odd.Changing the coin can also modify the limiting distribution while keeping the number of nodes fixed.
  • Hitting times: Quantum walks can have exponentially faster hypercube hitting times than corresponding classical random walks, but a classical polynomial-time traversal algorithm can match that efficiency.Thus, an exponential hitting-time separation from one classical walk does not by itself establish an exponential speedup over every classical algorithm.
  • Quantum-to-classical transition: Interference changes boundary behavior: the quantum walk reaches the boundary with probability 2/π, whereas the classical random walk reaches it with probability 1.The difference arises because quantum amplitudes interfere before probabilities are obtained.
  • Quantum-to-classical transition: Decoherence interpolates between unitary quantum evolution at p = 1 and interference-free classical-like evolution at p = 0, with intermediate p producing near-uniform distributions.The entropy-maximizing value depends on both p and the number of steps; spreading changes from ballistic to slower, normal-like behavior at larger times.
  • Algorithmic implications: Discrete-time quantum walks spread ballistically rather than diffusively, supporting faster mixing and graph-search applications including quadratic unstructured-search speedups.The article also presents quantum walks as subroutines for tasks such as k-subset finding and discusses Fourier transforms and path counting as analysis methods.

4.5 Other Examples of Searches on Graphs

Quantum-walk searches achieve speedups whose magnitude depends strongly on graph structure and problem formulation. The section also extends these ideas from graph search to Markov-chain search, sampling, and mixing.

  • Graph choice: Complete graphs provide quadratic search speedups over classical search, whereas circular graphs provide no comparable speedup.The walk’s efficiency depends on the graph choice, even when the oracle is unchanged.
  • Graph choice: Complete bipartite and complete M-partite graphs also permit quadratic speedups in oracle calls over the best classical algorithms.The complete graph is recovered by taking N = 1, while the complete bipartite graph is recovered by taking M = 2.
  • Scattering quantum walks: Quadratic improvement can arise without phase-flips in scattering quantum-walk searches, through interference between incoming and outgoing amplitudes.On the non-bipartite graph considered, the extra edge enables this interference.
  • k-clique finding: O(N^1.3) oracle calls find a triangle, improving on direct Grover search for k-cliques, although the known lower bound is only O(N).For k = 2, the algorithm matches Grover search with O(N) oracle calls; for k > 2, it is more efficient than direct Grover search.
  • Markov chains and sampling: Quantized Markov chains yield square-root speedups for search and sampling tasks, including mixing, simulated annealing, partition-function approximation, and quantum Metropolis algorithms.Szegedy’s construction replaces a classical dependence f(ε, δ) with f(√ε, δ) for the corresponding quantum walk.

Var

The quantum treatment replaces classical Markov-chain sampling and ratio estimation with coherent quantum samples, quantum walks, and phase estimation to approximate partition functions. Under efficient preparation assumptions, the resulting scheme achieves quadratic improvements in spectral-gap and precision dependence.

  • Assumptions and implementation: Approximate samples can be obtained from rapidly mixing Markov chains, but constructing such chains is difficult and is known for specific models including Ising and Potts systems.The analysis bounds the effect of imperfect samples using variation distance and product-distribution arguments.
  • Speedups: The quantum algorithm reduces the classical 1/δ dependence to a square-root dependence on the Markov-chain spectral gap parameter δ.This improvement uses quantum walks and the quadratic relation between spectral and phase gaps.
  • Ratio estimation: Classically, estimating αi requires repeated measurements of samples from πi, whereas the quantum scheme phase-estimates a unitary related to a quantum walk on |πi⟩.The quantum samples coherently encode πi, and the observable-based classical mean estimation is replaced by a quantum procedure.
  • Speedups: The precision dependence improves from 1/ϵ^2 classically to 1/ϵ through quantum ratio estimation.The ratios are estimated using phase estimation rather than repeated classical sampling.
  • Algorithm structure: The algorithm successively prepares approximate quantum samples |πi⟩ and applies a quantum circuit to estimate each ratio αi used in the partition-function product.The structure consists of successive approximate state preparations followed by quantum estimation of the ratios.
  • Guarantee: Theorem 6 establishes a fully polynomial quantum approximation scheme for the partition function, assuming efficient and perfect preparation of the states |πi⟩.The construction combines ratio-estimation, powering, and composition procedures into an approximation for Z.

6 Continuous Time Quantum Walks

Continuous-time quantum walks spread ballistically, with wavefront speed and mixing governed by the Hamiltonian spectrum. Their applications include search, graph traversal, NAND-tree evaluation, and universal quantum computation, although apparent speedups depend on the problem and cost model.

  • 6.1.1 Walking in 1D and Mixing: The continuous-time walk on a line spreads linearly with time, unlike the classical walk’s square-root scaling.Significant transition probability occurs when 2t ≈ y −x, with wavefront speed 2.
  • 6.1.1 Walking in 1D and Mixing: Quantum-walk mixing depends on small gaps throughout the energy spectrum, not only the ground-to-first-excited-state gap.For cycles, the mixing time has superlinear scaling in N, connected to the linear spreading of the wavefront.
  • 6.1.2 Symmetries and Continuous-time Quantum Walks: Continuous-time quantum walks can traverse a hypercube completely in constant time, but the cost also includes the dimensionless parameter ∥H∥t.The constant-time traversal follows from independent rotations of the qubits.
  • 6.1.2 Symmetries and Continuous-time Quantum Walks: The glued-trees oracle problem admits substantial EXIT probability after O(n) time, while classical exploration requires exponentially many queries.Random vertex names restrict classical algorithms to a connected neighborhood around ENTRANCE, making EXIT exponentially unlikely to find.
  • 6.3 NAND Trees and Games: Continuous-time quantum walks support universal quantum computation and can encode NAND-tree evaluation through transmission and reflection on graph Hamiltonians.Arbitrary n-qubit unitaries can be translated into walks on sparse graphs of maximum degree 3, while a multiple-walker construction reduces graph size to poly(n, L).

6.6 Summary

Continuous-time quantum walks describe excitation dynamics using a graph-based Hamiltonian, with wavepacket spreading, lattice-search applications, and symmetry-based analysis.

  • Continuous-time quantum walks model excitation dynamics, with the system Hamiltonian potentially given by a graph’s adjacency matrix.
  • Their wavepacket spreading can resemble discrete-time quantum walks and support lattice-search algorithms.
  • Symmetries enable analysis of continuous-time quantum-walk dynamics using standard quantum-mechanical tools.

A Limiting Distribution of Classical Random Walks

For connected, non-bipartite undirected graphs, the classical random walk admits a spectral description whose eigenvalues lie in [−1,1] and whose unique stationary eigenvector determines the limiting distribution π.

  • For a connected, non-bipartite graph, the random-walk transition matrix is M = AD−1, with A the adjacency matrix and D the diagonal degree matrix.
  • Although M is generally nonsymmetric, a similarity transformation relates it to the symmetric matrix Q, preserving eigenvalues and enabling spectral decomposition.
  • All eigenvalues of M lie in [−1,1], and π is its unique eigenvector with eigenvalue 1.
  • The stationary distribution is π = 1/(2|E|)(d(1), d(2), . . . , d(N))^T, proportional to vertex degrees.
  • As m →∞, contributions from eigenvalues λj for j = 2, 3, . . . , N vanish, yielding the limiting distribution π.
  • The treatment excludes eigenvalue −1 because only bipartite graphs produce that case.

B.1 Method of Stationary Phase

The method of stationary phase estimates oscillatory integrals by focusing on stationary points, where phase oscillations are small and contributions are largest.

  • Stationary-phase analysis identifies regions near stationary points of φ(k), where oscillations are small and integral contributions are largest.
  • Under smoothness and nonvanishing assumptions on g(k), the method provides an asymptotic approximation as t →∞.

B.2 Hadamard Walk Evolution Approximation

The Hadamard-walk evolution integrals are transformed into stationary-phase form, producing different asymptotic behavior depending on λ and the existence of stationary points.

  • The integrals are transformed by setting x = λm so they match the stationary-phase form used for asymptotic analysis.
  • For λ > 1/2, no stationary points exist, and I(m; λ) decreases exponentially fast as λ moves farther from zero.
  • For λ ∈ (−1/2, 1/2), stationary points ±kλ exist in [0, π] and have order p = 2.
  • Boundary points are treated as unimportant for the analysis.
  • The integration range [−π; π] is divided into four subintervals using 0 and ±kλ before applying the approximation.
  • The resulting expressions distinguish whether g is even or odd and determine the probability of occupying position λt after m steps.

C Catalan Numbers

Catalan numbers enumerate nonnegative paths that return to the origin after 2n steps and are used to analyze classical and quantum walks. Their generating-function derivation yields the Catalan-number form and a large-n approximation.

  • Catalan numbers enumerate paths on a semi-infinite line that start at position 0 and return there after 2n steps.
  • The recurrence is obtained by considering all paths returning to the origin after 2k steps for k = 1, 2, . . . , n.
  • The generating function c(x) is derived by writing its power series and solving the resulting quadratic equation.
  • The solution with a pole at x = 0 is rejected because c(x) must be a power series at x = 0.
  • Substituting y = −4x into the power series for √1 + y produces the Catalan generating-function expansion.
  • The expansion gives the Catalan-number form, with a separate approximation available for large n.

D Grover’s Fixed-point Search

Grover’s original search can lose success probability when run past its optimal stopping time, motivating a fixed-point construction based on iterative phase-π/3 composition. The construction reduces failure probability by cubic composition, but sacrifices Grover’s square-root query speedup.

  • Grover’s original algorithm is not fixed-point: running beyond its optimal time decreases the probability of finding a marked element and can return to the initial state.
  • The fixed-point algorithm achieves high-probability search even when runtime is overshot, but loses Grover’s square-root speedup and can remain useful when the marked-item ratio is not small.
  • The fixed-point modification intersperses an algorithm U with selective phase shifts for the uniform superposition and marked subspace, choosing θ = φ = π/3.
  • The construction analyzes U|s⟩ by decomposing it into marked and unmarked components, then uses an orthogonal state |s′⟩ to derive the failure probability.
  • At each composition level, the failure probability changes as f → f^3, producing progressively smaller failure probability.
  • For an initial algorithm using c0 = n oracle calls, the first two composition levels use c1 = 3n + 1 and c2 = 9n + 3 + 1 oracle calls.
Loading 1207.7283v2…