Certified Multi-State Measurement Design for Quantum-Inspired Classifiers

When you must tell apart several known quantum states with a single measurement, the best achievable success probability is the answer to a semidefinite program. A semidefinite program is an optimization over matrices that must stay positive semidefinite, meaning all their eigenvalues are non-negative. That program has a dual, a second optimization whose feasible solutions are upper bounds on the best achievable success. In practice, almost nobody solves it once the matrices get large. Quantum-inspired classifiers and multi-copy studies fall back on the closed-form "pretty good measurement", or restrict themselves to two classes, where the optimum has a formula. As a result they report accuracies with no indication of how far the measurement they used is from the best possible one. We propose a cheap map that turns any measurement into a matching dual certificate. Given candidate measurement operators, the map builds a feasible dual matrix whose trace upper-bounds the optimal success probability. The difference between the two, the duality gap, is exactly the total amount by which the measurement violates the known optimality conditions. The gap therefore brackets the true optimum from both sides, decides when an iterative solver can stop, and is zero only at an optimal measurement.

The payoff is both practical and scientific. Practically, the certificate costs a handful of eigendecompositions. It can therefore be attached to fast non-convex solvers that carry no optimality guarantee of their own, and to the problems that arise after reducing multi-copy ensembles by their permutation symmetry, where interior-point solvers run out of memory. Scientifically, it lets us settle a live disagreement. Giuntini et al. find that discrimination performance improves monotonically with the number of tensor copies of the encoded data. Hwang et al. find that classification performance peaks and then declines in the copy count. Without knowing how suboptimal the measurement is, one cannot tell whether that decline is a measurement artifact or genuine statistical overfitting.

Core Claim

Minimum-error discrimination of states $\rho_i$ with priors $p_i$ asks for measurement operators $M_i \succeq 0$ summing to the identity that maximize the success probability $P(M)=\sum_i p_i \mathrm{Tr}(M_i\rho_i)$. The dual asks for the smallest-trace matrix $Y$ with $Y \succeq p_i\rho_i$ for every $i$. At the optimum, $Y^* = \sum_i p_i\rho_i M_i$. We turn this optimality condition into a certificate valid at any measurement, optimal or not. Let $Y_0$ be the Hermitian part of $\sum_i p_i\rho_i M_i$, so that $\mathrm{Tr}(Y_0)=P(M)$, and let $(A)_+$ denote the positive-eigenvalue part of a Hermitian matrix $A$. Then the matrix

$$ Y(M) \;=\; Y_0 + \sum_{i=1}^m \big(p_i\rho_i - Y_0\big)_+ $$

is dual feasible. This holds because each added term dominates its own constraint violation, and all the other terms are positive semidefinite. The resulting bracket is

$$ P(M) \;\le\; P_{\mathrm{opt}} \;\le\; \mathrm{Tr}\,Y(M), \qquad \Delta(M) = \sum_{i=1}^m \mathrm{Tr}\big(p_i\rho_i - Y_0\big)_+ . $$

The gap $\Delta(M)$ vanishes exactly when the optimality conditions hold. A cruder certificate adds a multiple of the identity, $Y_0 + \max_i \lambda_{\max}(p_i\rho_i - Y_0)\, I$. That version is also valid, but it is looser by up to a factor of the Hilbert-space dimension $D$, because the trace of the identity is $D$. In high dimension this factor is the difference between a useful bound and a vacuous one.

The proposal claims three things. First, this positive-part certificate, attached to a fast but uncertified primal solver and to the symmetry-reduced multi-copy problem, brackets $P_{\mathrm{opt}}$ tightly at dimensions where interior-point solvers fail. Second, its gap is a reliable stopping rule where objective-change rules stop too early. Third, with it we can measure, for the first time on the benchmark suites used in the copy-number debate, how much test accuracy the pretty good measurement leaves on the table as copies increase.

The general device of mapping primal iterates to dual-feasible points is not new. Koh et al. use it for large-scale sparse logistic regression. Aditi and Becker derive an a-posteriori duality bound for factorized maximum-likelihood tomography. What is new here is threefold: the construction is specific to the coupled measurement constraint $\sum_i M_i = I$; the certificate equals the optimality-condition violation, so it closes to zero; and it is used to adjudicate a scientific question rather than only to stop a solver. Tomography also optimizes a state given fixed measurements. We optimize the measurement given known states, whose optimal operators are typically full rank, so Aditi and Becker's low-rank machinery does not transfer.

Why the obvious Frank-Wolfe approach does not work

