Optimal query complexity for fractional quantum evolution

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 $\delta$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}{\delta}\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\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $\Omega_\tau\!\left(\frac{1}{\delta}\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $\Theta_{\tau}\!\left(\frac{1}{\delta}\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 $\Omega_{\tau}\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $\delta$.

arXiv:2610.01940 [quant-ph]

(or arXiv:2610.01940v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.01940 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.