Optimal query complexity for fractional quantum evolution

The gist: The optimal query complexity for implementing a noninteger power of an unknown unitary, given spectral gap and approximation error constraints, is determined to be exactly proportional to 1/δ log 1/ε.

Fractional Query Problem Formulation

The fractional query problem asks how many queries are required to implement a noninteger power U t = e itH, where U = e iH is unknown and the spectrum is separated from the branch cut by a gap δ, for an approximation error ε. A successful algorithm must implement ε-approximation of fractional power of queries uniform over all possible oracle unitaries in the family defined in Definition 2.

Upper Bound Construction via QSVT

The known upper bound for the fractional query problem is established by the Quantum Singular Value Transformation (QSVT) construction, which yields O(1/δ log 1/ε) queries for approximation error ε. The QSVT construction involves a circuit made of controlled-(U')±1 queries and its inverse, where U' is a shifted version of the unitary that satisfies the QSVT setting. This leads to an upper bound of O(1/δ log 1/ε) queries for Q(t, δ, ε). This proof reduces the problem to a scalar polynomial approximation problem by constructing a hard subfamily of two-eigenvalue oracles Uθ = e iδ(I − P) + e iθP with θ ∈ [δ, 2π). A successful N-query circuit for this family is shown to correspond to a Laurent polynomial p(z) of degree at most 2N in z. The periodic mismatch obstruction is then exploited using the sharp Remez inequality to establish a lower bound on the query complexity, leading to N ≥ 1/(4δ log sin(πt) 4ε).

Alternative Lower Bound via Frequency Annihilation

An alternative lower bound is provided by constructing a frequency annihilator functional that annihilates the approximant space but not the target. This method yields a lower bound Q(t, δ, ε) = Ωτ log 1/ε (11). The proof involves defining a polynomial R(w) based on the accessible frequencies and using the functional norm inequality to show that for every f ∈ C(I), inf q∈VΛ f − q∞ ≥ φR(f) = (R(Th)f)(x0) ρR. This results in an error bound dependent on the query count N, leading to the lower bound N ≥ max 0, log(t(1 − t)/(2ε)) 4 log(6e).

Optimality and Conclusion

The main results establish that Q(t, δ, ε) = Θτ 1/δ log 1/ε (9). This shows that the QSVT construction is optimal up to constant factors. The dependence on t is noted as necessary because the bound vanishes once ε ≥ sin(πt), leading to a conjecture of Q = Θ 1/δ log sin(πt) ε uniformly for ε ≤ c sin(πt). The work resolves the open question stated in [20] by proving a lower bound that matches the upper bound. This confirms that the QSVT construction is optimal up to constant factors. The final conclusion is that the optimal query complexity for fractional queries is Θτ 1/δ log 1/ε. The proof of this theorem is given in Appendix D 3.

Alternative Proof for ε Lower Bound

The alternative proof for the ε lower bound uses a normalized functional that annihilates the attainable frequency space but not the target. This method constructs a frequency annihilator R(w) based on roots of polynomials and uses elementary estimation to obtain a lower bound with respect to ε. The resulting inequality shows that every successful circuit satisfies ε ≥ 1/2 sin(πk - t / 2 (4N + 1)). This geometric bound is shown to hold for all N ∈ N, proving the lower bound in Eq. (12). The entire analysis confirms that Q(t, δ, ε) = Θτ 1/δ log 1/ε. The final result is that the optimal query complexity for fractional queries is Θτ 1/δ log 1/ε.

Details about Query Model and Success Criterion

The query model allows access to controlled-U, controlled-U†, and arbitrary additional ancillary workspace, equivalent to a quantum comb. An N-query circuit has the form AU = WN O(σN) U WN−1 · · · W1 O(σ1) U W0, σj ∈ (−1, +1) (2). The success criterion is defined by dph Ae iH J, Je itH ≤ ε (5). This is equivalent to sup H=H† spec(H)⊂[δ,2π) dph Ae iH J, Je itH ≤ ε (5), where the phase may depend on H but must be common to all input states. The phase insensitive distance dph(V, W) is equivalent to the diamond norm of the induced channel.

QSVT Upper Bound Construction in Our Model

The QSVT construction fits our model and yields a joint upper bound. A shifted version of the unitary U' satisfies the QSVT’s setting where spec(H') ⊂ [-π + δ/2, π - δ/2). The circuit uses N controlled-(U')±1 queries and all other gates depend only on (t, δ, ε). This leads to a unitary circuit AU made of controlled-U' and its inverse satisfying J†AU J − e itH' op ≤ ε 2/2. The estimate is uniform over all promised H.

Details about Success Criterion

The metric induced by ordinary operator norm does not satisfy our need because they do not count for the equivalence up to global phases. Therefore, we adapt the diamond norm for the definition of the ε-approximation. The success criterion in Definition 5 is equivalent to Definition 3 up to universal constants. This means that a circuit is (t, δ, ε)-successful if sup H=H† spec(H)⊂[δ,2π) dphAe iH J, Je itH ≤ ε (5).

Alternative Proof for ε Lower Bound

The alternative proof for the ε lower bound uses a normalized functional that annihilates the attainable frequency space but not the target. This method constructs a frequency annihilator R(w) based on roots of polynomials and uses elementary estimation to obtain a lower bound with respect to ε. The resulting inequality shows that for every f ∈ C(I), inf q∈VΛ f − q∞ ≥ φR(f) = (R(Th)f)(x0) ρR. This results in an error bound dependent on the query count N, leading to the lower bound N ≥ max 0, log(t(1 − t)/(2ε)) 4 log(6e). The final result is that the optimal query complexity for fractional queries is Θτ 1/δ log 1/ε.

Details about Query Model and Success Criterion

The query model we consider in Definition 1 allows controlled-U, controlled-U†, and arbitrary additional ancillary workspace, equivalent to a quantum comb defined in [31]. The N-query circuit has the form AU = WN O(σN) U WN−1 · · · W1 O(σ1) U W0, σj ∈ (−1, +1) (2). The success criterion is defined by dph Ae iH J, Je itH ≤ ε (5). This is equivalent to sup H=H† spec(H)⊂[δ,2π) dph Ae iH J, Je itH ≤ ε (5), where the phase may depend on H but must be common to all input states. The phase insensitive distance dph(V, W) is equivalent to the diamond norm of the induced channel.

QSVT Upper Bound Construction in Our Model

The QSVT construction fits our model and yields a joint upper bound. A shifted version of the unitary U'

1. Be able to efficiently implement noninteger powers of unknown unitaries, specifically approximating an evolution like "U t = e itH for some 0 < t < 1, with a query complexity bounded by O(1/δ log 1/ε) queries for approximation error ε."

2. Perform spectral transformations on unknown unitaries by implementing the map U7→Ut using a quantum singular value transformation (QSVT), which reduces tasks like Hamiltonian simulation and linear system solving to a single polynomial design task.

3. Design quantum circuits that achieve the optimal query complexity of Θτ 1/δ log 1/ε, showing that the known QSVT construction is asymptotically optimal for fractional query problems under the assumption of a spectral gap δ.

4. Implement an alternative lower bound proof by constructing a frequency annihilator functional that annihilates the approximant space, yielding a complexity bound of omegaτ log 1/ε uniform to δ.

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 over epsilon) queries for approximation error epsilon. 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 over epsilon). Consequently, the optimal query complexity for fractional query problem is Θ τ! (δ 1 over epsilon), 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 Ω τ! (1 over epsilon) bound uniform to δ.