Robustness of Hidden-Variable Theories and Matrix Scaling

AI summary

Overview

Research area: Quantum foundations (hidden-variable theories), theoretical computer science (complexity classes DQP/PDQP), and matrix scaling / optimization (Sinkhorn scaling, entropically regularized optimal transport).

Technical level: Advanced. The paper assumes comfort with density matrices, unitary evolution, the Born rule, Kullback–Leibler divergence, transportation polytopes, and complexity classes such as SZK.

Scope: The paper disproves Aaronson's conjecture that Schrödinger's hidden-variable theory is robust, introduces a capacity-constrained variant ("capped Schrödinger theory") that is robust, and proves new impossibility results that together settle which combinations of Aaronson's axioms can be satisfied simultaneously.

What This Paper Is About

Aaronson formalized hidden-variable theories axiomatically: a theory maps a density matrix and a unitary to a joint distribution over "hidden" values, whose marginals must match the Born rule for the initial and final states. His Schrödinger theory builds this distribution by running the Sinkhorn algorithm — alternately rescaling rows and columns of the entrywise modulus of the unitary — and he conjectured that this map is robust, meaning inverse-polynomially small perturbations of the inputs produce inverse-polynomially small perturbations of the output. This paper constructs a counterexample showing the conjecture is false, then repairs the theory with an added capacity constraint, and finally maps out exactly which axiom combinations remain achievable.

Key Contributions

1. A counterexample to robustness of Schrödinger theory. For every dimension N = 2n+1 ≥ 5 the authors construct a pure state and two unitaries that are exponentially close in entrywise max-norm (below 2^−n) yet whose induced joint distributions differ by more than 1/(10N) in some entry and by a constant in total variation distance. Because the two unitaries have the same support, the failure is attributable to the scaling procedure itself, not to a change in support.

2. A new robust theory: capped Schrödinger theory. The authors add a capacity constraint C_ji = 2|U_ji|·√(ρ_ii (UρU†)_jj) to the transportation polytope and define the joint distribution as the Kullback–Leibler (KL) projection of |U| onto that polytope. They prove this theory satisfies symmetry, indifference, robustness, and distributional product commutativity.

3. New impossibility theorems. No hidden-variable theory satisfies both indifference and product commutativity in the strong (matrix-level) sense, and no hidden-variable theory satisfies both indifference and decomposition invariance (the latter strengthens Aaronson's earlier result and implies Dieks' theory is not decomposition invariant).

4. A complete picture of axiom compatibility. Combined with Aaronson's earlier theorems, the results determine which axioms can hold simultaneously, summarized in Table 1 of the paper. All axioms except indifference are achievable by the Product Theory; if indifference is required, decomposition invariance must be sacrificed and commutativity can hold at best in the distributional product sense — which the capped Schrödinger theory attains along with symmetry and robustness.

Main Findings

• Schrödinger theory is not robust (Theorem 1.3). It fails even the weaker property of block robustness. Quantitatively: ‖U₀ − U₁‖_max < 2^−n while ‖P_ST(ρ,U₀) − P_ST(ρ,U₁)‖_max > 1/(10N).

• The underlying matrix-scaling instability (Lemma 3.1). For the cyclic 0/1 matrix M_δ with one entry set to δ, the unique doubly stochastic scaling has diagonal entry t_δ = 1/(1 + δ^(1/n)) and off-diagonal entry 1 − t_δ. Taking δ = 2^−n and δ′ = 2^−3n gives ‖M_δ − M_δ′‖_max < 2^−n while ‖T_δ − T_δ′‖_max = 2/9 — an exponentially small input change producing a constant-size output change.

• The lift to quantum mechanics. Since no unitary has the same support as M_δ for n ≥ 3, the authors enlarge the dimension to N = 2n+1, encoding matrix entries as rank-one projections |+⟩⟨+| and |−⟩⟨−| (which are orthogonal yet both have entrywise modulus J/2), with one extra dimension to complete the construction.

