arXiv:2610.01940
Optimal query complexity for fractional quantum evolution
Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson, Mile Gu, Lirandë Pira
Abstract
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\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. 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 $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, 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 $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.
AI Summary
Given controlled access to an unknown unitary $U=e^{iH}$ and its inverse, how many oracle queries are needed to implement $U^t$ for noninteger $0<t<1$? The paper considers the branch convention $\operatorname{spec}(H)\subset[\delta,2\pi)$ and requires uniform approximation up to global phase, formulated using diamond distance, with arbitrary ancillas and oracle-independent gates. For $t\in[\tau,1-\tau]$, it proves optimal query complexity $\Theta_\tau(\delta^{-1}\log(1/\varepsilon))$, matching the known QSVT upper bound. Specifically, for $0<\delta<1$ and $\varepsilon<(\sin(\pi\tau)/4)^2$, every successful circuit needs at least $(8\delta)^{-1}\log(1/\varepsilon)$ queries. This excludes a previously claimed additive scaling $O(\delta^{-1}+\log(1/\varepsilon))$; the paper identifies missing error-reduction overhead in that construction’s analysis. The lower bound restricts to two-eigenvalue oracles with one fixed reference phase. An $N$-query circuit yields a Laurent polynomial of degree at most $2N$ approximating $e^{it\theta}$, after cancelling the unknown global phase through a product of matrix elements. A shifted difference is small over most of the circle but remains large at the branch cut. A sharp trigonometric Remez inequality then gives the joint gap–error bound. A separate frequency-annihilating functional proves $\Omega_\tau(\log(1/\varepsilon))$ uniformly in $\delta$. The result is worst-case and assumes $t$ stays away from integers. Optimal dependence near $t=0,1$, matching upper bounds without controlled access, average-case complexity, and extensions to other spectral transformations remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.