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)- Transport and localization in quantum walks on a random hierarchy of barriers
- Quantum algorithms for algebraic problems
- Action principles for quantum automata and Lorentz invariance of discrete time quantum walks
- Path-sum solution of the Weyl quantum walk in 3+1 dimensions
- Quantum impossible differential attacks: applications to AES and SKINNY
- On subset-resilient hash function families
- Multiparty quantum communication complexity of triangle finding
- scientific article; zbMATH DE number 7559397 (Why is no real title available?)
- Quantum adversary lower bound for element distinctness with small range
- Quantum walks can find a marked element on any graph
- Quantum sieving for code-based cryptanalysis and its limitations for ISD
- The staggered quantum walk model
- Arbitrated quantum signature scheme with quantum walk-based teleportation
- 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
- Low-gate quantum golden collision finding
- Algorithmic Polynomials
- Quantum walks
- Element distinctness revisited
- Quantum meet-in-the-middle attack on Feistel construction
- Search algorithm on strongly regular graph by lackadaisical quantum walk
- On the relationship between continuous- and discrete-time quantum walk
- Quantum algorithm design: techniques and applications
- Circulant graphs with valency up to 4 that admit perfect state transfer in Grover walks
- Quantum walks on two kinds of two-dimensional models
- Reducing the number of qubits in solving LWE
- Classical and quantum algorithms for variants of subset-sum via dynamic programming
- Quantum walk and its application domains: a systematic review
- Two quantum coins sharing a walker
- Quantum key search for ternary LWE
- Derandomization of quantum algorithm for triangle finding
- Quantum walks as thermalisations, with application to fullerene graphs
- Anderson localization for the unitary almost Mathieu operator
- General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk
- Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
- Quantum time/memory/data tradeoff attacks
- Quantum algorithm for lexicographically minimal string rotation
- The role of tessellation intersection in staggered quantum walks
- Lattice Sieving via Quantum Random Walks
- Constructing quantum hash functions based on quantum walks on Johnson graphs
- Quantum walk, entanglement and thermodynamic laws
- Quantum abstract detecting systems
- Quantum search of matching on signed graphs
- QW-search/zeta correspondence
- Spectral approximation for ergodic CMV operators with an application to quantum walks
- Quantum query complexity of constant-sized subgraph containment
- Discrete-time quantum walks: continuous limit and symmetries
- Quantum reversible circuit of AES-128
- The power of asymmetry in constant-depth circuits
- scientific article; zbMATH DE number 7716601 (Why is no real title available?)
- scientific article; zbMATH DE number 7559066 (Why is no real title available?)
- Quantum walks with memory on cycles
- Practical Implementation of a Quantum Backtracking Algorithm
- Three-state quantum walk on the Cayley graph of the dihedral group
- Szegedy quantum walks with memory on regular graphs
- Perfect state transfer on bi-Cayley graphs over abelian groups
- Quantum walks advantage on the dihedral group for uniform sampling problem
- On the fine-grained query complexity of symmetric functions
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Minimal quantum walk simulation of Dirac fermions in curved space-times
- Quantum key-length extension
- Models of quantum computation and quantum programming languages
- Periodicity of Grover walks on generalized Bethe trees
- Hash function based on quantum walks
- Quantum security of Trojan message attacks on Merkle-Damgård hash construction
- Quantum rectangle attack and its application on Deoxys-BC
- Quantum walks on simplicial complexes
- Quantum claw-finding attacks on 5-round Feistel structure and generalized Feistel schemes
- Quantum attacks against iterated block ciphers
- Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2
- Improved classical and quantum algorithms for subset-sum
- Quantum time-space tradeoff for finding multiple collision pairs
- Szegedy's quantum walk with queries
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- Quantum attacks on hash constructions with low quantum random access memory
- Quantum circuits for discrete-time quantum walks with position-dependent coin operator
- Multidimensional quantum walks, with application to k-distinctness
- On the equivalence between quantum and random walks on finite graphs
- Optimal merging in quantum k-xor and k-sum algorithms
- Quantum Walks with Multiple or Moving Marked Locations
- Path-integral solution of the one-dimensional Dirac quantum cellular automaton
- Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
- Strong dispersion property for the quantum walk on the hypercube
- Coined quantum walks lift the cospectrality of graphs and trees
- Theoretical computer science: computational complexity
- Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
- The Quantum Complexity of Markov Chain Monte Carlo
- Perfect state transfer using Markovian quantum walk
- Subset Sum Quantumly in 1.17 n .
- Finding many collisions via reusable quantum walks. Application to lattice sieving
- Tight quantum bounds for computational geometry problems
- Quantum security of the Legendre PRF
- Discrete-time semiclassical Szegedy quantum walks
- Improved quantum algorithms for the k-XOR problem
- Quantum boomerang attacks and some applications
- New results on quantum boomerang attacks
- One-dimensional lackadaisical quantum walks
- Evaluation of exact quantum query complexities by semidefinite programming
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)
