Quantum Change Intervals: Exact Asymptotic Localization with Collective Measurements

Technical Summary: Quantum Change Intervals: Exact Asymptotic Localization with Collective Measurements

Problem Statement
The paper investigates the problem of exact-label minimum-error localization of a transient, calibrated pure-state change within a stationary sequence of independent quantum outputs. Unlike permanent change-point problems where the system switches states indefinitely, this model considers a "returning" geometry: a source emits a reference state $|0\rangle$, switches abruptly to a known anomalous pure state $|\psi\rangle$ for a contiguous interval $I = [a, b]$, and then perfectly returns to $|0\rangle$.

The receiver retains the entire sequence of $n$ systems and performs an arbitrary collective measurement (POVM) to estimate the exact interval $I$. The study addresses two primary scenarios:

1. Known Length: The duration $i = b - a + 1$ is fixed and known; the task is to infer the starting position $a$.
2. Unknown Length: Both the start $a$ and end $b$ are unknown, requiring inference over the set of all nonempty contiguous intervals.

The performance metric is the asymptotic success probability (Bayes risk with zero-one reward) as the sequence length $n$ and the number of admissible translations $N$ tend to infinity, with the state overlap $c = |\langle 0|\psi\rangle|$ held fixed.

Methodology
The authors employ a rigorous mathematical framework combining Toeplitz operator theory, Følner sequences, and Gram matrix perturbation analysis.

1. Gram Matrix Formulation: The discrimination problem is mapped to the spectral properties of the Gram matrix $G$ of the candidate states. The success probability for the Square-Root Measurement (SRM) is given by $P_{SRM} = \frac{1}{M} (\text{tr}\sqrt{G})^2$, while the optimal probability $P_{opt}$ is bounded by this value.
2. Fixed-Length Analysis (Toeplitz Reduction): For a known interval length $i$, the Gram matrix is shown to be a perturbation of a circulant matrix. By analyzing the Toeplitz symbol $f_{i,r}(\theta)$ (where $r=c^2$), the authors prove that the optimal and SRM probabilities converge to a one-dimensional integral of the square root of this symbol.
3. Growing Length Analysis: When the known length $i$ grows with $n$, the Gram matrix approaches a standard Toeplitz matrix associated with a single change point. The authors utilize the Poisson kernel and Landen transformations to derive the asymptotic limit.
4. Unknown-Length Analysis (Følner and Exceptional-Sector Transfer): The unknown-length case presents a significant challenge: the physical Gram kernel is not globally a two-dimensional Toeplitz matrix because the overlap between disjoint intervals depends on the gap between them, not just the endpoint displacement.
   • To resolve this, the authors employ a triangular Følner reduction, restricting the analysis to a "retained sector" of long intervals where the prior mass is asymptotically full.
   • They prove an Exceptional-Sector Gram Transfer Theorem, which demonstrates that if a retained sub-ensemble is operator-norm close to a separable comparison kernel (a 2D Toeplitz structure) and satisfies specific diagonal convergence properties, the asymptotic limits of the full physical ensemble match those of the comparison kernel.
5. Joint Detection: The framework is extended to include a "no-change" hypothesis ($H_0$) with a fixed prior $\pi_0$, deriving the joint Bayes limit.
6. Numerical Verification: The theoretical limits are validated using finite-size semidefinite programs (SDPs) for small $n$ and dense SRM computations for larger $n$, confirming convergence rates and gap behaviors.

Key Contributions and Results

1. Fixed Known Length: For a fixed interval length $i$, as the number of translations $N \to \infty$, both the optimal success probability and the SRM success probability converge to the same limit:
   $$P_{\infty}(i, r) = \left[ \frac{1}{2\pi} \int_0^{2\pi} \sqrt{f_{i,r}(\theta)} \, d\theta \right]^2$$
   where $f_{i,r}$ is the specific Toeplitz symbol derived from the interval structure. The difference between optimal and SRM probabilities decays as $O(N^{-1/2})$.

2. Growing Known Length: If both the interval length $i$ and the number of translations $N$ diverge (with no restriction on their ratio), the success probabilities converge to the one-dimensional Toeplitz functional evaluated at the effective compound overlap $c^2$:
   $$\lim P = p_1(c^2)$$
   where $p_1(r)$ is the benchmark limit for a single permanent change point.

3. Unknown Interval Length: Under a uniform prior over all nonempty intervals, the success probability converges to a distinct limit:
   $$\lim P = p_1(c)^2$$
   This result arises because the unknown-length problem involves two endpoint coordinates rather than one translation coordinate. The physical kernel's non-Toeplitz nature (due to gap corrections) is overcome by the transfer theorem, showing the limit is the square of the one-dimensional functional evaluated at $c$ (not $c^2$).

4. Joint Detection with No-Change Hypothesis: When a no-change hypothesis is added with fixed prior $\pi_0$, the optimal joint Bayes limit is:
   $$\pi_0 + (1 - \pi_0)L$$
   where $L$ is the conditional localization limit derived in the previous cases. The paper notes that the weighted SRM for this augmented ensemble is not analyzed for optimality.

5. Numerical Confirmation: The paper provides rigorous numerical bounds for small $n$ using SDPs, showing that the SRM gap ($P_{opt} - P_{SRM}$) is small and consistent with theoretical decay rates, while high-overlap cases ($c \to 1$) exhibit slow pre-asymptotic convergence.

Significance and Claims
The paper claims to provide exact asymptotic laws for a class of quantum change-interval problems that were previously intractable due to the non-Toeplitz structure of the physical Gram matrix.

• Theoretical Breakthrough: The primary contribution is the development of the Exceptional-Sector Gram Transfer Theorem. This allows the authors to bypass the failure of direct multilevel Szegő theorems (which require global Toeplitz structure) by proving that the "gap-dependent" corrections in the physical kernel do not affect the asymptotic limit, provided the retained sector has full prior mass.
• Geometric Distinction: The results highlight a fundamental geometric difference between known and unknown length problems. The known-length limit depends on $c^2$ (reflecting a single translation coordinate), while the unknown-length limit depends on $c$ squared (reflecting two endpoint coordinates), resulting in the law $p_1(c)^2$.
• Benchmarking: The derived limits serve as ultimate benchmarks for collective measurements, demonstrating that collective strategies can achieve non-zero asymptotic success probabilities even for transient changes, outperforming potential online strategies (though online strategies are not explicitly compared in the asymptotic limit here).
• Modesty: The authors explicitly state that while they provide the asymptotic limits, they do not provide efficient physical implementations of the optimal measurements. They also note that determining the exact finite-size decay rate for the SRM gap in the fixed-length case remains an open problem, and their proofs for the growing-length and unknown-length cases are qualitative regarding convergence rates.

In summary, the paper establishes that the contiguity constraint of a returning quantum change interval reduces the complex discrimination problem to tractable spectral limits, solvable via a novel combination of Følner sequences and Gram matrix perturbation theory.