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
(54)- Quantum approaches to graph colouring
- Claw finding algorithms using quantum walk
- Quantum algorithm design: techniques and applications
- Image classification based on quantum K-nearest-neighbor algorithm
- Quantum algorithms for string processing
- Graph comparison via nonlinear quantum search
- The Exponential Time complexity of counting (quantum) graph homomorphisms
- Quantum algorithm for shortest path search in directed acyclic graph
- Quantum branch-and-bound algorithm and its application to the travelling salesman problem
- Evolutionary algorithms for quantum computers
- Considering nearest neighbor constraints of quantum circuits at the reversible circuit level
- Span programs and quantum algorithms for st-connectivity and claw detection
- Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs
- On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
- Quantum algorithms for algebraic problems
- Quantum property testing for bounded-degree graphs
- Quantum query complexity of minor-closed graph properties
- Solving Lyapunov equation by quantum algorithm
- 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
- Quantum walk sampling by growing seed sets
- Applications of the quantum algorithm for st-connectivity
- Algorithms and Computation
- Automata, Languages and Programming
- Quantum Algorithms for Evaluating Min-Max Trees
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Quantum and classical query complexities of local search are polynomially related
- 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
- Theoretical computer science: computational complexity
- NISQ-friendly measurement-based quantum clustering algorithms
- Symmetries, graph properties, and quantum speedups
- 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
- Quantum lower bounds by sample-to-query lifting
- Randomized and quantum query complexities of finding a king in a tournament
- Quantum optimization of coherent chaotic systems: a case for buses of Kathmandu
- Exponential speedup of quantum algorithms for the pathfinding problem
- Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
- A note on quantum divide and conquer for minimal string rotation
- Quantum algorithms for matrix scaling and matrix balancing
- Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
- Parameterized quantum query algorithms for graph problems
- Multidimensional quantum walks, recursion, and quantum divide \& conquer
- Quantum approximate k-minimum finding
- Quantum speedup for sampling random spanning trees
- The quantum query complexity of the determinant
- Adversary lower bounds for nonadaptive quantum algorithms
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)
