Source-linked AI summary
Universal quantum computation using the discrete time quantum walk
Neil B. Lovett, Sally Cooper, Matthew Everitt, Matthew Trevers, Viv Kendon
TL;DR
The paper asks whether discrete-time quantum walks can provide the same universal-computation capability established for continuous-time walks. It constructs discrete-time implementations of a universal gate set and supporting transfer structures, showing that both walk types serve as computational primitives. The construction uses different propagation graphs and has higher degree requirements than the continuous-time case.
Problem
Childs established universality for continuous-time quantum walks, leaving the corresponding universal construction for discrete-time quantum walks to be shown.
Method
The paper constructs quantum wires, perfect-state-transfer structures, and universal gates using discrete-time walks with degree-dependent coin operators.
Results
The discrete-time quantum walk implements a universal gate set, including the controlled-not and Hadamard gates.
Takeaways & Limitations
Discrete-time and continuous-time quantum walks can both be regarded as computational primitives, with equivalent computation when their step counts have the same order.
Abstract
from arXiv · showhide
A proof that continuous time quantum walks are universal for quantum computation, using unweighted graphs of low degree, has recently been presented by Childs [PRL 102 180501 (2009)]. We present a version based instead on the discrete time quantum walk. We show the discrete time quantum walk is able to implement the same universal gate set and thus both discrete and continuous time quantum walks are computational primitives. Additionally we give a set of components on which the discrete time quantum walk provides perfect state transfer.
I. INTRODUCTION
The paper adapts Childs’s universality construction from continuous to discrete time, showing that discrete-time quantum walks can implement universal quantum computation. The construction uses different propagation structures and incurs specific graph and timestep overheads.
- Motivation and contribution: Discrete-time quantum walks implement the same universal gate set as Childs’s continuous-time construction.This establishes both walk models as computational primitives for quantum computation.
- Motivation and contribution: The construction requires an exponentially large graph because an n-qubit input uses 2n wires.
- Construction challenge: Directional propagation requires a specific σx coin, which restricts direct propagation to degree-two vertices.The paper therefore uses double-edged wires to support higher-degree computational structures.
- Construction challenge: The discrete-time construction has maximum vertex degree eight, compared with degree three in the continuous-time construction.
- Construction challenge: Using the lazy-walk approximation would permit the same structures as the continuous-time construction but increase deterministic-computation overhead.
II. DISCRETE TIME QUANTUM WALK
A discrete-time quantum walk alternates a unitary coin operation with a conditional shift, producing interference-dependent propagation on graphs whose vertex coins depend on degree. Higher-dimensional coins introduce reflections that the computation must control.
- Walk definition: A discrete-time quantum walk applies a unitary coin toss followed by a conditional shift at each timestep.Basis states record both walker position and two-state coin value.
- Walk dynamics: Quantum interference combines multiple paths constructively or destructively, changing position probabilities during the walk.On a line, the quantum walk spreads quadratically faster than the classical walk.
- Graph structure and coins: The coin operator must act on the full local state space, so vertices with degree greater than two require higher-dimensional coins.
- Graph structure and coins: The Grover coin extends to arbitrary vertex degree, with four-dimensional coins needed at most computational vertices.
- Propagation constraint: Higher-dimensional coins can reflect the walker backward, whereas computation requires forward-only propagation from left to right.The paper addresses this propagation requirement in its gate constructions.
III. PERFECT STATE TRANSFER
The paper develops discrete-time-walk structures that transfer quantum states perfectly and uses directional cycle propagation plus Grover-coin behavior to motivate computational designs.
- Periodic structures: An eight-vertex cycle transfers the state from an initial vertex to the opposite vertex after 12 timesteps and returns it after 24 timesteps.
- Related transfer structures: Perfect state transfer is known for chains of length two or three, hypercubes of any size, and engineered chains with optimized couplings.
- Periodic structures: Discrete-time walks exhibit exact periodic behavior on some cycles, including a four-vertex cycle with an eight-timestep period.
- Directional transfer: A completely biased coin makes state transfer around a cycle perfectly directional, but attaching another structure breaks the cycle’s periodicity.
- Directional transfer: At even-degree vertices with equal input amplitudes and phases, the Grover coin transfers the entire state from input edges to output edges.These transfer properties guide the structures used for universal computation.
IV. UNIVERSAL GATE SET
The discrete-time quantum walk implements a universal gate set using wire structures and degree-dependent Grover coins, including C-NOT, phase-shift, and Hadamard operations.
- Gate set: The gate set comprises controlled-not, single-qubit Hadamard, and phase-shift gates, forming a universal set for quantum computation.The implemented phase shift is the specific π/8 gate.
- Wire propagation: The basic wire propagates the walk deterministically from left to right while splitting the initial state across two parallel edges.The walk reaches the incoming edges of the final vertex in four timesteps.
- C-NOT gate: The C-NOT gate flips the second qubit by exchanging its wires while leaving the first qubit unchanged.The construction uses crossing wires without interaction where dotted lines pass underneath solid lines.
- Phase gate: The phase gate adds a relative phase by assigning a common factor eiφ at degree-four vertices and inserting a dedicated phase structure.Setting φ = −π/4 yields a relative phase of π/4 between the computational-basis wires.
- Hadamard gate: The Hadamard structure combines and equally splits the two input wires, using phase sections and a degree-eight coin to realize the operation.The structure contributes a global phase of 3π/4, while the surrounding phase gates provide the required relative phase.
V. CONSTRUCTING QUANTUM CIRCUITS
Larger circuits are formed by linking degree-four input/output wires and structures so the discrete-time walk propagates deterministically from left to right. Although the graph expands exponentially with qubit count, its wires can be encoded using n qubits.
- V. CONSTRUCTING QUANTUM CIRCUITS: The graph is assembled by connecting wires and gate structures with degree-four input and output vertices, enabling left-to-right linking.The initial state occupies vertices on the graph’s left side, with amplitudes split across incoming edges.
- V. CONSTRUCTING QUANTUM CIRCUITS: The walk propagates across successive graph columns deterministically for the required timesteps, yielding the computation’s output at one vertex.Each column represents a further timestep, and the output is found at a single vertex.
- V. CONSTRUCTING QUANTUM CIRCUITS: For an n-qubit computation, the graph contains 2^n wires, while single-qubit and C-NOT structures are repeated 2^(n−1) and 2^(n−2) times.The phase gate on qubit three is repeated four times in the three-qubit graph.
- V. CONSTRUCTING QUANTUM CIRCUITS: A three-qubit example applies a Hadamard to qubit three, followed by two C-NOT gates and a phase gate on qubit three.The corresponding underlying graph is shown as the circuit’s graph representation.
- V. CONSTRUCTING QUANTUM CIRCUITS: Despite the exponential graph size, the 2^n wires can be represented with n qubits when the graph is encoded on a quantum computer.This follows the binary-label encoding used to represent an N-vertex graph with log2 N qubits.
VI. DISCUSSION
The discrete-time construction establishes universality and computational equivalence with the continuous-time walk under matched step-order scaling. It uses more edges and higher graph degree, while requiring the same timestep order with a small phase-gate-dependent overhead.
- VI. DISCUSSION: The discrete-time quantum walk is universal and can reformulate any quantum algorithm as a discrete-time quantum-walk algorithm.The construction confirms that discrete- and continuous-time walks are computational primitives.
- VI. DISCUSSION: Computational equivalence depends on the numbers of steps in the discrete- and continuous-time constructions being of the same order.The discrete-time computation uses the same timestep order, with a small overhead depending on the number of phase gates.
- VI. DISCUSSION: The discrete-time gate constructs require twice as many edges as the continuous-time case but the same number of wires.The discrete-time phase gate also requires one additional timestep relative to the continuous-time phase-gate construct.
- VI. DISCUSSION: The discrete-time construction has maximum vertex degree eight, compared with degree three in the continuous-time construction.Higher degree supports directional propagation; most structures double the degree, while the proposed Hadamard structure does not.
- VI. DISCUSSION: The authors suggest the Hadamard structure may be decomposable into degree-six vertices, which would align its degree doubling with the continuous-time case.This possibility is presented as reasonable rather than established.