Exponential algorithmic speedup by a quantum walk
From MaRDI portal
Abstract: We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time.
Recommendations
Cited in
(only showing first 100 items - show all)- One-dimensional quantum walks with a position-dependent coin
- One-dimensional three-state quantum walks: Weak limits and localization
- Quantum fractional revival on graphs
- Quantum speedups for exponential-time dynamic programming algorithms
- Tree search and quantum computation
- An introduction to quantum computing, without the physics
- Perfect edge state transfer on abelian Cayley graphs
- Central limit theorems for open quantum random walks on the crystal lattices
- Time averaged distribution of a discrete-time quantum walk on the path
- scientific article; zbMATH DE number 7453153 (Why is no real title available?)
- Strong edge geodetic problem in networks
- Optimal computation with non-unitary quantum walks
- Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
- Unbounded quantum-classical separation in sample complexity for sphere center finding
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Quantum stochastic walk models for quantum state discrimination
- Quantum computing algorithm for electromagnetic field simulation
- Randomizing quantum walk
- Scaling in the dynamics of directed lackadaisical quantum walks
- Characterization of anomalous diffusion in one-dimensional quantum walks
- An efficient quantum algorithm for spectral estimation
- Quantum algorithm for testing graph completeness
- Topological classification of time-asymmetry in unitary quantum processes
- Combining quantum and classical control: syntax, semantics and adequacy
- Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory
- Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions
- Symmetries, graph properties, and quantum speedups
- Intricacies of quantum computational paths
- Universal resources for quantum computing
- Multidimensional quantum walks
- Quantum depth in the random oracle model
- Progress in quantum algorithms
- Experimental pairwise entanglement estimation for an \(N\)-qubit system. A machine learning approach for programming quantum hardware
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- Long time dynamics of a single-particle extended quantum walk on a one-dimensional lattice with complex hoppings: a generalized hydrodynamic description
- Searching for antipodal vertices in a symmetric Cayley graph of the group of the Boolean cube
- Quantum walks on Sierpinski gasket and Sierpinski tetrahedron
- Quantum lattice algorithms: similarities and connections to some classic finite difference algorithms
- Ranking nodes in directed networks via continuous-time quantum walks
- Unitary coined discrete-time quantum walks on directed multigraphs
- Perfect edge state transfer on cubelike graphs
- Symmetries of the Dirac quantum walk and emergence of the De Sitter group
- Entropy generation in a model of reversible computation
- A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
- Experimental observations of 1D quantum walks in a limited region
- Hitting times of quantum and classical random walks in potential spaces
- Projection theorem for discrete-time quantum walks
- Green's function approach for quantum graphs: an overview
- Probability distributions for Markov chain based quantum walks
- Quantum-walk speedup of backtracking algorithms
- On the robustness of bucket brigade quantum RAM
- Exponential speedups for quantum walks in random hierarchical graphs
- High-dimensional graphs convolution for quantum walks photonic applications
- Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle
- Quantum computation and quantum information
- QWAK: quantum walk analysis kit
- Path-sum solution of the Weyl quantum walk in 3+1 dimensions
- Pretty good state transfer on Cayley graphs over dihedral groups
- Quantum algorithms for stochastic differential equations: a Schrödingerisation approach
- Levinson's theorem for graphs. II
- Controlled transport in chiral quantum walks on graphs
- Quantum walk on the line through potential barriers
- Zero transfer in continuous-time quantum walks
- Faster search of clustered marked states with lackadaisical quantum walks
- The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
- Simplifying continuous-time quantum walks on dynamic graphs
- An encryption protocol for NEQR images based on one-particle quantum walks on a circle
- Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target
- Quantum key distribution with quantum walks
- Graph matching using the interference of continuous-time quantum walks
- Complex quantum networks: a topical review
- On the relationship between continuous- and discrete-time quantum walk
- Quantum algorithm design: techniques and applications
- Quantum state transfer in coronas
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum Walks
- The spectrum of asymptotic Cayley trees
- Fast quantum search of multiple vertices based on electric circuits
- On state transfer in Cayley graphs for abelian groups
- Quantum variations of cyclotomic cosets for cyclic stabiliser codes construction
- On the need for large quantum depth
- Image classification based on quantum K-nearest-neighbor algorithm
- Quantum walk and its application domains: a systematic review
- Product formulas for exponentials of commutators
- Open system approach to neutrino oscillations in a quantum walk framework
- A novel image segmentation algorithm based on continuous-time quantum walk using superpixels
- Qswalk: a \textit {Mathematica} package for quantum stochastic walks on arbitrary graphs
- Efficient quantum algorithms for simulating sparse Hamiltonians
- An improved algorithm for computing hitting probabilities of quantum walks
- Limiting properties of stochastic quantum walks on directed graphs
- Perfect state transfer, equitable partition and continuous-time quantum walk based search
- Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory
- Exponential speedup of quantum algorithms for the pathfinding problem
- Uniform mixing and association schemes
- A polynomial quantum algorithm for approximating the Jones polynomial
- Quantum entanglement as a new information processing resource
- One-dimensional quantum walks with a time and spin-dependent phase shift
- Spatial search on Johnson graphs by continuous-time quantum walk
- Complexity classes of equivalence problems revisited
- Verification of quantum computation: an overview of existing approaches
This page was built for publication: Exponential algorithmic speedup by a quantum walk
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581288)
