Certified Task Ordering for Quantum Learners

When a model learns tasks one after another, the order of the tasks can matter a great deal. Li and Hiratani showed that in a simple model the best order can do up to seven times better than the worst, and that a good order can be chosen from about 1% of the data, provided you can estimate how similar the tasks are to one another. This proposal asks what that recipe costs when each task is an unknown quantum state. Every data point is then one copy of the state, and measuring a copy destroys it.

Our main claim is that choosing an order is itself a measurement problem, and its cost depends on how the learner is allowed to look at the data. Suppose the learner must measure each copy on its own and keep only classical records. Then estimating how similar two states are can require a number of copies that grows exponentially with the number of qubits. Quantum pseudorandom states make this concrete: they are states that no efficient test can tell apart from fully random ones. If instead the learner can compare one copy from each of two tasks directly, the cost is independent of size. We propose an order-selection rule that keeps collecting copies until it can certify, with a controlled false-claim rate, that its chosen order beats a random one. We then test whether the certified order still pays off once the copies spent on planning are subtracted from the learning budget.

Background and gap

Three groups of prior work set the stage, and each plays a different role.

The first group motivates the problem. Optimal Task Order for Continual Learning of Multiple Tasks analyses a linear teacher-student model and derives two ordering rules. The "periphery-to-core" rule says to learn atypical tasks first and representative ones last. The "max-path" rule says to make neighbouring tasks as dissimilar as possible. The paper reports that the best order performed "up to seven times better" than the worst, and that the order can be estimated from "approximately 10 images per task." It assumes cheap, reusable classical samples and never asks how confident the order estimate is. Task-Attentive Transformer Architecture for Continual Learning of Vision-and-Language Tasks Using Knowledge Distillation shows that order effects survive engineering fixes. Even with a 5% replay buffer, placing the hard OKVQA task late gives roughly 22% forgetting, against 74% for plain fine-tuning.

The second group constrains what any quantum version can do. Predicting Features of Quantum Systems using Classical Shadows introduces classical shadows, compact classical records built from randomized single-copy measurements. These are cheap for observables that touch few qubits but exponentially expensive for global ones. Limitations of measure-first protocols in quantum machine learning proves that protocols which measure first and learn afterwards need exponentially many samples on concept classes built from quantum pseudorandom phase states, while coherent multi-copy protocols need polynomially many. Pseudorandom Quantum States supplies the phase-state construction we reuse. It also establishes no-cloning for these states, which rules out keeping a buffer of quantum copies to replay later.

The third group supplies methods. Online Learning of Quantum States and Adaptive Online Learning of Quantum States give online learners that update a density-matrix hypothesis from measurement feedback. The adaptive version tracks drifting states, but it treats the order of the drift as given rather than chosen. Universal Sequential Changepoint Detection of Quantum Observables via Classical Shadows uses e-values, which are betting-based test statistics that stay valid whenever you decide to stop, to make sequential decisions with controlled false alarms. We adapt that machinery from detecting change to certifying an order.

