No Finite NPA Level Characterizes the Complete Quantum Set in the Simplest Bell Scenario

• URL: http://arxiv.org/abs/2607.14569v1
• Date: Thu, 16 Jul 2026 04:52:11 GMT
• Title: No Finite NPA Level Characterizes the Complete Quantum Set in the Simplest Bell Scenario
• Abstract summary: We show that emphno finite level is exact.<n>Every standard NPA relaxation based on a fixed finite list of words in the measurement projectors strictly contains the complete quantum set.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Navascués--Pironio--Acín (NPA) hierarchy gives the standard semidefinite outer approximations to quantum behaviors. Whether \emph{any} finite level can already equal the quantum set has remained open even in the bipartite scenario with two binary measurements per party. We demonstrate that \emph{no finite level} is exact. For the symmetric doubly tilted CHSH functional $h_α=A_0B_0+A_0B_1+A_1B_0-A_1B_1+α(A_0+B_0)$, set $T=1-α$. Its quantum maximum satisfies $[ω_{\rm Q}(1-T)-(4-2T)]/T^3\to4/3$, whereas every fixed NPA level satisfies $[ω_L(1-T)-ω_{\rm Q}(1-T)]/T^3\to+\infty$. Under the corresponding boundary rescaling, an explicit expectation of the positive operator $ω_{\rm Q}(1-t^2)I-H_t$ converges to the Motzkin polynomial. A bounded fixed-level error would therefore make the Motzkin polynomial plus a nonnegative constant a sum of squares, which is impossible. Consequently, every standard NPA relaxation based on a fixed finite list of words in the measurement projectors strictly contains the complete quantum set, and its nonquantum behaviors accumulate at a local deterministic behavior. Thus, the finite-level exactness of CHSH and all one-sided tilted CHSH maxima does not extend to an exact finite-level description of the complete quantum set in the minimal scenario.

Related papers

• Semidefinite extension complexity of the separable set, with applications to approximate disentanglers [0.6117371161379209]
  We consider semidefinite programs that approximate the maximum acceptance probability of a measurement over separable states.<n>Our proof combines the quantitative pseudo-density theorem of Lee, Raghavendra, and Steurer with explicit block-positive operators and Chebyshev amplification.
  arXiv  Detail & Related papers  (2026-09-08T17:00:11Z)
• Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms [42.57939149964391]
  We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB)<n>We prove the first minimax lower bounds of $(Klog(T/K))$ for QMAB and $(dlog(T/d))$ for finite-action QLB.
  arXiv  Detail & Related papers  (2026-08-14T14:04:21Z)
• Optimal Quantum de Finetti Theorems via Argmax Rounding [42.55259086694773]
  We prove optimal finite quantum de Finetti upper bounds for bosonic states and arbitrary exchangeable states.<n>Our proof formulates de Finetti approximation as the integrality gap of a symmetric-extension semidefinite program.<n> spectral truncation gives the first dimension-free bosonic de Finetti theorem in Hilbert--Schmidt distance.
  arXiv  Detail & Related papers  (2026-08-03T17:57:15Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• A phase transition in the exactness of the NPA hierarchy at the critical doubly-tilted CHSH functional [0.0]
  We prove the exact quantum maximum of the doubly-tilted CHSH functional $B_=langle A_0rangle+l B_0rangle+mathrmCHSH$.<n>For all $,ge 1$ and every level the hierarchy is exact, via three explicit rational certificates realizing an affine identity.<n>On the subcritical side we certify the first four levels in exact arithmetic.
  arXiv  Detail & Related papers  (2026-07-15T12:34:25Z)
• No finite level of the NPA hierarchy is exact for the doubly-tilted CHSH functional near the critical tilt [0.0]
  We prove that for every NPA level $kge 2$ there are an explicit rational $g_k>0$ and an $s*_k>0$ with $c_k(s)ge 4-s+g_k s2$ on $(0,s*_k)$.<n>For $kge 3$ no quantum state and no smooth curve of quantum models can realize the gain direction, so the overshoot lives strictly in the non-quantum part of the NPA cone.
  arXiv  Detail & Related papers  (2026-07-15T12:22:23Z)
• Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation [3.3636842548621275]
  A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization.<n>We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo.<n>Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map.
  arXiv  Detail & Related papers  (2026-05-31T14:47:58Z)
• Partial majorization and Schur concave functions on the sets of quantum and classical states [0.0]
  We construct for a Schur concave function $f$ on the set of quantum states a tight upper bound on the difference $f()-f()$ for a quantum state $$ with finite $f()$ and any quantum state $$ $m$-partially majorized by the state $$.<n>We show how the obtained results can be reformulated for Schur concave functions on the set of probability distributions with a finite or countable set of outcomes.
  arXiv  Detail & Related papers  (2026-04-14T17:59:12Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Quantum Mechanics from Finite Graded Equality [0.40611352512781856]
  We propose that quantum mechanics follows from a single hypothesis: equality has finite resolution.<n>We formalize the first two axioms as axioms; a structural Leibniz condition within the saturation axiom forces permutation invariance of basis elements.<n>Local tomography follows from $mathbbF = mathbbC$ with tensor product composition.
  arXiv  Detail & Related papers  (2026-03-12T13:14:48Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

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.