pipette
ENEnglish

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Weso{\l}owski, Jayne Thompson, Mile Gu, Lirand\"e Pira

Preprint

En palabras de los autores

Given oracle access to an unknown unitary , the fractional query problem asks how many queries are required to implement a noninteger power , , when the spectrum is separated from the branch cut by a gap . Quantum singular value transformation gives an upper bound of queries for approximation error . We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any -query circuit to the approximation of by a trigonometric polynomial with degree bounded by , together with Remez inequality. This allows us to establish the lower bound of . Consequently, the optimal query complexity for fractional query problem is , 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 bound uniform to .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.