Quantum Change Interval: Exact Asymptotics for Minimum Error Localization

• URL: http://arxiv.org/abs/2608.24543v2
• Date: Thu, 03 Sep 2026 03:58:38 GMT
• Title: Quantum Change Interval: Exact Asymptotics for Minimum Error Localization
• Abstract summary: We study a returning quantum change interval in which a source emits $lvertrangle$ over one interval and $lvert0rangle$ elsewhere.<n>We analyze the matrix using Toeplitz comparison and Flner transfer, together with an exact decomposition by excitation number and interval hull.
• Score: 8.906035369693457
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a returning quantum change interval in which a source emits $\lvertψ\rangle$ over one interval and $\lvert0\rangle$ elsewhere. A collective measurement on the full sequence identifies both endpoints with minimum error. We analyze the Gram matrix using Toeplitz comparison and Følner transfer, together with an exact decomposition by excitation number and interval hull. The resulting bounds establish asymptotic Bayes optimality of the square root measurement (SRM). Let $c=\lvert\langle0\vertψ\rangle\rvert$ and $p_1(x)=4(1-x^2)K^2(x^2)/π^2$, where $K$ is the complete elliptic integral of the first kind. For a known interval length $i$, the SRM success probability and the Bayes optimum converge to the same Toeplitz symbol integral as the number $N$ of translations grows. For fixed $i$ and $0<c<1$, their gap is $P_{\mathrm{opt}}(G_{N,i})-P_{\mathrm{SRM}}(G_{N,i})=O_{i,c}(N^{-1/2})$. If $i$ and $N$ both diverge, their common limit is $p_1(c^2)$, with no constraint on their relative growth. For unknown length, the uniform prior over all $M_n=n(n+1)/2$ nonempty intervals gives the common limit $p_1(c)^2$ at fixed overlap. For a varying overlap $c_n$, set $τ_n=n(1-c_n)(\log n)^2$. Uniformly for $0\leqτ_n\leq T$, we obtain $M_nP_X=(1+2\sqrt{τ_n}/π+\sqrt{2}τ_n/π^2)^2+O_T(\log\log n/\log n)$, where $X\in\{\mathrm{tr},\mathrm{SRM},\mathrm{opt}\}$. More generally, if $c_n$ approaches one from below and $n p_1(c_n)\to\infty$, the same three quantities satisfy $P_X\sim p_1(c_n)^2$. These asymptotic laws also extend to joint detection and exact localization in the presence of a no change prior.

Related papers

• Discretization and Statistical Consistency of Functional Flow Matching [0.0]
  We prove strong $L2$ convergence of finite conditional velocity targets for every strongly consistent sequence of finite-rank reconstructions.<n>For learned flows, coupling directly to a population superposition path yields an end-to-end Wasserstein bound.
  arXiv  Detail & Related papers  (2026-08-05T07:05:47Z)
• Non-asymptotic Tail Bounds for the Kostlan--Shub--Smale Field: Tensor PCA and Spherical $k$-Spin Complexity [0.6627152091494143]
  This paper builds a hierarchy of explicit, non-asymptotic tail bounds for the supremum of the Kostlan--Shub--Smale random field on the sphere.<n>It applies it to two problems: Spiked PCA and the landscape of the spherical $k$-spin model.
  arXiv  Detail & Related papers  (2026-06-16T08:27:25Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds [9.739744677824286]
  Constant-stepsize approximation (SA) is widely used in learning for computational efficiency.<n>Prior work shows that as the stepsize $downarrow 0$, the centered-and-scaled steady state converges weakly to a Gaussian random vector.<n>This paper provides explicit, non-asymptotic error bounds for fixed $$.
  arXiv  Detail & Related papers  (2026-02-15T02:34:50Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  We present algorithms for diffusion model sampling which obtain $$-error in $mathrmpolylog (1/)$ steps.<n>Our approach also yields the first $mathrmpolylog (1/)$ complexity sampler for general log-concave distributions.
  arXiv  Detail & Related papers  (2026-02-01T17:05:31Z)
• What Trace Powers Reveal About Log-Determinants: Closed-Form Estimators, Certificates, and Failure Modes [0.0]
  We study access to trace powers $p_k = tr(Ak)$, natural when matrix powers are available.<n>We prove a fundamental limit: no continuously positive moments can be uniformly accurate over unbounded conditioning.
  arXiv  Detail & Related papers  (2026-01-18T23:04:17Z)
• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  We develop a unified framework certified Top-$k$ attention truncation that quantifies error at both the distribution and output levels.<n>We show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$.
  arXiv  Detail & Related papers  (2025-12-08T15:36:41Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  We show that the Monotonic Value Omega (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land mathttVar_maxtextc$.
  arXiv  Detail & Related papers  (2025-06-06T20:33:57Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  We study inference in simulation-based models where the analytical form of the likelihood is unknown.<n>We use a ratio-free nested multi-time-scale approximation (SA) method that simultaneously tracks the score and drives the parameter update.<n>We show that our algorithm can eliminate the original bias $Obig(sqrtfrac1Nbig)$ and accelerate the convergence rate from $Obig(beta_k+sqrtfracalpha_kNbig)$.
  arXiv  Detail & Related papers  (2024-11-20T02:46:15Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• On the $O(\rac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
  arXiv  Detail & Related papers  (2024-02-01T07:21:32Z)
• Superfluid weight in the isolated band limit within the generalized random phase approximation [0.0]
  The superfluid weight of a generic lattice model with attractive Hubbard interaction is computed analytically in the isolated band limit. It is found that the relation obtained in [https://link.aps.org/doi103/PhysRevB.106.014518] between the superfluid weight in the flat band limit and the so-called minimal quantum metric is valid even at the level of the generalized random phase approximation.
  arXiv  Detail & Related papers  (2023-08-21T15:11:32Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  Heavy tails emerge in gradient descent (SGD) in various scenarios. We provide convergence guarantees for SGD under a state-dependent and heavy-tailed noise with a potentially infinite variance. Our results indicate that even under heavy-tailed noise with infinite variance, SGD can converge to the global optimum.
  arXiv  Detail & Related papers  (2021-02-20T13:45:11Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
  We find that a bound on the sample and computational complexity was previously unknown when $omega(1) leq d leq O(log k)$. These authors also show that the sample of complexity of a random mixture of gaussians in a ball of radius $d$ in $d$ dimensions, when $d$ is $Theta(sqrtd)$ in $d$ dimensions, when $d$ is at least $poly(k, frac1delta)$.
  arXiv  Detail & Related papers  (2020-04-13T08:06:29Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.