The Sample Complexity of Quantum Entanglement Allocation

arXiv:2609.10141v1 Announce Type: cross Abstract: 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^{-1}min{1,sqrt{dlog(k+1)/m}}, uniformly for 2leq 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.

Related

• Sample Complexity of Composite Quantum Hypothesis Testing
• Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements
• Quantum Generative Diffusion Model: A Fully Quantum-Mechanical Model for Generating Quantum State Ensemble

Source: arXiv cs.LG | 2026-09-10