Quantum query complexity of some graph problems
arXiv:quant-ph/0401091 · doi:10.1137/050644719
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.
7 figures. Subsumes and replaces quant-ph/9607014, quant-ph/0303131, and quant-ph/0303169
Cited by in corpus (34)
- Quantum algorithms for algebraic problems
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Quantum Algorithm Implementations for Beginners
- Noisy intermediate-scale quantum computers
- Quantum SDP-Solvers: Better upper and lower bounds
- Claw Finding Algorithms Using Quantum Walk
- Low depth mechanisms for quantum optimization
- Variational Quantum Algorithms for Dimensionality Reduction and Classification
- Lyapunov control-inspired strategies for quantum combinatorial optimization
- Convex optimization using quantum oracles
- Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
- Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers
- Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
- Opening the Black Box Inside Grover's Algorithm
- The quantum query complexity of read-many formulas
- Quantum Speedup Based on Classical Decision Trees
- Quantum-accelerated constraint programming
- Quantum Algorithms for String Processing
- Introducing Structure to Expedite Quantum Search
- Quantum property testing for bounded-degree graphs
- Quantum Computing Applications for Flight Trajectory Optimization
- Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs
- Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
- Preparing Many Copies of a Quantum State in the Black-Box Model
- Basic quantum subroutines: finding multiple marked elements and summing numbers
- Quantum Lower Bounds by Sample-to-Query Lifting
- Quantum Algorithm for Searching of Two Sets Intersection
- Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
- Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
- Quantum algorithm for unstructured search of ranked targets
- Quantum Algorithm for Online Convex Optimization
- A Note on Quantum Divide and Conquer for Minimal String Rotation
- Quantum community detection via deterministic elimination
- Quantum Data Structure for Range Minimum Query