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)- Quantum approaches to graph colouring
- Graph matching using the interference of continuous-time quantum walks
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Quantum algorithm design: techniques and applications
- Qswalk: a \textit {Mathematica} package for quantum stochastic walks on arbitrary graphs
- Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle
- Quantum walks: a comprehensive review
- Time averaged distribution of a discrete-time quantum walk on the path
- Spatial search using the discrete time quantum walk
- Quantum entanglement as a new information processing resource
- Intricacies of quantum computational paths
- Image classification based on quantum K-nearest-neighbor algorithm
- Quantum key distribution with quantum walks
- Universal state transfer on graphs
- Reducing the number of ancilla qubits and the gate count required for creating large controlled operations
- Perfect state transfer on weighted abelian Cayley graphs
- Laplacian fractional revival on graphs
- Hitting times of quantum and classical random walks in potential spaces
- 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
- Spatial search on Johnson graphs by continuous-time quantum walk
- Fast quantum search of multiple vertices based on electric circuits
- An encryption protocol for NEQR images based on one-particle quantum walks on a circle
- On state transfer in Cayley graphs for abelian groups
- An improved algorithm for computing hitting probabilities of quantum walks
- Laplacian pretty good fractional revival
- Randomizing quantum walk
- Singular continuous Cantor spectrum for magnetic quantum walks
- Periodicity of lively quantum walks on cycles with generalized Grover coin
- Quantum stochastic walk models for quantum state discrimination
- Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory
- One-dimensional quantum walks with a time and spin-dependent phase shift
- Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
- Anderson localization for electric quantum walks and skew-shift CMV matrices
- Central limit theorems for open quantum random walks on the crystal lattices
- Pretty good state transfer on Cayley graphs over dihedral groups
- Verification of quantum computation: an overview of existing approaches
- Quantum fractional revival on graphs
- Perfect state transfer on distance-regular graphs and association schemes
- Quantum algorithms for learning symmetric juntas via the adversary bound
- One-dimensional continuous-time quantum walks
- Progress in quantum algorithms
- Uniform mixing and association schemes
- Strong edge geodetic problem in networks
- Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target
- Optimal computation with non-unitary quantum walks
- Quantum computation and quantum information
- Discrete quantum walks hit exponentially faster
- Quantum state transfer in coronas
- Quantum walk on the line through potential barriers
- Quantum walk and its application domains: a systematic review
- Perfect edge state transfer on abelian Cayley graphs
- Pair state transfer
- Experimental pairwise entanglement estimation for an \(N\)-qubit system. A machine learning approach for programming quantum hardware
- A dynamic programming approach for distributing quantum circuits by bipartite graphs
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- Perfect edge state transfer on cubelike graphs
- Long time dynamics of a single-particle extended quantum walk on a one-dimensional lattice with complex hoppings: a generalized hydrodynamic description
- Quantum walks on Sierpinski gasket and Sierpinski tetrahedron
- Perfect state transfer on bi-Cayley graphs over abelian groups
- Quantum walk public-key cryptographic system
- Levinson's theorem for graphs. II
- Duality quantum computer and the efficient quantum simulations
- History dependent quantum random walks as quantum lattice gas automata
- One-dimensional three-state quantum walks: Weak limits and localization
- Perfect state transfer in Laplacian quantum walk
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Path-integral solution of the one-dimensional Dirac quantum cellular automaton
- \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers
- Quantum lattice algorithms: similarities and connections to some classic finite difference algorithms
- Searching for antipodal vertices in a symmetric Cayley graph of the group of the Boolean cube
- Practical Implementation of a Quantum Backtracking Algorithm
- Grover walks on a line with absorbing boundaries
- Localization of two-particle quantum walk on glued-tree and its application in generating Bell states
- Laplacian versus adjacency matrix in quantum walk search
- Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions
- Entropy generation in a model of reversible computation
- Path-sum solution of the Weyl quantum walk in 3+1 dimensions
- Forrelation: a problem that optimally separates quantum from classical computing
- Dephasing assisted transport on a biomimetic ring structure
- Coherence evolution in two-dimensional quantum walk on lattice
- One-dimensional lackadaisical quantum walks
- Probability distributions for Markov chain based quantum walks
- Limiting properties of stochastic quantum walks on directed graphs
- Quantum-walk speedup of backtracking algorithms
- Two-dimensional quantum walk with position-dependent phase defects
- scientific article; zbMATH DE number 7453153 (Why is no real title available?)
- Projection theorem for discrete-time quantum walks
- Characterization of anomalous diffusion in one-dimensional quantum walks
- An introduction to quantum computing, without the physics
- Symmetries of the Dirac quantum walk and emergence of the De Sitter group
- One-dimensional quantum walks with a position-dependent coin
- On the robustness of bucket brigade quantum RAM
- Green's function approach for quantum graphs: an overview
- Quantum speedups for exponential-time dynamic programming algorithms
- Quantum Walks
- Product formulas for exponentials of commutators
- Quantum Random Walks – New Method for Designing Quantum Algorithms
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)
