Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection

• URL: http://arxiv.org/abs/2607.16541v2
• Date: Wed, 22 Jul 2026 04:55:03 GMT
• Title: Efficient Exact Quantum Sampling from the Sun-Wootters Distribution for Optimal Polynomial Intersection
• Abstract summary: Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law.<n>We show that $P_u$ can be sampled efficiently for balanced OPI over prime fields.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal Polynomial Intersection (OPI) is a structured optimization problem for which Decoded Quantum Interferometry (DQI) attains a satisfaction guarantee governed by the semicircle law. Sun and Wootters recently showed that, for balanced OPI over prime fields, a Fourier-defined distribution $P_u$ gives a strict worst-case improvement from limiting rate $0.6225$ onward and asymptotically perfect solutions from rate $0.7496$ onward, and asked whether $P_u$ can be sampled efficiently. We answer this question for Reed--Solomon OPI parameters satisfying their exponent condition strictly below the dual Johnson radius. Under coherent membership-oracle access, we give a bounded-error polynomial-time quantum sampler for $P_u$. The ideal circuit samples $P_u$ exactly conditioned on success, while a finite-precision implementation achieves any prescribed inverse-polynomial total-variation error. Consequently, every fixed limiting rate $0.6225\le r<1$ admits a strict worst-case improvement over the DQI semicircle value, and every limiting rate $r\ge 3/4$ admits solutions of satisfaction $1-o(1)$ with high probability. The algorithm coherently sums the amplitudes of all low-weight errors in each syndrome class using deterministic complete list decoding. Complete Reed--Solomon list decoding and the Sun--Wootters denominator estimate make the list size and postselection overhead polynomial. In concurrent and independent work, Horinaga and Yamakawa obtain worst-case OPI algorithms over prime-power fields and exact satisfaction at every fixed rate strictly above $3/4$.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  We study the nonnegative submodular subject to a general matroid when the offline algorithm is given an arbitrary controlled value oracle.<n>Our algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives.<n>As a consequence, the offline-to-online reduction yields single-bandit CMAB algorithms for general matroid-constrained submodular rewards.
  arXiv  Detail & Related papers  (2026-08-12T14:54:15Z)
• Evaluating QAOA expectation values can be as hard as counting optimal solutions [0.0]
  We show that for $pgeq 2$ exact or exponentially precise expectation value evaluation is #P-hard under deterministic-time Turing reductions.<n>As an application we show our results imply analogous hardness results for computing and Hessians of QAOA circuits.
  arXiv  Detail & Related papers  (2026-08-11T19:47:04Z)
• Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry [6.7936678022428225]
  The Optimal Polynomial Intersection (OPI) problem asks us to find a low-degree over a finite field whose values lie in prescribed subsets on as many given inputs as possible.<n>As a byproduct, we also improve the existential bound of Sun and Wootters in certain parameter regimes.<n>Our results extend to the Max-LINSAT problem with respect to arbitrary distance separable (MDS) codes.
  arXiv  Detail & Related papers  (2026-07-16T07:18:57Z)
• Optimal algorithmic complexity of inference in quantum kernel methods [0.815557531820863]
  Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning.<n>Standard approach estimates each term independently via sampling, yielding a query complexity of $O(NlVertrVert2/varepsilon2)$.<n>We propose a query-optimal combination, encoding the full inference sum as the expectation value of a single observable.<n>Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities.
  arXiv  Detail & Related papers  (2026-04-16T16:45:02Z)
• On Worst-Case Optimal Polynomial Intersection [10.37026246853005]
  Decoded Quantum Interferometry (DQI) is a quantum algorithm that efficiently returns good solutions to the problem, even on worst-case instances.<n>We show that there are better solutions for worst-case instances over prime fields.
  arXiv  Detail & Related papers  (2026-04-10T17:50:46Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
  We study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs.<n>We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size.<n>Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.
  arXiv  Detail & Related papers  (2026-02-05T18:11:18Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

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.