Exact Coset Sampling for Quantum Lattice Algorithms

• URL: http://arxiv.org/abs/2509.12341v4
• Date: Sun, 26 Oct 2025 19:21:26 GMT
• Title: Exact Coset Sampling for Quantum Lattice Algorithms
• Authors: Yifan Zhang,
• Abstract summary: We give a simple replacement for the contested "domain-extension" in Step 9 of a recent windowed-QFT lattice algorithm with complex-Gaussian windows.<n>Our new subroutine replaces domain extension by a pair-shift difference that cancels unknown offsets exactly.
• Score: 9.910562011343009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a simple replacement for the contested "domain-extension" in Step 9 of a recent windowed-QFT lattice algorithm with complex-Gaussian windows (Chen, 2024). As acknowledged by the author, the reported issue is due to a periodicity/support mismatch when extending only the first coordinate in the presence of offsets, which breaks the intended $\mathbb{Z}_P$-fiber. Our new subroutine replaces domain extension by a pair-shift difference that cancels unknown offsets exactly and synthesizes a uniform cyclic subgroup (a zero-offset coset) of order $P$ inside $(\mathbb{Z}_{M_2})^n$. We adopt a gate-level access model and run a short prepass that measures the designated outcome registers (Chen's Steps 1, 3, and 5), fixing $E=(y',z',h^{\ast})$. We then identify a concrete program point $t^{\star}$ at which an index wire $J \in \mathbb{Z}_P$ is preserved and the coordinate block equals $\mathbf{X}(j)\equiv 2D^2 j\,\mathbf{b}^{\ast}+\mathbf{v}^{\ast}\ (\bmod M_2)$. A compute-copy-uncompute sandwich on the prefix up to $t^{\star}$ yields a reversible evaluator that we call only on basis inputs $j=0,1$ to harvest $V=\mathbf{X}(0)$ and $\Delta=\mathbf{X}(1)-\mathbf{X}(0)\equiv 2D^2\mathbf{b}^{\ast}$ within the same run. We never invert a measurement, and we do not claim the circuit suffix after $t^{\star}$. The default Step $9^{\dagger}$ uses only $\Delta$ (no foreknowledge of $\mathbf{b}^\ast$): set $\mathbf{Z}\leftarrow -\,T\cdot \Delta\ (\bmod M_2)$ for uniform $T\in\mathbb{Z}_P$ and erase $T$ coherently primewise by modular inversion and CRT.

Related papers

• $\mathsf{P} \ eq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weakness quantale $w_Q=K_mathrmpoly(cdotmidcdot)$.<n>For an efficiently samplable ensemble $D_m$ made by masking random $3$-CNFs, we prove a Switching-by-Weakness normal form.
  arXiv  Detail & Related papers  (2025-10-09T21:01:17Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms.<n>Our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance.
  arXiv  Detail & Related papers  (2025-04-03T08:24:15Z)
• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  We prove a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound when $epsilon$ is constant.<n>We also refute a prior conjecture that $mu_mathbfy(mathbfX)$ is hard to compute.
  arXiv  Detail & Related papers  (2024-12-03T18:11:37Z)
• 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)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast as finite-time error. Our analysis provides for faster convergence step-sizes for choosing step-sizes.
  arXiv  Detail & Related papers  (2022-09-06T15:04:57Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates [0.0]
  For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design. We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
  arXiv  Detail & Related papers  (2022-02-10T23:44:09Z)
• Quantum Algorithms for Ground-State Preparation and Green's Function Calculation [5.28670135448572]
  We present projective quantum algorithms for ground-state preparation and calculations of the many-body Green's functions in frequency domain. The algorithms are based on the linear combination of unitary (LCU) operations and essentially only use quantum resources.
  arXiv  Detail & Related papers  (2021-12-10T18:39:55Z)
• Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
  We develop and analyze an algorithm that, for most directions $bfu$ and $nu=mathrmpoly(k)$, estimates $bfu$ to high accuracy using $n=mathrmpoly(k)$ measurements. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.
  arXiv  Detail & Related papers  (2021-10-04T02:10:47Z)
• 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)
• 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)

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.