Optimization Over Trace Polynomials

Victor Magron

Moisés Bermejo Morán, Abhishek Mishra

Here we present PCPOP, a Julia package for polynomial optimization that supports non-commutative optimization, tracial polynomial optimization, trace polynomial optimization and state polynomial optimization. PCPOP fully supports exact arithmetic computations and incorporates convenient functionalities such as algebraic reductions based on Gröbner basis methods, automatized symmetrization via Wedderburn decompositions, and Jordan algebra reductions. As a distinguished feature, PCPOP implements a specialized framework for polynomial computations in partially commutative variables that provides significant computational advantages for problems appearing in quantum information.

Simai He, Zhening Li, Shuzhong Zhang

Paul B Slater

We address the `major open problem' of evaluating how much increased efficiency in estimation is possible using non-separable —as opposed to separable—measurements of N copies of m -level quantum systems. First, we study the six cases m = 2, N = 2, ..., 7 by computing the 3 × 3 Fisher information matrices for the corresponding optimal measurements recently devised by Vidal et al . We obtain simple polynomial expressions for the (`Gill–Massar') traces of the products of the inverse of the quantum Helstrom information matrix and these Fisher information matrices. The six traces all have minima of 2 N − 1 in the pure state limit—while for separable measurements, the traces can equal N , but not exceed it. Then, the result of an analysis for m = 3, N = 2 leads us to conjecture that for optimal measurements for all m and N , the Gill–Massar trace achieves a minimum of (2 N − 1)( m − 1) in the pure state limit.

Gretchen L. Matthews, Julia Shapiro

In 2025, Jordan et al. introduced Decoded Quantum Interferometry (DQI), a quantum algorithm for combinatorial optimization based on decoding. They considered Reed-Solomon decoding and its associated optimization problem, called Optimal Polynomial Intersection (OPI), which may be viewed as a polynomial regression problem over a finite field. DQI exhibits provable speedups on certain problem instances and establishes a connection between decoding problems and optimization tasks. Leveraging the well-understood dual structure and decoding theory of algebraic geometry codes from other curve families, we introduce COFI: Curve-based Optimal Function Intersection. By considering two-point Hermitian codes, Suzuki codes, and extended norm-trace codes, we broaden the range of algebraic geometry codes used in DQI and identify families that offer further improvements over one-point Hermitian codes in the Hermitian Optimal Polynomial Intersection framework considered by Jordan and Gu. Depending on the family and parameter regime, these curves can reduce quantum resource requirements or increase the number of constraints that can be considered.

Sourour Elloumi, Zoé Verchère