arXiv:2610.05389
On State Distinguishing Without Inverse Queries
Emma Wang, Joseph Carolan, Andrew M. Childs
Abstract
In the quantum state distinguishing problem, an algorithm is given copies of a state $|ψ\rangle$ or $|φ\rangle$ separated by trace distance $\varepsilon$, and tasked with deciding which is the case. It is a standard result that $Θ(\varepsilon^{-2})$ copies are required, while having access to a unitary state preparation oracle and its inverse improves this to $Θ(\varepsilon^{-1})$ queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires $Ω(\varepsilon^{-2})$ forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only $O(\varepsilon^{-1})$ total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.
AI Summary
The paper asks whether knowing both candidate states enables a quadratic advantage in state distinguishing when a preparation oracle is available only in the forward direction. It studies discrete-unitary and continuous-time Hamiltonian formulations, obtaining different complexity bounds under their respective promises. For discrete access, the promise is $U|0\rangle=|0\rangle$ or $U|0\rangle=\sqrt{1-\varepsilon^2}|0\rangle+\varepsilon|1\rangle$. Distinguishing requires $\Theta(\varepsilon^{-2})$ forward queries when $d\geq\varepsilon^{-8}$, even with controlled access. This strengthens a prior lower bound involving an unknown target state. The proof combines hardness of inverting a random in-place permutation with a direct hybrid argument bounding squared-distance growth per query. Its finite-dimensional lower bound is $\Omega(\min\{\varepsilon^{-2},d^{1/6}\varepsilon^{-2/3}\})$; preparing independent copies supplies the matching high-dimensional upper bound. For continuous-time access, $\|H\|\leq1$ and the promise is $H|0\rangle=0$ or $H|0\rangle=\varepsilon|1\rangle$. The optimal total forward evolution time is $\Theta(\varepsilon^{-1})$, independently of dimension. Repeated projections onto $\mathrm{span}\{|0\rangle,|1\rangle\}$ implement quantum Zeno confinement, reducing the task to two-dimensional channel learning. The projected-evolution error scales as $O(t^2/n)$ for $n$ interventions, and a two-dimensional hybrid argument gives the time lower bound. The continuous-time promise is not equivalent to fractional-power access to the discrete oracle. Its resource accounting charges only unknown-Hamiltonian evolution, not intervention count or duration, and permits arbitrarily short evolutions. Optimal discrete dimension dependence and the effects of a minimum evolution duration remain open.
GPT-6-Astra was used to check and simplify calculations, help prepare the bibliography, and find related works.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.