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.
Quantum query complexity of some graph problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
citation-role summary
background 1
citation-polarity summary
fields
cs.PL 1years
2026 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
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.