Quantum Walk Algorithm for Element Distinctness
From MaRDI portal
Publication:5454249
DOI10.1137/S0097539705447311zbMath1134.81010arXivquant-ph/0311001OpenAlexW2058286540WikidataQ56386238 ScholiaQ56386238MaRDI QIDQ5454249
Publication date: 28 March 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0311001
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Theory of computing (68Q99)
Related Items
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 ⋮ New results on quantum boomerang attacks ⋮ Quantum meet-in-the-middle attack on Feistel construction ⋮ Deterministic quantum search with adjustable parameters: implementations and applications ⋮ Lattice Sieving via Quantum Random Walks ⋮ Almost everything about the unitary almost Mathieu operator ⋮ Quantum circuit implementation and resource analysis of LBlock and LiCi ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ Quantum walk mixing is faster than classical on periodic lattices ⋮ MPMCT gate decomposition method reducing T-depth quickly in proportion to the number of work qubits ⋮ Optimizing the walk coin in the quantum random walk search algorithm ⋮ Improvement of quantum walks search algorithm in single-marked vertex graph ⋮ Quantity study on a novel quantum neural network with alternately controlled gates for binary image classification ⋮ Unitary coined discrete-time quantum walks on directed multigraphs ⋮ A high-fidelity quantum state transfer algorithm on the complete bipartite graph ⋮ Quantum circuits for discrete-time quantum walks with position-dependent coin operator ⋮ Quantum impossible differential attacks: applications to AES and SKINNY ⋮ Quantum time/memory/data tradeoff attacks ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ The role of tessellation intersection in staggered quantum walks ⋮ Discrete-time semiclassical Szegedy quantum walks ⋮ The Witten index for one-dimensional split-step quantum walks under the non-Fredholm condition ⋮ Near-optimal quantum algorithms for string problems ⋮ Lackadaisical discrete-time quantum walk on Johnson graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Directional correlations in quantum walks with two particles ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Algorithmic Polynomials ⋮ An Introduction to Quantum Computing, without the Physics ⋮ Symmetries of the Dirac quantum walk and emergence of the de Sitter group ⋮ Quantum walks ⋮ One-dimensional quantum walks with a position-dependent coin ⋮ On the robustness of bucket brigade quantum RAM ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Periodicity of the Discrete-time Quantum Walk on a Finite Graph ⋮ Subset Sum Quantumly in 1.17 n . ⋮ ASYMPTOTIC ENTANGLEMENT IN 1D QUANTUM WALKS WITH A TIME-DEPENDENT COINED ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Walks with Multiple or Moving Marked Locations ⋮ Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations ⋮ Quantum state transfer on unsymmetrical graphs via discrete-time quantum walk ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum walks simulating non-commutative geometry in the Landau problem ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Strong dispersion property for the quantum walk on the hypercube ⋮ The staggered quantum walk model ⋮ Quantum walk, entanglement and thermodynamic laws ⋮ Landau levels for discrete-time quantum walks in artificial magnetic fields ⋮ Low-gate quantum golden collision finding ⋮ Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Quantum walks on simplicial complexes ⋮ Path-integral solution of the one-dimensional Dirac quantum cellular automaton ⋮ Quantum walks on two kinds of two-dimensional models ⋮ Randomizing quantum walk ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Grover walks on a line with absorbing boundaries ⋮ Quantum reversible circuit of AES-128 ⋮ Discrete-time quantum walks in random artificial gauge fields ⋮ Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ Spectral approximation for ergodic CMV operators with an application to quantum walks ⋮ Quantum walks and gravitational waves ⋮ Optimal parallel quantum query algorithms ⋮ Quantum walk and its application domains: a systematic review ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ The excitonic qubit coupled with a phonon bath on a star graph: anomalous decoherence and coherence revivals ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Action principles for quantum automata and Lorentz invariance of discrete time quantum walks ⋮ Szegedy quantum walks with memory on regular graphs ⋮ Weyl, Dirac and Maxwell quantum cellular automata ⋮ Quantum Walk Based Search Algorithms ⋮ Quantum walks with memory provided by parity of memory ⋮ Quantum abstract detecting systems ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ Quantum field as a quantum cellular automaton: the Dirac free evolution in one dimension ⋮ The Quantum Complexity of Markov Chain Monte Carlo ⋮ On the relationship between continuous- and discrete-time quantum walk ⋮ 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 ⋮ Time-bin quantum RAM ⋮ On the hitting times of quantum versus random walks ⋮ Quantum search of matching on signed graphs ⋮ One-dimensional lackadaisical quantum walks ⋮ Generalized teleportation by quantum walks ⋮ Probability distributions for Markov chain based quantum walks ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Quantum all-subkeys-recovery attacks on 6-round Feistel-\(2^\ast\) structure based on multi-equations quantum claw finding ⋮ Quantum key-length extension ⋮ Adjacent Vertices Can Be Hard to Find by Quantum Walks ⋮ Tree search and quantum computation ⋮ Perfect state transfer on bi-Cayley graphs over abelian groups ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Quantum search with variable times ⋮ Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks ⋮ Quantum algorithm design: techniques and applications ⋮ Practical Implementation of a Quantum Backtracking Algorithm ⋮ On the power of non-adaptive learning graphs ⋮ Discrete-time quantum walk search on Johnson graphs ⋮ Fourier 1-norm and quantum speed-up ⋮ Massless Dirac equation from Fibonacci discrete-time quantum walk ⋮ Two quantum coins sharing a walker ⋮ Szegedy's quantum walk with queries ⋮ 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 ⋮ Models of quantum computation and quantum programming languages ⋮ Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk ⋮ Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations ⋮ Quantum algorithm for the multicollision problem ⋮ The QWalk simulator of quantum walks ⋮ Coined quantum walks lift the cospectrality of graphs and trees ⋮ Central limit theorems for open quantum random walks on the crystal lattices ⋮ Quantum walks in artificial electric and gravitational fields ⋮ Quantum walks with memory on cycles ⋮ Periodicity of Grover walks on generalized Bethe trees ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Quantum algorithms for algebraic problems ⋮ Квантовые атаки на итерационные блочные шифры ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions ⋮ Unnamed Item ⋮ TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS ⋮ Key establishment à la Merkle in a quantum world ⋮ Discrete-time quantum walks and graph structures ⋮ Claw finding algorithms using quantum walk ⋮ Hash function based on quantum walks ⋮ Quantum search on simplicial complexes ⋮ 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 ⋮ Perfect state transfer on distance-regular graphs and association schemes ⋮ Discrete-time quantum walks: Continuous limit and symmetries ⋮ On subset-resilient hash function families ⋮ Quantum key search for ternary LWE ⋮ Quantum walks can find a marked element on any graph ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms
