Quantum Walk Algorithm for Element Distinctness
From MaRDI portal
Abstract: We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman et.al. (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm.
Recommendations
Cited in
(only showing first 100 items - show all)- Claw finding algorithms using quantum walk
- Quantum walk, entanglement and thermodynamic laws
- Landau levels for discrete-time quantum walks in artificial magnetic fields
- Quantum reversible circuit of AES-128
- Spectral approximation for ergodic CMV operators with an application to quantum walks
- Quantum walks and gravitational waves
- A note on the search for k elements via quantum walk
- The excitonic qubit coupled with a phonon bath on a star graph: anomalous decoherence and coherence revivals
- Quantum field as a quantum cellular automaton: the Dirac free evolution in one dimension
- Generalized teleportation by quantum walks
- Quantum algorithm design: techniques and applications
- Two quantum coins sharing a walker
- Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
- Quantum walks in artificial electric and gravitational fields
- Quantum walks with memory on cycles
- Quantum search with variable times
- Constructing quantum hash functions based on quantum walks on Johnson graphs
- Element distinctness revisited
- Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
- Quantum algorithm for the multicollision problem
- The variational quantum eigensolver: a review of methods and best practices
- Arbitrated quantum signature scheme with quantum walk-based teleportation
- Evaluation of exact quantum query complexities by semidefinite programming
- A quantum searching model finding one of the edges of a subgraph in a complete graph
- The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
- Quantum multi-secret sharing via trap codes and discrete quantum walks
- A new kind of universal and flexible quantum information splitting scheme with multi-coin quantum walks
- On subset-resilient hash function families
- Quantum key search for ternary LWE
- Optimal merging in quantum k-xor and k-sum algorithms
- Randomizing quantum walk
- Quantum walks with memory provided by parity of memory
- Models of quantum computation and quantum programming languages
- Coined quantum walks lift the cospectrality of graphs and trees
- Central limit theorems for open quantum random walks on the crystal lattices
- Key establishment à la Merkle in a quantum world
- Discrete-time quantum walks and graph structures
- Hash function based on quantum walks
- Quantum search on simplicial complexes
- Perfect state transfer on distance-regular graphs and association schemes
- Action principles for quantum automata and Lorentz invariance of discrete time quantum walks
- On the hitting times of quantum versus random walks
- Quantum walks can find a marked element on any graph
- Quantum walks on two kinds of two-dimensional models
- The staggered quantum walk model
- Quantum walk and its application domains: a systematic review
- Szegedy quantum walks with memory on regular graphs
- Quantum abstract detecting systems
- A systematic method to building Dirac quantum walks coupled to electromagnetic fields
- Implementation of quantum walks on IBM quantum computers
- On the equivalence between quantum and random walks on finite graphs
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk
- Three-state quantum walk on the Cayley graph of the dihedral group
- Quantum search of matching on signed graphs
- Improved classical and quantum algorithms for subset-sum
- Quantum all-subkeys-recovery attacks on 6-round Feistel-2^ structure based on multi-equations quantum claw finding
- Quantum key-length extension
- Perfect state transfer on bi-Cayley graphs over abelian groups
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- Superlinear advantage for exact quantum algorithms
- Discrete-time quantum walks: continuous limit and symmetries
- Quantum query complexity of constant-sized subgraph containment
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Quantum complexity of Boolean matrix multiplication and related problems
- Quantum walks on simplicial complexes
- Time-bin quantum RAM
- Adjacent vertices can be hard to find by quantum walks
- Path-integral solution of the one-dimensional Dirac quantum cellular automaton
- Quantum algorithms for algebraic problems
- Quantum property testing for bounded-degree graphs
- Quantum adversary lower bound for element distinctness with small range
- Practical Implementation of a Quantum Backtracking Algorithm
- Grover walks on a line with absorbing boundaries
- Quantum attacks against iterated block ciphers
- Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions
- Tight quantum bounds for computational geometry problems
- Discrete-time quantum walks in random artificial gauge fields
- Quantum Walk Based Search Algorithms
- The Quantum Complexity of Markov Chain Monte Carlo
- How significant are the known collision and element distinctness quantum algorithms?
- Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks
- Path-sum solution of the Weyl quantum walk in 3+1 dimensions
- The power of asymmetry in constant-depth circuits
- One-dimensional lackadaisical quantum walks
- Probability distributions for Markov chain based quantum walks
- Quantum-walk speedup of backtracking algorithms
- Quantum query algorithms are completely bounded forms
- Multiparty quantum communication complexity of triangle finding
- On the power of non-adaptive learning graphs
- Asymptotic entanglement in 1D quantum walks with a time-dependent coined
- Massless Dirac equation from Fibonacci discrete-time quantum walk
- Quantum query algorithms are completely bounded forms
- Quantum walks simulating non-commutative geometry in the Landau problem
- Growing random graphs with quantum rules
- Spatial search on Johnson graphs by discrete-time quantum walk
- The Walker speaks its graph: global and nearly-local probing of the tunnelling amplitude in continuous-time quantum walks
- Transport and localization in quantum walks on a random hierarchy of barriers
- Approximate Degree in Classical and Quantum Computing
- Gate-based circuit designs for quantum adder-inspired quantum random walks on superconducting qubits
This page was built for publication: Quantum Walk Algorithm for Element Distinctness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454249)
