Discrete quantum walks hit exponentially faster
From MaRDI portal
Publication:2571012
It is well-known that a simple random walk on the \(n\)-bit hypercube \(\{0,1\}^ n\) needs an exponential expected time until it hits the corner opposite to its initial corner for the first time. The paper contrasts this to the discrete quantum walk on the hypercube, which needs only a polynomial time for this. This result may be seen as one of the first rigorous examples of a process that takes much shorter time on a quantum computer than on a classical computer. The notion of a discrete quantum walk is motivated and introduced, and two alternate definitions of the hitting time for such a walk are given. An application to sequential packet routing is provided as well.
Recommendations
Cites work
- A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
- A random polynomial-time algorithm for approximating the volume of convex bodies
- An example of the difference between quantum and classical random walks
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Discrete quantum walks hit exponentially faster
- Exponential algorithmic speedup by a quantum walk
- From quantum cellular automata to quantum lattice gases
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 2013818 (Why is no real title available?)
- scientific article; zbMATH DE number 2019633 (Why is no real title available?)
- scientific article; zbMATH DE number 2086385 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Normal subgroup reconstruction and quantum computation using group representations
- On the Power of Quantum Computation
- One-dimensional quantum walks
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
- Quantum simulations of classical random walks and undirected graph connectivity
- Quantum walks on graphs
- Strengths and Weaknesses of Quantum Computing
Cited in
(38)- Simulation methods for quantum walks on graphs applied to formal language recognition
- Quantum algorithm design: techniques and applications
- Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
- Construction of distinct discrete time scattering quantum walk formulations on the honeycomb lattice
- Hitting time of quantum walks with perturbation
- Discrete-time quantum walk on the Cayley graph of the dihedral group
- Mean hitting times of quantum Markov chains in terms of generalized inverses
- Discrete-time quantum walks and graph structures
- Quantum random walk polynomial and quantum random walk measure
- Quantum walks can find a marked element on any graph
- Quantum walk and its application domains: a systematic review
- Disordered quantum walks in one lattice dimension
- Absorption probabilities of discrete quantum mechanical systems
- Exponential algorithmic speedup by a quantum walk
- scientific article; zbMATH DE number 2013818 (Why is no real title available?)
- Möbius quantum walk
- Gate-based circuit designs for quantum adder-inspired quantum random walks on superconducting qubits
- Quantum Walks
- QUANTUM TIMING AND SYNCHRONIZATION PROBLEMS
- Decoherence in quantum walks – a review
- Quantum transport in d-dimensional lattices
- Implementation of quantum hitting times of cubelike graphs on IBM's qiskit platform
- Strong dispersion property for the quantum walk on the hypercube
- The uniform measure for quantum walk on hypercube: A quantum Bernoulli noises approach
- Discrete quantum walks hit exponentially faster
- A new definition of hitting time and an embedded Markov chain in continuous-time quantum walks
- Ranking nodes in directed networks via continuous-time quantum walks
- A hybrid classical-quantum clustering algorithm based on quantum walks
- The hitting time of quantum walk on 2D lattice
- High-dimensional graphs convolution for quantum walks photonic applications
- Quantum simulation of perfect state transfer on weighted cubelike graphs
- Experimental observations of 1D quantum walks in a limited region
- Optimal detection of quantum states via projective measurements
- Exponential speedups for quantum walks in random hierarchical graphs
- Introduction to Quantum Algorithms
- Spectral property of magnetic quantum walk on hypercube
- The first passage time in quantum dynamics
- Quantum walk on a line with absorbing boundaries
This page was built for publication: Discrete quantum walks hit exponentially faster
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2571012)
