Efficient Quantum Walk on a Quantum Processor
arXiv:1510.08657 · doi:10.1038/ncomms11511
Abstract
The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise quantum walks have shown much potential as a frame- work for developing new quantum algorithms. In this paper, we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks which could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle we have experimentally implemented the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.
arXiv comment10 pages, 5 figures
References in corpus (33)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- Quantum fingerprinting
- On the Power of One Bit of Quantum Information
- Environment-Assisted Quantum Transport
- Spatial search by quantum walk
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Realization of a quantum walk with one and two trapped ions
- Quantum walk of a trapped ion in phase space
- Universal computation by multi-particle quantum walk
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- On the relationship between continuous- and discrete-time quantum walk
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Experimental Implementation of the Quantum Random-Walk Algorithm
- On the experimental verification of quantum complexity in linear optics
- Adding control to arbitrary unknown quantum operations
- Instantaneous Quantum Computation
- Stability of quantum motion and correlation decay
- Two-particle quantum walks applied to the graph isomorphism problem
- Optimizing type-I polarization-entangled photons
- Quantum Navigation and Ranking in Complex Networks
- Classical approach to the graph isomorphism problem using quantum walks
- Quantum walk on a line for a trapped ion
- Error tolerance of the BosonSampling model for linear optics quantum computing
- Quantum walk-based search and centrality
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Simulating Quantum Circuits with Sparse Output Distributions
- The complexity of approximating complex-valued Ising and Tutte partition functions
Cited by in corpus (55)
- Quantum information processing with superconducting circuits: a review
- Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
- Quantum Fourier Transform in Computational Basis
- Reconfigurable optical implementation of quantum complex networks
- Quantum walk-based portfolio optimisation
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Centrality measure based on continuous-time quantum walks and experimental realization
- A quantum walk assisted approximate algorithm for bounded NP optimisation problems
- Combinatorial optimisation via highly efficient quantum walks
- Quantum walks of two correlated photons in a 2D synthetic lattice
- Efficient quantum circuits for Szegedy quantum walks
- Experimental parity-time symmetry quantum walks on a directed graph
- Dynamical learning of a photonics quantum-state engineering process
- Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- Continuous-Time Quantum Walks on Dynamic Graphs
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Non-Markovian channel from the reduced dynamics of coin in quantum walk
- Link prediction with continuous-time classical and quantum walks
- Transport efficiency of continuous-time quantum walks on graphs
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- Deterministic spatial search using alternating quantum walks
- Efficient implementation of discrete-time quantum walks on quantum computers
- Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware
- Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
- Multi-qubit quantum computing using discrete-time quantum walks on closed graphs
- Quantum Financial Modeling on Noisy Intermediate-Scale Quantum Hardware: Random Walks using Approximate Quantum Counting
- Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
- Controlled quantum search on structured databases
- Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
- Estimating Gibbs partition function with quantumClifford sampling
- Multiparameter estimation of continuous-time Quantum Walk Hamiltonians through Machine Learning
- General Quantum Bernoulli Factory: Framework Analysis and Experiments
- Characterization, synthesis, and optimization of quantum circuits over multiple-control -rotation gates: A systematic study
- Overcomplete quantum tomography of a path-entangled two-photon state
- Implementation of Continuous-Time Quantum Walk on Sparse Graph
- Open system approach to Neutrino oscillations in a quantum walk framework
- High-fidelity state transfer via quantum walks from delocalized states
- Quantum walk processes in quantum devices
- On the physical realizability of quantum stochastic walks
- Experimental realization of universal quantum gates and six-qubit entangled state using photonic quantum walk
- History states of one-dimensional quantum walks
- Design for implementation of discrete-time quantum walk with circulant matrix on graph by optical polarizing elements
- Efficient quantum circuits for dense and non-unitary operators
- Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
- Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
- Interference-induced localization in quantum random walk on clean cyclic graph
- Photonic cellular automaton simulation of relativistic quantum fields: observation of Zitterbewegung
- Dimerized Decomposition of Quantum Evolution on an Arbitrary Graph
- Topological Sensing in the Dynamics of Quantum Walks with Defects
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Quantum walk on a square lattice with identical particles
- Implementation of Continuous-Time Quantum Walks on Quantum Computers
- Neighborhood-History Quantum Walk
- Spectral analysis of three-state quantum walks with general coin matrices
- Complexity for one-dimensional discrete time quantum walk circuits