The natural pairing of these two directions is a Frank-Wolfe solver over the set of measurements. Frank-Wolfe, or conditional gradient, is an optimizer that at each step solves a linear problem over the feasible set and moves toward its solution. Its surrogate duality gap, analyzed by Jaggi and Pokutta, would serve as the stopping rule. That plan fails for a structural reason. The linear subproblem over the set of measurements, maximizing $\sum_i \mathrm{Tr}(G_iM_i)$ subject to $\sum_i M_i=I$ and $M_i \succeq 0$, is itself a discrimination problem of full size. The "cheap oracle" is therefore as hard as the original problem.

SketchyCGAL (Yurtsever et al.) sidesteps hard oracles by keeping only a trace bound and handling a small number of affine constraints through an augmented Lagrangian. The identity-resolution constraint, however, imposes $D^2$ affine constraints, which violates that method's "weakly constrained" assumption. The optimistic and gap-minimizing step rules of Martínez-Rubio and Pokutta inherit the same oracle problem. This is why we separate the two roles. Any fast primal method generates measurements, and a closed-form dual map certifies them.

Research Program

The primal side writes each measurement operator as $M_i = B_i^\dagger B_i$. The stacked matrix $[B_1;\dots;B_m]$ is then an isometry, a matrix whose columns are orthonormal, so the constraints hold by construction. We run Riemannian gradient ascent over this set of isometries, in the spirit of the Riemannian Holevo-capacity solver of the Holevo optimization paper. We warm-start from the pretty good measurement, $M_i = S^{-1/2}p_i\rho_iS^{-1/2}$ with $S=\sum_j p_j\rho_j$. This landscape is non-convex and offers only stationarity guarantees. That limitation is exactly what makes an external certificate valuable.

Every $k$ iterations we evaluate $Y(M)$. This costs $m$ Hermitian eigendecompositions of size $D$. When the violations are low rank, it reduces to a few Lanczos calls (Lanczos being an iterative method that extracts a few extreme eigenvectors). We then stop when the relative gap $\Delta/P(M)$ falls below a target. We will also test a light "certificate polishing" step: a few subgradient iterations on the dual starting from $Y(M)$. These iterations can only lower the upper bound, so the bracket remains valid.

The scaling lever is symmetry. Multi-copy ensembles $\rho_i^{\otimes n}$, and class averages of $|\psi\rangle\langle\psi|^{\otimes n}$, are invariant under permuting the copies. Averaging any measurement over permutations leaves its success probability unchanged. The optimal measurement can therefore be taken block-diagonal in the decomposition of the tensor space into its irreducible symmetry components (the Schur–Weyl decomposition). For averaged pure copies, all states lie in the symmetric subspace of dimension $\binom{d+n-1}{n}$, and the restriction to that subspace is exact. This dimension grows polynomially in $n$ for a fixed encoding dimension $d$, instead of as $d^n$, which removes the "curtain of dimensionality" that forced Giuntini et al. to stop at small copy numbers. The certificate decomposes block by block, so it applies unchanged. Following Chambolle and Rasch, who use inner-loop gaps to avoid over-solving nested subproblems, we also use the bracket to control the outer sweep over copy number. Each solve at a given $n$ stops once its bracket is narrower than the difference in success probability that would change the choice of copy number.

The scientific study then compares, at each $n$ and on each dataset, three quantities on held-out data: the test accuracy of the pretty good measurement, the test accuracy of the certified near-optimal measurement, and the certified training-ensemble bracket. Giuntini's theorem concerns the optimal success probability on the training class ensembles. Hwang's finding concerns test F1. The two may not actually contradict each other, and the experiment is designed to say so if they do not.

Baselines

The naive reference point is the pretty good measurement used alone, as in Giuntini et al.. Its only certificate is the classical square-root relation, $P_{\mathrm{opt}} \le \sqrt{P_{\mathrm{PGM}}}$ (a standard result for this measurement, not taken from the file). Since the pretty good measurement is our warm start, any certified bracket we report must be strictly tighter than $[P_{\mathrm{PGM}}, \sqrt{P_{\mathrm{PGM}}}]$ to count as progress. On this question the reported reference is the 0.9468 Pearson correlation between Helstrom distinguishability and balanced accuracy across 14 tabular datasets in Giuntini et al.. The Helstrom bound is the closed-form optimum for two states. We found no reported result on Lacuna for multi-class optimal-measurement accuracy on those datasets.

