The Sample Complexity of Quantum Entanglement Allocation

• URL: http://arxiv.org/abs/2609.10141v1
• Date: Wed, 09 Sep 2026 13:19:27 GMT
• Title: The Sample Complexity of Quantum Entanglement Allocation
• Abstract summary: We show that the answer depends on the allocation choices created by the queries.<n>A larger memory can require no more data.<n>We derive an exact tradeoff with extra fresh detector calls and transfer the learning law to structured transaction co-location.
• Score: 0.13537117504260623
• License: http://creativecommons.org/licenses/by/4.0/
• 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{d\log(k+1)/m}\}$, uniformly for $2\leq 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 papers

• Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff [32.65125292684608]
  We study one-dimensional mean estimation under a 1-bit communication constraint.<n>We find that for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate.
  arXiv  Detail & Related papers  (2026-09-08T10:52:52Z)
• A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States [2.5735476569508995]
  We construct a single fixed shallow quantum analyzer whose Born outcomes replace externally sampled settings as labels for reusable shadow snapshots.<n>The analyzer combines a freshly prepared $n$-qubit fiducial register $A$ with parallel Bell readout of $A$ and the unknown system $S$, producing one $2n$-bit record per copy.
  arXiv  Detail & Related papers  (2026-09-07T04:36:39Z)
• Random Projections for Multi-Copy Quantum Algorithms [3.995502708329505]
  Estimating nonlinear properties of quantum states is a central task in quantum information science.<n>Standard protocols based on swap tests require coherent operations on the full Hilbert space.<n>We introduce a framework for multi-copy measurements based on random projections onto lower-dimensional subspaces.
  arXiv  Detail & Related papers  (2026-06-18T13:49:14Z)
• Stochastic Sparse Attention for Memory-Bound Inference [19.301894658575502]
  We present Additive No-mulT Attention (SANTA), a method that sparsifies value-cache access by sampling $S ll n_k$ indices from the post-softmax distribution.<n>We also propose Bernoulli $qKmathsfT$ sampling as a complementary technique to sparsify the score stage.
  arXiv  Detail & Related papers  (2026-05-03T14:44:14Z)
• Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence [0.0]
  We present QKLA (Quantum Kullback-Leibler Amplitude estimation), a quantum algorithm that encodes a clipped logdensity ratio as amplitude estimation to recover a clipped KL expectation.<n>QKLA achieves a quadratic precision improvement, needing only $mathcalO((L/)log (1/)$ queries, where $L$ is the log-ratio clip bound.<n>Under per-stratum conditional-oracle access and a margin assumption for CI decisions, embedding this estimator in the PC algorithm compounds to an $widetilde (1/(L
  arXiv  Detail & Related papers  (2026-04-25T21:46:28Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
  We propose a novel adaptive mean estimator based solely on randomized threshold queries.<n>Our estimator's sample complexity has an extra multiplicative $O(log(/))$ penalty.<n>For both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly.
  arXiv  Detail & Related papers  (2026-04-09T04:49:21Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  We study high-dimensional multi-armed contextual bandits with batched feedback where the $T$ steps of online interactions are divided into $L$ batches. In specific, each batch collects data according to a policy that depends on previous batches and the rewards are revealed only at the end of the batch. Our algorithm achieves regret bounds comparable to those in fully sequential setting with only $mathcalO( log T)$ batches.
  arXiv  Detail & Related papers  (2023-11-22T06:06:54Z)
• Mixed-Precision Neural Network Quantization via Learned Layer-wise Importance [50.00102219630088]
  Mixed-precision quantization (MPQ) makes it hard to determine the optimal bit-width for each layer. We propose a joint training scheme that can obtain all indicators at once. For example, MPQ search on ResNet18 with our indicators takes only 0.06 seconds.
  arXiv  Detail & Related papers  (2022-03-16T03:23:50Z)
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning [58.6792963686231]
  Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. It is not clear how to choose the WNs' minimum update directions, the first minibatch sizes, and the local update frequency. We show that there is a trade-off curve between local update frequencies and local mini sizes, on which the above complexities can be maintained.
  arXiv  Detail & Related papers  (2021-06-19T06:13:45Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.