Quantum Query Complexity of Some Graph Problems

DOI10.1137/050644719zbMath1101.81024arXivquant-ph/0401091OpenAlexW3100558667WikidataQ62039250 ScholiaQ62039250MaRDI QIDQ5470736

Mark Heiligman, Mehdi Mhalla, Peter Høyer, Christoph Dürr

Publication date: 1 June 2006

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

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

zbMATH Keywords

graph theoryconnectivitylower boundquantum algorithmminimum spanning treesingle source shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (20)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Solving Lyapunov equation by quantum algorithm ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ Unnamed Item ⋮ Evolutionary algorithms for quantum computers ⋮ Considering nearest neighbor constraints of quantum circuits at the reversible circuit level ⋮ Quantum algorithm design: techniques and applications ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Image classification based on quantum K-nearest-neighbor algorithm ⋮ Unnamed Item ⋮ Adversary lower bounds for nonadaptive quantum algorithms ⋮ Quantum approaches to graph colouring ⋮ Quantum algorithms for algebraic problems ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Quantum algorithm for shortest path search in directed acyclic graph ⋮ Claw finding algorithms using quantum walk ⋮ Quantum branch-and-bound algorithm and its application to the travelling salesman problem ⋮ Quantum algorithms for string processing

This page was built for publication: Quantum Query Complexity of Some Graph Problems