Tight bounds for hybrid quantum-classical query algorithms
Abstract
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision ε requires Θ(1/(q ε2)) queries; (ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ((p(1−p))/(q ε2)) queries; (iii) Search among N items requires Θ(N/q) queries; (iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(nm/q) queries. All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
Related
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
- Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
- Tight Universal Bounds on Quantum Data Hiding with Multipartite Werner States
- Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
BibTeX
@misc{ambainis2026tight,
title = {{Tight bounds for hybrid quantum-classical query algorithms}},
author = {Andris Ambainis and András Gilyén and Martins Kokainis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06803},
eprint = {2610.06803},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06803},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight bounds for hybrid quantum-classical query algorithms
AU - Andris Ambainis
AU - András Gilyén
AU - Martins Kokainis
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06803
UR - https://arxiv.org/abs/2610.06803
AB - We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision ε requires Θ(1/(q ε^2)) queries; (ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ((p(1−p))/(q ε^2)) queries; (iii) Search among N items requires Θ(N/q) queries; (iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(nm/q) queries. All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
ER -