REVIEW 1 cited by
Quantum query complexity of some graph problems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 1 Pith paper
-
ReOC: Compilation of Recursive Quantum Oracles with Recursion-Aware Uncomputation
A compilation framework from the new language RQIMP to the existing RQC++ language compiles recursive quantum oracles with quantum-controlled recursion and adds recursion-aware automatic uncomputation.
Discussion (0). Continue with ORCID to comment.