No Free Compression in Quantum Relaxations for Optimization

• URL: http://arxiv.org/abs/2608.25151v1
• Date: Tue, 25 Aug 2026 20:57:14 GMT
• Title: No Free Compression in Quantum Relaxations for Optimization
• Abstract summary: Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits.<n>We show that compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding on $n$ qubits, pairwise correlators can represent $m=Θ(n^2)$ binary variables. We define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign assignment. We show that it is exactly $Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)$, whereas uniformly random sign assignments retain $Θ(1/\sqrt n)$ target-specific margins. The stronger $1/n$ worst-case scaling is Majorana-specific. Moreover, arbitrary density operators and fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. Beyond Majoranas, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of $m$ designated binary observables on $n$ qubits, the universal margin is at most $\sqrt{(2\ln2\;n/m)}$, while arbitrary random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=Ω(m)$. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.

Related papers

• A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States [2.5735476569508995]
  We construct a single fixed shallow quantum analyzer whose Born outcomes replace externally sampled settings as labels for reusable shadow snapshots.<n>The analyzer combines a freshly prepared $n$-qubit fiducial register $A$ with parallel Bell readout of $A$ and the unknown system $S$, producing one $2n$-bit record per copy.
  arXiv  Detail & Related papers  (2026-09-07T04:36:39Z)
• 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)
• Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
  For general max-k-XORSAT with $k geq 3$, no-time algorithm can do substantially better than random guessing on worst-case instances.<n>We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields.
  arXiv  Detail & Related papers  (2026-06-11T16:59:12Z)
• Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
  We identify the wavelet scaling exponent $$ as a critical diagnostic.<n>We establish $= 1/2$ as a sharp transition boundary for the classical simulability of amplitude-encoded quantum kernels.<n>We prove this variance scales strictly as $Var[X] = (d-2)$.
  arXiv  Detail & Related papers  (2026-05-12T05:41:12Z)
• FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression [35.73320708128261]
  We introduce textscFibQuant, a universal fixed-rate vector quantizer.<n>The codebook combines Beta-quantile radii, Fibonacci,/,Roberts--Kronecker quasi-Max refinement.<n>On GPT-2 small KV caches, textscFibQuant traces a memory--fidelity frontier.
  arXiv  Detail & Related papers  (2026-05-12T03:45:53Z)
• Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility [0.0]
  We propose quantum algorithms for the exact simulation of a normalised correlated Gaussian random vector.<n>Motivated by financial applications, we provide an end-to-end resource analysis.
  arXiv  Detail & Related papers  (2026-04-24T11:29:09Z)
• Quantum Sketches, Hashing, and Approximate Nearest Neighbors [0.0]
  In a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state $_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $_P$.<n>For every approximation factor $cge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $0,1d$ with $d=(log n)$ for which any such sketch requires $m=(n)$ qubits.
  arXiv  Detail & Related papers  (2026-02-22T16:18:36Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)

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.