Search via Quantum Walk

DOI10.1137/090745854zbMath1223.05289arXivquant-ph/0608026OpenAlexW2006096862MaRDI QIDQ2999859

Miklos Santha, Jérémie Roland, Frédéric Magniez, Ashwin Nayak

Publication date: 17 May 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0608026

Mathematics Subject Classification ID

Quantum computation (81P68) Random walks on graphs (05C81) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (59)

The staggered quantum walk model ⋮ Efficient quantum circuits for Szegedy quantum walks ⋮ Low-gate quantum golden collision finding ⋮ Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model ⋮ Quantum algorithms for the \(k\)-XOR problem ⋮ Quantum Walks ⋮ Quantum machine learning: a classical perspective ⋮ Beyond quadratic speedups in quantum attacks on symmetric schemes ⋮ Optimal parallel quantum query algorithms ⋮ Quantum walk and its application domains: a systematic review ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Exceptional quantum walk search on the cycle ⋮ Lattice Sieving via Quantum Random Walks ⋮ Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture ⋮ Finding many collisions via reusable quantum walks. Application to lattice sieving ⋮ Improvement of quantum walks search algorithm in single-marked vertex graph ⋮ Efficient and scalable quantum walk algorithms via the quantum Fourier transform ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ Quantum circuits for discrete-time quantum walks with position-dependent coin operator ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ A systematic method to building Dirac quantum walks coupled to electromagnetic fields ⋮ Periodicity of lively quantum walks on cycles with generalized Grover coin ⋮ Near-optimal quantum algorithms for string problems ⋮ Efficient quantum circuits for continuous-time quantum walks on composite graphs ⋮ Probability distributions for Markov chain based quantum walks ⋮ Improved classical and quantum algorithms for subset-sum ⋮ On new PageRank computation methods using quantum computing ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Spectral transition for random quantum walks on trees ⋮ Evolutionary algorithms for quantum computers ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum mixing of Markov chains for special distributions ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ On the power of non-adaptive learning graphs ⋮ Connecting Coined Quantum Walks with Szegedy's Model ⋮ Massless Dirac equation from Fibonacci discrete-time quantum walk ⋮ Szegedy's quantum walk with queries ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk ⋮ Unnamed Item ⋮ Quantum walk with a general coin: exact solution and asymptotic properties ⋮ Unnamed Item ⋮ Spectral properties of quantum walks on rooted binary trees ⋮ Квантовые атаки на итерационные блочные шифры ⋮ Extended learning graphs for triangle finding ⋮ Quantum-enhanced deliberation of learning agents using trapped ions ⋮ Key establishment à la Merkle in a quantum world ⋮ Unnamed Item ⋮ Lower bounds on the localisation length of balanced random quantum walks ⋮ Quantum walks simulating non-commutative geometry in the Landau problem ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems ⋮ Directed graph encoding in quantum computing supporting edge-failures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum computation and quantum information ⋮ Quantum key search for ternary LWE ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms

This page was built for publication: Search via Quantum Walk