• Capped Schrödinger theory is robust (Theorem 1.4). The capacity bound allows elements of the feasible polytope for (ρ, U) to be projected into the polytope for a nearby input (ρ̃, Ũ). This makes each optimum an approximate minimizer for the other problem, and strong convexity of KL divergence (derived from Pinsker's inequality, D_KL ≥ ½‖P − Q‖₁²) converts this into closeness of the optima.

• The constant 2 in the capacity is tight. Using U_ε = [[√ε, √(1−ε)], [√(1−ε), −√ε]] with ρ = |+⟩⟨+|, one has p₁ + q₁ − 1 = √(ε(1−ε)) while q₁ → 1/2, so the necessary inequality p₁ + q₁ − 1 ≤ C₁₁ would fail for any constant smaller than 2 as ε → 0.

• Feasibility of the capped polytope is established via the max-flow min-cut theorem (Theorem 2.2); uniqueness of the minimizer follows from strict convexity.

• Indifference conflicts with decomposition invariance (Theorem 1.6) and with strong-sense product commutativity (Theorem 1.5).

• Aaronson's earlier limits still stand: no theory satisfies indifference together with distributional commutativity (Theorem 1.1), and none satisfies indifference, robustness, and decomposition invariance together (Theorem 1.2).

• Complexity-theoretic context. Aaronson showed graph isomorphism can be solved with bounded error by a deterministic classical polynomial-time machine making a single query to an oracle that samples histories from any indifferent and robust hidden-variable theory; this defines the class DQP, which contains SZK. Related work defines PDQP (product dynamical quantum polynomial time), characterizing quantum computers making non-collapsing measurements.

• AI disclosure. The paper states that the counterexamples, the capped theory, and its robustness proof were found by ChatGPT in interactive conversations with the authors; the manuscript itself was written entirely by the authors, who take full responsibility for its content.

Methodology in Plain English

The authors start with the observation that Schrödinger's rule is equivalent to a well-studied optimization: among all non-negative tables with prescribed row and column sums, pick the one closest to |U| in KL divergence. Sinkhorn's alternating rescaling converges to exactly this minimizer.

To break robustness, they design a sparse matrix with a cyclic structure and one very small entry δ. The scaling of such a matrix is forced into a rigid form, and a quantity called the cross-ratio — invariant under row and column rescaling — pins down the exact scaled values. Changing δ by an exponential factor barely changes the matrix but dramatically changes the scaling. Because that matrix is not the modulus of any unitary, they embed it into a larger Hilbert space using Hadamard-basis projections, so that each matrix entry becomes a two-dimensional block, plus one auxiliary dimension to make everything orthogonal.

To restore robustness, they add an upper bound on each entry: no cell of the joint distribution may exceed twice the value that a product of the two marginal square roots and |U_ji| would suggest. Intuitively, this prevents the flow from concentrating in a way that is hypersensitive to tiny input changes. The bounded polytope lets them shuttle a feasible point for one input into a feasible point for a nearby input; since KL divergence is strongly convex (via Pinsker's inequality), near-optimal points must be close, giving robustness.

The impossibility results are proved separately by constructing axiom-violating configurations, complementing Aaronson's earlier no-go theorems.

Why This Matters

• For quantum foundations: it sharpens the boundary of what hidden-variable theories can do. The paper delivers a complete answer to which of Aaronson's axioms can coexist, and identifies a specific theory that achieves the best feasible combination when indifference is required.

• For complexity theory: Aaronson's reduction from graph isomorphism (and the DQP ⊇ SZK result) requires an indifferent and robust theory. Since Schrödinger theory is now known not to be robust, that route needs a substitute — and the capped Schrödinger theory is exactly such a candidate, being both indifferent and robust.

• For matrix scaling: the counterexample shows that Sinkhorn scaling is genuinely unstable when matrices are sparse and entries are asymptotically small, explaining why existing quantitative robustness bounds require non-degeneracy assumptions (all-positive entries, common row support) that fail here.

Real-world applications (these are areas where matrix scaling is used, as reviewed in the paper's related-work section, not direct applications claimed for the new theory):

• Entropically regularized optimal transport, where Sinkhorn scaling is the standard solver; the paper notes that capacity-constrained versions have been studied but stability of the solution was not previously analyzed.
• Preconditioning linear systems in numerical linear algebra.
• Minimum-information and maximum-likelihood estimation of contingency tables in statistics, where the method is known as iterative proportional fitting or the RAS algorithm in economics.
• Approximation of the permanent of a non-negative matrix, and discrete analogues of the Schrödinger bridge problem.

Industry relevance: the paper's stability analysis speaks directly to practitioners of regularized optimal transport and statistical table estimation, warning that sparse inputs with tiny entries can produce wildly different outputs under scaling — and offering a capacity-constrained formulation with provable stability guarantees.

Future Directions

• Deriving explicit robustness parameters. The paper proves robustness exists (a polynomial relation between input perturbation and output perturbation) but does not state explicit polynomial degrees; extracting concrete bounds for the capped theory would make it usable in quantitative complexity reductions.

• Tightness of the capacity constant. The constant 2 is shown to be necessary for feasibility, but whether the same constant is optimal for stability, or whether a refined analysis allows a sharper bound in structured settings, is left open.

• Consequences for DQP and PDQP. With a robust and indifferent theory now available, the complexity-theoretic corollaries Aaronson derived — including the single-query graph isomorphism algorithm — can be revisited for the capped Schrödinger theory specifically.

• Stability of capacity-constrained entropic optimal transport. The authors note they are not aware of prior results on stability of the solution in this setting; their proof technique may generalize to broader capacity-constrained transport problems.

• Behavior at zero marginals. The treatment of columns with ρ_ii = 0 differs between the original and capped theories (a limiting procedure versus setting S_ji = |U_ji|²), and the paper notes other reasonable conventions exist; how these choices interact with the axioms is not fully resolved.

Target Audience

Researchers in quantum foundations and quantum information theory working on hidden-variable theories and the measurement problem; theoretical computer scientists interested in DQP, PDQP, SZK, and oracle-based complexity; and mathematicians working on matrix scaling, Sinkhorn's algorithm, and entropically regularized optimal transport who want to understand when the scaling limit is unstable. The paper is also relevant to mathematically mature readers in optimization who want a concrete, well-structured counterexample to naive stability intuitions.

Authors’ abstract

Motivated by quantum foundations and complexity theory, Aaronson formalized a hidden-variable theory inspired by a proposal by Schrödinger. To any quantum state and unitary, this Schrödinger theory assigns a joint probability distribution via the Sinkhorn algorithm: rescale the columns and rows of the entrywise modulus of the unitary so that the marginals match the Born rule for the initial and final quantum states, respectively. He conjectured that this map is robust, i.e., inverse polynomially small perturbations in the inputs lead to inverse polynomially small perturbations of the joint distribution, which is important for complexity theoretic applications. We present a counterexample to this conjecture: We construct a pure state and two unitaries that are exponentially close, yet the joint probability distributions assigned by the Schrödinger theory differ by at least an inverse-linear term in at least one entry, and by a constant in total variation distance. We also propose a modified version of Schrödinger's theory that satisfies robustness, while retaining all of its other desirable properties. This yields a complete picture of which axioms of Aaronson can be simultaneously satisfied by hidden-variable theories.