Suppose you store a yes-or-no answer in a quantum memory. You can choose how to arrange its qubits, the basic units of quantum memory, but the machine will later get just one measurement from a fixed menu. You have to prepare the memory before you know which measurement will be requested.
Entangling qubits means preparing them in a shared quantum state that cannot be reproduced by preparing each qubit separately. It can make more of the measurements useful, but the device may only support small groups, and every extra operation is another opportunity for an error. A sensible arrangement depends on what people ask the memory to do.
In The Sample Complexity of Quantum Entanglement Allocation, I study how to choose that arrangement from past requests. The number of qubits turns out to be a poor guide to how much history you need. For some query structures, a larger memory creates more choices to learn. For others, adding more qubits need not require more history.
Start with three qubits
The smallest useful example stores a single classical bit across three qubits. The measuring device has three options: a joint measurement on the left pair, one on the right pair, or a different joint measurement on all three. Each returns one binary result. Think of these as three ways of asking for the same stored answer.
For now, assume the device works perfectly. It asks the all-three question half the time and splits the remaining requests equally between the two pairs. A simple preparation with no entanglement answers the pair questions perfectly, but the all-three question gives no information. Guessing on that half of the requests means getting a quarter of all answers wrong.
Entangling one pair makes the all-three question informative too, at the cost of losing one pair question. The error falls to one eighth. Move the request slider below, and the better pair changes.
All these preparations retain the bit perfectly. What changes is how often the permitted measurement can recover it. Keeping the bit does not guarantee that this device can retrieve it.
The device restriction matters. It performs a prescribed collective measurement, and the preparation happens before the request arrives. An ordinary copy of the bit is not available on the side. If the device could instead make arbitrary measurements, it could recover the bit from any of these preparations. The paper also studies how extra detector calls can substitute for entangled preparation.
What is a collective measurement here?
The three labels in the figure are ZZI, XXX, and IZZ. X and Z denote different measurement directions; I means leave that qubit alone. Each measurement returns the parity, a binary property of the group. The prescribed detector must preserve quantum coherence within each parity outcome. Measuring every qubit separately and combining the answers can destroy that coherence, so it is a different operation. Entanglement in the preparation is judged relative to this fixed interface, not against every possible measuring device.
Learn the arrangement from requests
With a longer memory, there are too many useful groupings to choose by inspection. The paper gives an exact way to find the best one for a family of queries arranged along a path.
Associate each query with a position on the path. Choose which queries the memory will answer reliably, subject to one rule: every uninterrupted run of chosen positions must fit inside the allowed group size. The preparation entangles the qubits in each run. Queries left out of the selection yield no information in this ideal example, so the best selection gives up as little request probability as possible. Their qubits stay in the memory.
If you already knew the request frequencies, an algorithm could compute the best selection. A learner gets only a finite history. It counts how often each query appeared and optimizes those counts. A short history can make an uncommon query look important or miss a useful query altogether.
The comparison that matters is with the best arrangement under the same group limit. The gap between their error rates is the cost of having to learn. More observations usually shrink that gap, though any one history can be misleading. The figure lets you draw another history without changing the underlying requests.
The remaining question is how much history this choice can require as the memory grows.
Size is only part of the story
A long path contains many places where a small change in demand can move a useful group boundary. In difficult cases, the learner needs to resolve small differences all along the path.
Now arrange the queries into a region with two sides, where every query on one side connects to every query on the other. Under the paper's rules, a maximal useful selection is either a whole side or a small mixed selection. Adding positions inside that region does not create the same sequence of boundary decisions as extending a path.
The paper proves matching upper and lower bounds for these families. On a path, the learning rate depends on the number of positions. For regions with this two-sided structure, connected through a bounded number of designated positions, it depends on the number of regions and the group limit. The leading rate has no dependence on how many positions sit inside each region.
That is a statement about the data needed to choose an arrangement. A larger region can still require more storage and more demanding measurements. And the bound describes the hardest request distributions in the family; a particular workload with an obvious best choice can be much easier.
The rates, for readers who want them
Let d be the number of qubits, k the largest allowed entangled group, and m the number of past requests. With a noiseless stored bit, the path's worst-case expected excess error is Θ((1/k) min{1, √(d log(k+1)/m)}), for d ≥ 3 and 2 ≤ k ≤ d−1. For r biclique regions satisfying the paper's size and bounded-port conditions, the rate is Θ(min{1, √(rk/m)}); constants may depend on the port bound. The figure holds k = 3 and r = 1. Its relative factors show the leading sample requirements in the small-error regime, with unknown constants omitted. They are not predicted error percentages. The proof covers more than the isolated region drawn here.
The machine needs its own measurements
Request history tells you which questions matter. It cannot tell you which physical connections are reliable. That takes calibration: repeated tests of the gates and measurements themselves.
The paper studies these two sources of uncertainty separately. In the simulation below, you can increase the request history while holding calibration fixed, or spend more on calibration with the same history. The learner uses both to choose groups of at most three qubits. Its competitor uses the request history but plans as if the connections were perfect.
Show the measurements and uncertainty
Population error under the paper's synthetic noise model, averaged over 32 independent workload/device instances per setting. Each instance crosses four request histories with four calibration panels. The shaded band is a pointwise 95% bootstrap interval for the learner using both data sources; the error reduction compares both learners on the same instances and has its own interval. Positive reductions mean fewer errors with calibration. Calibration uses B trials for each of d query reliabilities and d−1 edge parameters: B(2d−1) observations in total. The three constrained methods use groups of at most three; the full chain is outside that limit.
| Method | Error | 95% interval |
|---|
At the study's main comparison, with 63 qubits, 1,008 past requests, and 256 calibration trials per parameter, using both sources of information reduced the error from 9.79% to 8.58%. The paired improvement was 1.21 percentage points, with a 95% interval of 0.95 to 1.50 points. Those calibration trials amounted to 32,000 observations in total.
With very little calibration, more requests eventually stop helping much. With very few requests, even excellent calibration leaves the learner unsure which connections are worth using. The theory identifies both terms in the learning cost.
Try the low-noise setting, too. The full chain wins there. It is allowed to entangle all the qubits, whereas the learner has a limit of three. Across the study, the full chain had lower error in 76 of the 150 settings. Small groups help when the demand and connection quality make their savings worth the questions they give up.
What happened on the quantum computer
I also ran four fixed preparations on a 15-qubit path on IBM's ibm_marrakesh device. There were 7,680 measurement shots in the commissioning job, split equally among the preparations.
The full chain did best: 5.57% error, compared with 14.27% for the preparation using groups of at most three. The two tested preparations without entanglement had errors of 25.05% and 30.42%. Switch to individual requests to see where those averages come from.
The full chain has the lowest measured error.
Show exact counts and measurement details
Four fixed preparations on ibm_marrakesh, with 1,920 shots each: 64 for each of two bit values and each of 15 queries. Averages weight the queries equally. Whiskers are 95% simultaneous Hoeffding bounds across the four means, conditional on independent shots within this job; they do not measure drift between jobs. Individual-request values each pool 128 shots and are descriptive. These data do not include a learned preparation or a hardware learning curve.
| Preparation | Errors / shots | Error |
|---|---|---|
| Separate A | 481 / 1,920 | 25.05% |
| Separate B | 584 / 1,920 | 30.42% |
| Groups of three | 274 / 1,920 | 14.27% |
| Full chain | 107 / 1,920 | 5.57% |
For this device run, answering more of the queries was worth the extra operations. That agrees with the low-noise side of the simulation and puts a useful limit on the claim that smaller groups are better.
These are measurements of fixed preparations. The hardware experiment in which a learner sees a request history and then chooses its preparation is still unfinished. Separate coherence checks also did not establish that the whole path implements the ideal collective detector. The device results are evidence about these circuits, not a physical verification of the learning law.
The same choice appears in ordinary storage
There is a classical version of the allocation problem. Suppose requests ask for neighboring pairs of records, and a request is cheap when both records are on the same server. A limit on server capacity restricts how many consecutive pair requests one placement can serve locally. That is the same path selection problem, with records replacing qubits and server capacity replacing the group limit.
The paper gives a second exact construction for structured row-and-column requests, where the regional learning law applies. This connects the result to a practical question in database design: how much of the demand log do you need before choosing where records should live?
The public retail-data experiment is more modest. With 512 training baskets and space for 512 records per shard, the paper's basket-search method kept 10.90% of held-out invoices on one shard; simple frequency grouping kept 11.37%. The exact connection establishes a shared learning problem. That benchmark does not establish a better general-purpose database partitioner.
For quantum memories, the next decisive test is to learn an arrangement from past requests, freeze it, and measure its performance on independent hardware jobs. It will need to earn its advantage after paying for preparation and calibration. The theory tells us which request structures make that experiment worth trying, and how to distinguish a shortage of request data from a shortage of knowledge about the device.