Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.
Abstract We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of sum-of-squares relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty and Wehner. Specifically, we show that the rate of convergence is no worse than
O(d2/ℓ2) O ( d 2 / ℓ 2 ) in the regime
ℓ=Ω(d) ℓ = Ω ( d ) where
ℓ ℓ is the level of the hierarchy and d the dimension, solving a problem left open in the recent paper by de Klerk and Laurent ( arXiv:1904.08828 ). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the Doherty–Parrilo–Spedalieri hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascués, Owari and Plenio.
Moment/Sum-of-Hermitian-Squares relaxations for noncommutative polynomial optimization problems have become an important tool for analyzing problems within quantum theory. Despite their widespread success, little is known about their rate of convergence and, consequently, their accuracy. In this work, we develop explicit convergence rates for relaxations of noncommutative polynomial optimization problems generated from the Pauli algebra -- covering applications to the ground state energy problem for n-qubit systems. In particular, we show that the rate of convergence can be bounded in terms of the smallest roots of a family of orthogonal polynomials known as Krawtchouk polynomials. Our result represents the first quantitative analysis of the rate of convergence for relaxations of noncommutative polynomial optimization problems.
We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex m ’th root of unity. Such problems have applications in signal processing, MIMO detection, and the computation of ground states in statistical physics, among others. In this paper, we construct an integer binary reformulation of the problem based on zonotopes. Compared to the standard reformulation, the number of binary variables is reduced by half or even m . ealWe also provide, with the help of tools from number theory, lower bounds on the number of variables in a real binary reformulation when m is an odd prime or a power of 2. We show on numerical experiments that zonotope reformulation can result in one order of magnitude speedup in solution time.
The
k-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For
k-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most
C(k)ξd+1n,4/n, where
ξd+1n,4 is the smallest root of a Krawtchouk polynomial and
C(k) is independent of the number of qubits
n and the hierarchy level
d. General
k-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.
We study the problem of maximizing a complex-valued quadratic form over the
Kth roots of unity. We show that when the objective matrix
Q⋆∈Cn×n of the quadratic has rank
r, the global maximizer belongs to a candidate set of size
O(rn2r−1). This set can be constructed deterministically in
O(rn2r+1) time by enumerating the vertices of a hyperplane arrangement in
R2r. The algorithm is embarrassingly parallel; with~
P processors, the time complexity drops to
O(rn2r+1/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-
r matrix, we prove that applying our framework to a spectral truncation yields a multiplicative
(1−O(∥H∥2/δ⋆))-approximation guarantee, where
δ⋆ denotes the eigengap of the underlying rank-
r matrix and
H represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling
S≥O(1/εr−1) candidates achieves a
(1−ε)cos2(π/K)-approximation of the optimal rank-
r solution with high probability. Crucially, this sample size is entirely independent of
n, reducing the overall runtime to
O(S⋅n2). Computational experiments on synthetic benchmarks and large-scale graphs for \textsc{Max-3-Cut} confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where
n≥106.