Two companies want to know whether shared quantum entanglement would let their systems coordinate better than any classical rule. Neither will reveal its own data. In a nonlocal game (a coordination task where two players answer questions without communicating and win if their answers satisfy a rule), the answer depends on both parties' private statistics, such as how often each one receives each question. The gain from entanglement is often thin. In the CHSH game the quantum winning probability is about 0.853 against a classical 0.75, and many other binary games have separations near 0.012 (Analysis of boolean functions related to binary input binary output two-party nonlocal games).
We propose to compute the best quantum and classical strategies for such a jointly-private game under homomorphic encryption. Homomorphic encryption lets a server compute on data it cannot read, but each multiplication uses up a limited "depth" budget. Restoring that budget requires bootstrapping, an expensive refresh that dominates runtime (Circuit Bootstrapping: Faster and Smaller). The engine we use is a replicator-style learning dynamic whose every step is a low-degree polynomial, so it runs natively under encryption. The central observation is that the quantum-to-classical winning ratio fixes how accurate the optimization must be, and therefore predicts how many bootstraps it costs to certify an advantage.
Core Claim
For two-player XOR games (nonlocal games whose winning rule depends only on the parity of the two binary answers), Tsirelson's theorem, the tool used by Quantum strategies are better than classical in almost any XOR game, writes both the classical and quantum values as one optimization. That optimization differs only in the dimension $d$ of the vectors each player assigns to its questions:
$$\Delta(d) = \max_{\|u_s\| = \|v_t\| = 1,\; u_s, v_t \in \mathbb{R}^d} \sum_{s,t} M_{st}\, \langle u_s, v_t \rangle .$$
Here $M_{st} = \pi(s,t)(-1)^{f(s,t)}$ combines the probability $\pi$ of question pair $(s,t)$ with the winning parity $f$. Setting $d = 1$ gives the classical bias $\Delta_{cl}$ (bias means the winning probability minus one half, times two). Setting $d = n$ gives the quantum bias $\Delta_q$.
Ascent on the unit sphere is the square-root-coordinate form of replicator dynamics. Replicator dynamics is the evolutionary update in which strategies grow in proportion to how much they beat the population average. Ascent on the sphere can be written as a polynomial step:
$$u_s \leftarrow u_s + \eta\,(g_s - \langle u_s, g_s\rangle u_s), \qquad g_s = \sum_t M_{st} v_t ,$$
where $\eta$ is a step size. This step is followed by one cheap Newton correction, $u_s \leftarrow u_s(3 - \|u_s\|^2)/2$, which keeps the norm near one. The full iteration, including Bob's symmetric update, costs a handful of multiplicative levels. It needs no exponentials and no divisions, so it can run under CKKS, the approximate real-number encryption scheme of Floating-Point Homomorphic Encryption.
The quantitative claim follows from the iteration count. Suppose the dynamic reaches accuracy $\varepsilon$ in about $c/\varepsilon$ iterations. That rate is borrowed from the $O(1/\epsilon)$ guarantee for quantum best response in Quantum Potential Games, Replicator Dynamics, and the Separability Problem, and we test it rather than assume it. To beat classical play, the learned quantum strategy must come within $\Delta_q - \Delta_{cl} = \Delta_q(1 - 1/r)$ of optimal, where $r = \Delta_q/\Delta_{cl}$ is the winning ratio. The bootstrap count is then roughly
$$B \approx \frac{k\,c}{L\,\Delta_q\,(1 - 1/r)} ,$$
where $k$ is the number of levels each iteration uses and $L$ is the number of levels available between bootstraps.
On this estimate, CHSH-like games with separation 0.103 should cost roughly an order of magnitude fewer bootstraps than games with separation 0.012. For random XOR games with $r \approx 1.305$ and $\Delta_q \approx 2/\sqrt{n}$, the cost should grow like $\sqrt{n}$. The winning ratio, usually read as a physics quantity, becomes a cryptographic price tag.
Setting and Relation to Prior Work
The privacy setting is as follows. Alice holds her question distribution $p_A$, Bob holds $p_B$, and the winning predicate is public, so $M = \mathrm{diag}(p_A)\,\Sigma\,\mathrm{diag}(p_B)$, where $\Sigma$ is the public matrix of $\pm 1$ parity signs. Neither party can solve the problem alone. Alice encrypts $p_A$ under her key, and Bob runs both players' updates homomorphically, packing all vectors into SIMD slots as in CryptoNets. Bob returns Alice's vectors encrypted, and returns his own encrypted but masked with random values he can later remove. The outputs are each party's strategy and the achieved bias. Any information these outputs reveal is inherent to the task.
Prior work supplies the mechanism but not this question. Quantum Potential Games, Replicator Dynamics, and the Separability Problem builds non-commutative replicator and matrix multiplicative-weights dynamics for common-interest quantum games. It also warns that discrete updates can stall at non-Nash fixed points. Its variables are product density matrices, which corresponds to separable correlations, and all of its arithmetic is free plaintext. We instead optimize the entangled (Tsirelson) value, and we make arithmetic depth the binding cost.
Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence studies competitive games, where dynamics cycle. Our XOR games are cooperative, so the dynamic is an ascent. Recurrence is therefore not the concern, but its warnings about discretization drift motivate our noise ablation. A Quantum Protocol for Sampling Correlated Equilibria Unconditionally and without a Mediator replaces a cryptographic mediator with quantum coin flipping in order to sample equilibria. It does not compute the value of a game whose specification is private.
The encryption literature constrains the design. SecureNets and SAFENet show that polynomial substitutes for non-polynomial operations trade accuracy against depth. That is exactly why we prefer the polynomial sphere-replicator step over matrix multiplicative weights, which needs an exponential and a normalizing division.
Research Program
The work has three parts.
First, we derive and implement the encrypted sphere-replicator iteration. This covers level accounting per iteration, a bootstrap schedule, and a step-size rule that keeps vector norms inside the region where a single Newton correction is accurate even after CKKS rounding noise.
Second, we measure the iteration-to-accuracy curve in plaintext across vector dimensions $d$. The aim is to test whether the $1/\varepsilon$ rate holds, and whether spurious local optima of the kind reported by Lin et al. appear at small $d$. We expect them to fade as $d$ grows, but treat that as a hypothesis.
Third, we validate the bootstrap-cost formula against measured encrypted runs. We fit $c$ and the exponent, and check whether the ratio $r$ predicts cost across games with very different separations.
A secondary question is whether encryption noise behaves like small random perturbation of the dynamic, which would be harmless or even helpful for escaping stalls, or like systematic drift that biases the result. We separate the two by injecting matched synthetic noise into plaintext runs.
Baselines
The plaintext oracle is the exact Tsirelson semidefinite program on the decrypted game, together with brute-force classical values for $n$ up to about 20. It defines 100% accuracy and the true advantage margin. As a sanity anchor on random games, our plaintext runs should reproduce the average ratio of about 1.305 reported by Quantum strategies are better than classical in almost any XOR game.
The naive "do nothing" reference uses no joint computation. Each party assumes the other's distribution is uniform, solves its own public surrogate game in plaintext, and plays the result on the true game. Encrypted joint optimization must beat this surrogate's realized bias to justify its cost.
The strongest existing method family is interactive secure multi-party computation. We run the same sphere-replicator iteration under CrypTen-style secret sharing on identical games, hardware, and iteration counts, in both LAN and simulated WAN settings, and report latency and bytes. The only reported numbers on Lacuna concern image inference, not game optimization: CrypTen at 0.25 s per inference on the Malaria model versus 549 s and 56 GB for HE-Transformer (A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification). No reported result was found on Lacuna for encrypted optimization of nonlocal-game strategies. Beating secret sharing means lower end-to-end time or traffic at equal certified bias in the WAN regime. We expect to lose in the LAN regime, and will report it.
Two ablations isolate the key ingredient. The first replaces the polynomial step with encrypted matrix multiplicative weights on the Gram matrix, using polynomial approximations of the exponential and the division, under the same depth budget. The second sets $d = 1$, which runs encrypted classical replicator dynamics at the same cost per iteration. This gives the "found classical" strategy that the quantum result must beat with a matched budget.
Why not just…?
Why not just run the plaintext solver inside a trusted enclave? Enclaves are about three orders of magnitude faster than homomorphic encryption on inference: 0.14 s versus 549 s in A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification. For parties willing to trust hardware vendors, this is the right answer and we say so. The proposal targets the threat model where hardware trust is excluded. Its contribution, the bootstrap-cost law, is still informative because it tells such parties how much they pay for removing that trust.
Why not just use secret sharing, since the parties are interacting anyway? This is a genuine threat. Secret sharing avoids bootstrapping, and the sphere step is cheap arithmetic for it. Its cost is rounds of communication: hundreds of iterations, several multiplications each, every one a network round trip. The head-to-head baseline above settles which wins in each latency regime, and we expect a crossover. If secret sharing dominates everywhere, the cost law still transfers, with rounds in place of bootstraps.
Why not just have each party optimize against a guessed distribution? That is the do-nothing baseline. When separations are near 0.012, a surrogate built from a misspecified distribution can easily land below the true classical value. We measure how often that happens across non-uniform distributions placed on the binary-input games of Analysis of boolean functions related to binary input binary output two-party nonlocal games. If the surrogate rarely loses the advantage, the joint computation is unnecessary and the paper reports that.
Why not just use matrix multiplicative weights, which has better theory? Its exponential and normalization require high-degree polynomial approximations. SAFENet and SecureNets show that such approximations cost either depth or accuracy. The matched-depth ablation directly measures whether the extra levels pay for themselves.
Proposed Experiments
The games are CHSH and the binary-input partition games, with separations from 0.012 to 0.103, each placed under 200 random non-uniform private input distributions. We add random Bernoulli XOR games for $n$ from 4 to 26, matching the range of Ambainis et al.'s simulations. Encryption uses a standard CKKS parameter set at 128-bit security.
The metrics are: achieved bias as a fraction of the semidefinite optimum; the certification rate, meaning the fraction of instances where the encrypted quantum strategy beats both the brute-force classical value and the matched-budget $d = 1$ strategy; bootstrap count; wall-clock time; and bytes transferred.
The decisive check is a held-out prediction. We fit the bootstrap-cost formula on random XOR games and then predict bootstrap counts for the binary partition games before running them. If measured cost scales with $1/(\Delta_q(1 - 1/r))$ within a factor of two across this range, the winning ratio is validated as a cost predictor. If it does not, the iteration-rate assumption is wrong, and the plaintext rate curves show where.
A second check fixes the depth budget and compares the polynomial replicator step against matrix multiplicative weights on certification rate. A third compares CKKS runs with plaintext runs carrying matched injected noise, to test whether encryption noise changes where the dynamic converges.
References
- Analysis of boolean functions related to binary input binary output two-party nonlocal games
- Circuit Bootstrapping: Faster and Smaller
- Quantum Strategies Are Better Than Classical in Almost Any XOR Game
- Floating-Point Homomorphic Encryption
- Quantum Potential Games, Replicator Dynamics, and the Separability Problem
- CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy
- Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence
- A Quantum Protocol for Sampling Correlated Equilibria Unconditionally and without a Mediator
- SecureNets: Secure Inference of Deep Neural Networks on an Untrusted Cloud
- SAFENet: A Secure, Accurate and Fast Neural Network Inference
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification