On State Distinguishing Without Inverse Queries

Technical Summary: On State Distinguishing Without Inverse Queries

Problem Definition
The paper investigates the quantum state distinguishing problem under the constraint of forward-only access to an oracle. In the standard setting, an algorithm is given copies of a state $|\psi\rangle$ or $|\phi\rangle$ separated by a trace distance $\epsilon$ and must determine which state is present. While access to a unitary state preparation oracle $U$ and its inverse $U^\dagger$ allows for a query complexity of $\Theta(\epsilon^{-1})$ via amplitude amplification, the absence of the inverse oracle typically degrades performance to $\Theta(\epsilon^{-2})$ copies.

The authors study two specific settings where the oracle is a physical process that cannot be reversed:

1. Discrete-time setting: An unknown unitary $U$ prepares one of two known states. The algorithm has access only to forward queries of $U$.
2. Continuous-time setting: An unknown Hamiltonian $H$ (with $\|H\| \le 1$) generates the evolution. The algorithm has access to forward evolutions $e^{-iHt}$ for arbitrary durations $t$, but cannot apply $e^{iHt}$ (inverse evolution).

The core question is whether the quadratic advantage ($\epsilon^{-1}$ vs. $\epsilon^{-2}$) achievable with inverse access persists in these forward-only scenarios.

Methodology

• Discrete-Time Lower Bound:
  The authors strengthen a recent result by Tang and Wright [TW25], which showed that distinguishing a known state from an unknown close state requires $\Omega(\epsilon^{-2})$ queries. The authors prove that this lower bound holds even when both states are known.

  • Hard Instance: They construct a hard instance using a random in-place permutation $\pi$ on $d-1$ elements (fixing $|0\rangle$). The "YES" case is the permutation $P_\pi$, and the "NO" case is $R_\epsilon P_\pi$, where $R_\epsilon$ is a small rotation in the span of $\{|0\rangle, |1\rangle\}$.
  • Hybrid Argument: Unlike prior work that utilized advanced compressed oracle techniques, the authors employ a direct hybrid argument. They leverage the known hardness of inverting in-place permutations (Fefferman and Kimmel [FK18]) to show that an algorithm cannot place significant amplitude on the state $|\pi^{-1}(1)\rangle$.
  • Distance Analysis: They demonstrate that without the ability to reverse the permutation, the amplitude difference between the two cases does not accumulate coherently. Instead, the squared magnitudes of the differences add up, leading to a total distinguishability that scales as $\epsilon\sqrt{T}$ after $T$ queries, necessitating $T = \Omega(\epsilon^{-2})$.

• Continuous-Time Algorithm:
  For the continuous-time setting, the authors design an algorithm that achieves $O(\epsilon^{-1})$ total evolution time, independent of the dimension $d$.

  • Quantum Zeno Dynamics: The algorithm prevents the state from leaking into the high-dimensional subspace (where the distinguishing signal would be lost) by interspersing short forward evolutions with projective measurements $\Pi$ onto the subspace $\text{span}\{|0\rangle, |1\rangle\}$.
  • Convergence: Using the Gentle Measurement Lemma, they show that as the number of measurements $n$ increases, the evolution converges to the dynamics generated by the projected Hamiltonian $\Pi H \Pi$.
  • Reduction to 2D: This effectively reduces the problem to a two-dimensional system where the distinguishing signal accumulates linearly, allowing for optimal $\Theta(\epsilon^{-1})$ scaling using only forward evolution.

Key Results

1. Discrete-Time Hardness (Theorem 1.1): In sufficiently high dimensions ($d = \Omega(\epsilon^{-8})$), distinguishing between two known states prepared by a forward-only unitary oracle requires $\Theta(\epsilon^{-2})$ queries. This confirms that the quadratic advantage of inverse access is lost in the discrete setting, even when the target states are known.
2. Continuous-Time Efficiency (Theorem 1.2): In the continuous-time setting, distinguishing the states requires only $\Theta(\epsilon^{-1})$ total evolution time. This result is dimension-independent and relies on the ability to perform arbitrarily short forward evolutions combined with projective measurements.

Significance and Claims

The paper claims a qualitative separation between the power of forward-only access to a fixed discrete unitary versus forward-only access to continuous-time evolution.

• Discrete vs. Continuous: While the discrete case suffers from the loss of the quadratic speedup (requiring $\epsilon^{-2}$ queries), the continuous analogue retains the Grover-type speedup ($\epsilon^{-1}$ time) without needing inverse access.
• Methodological Contribution: The authors highlight that their discrete lower bound is proven via a direct hybrid argument, avoiding the complex "compressed oracle" machinery used in previous literature, thereby simplifying the proof of hardness for state distinguishing.
• Physical Relevance: The work addresses scenarios where unitaries represent physical processes or laboratory experiments where time reversal (inverse queries) is intractable or impossible, providing a theoretical boundary for what is achievable in such realistic constraints.

The authors note that their continuous-time formulation relies on a promise regarding the first column of the Hamiltonian ($H|0\rangle$), which mirrors the promise in the discrete problem but is distinct from simply having access to fractional powers of a discrete unitary. They conclude that while the discrete barrier is robust, the continuous-time model offers a natural analogue where quantum advantages persist even without time-reversal capabilities.