Physics adds a methodological warning. Small samples produce hints at the 2σ level that later disappear (Branching fractions for psi(2S) -> gamma eta' and gamma eta). Search over many hypotheses erodes significance after the "trials factor" correction (INDICATIONS OF INTERMEDIATE-SCALE ANISOTROPY OF COSMIC RAYS WITH ENERGY GREATER THAN 57 EeV IN THE NORTHERN SKY MEASURED WITH THE SURFACE DETECTOR OF THE TELESCOPE ARRAY EXPERIMENT). Choosing the best of $K!$ orders from noisy similarity estimates is exactly such a search.

No paper in the file studies task order for quantum learners. None asks how many copies are needed to justify an order choice. None checks whether the planning cost is recovered downstream.

Core claim

Write $F_{ij} = |\langle\psi_i|\psi_j\rangle|^2$ for the overlap between task states $i$ and $j$, and $d_{ij} = 1 - F_{ij}$ for their dissimilarity. Both ordering rules depend only on the matrix $d$. The max-path score of an order $\pi$ is

$$D(\pi) = \sum_{t=1}^{K-1} d_{\pi_t \pi_{t+1}},$$

the total dissimilarity between consecutive tasks. The periphery-to-core rule ranks tasks by their average similarity to all the others.

We make three predictions. First, with coherent pairwise access, a SWAP test on one copy of each of two states returns a coin with bias $(1+F_{ij})/2$. Certifying a score gap $\Delta$ between orders should therefore cost about $1/\Delta^2$ copies, by the usual inverse-square law for estimating a mean, and this cost should not depend on the number of qubits $n$. Second, with measure-first access, the cost should grow exponentially in $n$ on pseudorandom phase-state families. Their single-qubit and few-qubit marginals are essentially maximally mixed, so classical shadows see a flat similarity matrix, consistent with the separation in Limitations of measure-first protocols in quantum machine learning. Third, on families whose similarity structure shows up in local observables, measure-first access should remain cheap.

The quantity that matters in practice is the net benefit. That is the order-induced gain in final average loss, minus the loss from moving the planning copies out of the learning budget.

Research program

Task families. We build task families with a prescribed similarity graph. Following Li and Hiratani, the graphs are chains, rings and trees. Each task is a phase state $2^{-n/2}\sum_x (-1)^{f_i(x)}|x\rangle$ with $f_i = f \oplus g_i$. Here $f$ is a shared pseudorandom function, and $g_i$ is a mask that flips a chosen fraction of signs. If $p_{ij}$ is the fraction of inputs on which $g_i$ and $g_j$ differ, then $F_{ij} = (1-2p_{ij})^2$ exactly, so the mask overlaps set the similarity graph.

At simulable sizes, from 4 up to roughly 18 qubits, truly random functions stand in for pseudorandom ones. We state plainly that pseudorandomness is the asymptotic justification, not something the simulation tests. A pseudoentangled variant uses subset phase states from Quantum Pseudoentanglement. These carry low true entanglement that an efficient test cannot see, so entanglement-based shortcuts should mislead. A control family realises the same similarity graph with product states and shallow circuits, whose overlaps are visible locally.

Certification procedure. A planning phase draws copies task by task, or pair by pair for coherent access. Each draw updates an e-process, a running betting score in the style of Zecchin et al. The score tests the null hypothesis that the currently best-scoring order is no better than a uniformly random order. Because the same data are used to pick the order and to test it, the procedure accounts for selection through either sample splitting or a union bound over a candidate set of orders. Planning stops when the score passes $1/\alpha$, or when the budget runs out, in which case the planner falls back to a random order.

Downstream learners. Two learners consume the remaining copies one task window at a time. The main one is the matrix multiplicative-weights online learner from Online Learning of Quantum States. It is computationally exponential, which is acceptable at $n \le 8$. Unlike the original analysis, it receives single-shot binary outcomes rather than exact expectation values. Its final hypothesis is a single state, so forgetting is directly its loss on earlier targets. This makes it a clean, nonlinear test of both ordering rules beyond the linear teacher-student setting.

The second learner is a shared-parameter variational circuit with task-specific final layers, trained with a SWAP-test loss. It probes interference between tasks in shared parameters, which is the regime the Li and Hiratani analysis leaves open.

Baselines

The naive reference is a uniformly random order with no planning, so every copy goes to learning. Any method must beat this after paying for its planning copies. The two ends of the range are the oracle best and oracle worst orders, computed from exact $F_{ij}$. Their ratio is our analogue of the seven-fold gap in Optimal Task Order for Continual Learning of Multiple Tasks. For quantum task ordering, no reported result was found on Lacuna, so the oracle gap must be measured here before anything else is interpreted.

The strongest existing method is Li and Hiratani's plug-in rule. It estimates $d$ from a fixed small sample, about 1% of the per-task copy budget, takes the best max-path or periphery-to-core order, and does not test whether the choice is justified. We run it with shadow-based overlap estimates and, separately, with SWAP-test estimates. Both versions get the same total copy budget as our method and the same candidate-order set. Our method beats it if it reaches equal or lower final average loss at equal total copies. It must also do so with a false-certification rate at most $\alpha$ under a null family in which all tasks are equally similar, where the plug-in rule will report gains that do not replicate.

A robustness baseline is the adaptive learner of Adaptive Online Learning of Quantum States, run on random orders with the full budget. It tests whether adaptivity alone removes the need to plan. A memory-unbounded upper bound stores every shadow and trains jointly on all tasks. This is not continual learning, but it tells us how much order sensitivity is really a memory limitation.

Two ablations isolate the key ingredients. The first keeps the stopping rule but replaces coherent overlap estimates with shadow estimates, isolating the access model. The second keeps coherent estimates but drops the stopping rule in favour of the fixed 1% budget, isolating certification.

Why not just…?

Why not just estimate similarity from classical shadows? Shadows are the natural first choice and work well on structured states. The shadow paper reports 0.99 fidelity on GHZ states with a constant number of measurements up to 162 qubits. Bootstrapping Classical Shadows for Neural Quantum State Tomography reports 8-qubit GHZ infidelity as low as 5%. The overlap of two unknown, globally spread states is a global quantity, though. Both the Pauli bottleneck and the measure-first separation suggest the required copies will grow exponentially on our phase-state families. The first ablation measures this curve directly. If shadow costs stay flat in $n$ on the phase family, our central claim fails, and we will report that.

Why not just store shadows and replay them, which removes order effects? This is a real threat. A learner that keeps every classical record can train jointly, and order then stops mattering. The memory-unbounded baseline quantifies exactly this. Our claim concerns learners with bounded memory, or coherent learners that cannot keep copies because of no-cloning. If bounded shadow replay at realistic sizes closes most of the gap, the practical case for planning shrinks to the coherent setting, and we will say so.

Why not just order by a cheap local proxy such as single-qubit entropies? On the control family this may work as well as our method, and we expect to report that honestly. On phase and pseudoentangled families the local marginals are nearly identical across tasks by construction, so such proxies should do no better than random ordering. The proxy baseline is run on both families so the comparison is explicit.

Why not just use an adaptive online learner and ignore order? Adaptive regret bounds control how well the learner tracks the current task, not how much it retains about earlier ones. Running Shen et al.'s learner on random orders tests whether tracking implies retention in our setting.

Proposed experiments and decisive checks

The first decisive check is the scaling of copies-to-certify with $n$, from 4 to 18 qubits, under each access model and each family. The prediction is roughly constant cost for SWAP tests everywhere, exponential cost for shadows on phase families, and flat cost for shadows on the control family. A matching curve on the pseudoentangled family would show that the barrier comes from global structure rather than from entanglement alone.

The second check is downstream. For the online learner at $n \le 8$ and $K$ between 5 and 8 tasks, we measure final average loss, with per-task forgetting, under certified, plug-in, random and oracle orders, all at equal total copies. The question is whether certified planning recovers a meaningful share of the oracle gap net of its own cost.

The third check is calibration. On exchangeable null families, we compare how often each method claims an order improvement against how often that improvement holds up on fresh copies. This is the trials-factor test, applied to curriculum choice.

Together these determine whether ordering advice for quantum learners can be followed at all, and under which access model.