# The Sample Complexity of Quantum Entanglement Allocation

arXiv: https://arxiv.org/abs/2609.10141 · HTML: https://mlsanity.com/paper/2609.10141/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 42 references that are in the map.
- First posted on arXiv 9 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Learning to Cache With No Regrets](https://mlsanity.com/paper/1904.09849/) (2019)
- [On the Computational Complexity of Vertex Integrity and Component Order Connectivity](https://mlsanity.com/paper/1403.6331/) (2014)
- [Entanglement as Memory: Mechanistic Interpretability of Quantum Language Models](https://mlsanity.com/paper/2603.26494/) (2026)
- [A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity](https://mlsanity.com/paper/2607.09469/) (2026)

## Abstract (arXiv)

How many past requests are needed to decide which qubits should share entanglement? We show that the answer depends on the allocation choices created by the queries: a larger memory can require no more data. The memory stores a classical bit and answers requests through a fixed detector that preserves coherence within each measured sector. For independent commuting X- and Z-type Pauli queries, we characterize the full attainable prediction-contrast region and construct encodings that preserve the bit at every nonzero vertex. With sharp reports, a d-qubit path and groups of at most k qubits have minimax excess error after m requests proportional to k-1min1,√dlog(k+1)/m, uniformly for 2≤ k<d. Connected biclique regions can grow without increasing sample demand when depth, region count and connections per region stay bounded. Preparation noise introduces a separate calibration requirement. We derive an exact tradeoff with extra fresh detector calls and transfer the learning law to structured transaction co-location. Population-risk experiments test the statistical predictions. We also compare encodings on a native 15-qubit device and learned partitions on public purchase baskets. The full chain wins on the device; frequency grouping outperforms basket search in the largest-capacity retail setting.