Universal quantum computation using the discrete time quantum walk
arXiv:0910.1024 · doi:10.1103/PhysRevA.81.042330
Abstract
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.
9 pages, 10 figures. Updated after referee comments - Section V expanded and minor changes to other parts of the text
References in corpus (8)
- Universal computation by quantum walk
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- Faster quantum walk algorithm for the two dimensional spatial search
- Connecting the discrete and continuous-time quantum walks
- Spatial search and the Dirac equation
- Quantum Random Walks Hit Exponentially Faster
Cited by in corpus (269)
- Quantum walks: a comprehensive review
- Boson Sampling on a Photonic Chip
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Simulating chemistry using quantum computers
- Photonic quantum walk in a single beam with twisted light
- Quantum walks and wavepacket dynamics on a lattice with twisted photons
- Quantum Algorithm Implementations for Beginners
- Implementing Quantum Walks Using Orbital Angular Momentum of Classical Light
- Universal Variational Quantum Computation
- Realization of single-qubit positive operator-valued measurement via a one-dimensional photonic quantum walk
- Quantum Walk in Momentum Space with a Bose-Einstein Condensate
- Propagation and spectral properties of quantum walks in electric fields
- Dynamically Disordered Quantum Walk as a Maximal Entanglement Generator
- Perfect state transfer and efficient quantum routing: a discrete-time quantum walk approach
- Multi-walker discrete time quantum walks on arbitrary graphs, their properties, and their photonic implementation
- Discrete Time Quantum Walk Approach to State Transfer
- Quantum walk as a generalized measuring device
- Scattering theory of topological phases in discrete-time quantum walks
- Localization, delocalization, and topological phase transitions in the one-dimensional split-step quantum walk
- Universal quantum computation by discontinuous quantum walk
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Bulk-edge correspondence of one-dimensional quantum walks
- Entangling Power of Disordered Quantum Walks
- Quantum key distribution with quantum walks
- Edge-state enhanced transport in a 2-dimensional quantum walk
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Centrality measure based on continuous-time quantum walks and experimental realization
- Weak Limit of the 3-State Quantum Walk on the Line
- Quantum Walks
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Quantum walks in external gauge fields
- Efficiency of open quantum walk implementation of dissipative quantum computing algorithms
- Complex Quantum Networks: a Topical Review
- Discrete-time quantum walk with feed-forward quantum coin
- Limit distributions of three-state quantum walks: the role of coin eigenstates
- Quantum Walks with Dynamical Control: Graph Engineering, Initial State Preparation and State Transfer
- Large scale quantum walks by means of optical fiber cavities
- Universal quantum computing using single-particle discrete-time quantum walk
- Quantum walks public key cryptographic system
- Quantum walks with memory - goldfish, elephants and wise old men
- Directional correlations in quantum walks with two particles
- The Thirring quantum cellular automaton
- Two-dimensional quantum walk under artificial magnetic field
- Entanglement engineering and topological protection by discrete-time quantum walks
- Advances in quantum machine learning
- Trapping photons on the line: controllable dynamics of a quantum walk
- Driven Quantum Walks
- Fidelity susceptibility near topological phase transitions in quantum walks
- Controlling quantum random walk with a step-dependent coin
- Quantum Walk Search on the Complete Bipartite Graph
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Emergence of Randomness and Arrow of Time in Quantum Walks
- Localized quantum walks as secured quantum memory
- Experimental realization of a momentum-space quantum walk
- Green's function approach for quantum graphs: an overview
- Simulating Dirac Hamiltonian in Curved Space-time by Split-step Quantum Walk
- Localized State in a Two-Dimensional Quantum Walk on a Disordered Lattice
- Quantum Walks on Trees with Disorder: Decay, Diffusion, and Localization
- Nonlocality, quantum correlations, and violations of classical realism in the dynamics of two noninteracting quantum walkers
- Discrete-time quantum walk algorithm for ranking nodes on a network
- Equivalence of Szegedy's and Coined Quantum Walks
- Dynamics and energy spectra of aperiodic discrete-time quantum walks
- Implementation of multidimensional quantum walks using linear optics and classical light
- Open Quantum Walks: a short introduction
- Quantum state revivals in quantum walks on cycles
- Aperiodic space-inhomogeneous quantum walks: localization properties, energy spectra and enhancement of entanglement
- Enhanced non-Markovian behavior in quantum walks with Markovian disorder
- Quantum random access memory via quantum walk
- Quantum Walk with a four-dimensional coin
- Bounds on the dynamics of periodic quantum walks and emergence of the gapless and gapped Dirac equation
- Revivals in Quantum Walks with quasi-periodically time-dependent coin
- Creating cat states in one-dimensional quantum walks using delocalized initial states
- Electric circuits for universal quantum gates and quantum Fourier transformation
- Persistence of Topological Phases in Non-Hermitian Quantum Walks
- Quantum spatial search in two-dimensional waveguide arrays
- Asymptotic entanglement in quantum walks from delocalized initial states
- Entanglement dynamics and quasi-periodicity in discrete quantum walks
- Electric quantum walks in two dimensions
- Eigenvalue Measurement of Topologically Protected Edge states in Split-Step Quantum Walks
- Quantum walks: decoherence and coin-flipping games
- Solutions of a two-particle interacting quantum walk
- Bloch-Landau-Zener dynamics induced by a synthetic field in a photonic quantum walk
- Fermion confinement via Quantum Walks in 2D+1 and 3D+1 spacetime
- Bose-Hubbard model for universal quantum walk-based computation
- Implementation of generalized measurements on a qudit via quantum walks
- Quantum-Clustered Two-Photon Walks
- Quantized recurrence time in iterated open quantum dynamics
- Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction
- Two-walker discrete-time quantum walks on the line with percolation
- Weak disorder enhancing the production of entanglement in quantum walks
- Connecting velocity and entanglement in quantum walks
- Disorder-free localization in quantum walks
- Time evolution of continuous-time quantum walks on dynamical percolation graphs
- Discrete time quantum walks on percolation graphs
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Quantum walks on embedded hypercubes
- Simulation of Quantum Walks and Fast Mixing with Classical Processes
- Asymptotic properties of the Dirac quantum cellular automaton
- Singular continuous Cantor spectrum for magnetic quantum walks
- Classical-like behavior in quantum walks with inhomogeneous, time-dependent coin operators
- Percolation induced effects in 2D coined quantum walks: analytic asymptotic solutions
- Unitary Equivalence of Quantum Walks
- Quantum algorithms for scientific computing
- Localization and limit laws of a three-state alternate quantum walk on a two-dimensional lattice
- Entropy rate of message sources driven by quantum walks
- Efficient implementation of discrete-time quantum walks on quantum computers
- Quantum magnetometry using discrete-time quantum walk
- Quantum walk on a cylinder
- Bulk-edge correspondence and stability of multiple edge states of a symmetric non-Hermitian system by using non-unitary quantum walks
- Almost Everything About the Unitary Almost Mathieu Operator
- Trojan Quantum Walks
- Highly noise resistant multipartite quantum correlations
- Discrete time quantum walk with nitrogen-vacancy centers in diamond coupled to a superconducting flux qubit
- Maximal coin-position entanglement generation in a quantum walk for the third step and beyond regardless of the initial state
- Entanglement and interaction in a topological quantum walk
- Simulation of the multiphase configuration and phase transitions with quantum walks utilizing a step-dependent coin
- Toward simulation of topological phenomenas with one-, two- and three-dimensional quantum walks
- Multi-qubit quantum computing using discrete-time quantum walks on closed graphs
- One-Dimensional Quantum Walks with a Position-Dependent Coin
- General condition of quantum teleportation by one-dimensional quantum walks
- Driven Discrete Time Quantum Walks
- Quantum walks with quantum chaotic coins: Of the Loschmidt echo, classical limit and thermalization
- Higher-dimensional Hong-Ou-Mandel effect and state redistribution with linear-optical multiports
- Percolation assisted excitation transport in discrete-time quantum walks
- The Lackadaisical Quantum Walker is NOT Lazy at all
- Quantum ratchet in disordered quantum walk
- Out-of-time-ordered correlators and quantum walks
- Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
- Optimizing the spatial spread of a quantum walk
- Alternation in Quantum Programming: From Superposition of Data to Superposition of Programs
- The quantum walk search algorithm: Factors affecting efficiency
- Probability distributions for Markov chains based quantum walks
- Exactly solvable interacting two-particle quantum graphs
- Rogue waves in discrete-time quantum walks
- Discrete dynamics and non-Markovianity
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Controlled quantum search on structured databases
- Quantum walk, entanglement and thermodynamic laws
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Average position in quantum walks with a U(2) coin
- Green function approach for scattering quantum walks
- How to Compute Using Quantum Walks
- Spontaneous Emission in Quantum Walks of a Kicked Bose-Einstein Condensate
- Continuous-Time Quantum Walks on Directed Bipartite Graphs
- Disorder-induced two-body localised state in interacting quantum walks
- Quantum Simulation of a Quantum Stochastic Walk
- Interacting quantum walk on a graph
- Nonlinear flip-flop quantum walks through potential barriers
- Symmetry Protected Topological Phases and Majorana Mode in One-dimensional Quantum Walk with Boundary
- Ramsauer effect in one-dimensional quantum walk with multiple defects
- Quantum State Discrimination on Reconfigurable Noise-Robust Quantum Networks
- Driven Gaussian quantum walks
- Flux induced re-entrant dynamics in the quantum walk of interacting bosons
- Dirac formulation for universal quantum gates and Shor's integer factorization in high-frequency electric circuits
- Quantum walk on a graph of spins: magnetism and entanglement
- Chirality from quantum walks without quantum coin
- Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
- Grover Walks on a Line with Absorbing Boundaries
- Coin dimensionality as a resource in quantum metrology involving discrete-time quantum walks
- Parrondo's paradox in quantum walks with inhomogeneous coins
- Causality, localization, and universality of monitored quantum walks with long-range hopping
- Exact mobility edges for almost-periodic CMV matrices via gauge symmetries
- Controllable simulation of topological phases and edge states with quantum walk
- Role of symmetry in quantum search via continuous-time quantum walk
- On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
- Adjustable self-loop on discrete-time quantum walk and its application in spatial search
- Discrete-time quantum walk dispersion control through long-range correlations
- Multiparameter estimation of continuous-time Quantum Walk Hamiltonians through Machine Learning
- Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
- Single-qubit unitary gates by graph scattering
- Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
- Multiparticle quantum walk with a gas-like interaction
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
- A quantum walk control plane for distributed quantum computing in quantum networks
- Implementing arbitrary quantum operations via quantum walks on a cycle graph
- Quantum random walk in periodic potential on a line
- Quantum Path Computing: Computing Architecture with Propagation Paths in Multiple Plane Diffraction of Classical Sources of Fermion and Boson Particles
- Quantum walk on a toral phase space
- Quantum Corralling
- Localization in Quantum Walks with a Single Lattice Defect: A Comparative Study
- History Dependent Quantum Walk on the Cycle with an Unbalanced Coin
- One-dimensional quantum walks driven by two-entangled-qubit coins
- Quantum walk on a chimera graph
- Where to quantum walk
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description
- Nonlinear three-state quantum walks
- Experimental realization of universal quantum gates and six-qubit entangled state using photonic quantum walk
- Dual Symmetry Classification of Non-Hermitian Systems and Point-Gap Topology of a Non-Unitary Quantum Walk
- Entanglement entropy distinguishes PT-symmetry and topological phases in a class of non-unitary quantum walks
- High-fidelity state transfer via quantum walks from delocalized states
- Search by Lackadaisical Quantum Walk with Symmetry Breaking
- On the equivalence between quantum and random walks on finite graphs
- Non-markovianity and bound states in quantum walks with a phase impurity
- On the physical realizability of quantum stochastic walks
- Suitable bases for quantum walks with Wigner coins
- A massless interacting Fermionic Cellular Automaton exhibiting bound states
- Hitting statistics from quantum jumps
- Revivals in One-dimensional Quantum Walks with a Time and Spin-dependent Phase Shift
- Universal dynamical scaling laws in three-state quantum walks
- Quantum walks and entanglement in cavity networks
- Interference Phenomena in Quantum Information
- Symmetries of the Dirac quantum walk and emergence of the de Sitter group
- Quantum walk-based protocol for secure communication between any two directly connected nodes on a network
- Scattering Expansion for Localization in One Dimension: from Disordered Wires to Quantum Walks
- Quantum Simulation of a Discrete-Time Quantum Stochastic Walk
- Spin-1 Quantum Walks
- Temperature of the three-state quantum walk
- Quantum Walks on Embeddings
- Optical realization of one-dimensional generalized split-step quantum walks
- Quantum Walk on Orbit Spaces
- History states of one-dimensional quantum walks
- Programmable non-Hermitian photonic quantum walks via dichroic metasurfaces
- Entangled state generation via quantum walks with multiple coins
- Deterministic generation of hybrid entangled states using quantum walks
- Quantum Walks in Weak Stochastic Gauge Fields
- Spontaneous-emission induced ratchet in atom-optics kicked rotor quantum walks
- Quantum Software Ecosystem Design
- Spectral Magnetization Ratchets with Discrete Time Quantum Walks
- Dynamics and computation in linear open quantum walks
- Scattering Expansion for Localization in One Dimension
- Localization and Fractality in Inhomogeneous Quantum Walks with Self-Duality
- Polarization-path-frequency entanglement using interferometry and frequency shifters
- Theoretical analysis of quantum random walks with stress-engineered optics
- Coherent transport over an explosive percolation lattice
- Quantum Simulation of Neutrino Oscillation and Dirac Particle Dynamics in Curved Space-time
- Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
- Quantum walk for SU(1,1)
- The Open Quantum Brownian Motion and continual measurements
- Mimicking the Hadamard discrete-time quantum walk with a time-independent Hamiltonian
- On the nonlinearity of quantum dynamical entropy
- Topological quantum walks in cavity-based quantum networks
- Directional quantum random walk induced by coherence
- Persistence of unvisited sites in quantum walks on a line
- The role of coherence on two-particle quantum walks
- Simulating Non Commutative Geometry with Quantum Walks
- Source Independent Quantum Walk Random Number Generation
- The Witten index for one-dimensional split-step quantum walks under the non-Fredholm condition
- Localization in quantum walks with periodically arranged coin matrices
- Simulating the discrete-time quantum walk dynamics with simultaneous coin and shift operators
- Complementarity in quantum walks
- Optimizing topology for quantum probing with discrete-time quantum walks
- Two-dimensional quantum central limit theorem by quantum walks
- Clustering-induced localization of quantum walks on networks
- Exciton propagation via quantum walks based on non-Hermitian coin flip operations
- Quantum walk with coherent multiple translations induces fast quantum gate operations
- Quantum Magic in Discrete-Time Quantum Walk
- Resource-efficient universal photonic processor based on time-multiplexed hybrid architectures
- Dissipative realization of a quantum distance-based classifier using open quantum walks
- Quantum walk on a square lattice with identical particles
- Implementation of hitting times of discrete time quantum random walks on Cubelike graphs
- Theoretical Studies on Quantum Walks with a Time-varying Coin
- Path integral approach to one-dimensional discrete-time quantum walk
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- The expressive power of quantum walks in terms of language acceptance
- Formal languages analysed by quantum walks
- Spectral quantization of discrete random walks on half-line, and orthogonal polynomials on the unit circle
- Generalized quantum teleportation of shared quantum secret with quantum walks
- Quantum walk on a ladder
- Generation of topologically useful entangled states
- Controlling quantum chaos via Parrondo strategies on noisy intermediate-scale quantum hardware
- Neighborhood-History Quantum Walk
- Partition of graphs and quantum walk based search algorithms
- Next-generation interferometry with gauge-invariant linear optical scatterers
- Continuous-time quantum walks on a defective lattice: Boosting the spreading of delocalized states through Parrondo's strategy
- Absorption-based qubit estimation in discrete-time quantum walks
- Quantum walks under superposition of causal order
- Light-shift induced behaviors observed in momentum-space quantum walks
- Shannon Entropy and Diffusion Coeffcient in Parity-Time Symmetric Quantum Walks
- Asymptotic reduced density matrix of discrete-time quantum walks