Optimal query complexity for fractional quantum evolution
Abstract
Given oracle access to an unknown unitary U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitH, 0<t<1, when the spectrum is separated from the branch cut by a gap δ. Quantum singular value transformation gives an upper bound of O (1/δlog1/ε) queries for approximation error ε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any N-query circuit to the approximation of eitθ by a trigonometric polynomial with degree bounded by O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ (1/δlog1/ε). Consequently, the optimal query complexity for fractional query problem is Θτ (1/δlog1/ε), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ (log1/ε) bound uniform to δ.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Noisy Quantum Query Complexity via Fractional Block Sensitivity
- Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
- Multivariate quantum signal processing with optimal query complexity
- Query-optimal quantum simulation of Lindblad evolution
BibTeX
@misc{liu2026optimal,
title = {{Optimal query complexity for fractional quantum evolution}},
author = {Anthony Yuezhang Liu and Adam Wesołowski and Jayne Thompson and Mile Gu and Lirandë Pira},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01940},
eprint = {2610.01940},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01940},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Optimal query complexity for fractional quantum evolution
AU - Anthony Yuezhang Liu
AU - Adam Wesołowski
AU - Jayne Thompson
AU - Mile Gu
AU - Lirandë Pira
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01940
UR - https://arxiv.org/abs/2610.01940
AB - Given oracle access to an unknown unitary U=e^iH , the fractional query problem asks how many queries are required to implement a noninteger power U^t=e^itH, 0<t<1, when the spectrum is separated from the branch cut by a gap δ. Quantum singular value transformation gives an upper bound of O (1/δlog1/ε) queries for approximation error ε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any N-query circuit to the approximation of e^itθ by a trigonometric polynomial with degree bounded by O(N), together with Remez inequality. This allows us to establish the lower bound of Ω_τ (1/δlog1/ε). Consequently, the optimal query complexity for fractional query problem is Θ_τ (1/δlog1/ε), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ω_τ (log1/ε) bound uniform to δ.
ER -