Quantum Query Complexity of Some Graph Problems
From MaRDI portal
Abstract: Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the bounded error quantum query complexity of Connectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source Shortest Paths. For example we show that the query complexity of Minimum Spanning Tree is in Theta(n^{3/2}) in the matrix model and in Theta(sqrt{nm}) in the array model, while the complexity of Connectivity is also in Theta(n^{3/2}) in the matrix model, but in Theta(n) in the array model. The upper bounds utilize search procedures for finding minima of functions under various conditions.
Recommendations
Cited in
(50)- On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
- Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
- Quantum algorithms for algebraic problems
- Randomized and quantum query complexities of finding a king in a tournament
- The Exponential Time complexity of counting (quantum) graph homomorphisms
- Graph comparison via nonlinear quantum search
- Considering nearest neighbor constraints of quantum circuits at the reversible circuit level
- Quantum algorithm design: techniques and applications
- Image classification based on quantum K-nearest-neighbor algorithm
- Span programs and quantum algorithms for st-connectivity and claw detection
- Quantum optimization of coherent chaotic systems: a case for buses of Kathmandu
- Quantum branch-and-bound algorithm and its application to the travelling salesman problem
- Quantum and classical query complexities of local search are polynomially related
- Quantum Algorithms for Evaluating Min-Max Trees
- Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
- Adversary lower bounds for nonadaptive quantum algorithms
- Exponential speedup of quantum algorithms for the pathfinding problem
- Automata, Languages and Programming
- Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs
- Algorithms and Computation
- Quantum algorithms for matrix scaling and matrix balancing
- A note on quantum divide and conquer for minimal string rotation
- Quantum approaches to graph colouring
- Theoretical computer science: computational complexity
- scientific article; zbMATH DE number 7378719 (Why is no real title available?)
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Evolutionary algorithms for quantum computers
- NISQ-friendly measurement-based quantum clustering algorithms
- Claw finding algorithms using quantum walk
- Quantum speedups for linear programming via interior point methods
- Quantum and classical query complexities for determining connectedness of matroids
- Quantum data structure for range minimum query
- Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
- Parameterized quantum query algorithms for graph problems
- Quantum algorithm for dynamic programming approach for DAGs and applications
- SOFSEM 2004: Theory and Practice of Computer Science
- Quantum complexity for vector domination problem
- Quantum query complexity of minor-closed graph properties
- Symmetries, graph properties, and quantum speedups
- Quantum time complexity and algorithms for pattern matching on labeled graphs
- The quantum query complexity of the determinant
- Quantum lower bounds by sample-to-query lifting
- Solving Lyapunov equation by quantum algorithm
- Quantum query complexity of minor-closed graph properties
- Quantum property testing for bounded-degree graphs
- Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
- scientific article; zbMATH DE number 7525446 (Why is no real title available?)
- Query complexity of global minimum cut
- Quantum algorithm for shortest path search in directed acyclic graph
- Quantum algorithms for string processing
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 Q5470736)