The strongest exact method is a standard interior-point solver run on the same symmetry-reduced problem. It natively reports a duality gap near $10^{-8}$. It is the right competitor because, once the symmetry reduction is applied, it might already suffice. We run it on identical reduced instances and hardware, with default tolerances. We record wall-clock time, peak memory, and the largest copy number $n$ it completes. We count a win only in the regime where it runs out of memory or time while our bracket stays below a relative width of $10^{-3}$. Where both run, its optimum is the ground truth against which we check our bracket's validity and width.

The second competitor is the same Riemannian solver stopped by an objective-change rule, $|P_{k+1}-P_k|<\epsilon$, with no certificate. It shows what certification buys. We match the iteration budget and measure how often the heuristic stops with a true gap, computed against the interior-point optimum, above its implied tolerance.

For binary problems we also compare against the closed-form Helstrom solution, including Hwang et al.'s fidelity-based simulation. There the true optimum is known exactly, and the reported reference is the optimal copy hyperparameter $k=147.5$ for Transfusion in Hwang et al..

The key ablation replaces the positive-part certificate with the scalar identity-shift certificate on the same iterates. This isolates whether the sum of positive parts, rather than duality bookkeeping in general, is responsible for tight brackets at large $D$. A second ablation removes the symmetry reduction to measure how much of the reach in $n$ comes from symmetry alone.

Why not just…?

Why not just run MOSEK or SDPT3, which already report exact gaps? On small reduced problems we will, and they will win on accuracy. This alternative is a genuine threat. The question is where the crossover lies. Yurtsever et al. report SDPT3 failing from memory limits on phase retrieval at $n=10^6$. Krechetov et al. report about 10 minutes for standard solvers against about 5 seconds for a first-order method on BiqMac instances. The discrimination problem has $m$ matrix blocks of size $D$ tied together by $D^2$ equality constraints, so the second-order system an interior-point method must form grows roughly as $(mD^2)^2$. With a four-dimensional encoding and $n=20$ copies, $D$ is already 1771, which should be out of reach. If the crossover turns out to lie beyond every copy number of scientific interest, we will report that the certificate's value lies in validating fast heuristics rather than in raw scale.

Why not just use the pretty good measurement, perhaps with its square-root guarantee? This is free, and for symmetric ensembles it is exactly optimal. But the square-root bound is loose in exactly the regime that matters. At 70% success it allows an optimum as high as 84%, too wide to say whether a 3-point accuracy dip with copy number is a measurement artifact. Our experiments report both brackets side by side on every dataset and copy number. If the pretty good measurement turns out to be certified near-optimal everywhere, that is itself the answer to the copy-number debate, and we will report it as such.

Why not just stop the non-convex solver when progress stalls, as Burer-Monteiro tomography effectively does? Aditi and Becker show that factorized solvers scale remarkably well. They nonetheless felt the need to add a duality bound, and the Riemannian Holevo work concedes convergence only to critical points. Stalls on flat or ill-conditioned regions are the documented failure mode of objective-change rules (Pokutta). The stopping-rule experiment below measures directly how often stalls masquerade as convergence on discrimination landscapes.

Proposed Experiments

The validation stage checks correctness where the answer is known. For binary ensembles of random mixed states up to $D\approx 2^{12}$, the bracket must contain the Helstrom value $\tfrac12+\tfrac12\|p_1\rho_1-p_2\rho_2\|_1$. For geometrically uniform pure-state ensembles, the pretty good measurement is optimal, so the gap at the warm start must be at numerical zero. For random multi-class mixed ensembles small enough for an interior-point solver, the bracket must contain its optimum, and we report bracket width against iterations and wall-clock time for both certificate variants.

The scaling stage runs on the symmetry-reduced multi-copy class ensembles built from the amplitude encodings of the tabular datasets in Giuntini et al. and Hwang et al.. It sweeps $n$ upward and records, for each method, the largest $n$ completed and the certified relative gap reached.

The scientific stage evaluates three things on held-out folds at each $n$: balanced accuracy and F1 of the pretty good measurement, the same metrics for the certified measurement, and the training-ensemble bracket. Multi-class members of the 14-dataset suite are the primary targets, because two-class problems already have closed forms.

Two outcomes would be decisive. If the certified-optimal measurement's test accuracy rises monotonically wherever the pretty good measurement's dips, the reported non-monotonicity is a measurement artifact. If both measurements dip together while the training bracket keeps rising, as Giuntini's theorem requires, the decline is overfitting of class centroids. In that case copy number behaves as the regularizer that Hwang et al. describe, and the two papers are reconciled rather than in conflict. Either result is informative. The certificate is what lets us tell them apart.