Quantum query complexity of some graph problems

DOI10.1007/978-3-540-27836-8_42MaRDI QIDQ5466487zbMATH OpenOpenAlexFDO

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

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• Quantum Query Complexity of Some Graph Problems
• SOFSEM 2004: Theory and Practice of Computer Science
• Quantum query complexity of minor-closed graph properties
• Quantum query complexity of minor-closed graph properties
• Span programs and quantum algorithms for st-connectivity and claw detection

Cited in

(32)

• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Quantum speed-up for unsupervised learning
• Graph comparison via nonlinear quantum search
• Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation
• The Exponential Time complexity of counting (quantum) graph homomorphisms
• Quantum algorithm for shortest path search in directed acyclic graph
• Approximate span programs
• Span programs and quantum algorithms for st-connectivity and claw detection
• Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
• Quantum algorithms for the triangle problem
• New bounds on the classical and quantum communication complexity of some graph properties
• On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
• Quantum query complexity of minor-closed graph properties
• A survey on tree matching and XML retrieval
• Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
• Quantum query complexity of minor-closed graph properties
• Quantum algorithms for connectivity and related problems
• Applications of the quantum algorithm for st-connectivity
• Algorithms and Computation
• Quantum Query Complexity of Some Graph Problems
• On the power of Ambainis lower bounds
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• SOFSEM 2004: Theory and Practice of Computer Science
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Query complexity of global minimum cut
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs
• Quantum complexity for vector domination problem
• A direct reduction from the polynomial to the adversary method
• Quantum algorithms for matching problems
• Improved algorithms for quantum identification of Boolean oracles
• The quantum query complexity of the determinant

This page was built for publication: Quantum query complexity of some graph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5466487)