Quantum advantage in learning from experiments

• Quantum-enhanced experiments coherently transfer physical quantum information to quantum memory for later quantum processing, unlike conventional experiments that measure each copy and classically process the outcomes.Future applications may use analog simulators, gate-based quantum computers, or quantum sensors equipped with quantum processors interacting coherently with the physical world.Source: §I · pp. 1–2, Figure 1 · p. 2
• Experiments with up to 40 superconducting qubits demonstrate that substantial quantum advantage persists on noisy processors and quantum memories.The proof-of-principle experiments were performed on a Google Sycamore processor.Source: §I · pp. 1–2
• Quantum-enhanced strategies require polynomially many experiments where conventional strategies require exponentially many, including learning physical states and quantum processes.For some tasks, storing two copies of a state and performing an entangling measurement suffices; related advantages apply to learning quantum processes. [9]Source: §I · pp. 1–2
• The work establishes exponential advantages for learning many non-commuting observables, even when the measured state is unentangled.This result builds on observations in [12].Source: §I · p. 2
• The paper demonstrates quantum advantage in learning the symmetry class of a physical evolution operator and proves an exponential advantage for learning the principal component of a noisy state.The symmetry-class result is inspired by [9] [12], while the noisy-state result extends an indication in.Source: §I · p. 2

Proof framework

• The proofs represent classical learners as decision trees and derive information-theoretic lower bounds by comparing transitions for different measured physical systems.All three results are formulated as theorems, with precise statements and proofs provided in the Supplemental Material.Source: §II · p. 2

Predicting observables

• At least order 2^n conventional experiments are required to predict one observable’s absolute value, whereas a constant number suffices quantum-enhanced.The quantum advantage persists for unentangled states and can be achieved with simple entangling measurements on pairs of copies.Source: §II · p. 3

Quantum PCA

• At least order 2^(n/2) conventional experiments are needed to learn a fixed principal-component property, while a constant number suffices quantum-enhanced.The exponential separation is rigorously established against all conventional algorithms and also holds for near-term quantum PCA proposals [16].Source: §II · p. 3
• The quantum PCA separation does not contradict polynomial-time classical algorithms that assume exponentially precise access to every matrix entry, because obtaining that precision requires exponentially many experiments.Those assumptions therefore differ from the experimental-access model considered here.Source: §II · p. 3

Learning quantum processes

• For any polynomial-time quantum process, approximate output-state models require at least order 2^n conventional experiments but only polynomially many quantum-enhanced experiments.The quantum-enhanced model predicts outputs accurately on average over a distribution of input states.Source: §II · pp. 3–4

Pauli-observable estimation

• The Pauli-estimation demonstration uses Bell measurements on pairs of stored copies and a gated recurrent neural network trained on noiseless small-system simulations before testing larger systems.The model is trained for n<8 and evaluated experimentally for 8≤n≤20.Source: §III · p. 4
• Despite noisy storage and processing, quantum-enhanced experiments achieve a significant advantage in estimating Pauli-observable expectation values, compared with conventional experiments requiring exponentially many copies.The task asks whether two announced Pauli observables have the larger absolute expectation value, with performance measured by prediction accuracy and experiments compared at 70% accuracy.Source: §III · pp. 4–5

Quantum-dynamics symmetry learning

• For dynamics classification, quantum-enhanced experiments entangle system qubits with memory qubits, apply the unknown evolution twice with a swap between applications, and finish with Bell measurements.Conventional experiments repeatedly evolve |0⟩^⊗n and measure each output qubit in the Y basis, where the distinguishing signal can be exponentially small.Source: §III · p. 5
• Quantum-enhanced data cleanly separates time-reversal-symmetric from general quantum dynamics, whereas conventional data shows no discernable class separation.The distinction is learned by unsupervised kernel PCA without labeled training data; Figure 3 compares data from 500 quantum-enhanced repetitions with 1000 conventional repetitions.Source: Figure 3 · p. 5, §III · p. 6

IV. Outlook

• Quantum-enhanced strategies using quantum memory and processing can predict physical-system properties with exponentially fewer experiments than conventional strategies.The advantage remains achievable with unlimited classical processing and even when the physical system exhibits only classical correlations.Source: §IV · p. 6
• The work shifts quantum-advantage analysis toward learning about a priori unknown physical systems, informing quantum machine learning [27] and quantum sensing.This contrasts with prior work focused primarily on computational tasks with known inputs.Source: §IV · p. 6
• Experiments with up to 40 qubits show substantial quantum advantage on today’s noisy intermediate-scale quantum platforms.The experiments used supervised and unsupervised machine learning models with data obtained from quantum-enhanced experiments.Source: §IV · p. 6

Supplementary information

• The supplement covers experimental details, quantum-information background, proofs of exponential advantage, observable prediction, quantum principal component analysis, process learning, and bounded-memory results.It also includes experiments on learning physical states and dynamics, additional experimental results, and performance characterization data.Source: Supplementary information · p. 8

A. Experimental details

• Experiments used a Google Sycamore processor with up to 53 transmon qubits, whose dominant errors were 3%–7% readout and 0.5%–1.5% two-qubit-gate errors.Single-qubit gate errors were approximately 0.05%–0.5%, and the chip was controlled through Cirq and TensorFlow Quantum.Source: §A.1 · p. 8

A.1. General description

• Learning experiments varied system sizes from 4 to 40 qubits, selecting contiguous low-error patches and using swaps when needed to satisfy connectivity requirements.The experimental complexity differed substantially for learning states, one-dimensional dynamics, and two-dimensional dynamics.Source: §A.1 · p. 9

A.2. Experiments on learning physical states

• Unknown states and dynamics were implemented directly on the processor while learning algorithms remained unaware of them, emulating imperfect data collection from a physical system.The state-learning experiments separated unknown-state generation, conventional experiments, quantum-enhanced experiments, and supervised neural-network prediction.Source: §A.1 · p. 9, §A.2 · p. 9

Procedure for generating the class of unknown states

• The unknown states have the form ρ = 2^-n(I + αP), where α ∈ {−0.95, 0.95} and P is an unknown n-qubit Pauli operator.The states are unentangled but possess strong non-local classical correlations, and copies are prepared using randomized constant-depth circuits.Source: Procedure for generating the class of… · p. 9
• The preparation procedure samples Pauli eigenstates qubit by qubit, using η = sign(α) and updating η with selected eigenvalues to control the final state ensemble.Identity factors are randomized, while non-identity factors follow the procedure specified for whether later non-identity factors remain.Source: Procedure for generating the class of… · p. 9
• The resulting density operator is an ensemble of tensor-product Pauli eigenstates with no entanglement across qubits, while step 3 ensures |tr(Pρ)| = 0.95.For qubit i, the procedure assigns either |0⟩⟨0| or |1⟩⟨1| with equal probability with probability 0.05.Source: Procedure for generating the class of… · p. 9

Conventional experiments

• Conventional experiments use randomized Pauli measurements on fresh copies of ρ, with classical post-processing to predict expectation values of observables.The optimal randomized Clifford strategy has polynomial-size circuits but exponential classical post-processing, whereas randomized Pauli measurements are used here because Clifford circuits are infeasible on current noisy devices.Source: Conventional experiments · pp. 9–10
• For n≥10, conventional experiments remain near random-guessing accuracy after 1000 experiments and fail to reach 70% accuracy within 5000 experiments.Randomized Clifford and Pauli measurements require exponentially many experiments for the announced-observable task.Source: Conventional experiments · p. 10

Quantum-enhanced experiments

• Quantum-enhanced experiments perform an entangling Bell measurement across two copies of ρ, producing a classical bitstring of size 2n for each experiment.The comparison uses the same selected qubits as conventional experiments; 500 quantum-enhanced repetitions consume 1000 state copies, matching 1000 conventional experiments.Source: Quantum-enhanced experiments · pp. 10–11
• The Bell measurements are compiled into Sycamore-native gates, including SYC and phased XZ operations, with inverse-gate differences compensated numerically.The hardware compilation is tailored to the Sycamore processor rather than using the simple Hadamard-CNOT Bell-measurement circuit directly.Source: Quantum-enhanced experiments · pp. 10–11

A supervised neural network model using data from quantum-enhanced experiments

• The supervised model compares two Pauli strings by processing Bell-measurement bitstrings through a three-layer recurrent, aggregation, and Siamese-style architecture.A GRU inner layer processes each bitstring and Pauli operator, the aggregation layer averages across experiments, and the outer layer compares the resulting scalar scores.Source: A supervised neural network model… · p. 11
• Only the GRU-based inner layer is trainable, while the aggregation and outer layers are fixed operations that compare the two Pauli-operator scores.The inner layer uses an encoding dimension of 30, a GRU with 30 neurons, and a decoding layer mapping 30 neurons to 2 neurons.Source: A supervised neural network model… · pp. 11–12
• The model is trained on noiseless simulations for n<8 and uses per-qubit measurement-error calibration to expand noisy experimental data before prediction.Training uses synthetic states ρ=2^-n(I+αP), cross-entropy loss, and Adam; prediction expands each measurement to 20 calibrated variants.Source: A supervised neural network model… · pp. 12–13

A.3. Experiments on learning physical dynamics

• The dynamics experiments use random 1D and 2D quantum circuits, with half time-reversal symmetric and half general unitary, and generate both conventional and quantum-enhanced measurement data.The resulting data are processed by an unsupervised model to learn a low-dimensional representation of the physical dynamics.Source: §A.3 · p. 13
• The unsupervised model successfully classifies quantum circuits by symmetry class from quantum-enhanced data, but not from conventional data.The experiments analyze 180 circuits in each of the general-unitary and T-symmetric classes.Source: §A.3 · p. 13

1D dynamics

• For 1D dynamics, T-symmetric circuits replace random single-qubit gates with real orthogonal gates and replace SYC entangling gates with numerically optimized T-symmetric gates.The optimized two-qubit gate is accepted when the Frobenius norm of its imaginary part falls below 10^-9.Source: 1D dynamics · p. 14
• In the 1D quantum-enhanced protocol, Bell pairs are prepared, the unknown dynamics is applied twice with a system-memory swap between applications, and every pair is measured in the Bell basis.Each experiment produces a 2n-bit outcome, with the preparation, swap, and measurement implemented using Sycamore-native gates.Source: 1D dynamics · p. 14

2D dynamics

• The 2D protocol alternates qubit layouts and depth-4 1D random circuits so that repeated rounds connect different system-qubit sets and eventually produce globally entangled dynamics.The layout changes are implemented by swapping system and memory qubits.Source: 2D dynamics · p. 15

An unsupervised machine learning model

• The unsupervised model forms bitwise first- and second-moment features, maps them through a Gaussian-kernel feature space, and uses kernel PCA to obtain a low-dimensional representation for classification.A one-dimensional representation classifies circuits by splitting the representation at its midpoint; two-dimensional representations are analyzed in Appendix A.4.Source: An unsupervised machine learning model · p. 15

A.4. Additional experimental results

• The second learned dimension for quantum-enhanced 1D data separates T-symmetric dynamics into groups associated with evolution-depth parity, while the primary axis captures the general-versus-T-symmetric distinction.The model therefore identifies the symmetry distinction as the dominant structure and parity as a less prominent structure.Source: §A.4 · p. 15
• Quantum-enhanced experiments substantially outperform conventional experiments at distinguishing general unitary dynamics from T-symmetric dynamics in both physical experiments and noiseless simulations.The comparison is reported for the model’s classification accuracy in Supplementary Fig. 4.Source: §A.4 · p. 15

A.5. Performance and characterization data

• Readout errors typically range from 3% to 7%, while single-qubit gate errors are around 0.001 to 0.005 and two-qubit gate errors around 0.01 to 0.05.Measurement errors limit quantum-state learning; dynamics-learning experiments are limited by both measurement and two-qubit gate errors, so layouts avoid qubits with the worst readout performance.Source: §A.5 · pp. 15–17
• Quantum-enhanced experiments accurately reveal time-reversal symmetry patterns, whereas conventional experiments fail to do so for the studied one- and two-dimensional dynamics.Supplementary Figure 3 compares unsupervised representations using quantum-enhanced and conventional experimental data.Source: Figure 3 · p. 16

B.1. Definition and properties of quantum processes

• Quantum processes are completely positive, trace-preserving linear maps, encompassing unitary evolution and open-system dynamics realized through an environment and partial trace.The review introduces quantum processes as the general evolution of density matrices and states their CPTP characterization and Stinespring representation.Source: §B.1 · pp. 17, 19

B.2. Definition and properties of POVMs

• POVMs generalize projective measurements: positive semidefinite operators summing to identity produce outcome i with probability tr(F_iρ), and rank-1 POVMs suffice without loss of generality.The construction uses an ancilla, unitary evolution, and projective measurement to implement generalized measurements.Source: §B.2 · pp. 20–21

C. Mathematical framework for proving exponential advantage

• The lower-bound framework combines learning-tree representations, reductions to distinguishing tasks, information-theoretic bounds, and a partially revealed many-versus-one task; noise only strengthens conventional lower bounds.These tools are presented to establish exponential advantages across physically relevant learning tasks, building partly on [12].Source: C. Mathematical framework for proving… · p. 21

C.1. Tree representation; Experiments for learning physical world; Dynamics of the learning algorithm

• With unrestricted classical memory, each experiment and measurement outcome gives a unique tree transition, so an algorithm using T experiments follows a root-to-leaf path of depth T.The framework analyzes physical-state and process learning, where memory-dependent POVMs and input states determine experimental outcomes.Source: Dynamics of the learning algorithm · p. 22, Experiments for learning physical world · p. 22, Figure 9 · p. 23

Reduction

• Lower bounds reduce learning to distinguishing a null state or channel from all alternatives, choosing a null hypothesis close to every alternative while preserving the target property’s distinguishability.The central question is how hard it is to distinguish the alternative hypothesis from the null hypothesis, following [12].Source: Reduction · pp. 22–23
• The reduction defines the task as distinguishing one null state/process from many alternative states/processes.The alternative hypothesis contains multiple elements, whereas the null hypothesis contains only one.Source: Reduction · p. 23

Information-theoretic lower bound

• Unknown states or processes induce different transition and leaf probabilities in the depth-T execution tree, so the leaf distribution depends on both the physical instance and the learning algorithm.Supplementary Figure 10 illustrates the null distribution from one state/process and the alternative distribution obtained by averaging distributions over multiple possibilities.Source: Information-theoretic lower bound · p. 23, Figure 10 · p. 24
• LeCam’s two-point method bounds distinguishing success using the total variation distance between null and alternative leaf distributions.The alternative prior can be chosen to yield the largest lower bound, and increasing the number of experiments increases tree depth and permits a monotonically increasing upper bound on total variation, yielding a lower bound on T as a function of success probability p.Source: Information-theoretic lower bound · pp. 23–24

C.3. Many-versus-many distinguishing task

• Many-versus-many distinguishing separates a random state or channel from subset 𝒜 versus its complement ℬ, each selected with probability 1/2.The task reduces learning to distinguishing which of two hypotheses holds when each hypothesis contains many possible states or channels.Source: §C.3 · p. 24
• The framework represents conventional learning algorithms as learning trees and converts a target prediction accuracy into a total-variation condition that lower-bounds the number of experiments.This derivation applies to many-versus-many distinguishing and extends analogously to partially revealed information.Source: §C.3 · pp. 24–25

C.4. Partially-revealed many-versus-one distinguishing task

• Partially revealing information makes many-versus-one distinguishing easier, but substantial revealed information may not significantly improve classical-memory distinguishing power.When the conditional null-versus-alternative probabilities remain uniform, the resulting lower bound on experiments is weaker because accurate prediction is easier.Source: §C.4 · p. 26

C.5. Presence of noise

• Noise cannot decrease the classical-memory lower bound: any bound on total variation distance and required experiments in the noiseless setting also holds with noise.Noise on input states, measurements, or physical processes can be absorbed into a modified learning tree with classical memory.Source: §C.5 · pp. 26–27

C.6. Related works

• Prior work established polynomial or exponential separations for testing, reconstructing, predicting, and characterizing quantum states, channels, and dynamics under various strategy restrictions, [9] [12], -.These works cover ancilla assistance, communication, restricted conventional strategies, and bounded-depth quantum learning algorithms.Source: §C.6 · p. 27

D. Predicting highly-incompatible observables

• Conventional experiments measure each copy of an n-qubit state individually, whereas quantum-enhanced experiments collectively process multiple copies with a quantum computer to produce entangled measurement data.Both approaches ultimately retain only classical measurement data for prediction.Source: D. Predicting highly-incompatible… · p. 27, Figure 12 · p. 28
• The learner predicts an observable expectation chosen from an exponentially large set whose members may not commute, making simultaneous measurement impossible and naïve individual measurement exponentially sample-intensive.The set is {O_1, O_2, . . . , O_M}, with M exponential in n.Source: D. Predicting highly-incompatible… · p. 28

D.1. Exponential advantage in predicting absolute value of a single observable

• Quantum memory can predict expectation values for M arbitrary observables using 𝒪(n log(M)/𝜖^4) copies, remaining polynomial even when M is exponential.This uses shadow tomography [47].Source: §D.1 · p. 28
• The separation instance samples either the maximally mixed state with a random nonidentity Pauli observable or a signed 0.9-Pauli-correlated state with that Pauli observable.The states contain no quantum entanglement, and any constant coefficient below 1 can replace 0.9.Source: §D.1 · p. 28
• The single-observable separation improves on, which achieved Ω(2^n/3) versus 𝒪(n) but required verifying exponentially many observables.The earlier task therefore required exponential verification time, unlike the present single-observable prediction task.Source: §D.1 · p. 29
• 𝒪(1) quantum copies versus Ω(2^n) conventional copies suffice to predict |tr(Oρ)| within 0.25 additive error with probability at least 0.8.This establishes an exponential-versus-constant separation for a single observable rather than an exponentially large set of observables.Source: §D.1 · p. 29

D.2. A constant upper bound for quantum-enhanced experiments

• The quantum-enhanced algorithm separates learning from prediction, performing entangled measurements in the learning phase before predicting the desired property.The protocol builds on results presented in.Source: §D.2 · p. 29

Learning phase

• During learning, the protocol performs N_Q rounds of two-copy entangled measurements, measuring corresponding qubits from both copies in the Bell basis.The Bell basis consists of four maximally entangled two-qubit states.Source: Learning phase · p. 29
• Each learning round measures every one of the n qubit pairs, producing Bell-basis outcomes that are stored in classical memory.The supplied passage specifies storage using 2^n N_Q classical bits.Source: Learning phase · p. 29

Prediction phase

• N_Q = Θ(1) quantum experiments estimate |tr(Oρ)| to error 0.25 with probability at least 0.8 for every allowed observable O.This establishes the constant upper bound for quantum-enhanced experiments in Theorem 6.Source: Prediction phase · p. 31

Reduction to partially-revealed many-versus-one distinguishing task

• The reduction distinguishes the null state ρ = I/2^n from alternatives ρ = (I + 0.9sP)/2^n, where the target observable is P.The corresponding absolute expectations are 0 and 0.9, so 0.25-accurate prediction distinguishes the hypotheses with success probability at least 1 − δ.Source: Reduction to partially-revealed… · p. 31

Total variation distance

• The conventional lower-bound analysis expresses distinguishing power through total variation distance between leaf distributions generated by the learning algorithm.The leaf is the algorithm’s final classical memory state, and the proof derives the relevant distance from root-to-leaf path probabilities.Source: Total variation distance · pp. 31–32

Upper bound for total variation distance

• Jensen’s inequality and the ±1 eigenvalue structure of P upper-bound the total variation distance used in the conventional prediction lower bound.These steps control the leaf-distribution separation before converting it into a measurement lower bound.Source: Upper bound for total variation distance · p. 32

Lower bound for the number of measurements

• Combining the total-variation estimate with expectation bounds yields the exponential lower bound on the number of conventional experiments.The proof sets δ = 0.2, corresponding to success probability at least 0.8.Source: Lower bound for the number of… · p. 33

D.3. An exponential lower bound for conventional experiments

• Conventional experiments face an exponential lower bound for predicting |tr(Oρ)| to error 0.25 with success probability at least 1 − δ.The proof reduces prediction to a partially-revealed many-versus-one distinguishing task and bounds its total variation distance.Source: §D.3 · p. 31, Lower bound for the number of… · p. 33

D.4. An exponential lower bound for comparing absolute values

• For Task 1, quantum-enhanced strategies achieve classification accuracy at least 1 − δ using only O(log(1/δ)) experiments, whereas conventional strategies require an exponential number for accuracy 1 − δ.Source: §D.4 · p. 34

Lower bound for total variation distance; Combining upper and lower bounds

• Le Cam’s method bounds comparison accuracy through total variation distance, and combining its lower and upper bounds proves the conventional lower bound stated in Theorem 7.The argument averages over distinct uniformly sampled P and Q and uses triangle inequalities together with the earlier estimates.Source: Lower bound for total variation distance · pp. 34–35, Combining upper and lower bounds · p. 36

E. Performing quantum principal component analysis

• Quantum PCA predicts ⟨φ|O|φ⟩ for an unknown mixed state whose top eigenvalue exceeds the others by a constant factor.The task targets the top eigenvector's observable expectation up to a small additive error.Source: E. Performing quantum principal… · p. 36
• The quantum PCA algorithm in [13] uses conditional exp(−iρt), quantum Fourier transform, and measurement to prepare eigenstates and read their eigenvalues.With a constant number of copies, eigenvalues have constant accuracy and prepared eigenstates have constant fidelity; repeating the procedure yields constant-accuracy estimates.Source: E. Performing quantum principal… · pp. 36–37
• Ω(2^n/2) conventional copies versus O(1) quantum-enhanced copies are required to estimate ⟨φ|Z_1|φ⟩ within 0.25 error at probability at least 0.8.The state is an unknown n-qubit mixed state with a constant spectral gap above its top eigenvector.Source: E. Performing quantum principal… · p. 37
• Near-term proposals [16] estimate tr(Z_1ρ^2)/tr(ρ^2) using entangling Bell measurements over at most two copies of ρ at a time.When the principal-component eigenvalue is constant, quantum-enhanced experiments over a constant number of copies achieve any constant error, whereas single-copy measurements require exponentially many copies.Source: E. Performing quantum principal… · p. 37
• Ω(2^n/2) conventional copies versus O(1) quantum-enhanced copies are required to estimate tr(Z_1ρ^2)/tr(ρ^2) within 0.25 error at probability at least 0.8.This near-term task assumes an n-qubit state with an eigenvalue separated from all others by a constant.Source: E. Performing quantum principal… · p. 37

E.1. An exponential lower bound for conventional experiments

• The lower-bound proofs reduce quantum PCA and its near-term analogs to many-versus-many distinguishing and then bound total variation distance.This establishes the exponential conventional-experiment lower bounds for both Theorem 8 and Theorem 9.Source: §E.1 · p. 37

Reduction to many-versus-many distinguishing task

• T = Ω(2^n/2) measurements are required to distinguish the two hypotheses in the conventional setting, implying the lower bounds of Theorems 8 and 9.The hypotheses encode opposite principal components and observable values, so successful conventional prediction would distinguish them with probability at least 0.8.Source: Reduction to many-versus-many… · pp. 38, 40

E.2. An exponential lower bound using pseudorandomness

• The pseudorandom construction avoids the impracticality of preparing Haar-random states, whose preparation from simple initial states requires exponential circuit depth.Consequently, the pseudorandom setting transfers the quantum principal-component-learning advantage, although the separation is between arbitrary polynomial-time quantum learners rather than strictly exponential sample complexity.Source: §E.2 · pp. 40, 42
• The pseudorandom-state result requires the existence of quantum-secure one-way functions, an unproven but widely believed cryptographic assumption.Under this assumption, pseudorandom quantum states can be constructed efficiently.Source: §E.2 · pp. 40–41
• Any polynomial-time conventional algorithm cannot distinguish ρ_A(|φ_k⟩) from ρ_B(|φ_k⟩) when |φ_k⟩ is sampled from a pseudorandom-state family.The result applies to states generated efficiently and relies on computational indistinguishability from Haar-random states for polynomial-time quantum algorithms.Source: §E.2 · pp. 41–42

F. Learning a polynomial-time quantum process

• The paper establishes a rigorous exponential separation between conventional and quantum-enhanced learning for polynomial-time quantum processes.This section studies learning an unknown process ℰ on n qubits generated by a polynomial-size circuit with hidden ancillas.Source: F. Learning a polynomial-time quantum… · p. 42, §F.1 · p. 43

F.1. Problem setting

• A polynomial-time quantum process applies p unknown two-qubit gates to an n-qubit input with m initialized ancillas, then hides the ancillas to produce an n-qubit mixed output.The process is called polynomial-time when m, p = poly(n).Source: §F.1 · pp. 42–43
• The learning goal is to construct an approximate model Ẽ that accurately predicts the output state on average over an input distribution 𝒟.Prediction error is measured using the trace norm ‖X‖_1.Source: §F.1 · p. 43

F.2. Rigorous statements

• Ω(2^n) accesses are necessary conventionally, whereas quantum-enhanced learning uses Õ(poly(n) log(1/δ)/ε^4) accesses to construct an approximate process model.The conventional lower bound follows by reducing process learning to predicting tr(Oρ) within error 0.25; the quantum upper bound holds with probability at least 1−δ.Source: §F.2 · pp. 43–44
• The exponential conventional lower bound is realized by an O(n)-gate process that always outputs a hard state ρ, regardless of its input state σ.Ancilla-assisted Bell-state preparation and parity encoding generate the maximally mixed state or (I+0.9sP)/2^n, establishing the reduction.Source: §F.2 · pp. 43–44

F.3. Proof of polynomial upper bound in Theorem 11

• The polynomial upper bound applies to processes built from p=poly(n) two-qubit gates, but bounds only process accesses, not the learning procedure’s computational complexity.The proof uses a diamond-norm covering net and quantum hypothesis testing, which is available in the quantum-enhanced but not conventional setting.Source: §F.2 · pp. 43–44, §F.3 · p. 44

Covering net

• An ε′-covering net approximates every process on n input qubits, m ancillas, and p two-qubit gates, with errors accumulated across the composed gates.The construction discretizes two-qubit channels in diamond norm, accounts for all possible qubit pairs, and sets the per-gate approximation scale to ε′/p.Source: Covering net · p. 45

Learning via Hypothesis Selection: Protocol and Analysis

• The learning protocol samples input states, stores outputs for every covering-net hypothesis in quantum memory, and uses quantum hypothesis selection [47] to choose an approximate process.The selected hypothesis is compared through product-state trace distance, while concentration bounds control the sampled inputs and candidate hypotheses.Source: Learning via Hypothesis Selection:… · pp. 46–47
• The protocol requires Õ(p^4/ε^4) accesses to the process for constant failure probability, with an additional Θ(log(1/δ)) factor for general failure probability.The constant-success analysis combines covering-net concentration with Theorem 12, and independent repetitions plus clustering reduce the failure probability.Source: Learning via Hypothesis Selection:… · p. 48

G. Predicting highly-incompatible observables with bounded quantum memory

• With insufficient additional quantum memory, predicting highly-incompatible observables requires exponentially many experiments.This section substantively generalizes the earlier highly-incompatible-observable results to bounded quantum memory.Source: G. Predicting highly-incompatible… · p. 48

G.1. Background and statement of results

• The first realizable quantum-memory advantage improves both query and gate complexity, and was demonstrated experimentally on the Sycamore quantum computer.This addresses the prior result’s exponential gate-complexity barrier, which prevented a device-realizable memory advantage.Source: §G.1 · p. 49
• When k=n, the distinguishing task requires only a constant number of copies of ρ and O(n) quantum gates.The total register size is then 2n, enabling the Appendix D.2 algorithm.Source: §G.1 · p. 49
• When k<n, determining |tr(Oρ)| requires Θ(2^(n−k)/3) copies of ρ.The task uses an unknown state drawn between the maximally mixed state and a random fixed nonidentity Pauli perturbation, with O revealed after the copies are processed.Source: §G.1 · p. 49

G.2. Review of learning tree framework for bounded quantum memories

• The bounded-memory model holds each received n-qubit copy alongside k memory qubits, while allowing arbitrary quantum processing and unlimited classical data.For k<n, only one copy can be held at a time because the non-memory registers cannot store an additional copy.Source: §G.2 · p. 49, §G.1 · p. 49
• A bounded-memory protocol can be represented by a depth-T rooted learning tree whose nodes encode the measurement transcript and an unnormalized k-qubit memory state.The root carries the initial state Σ0; each node applies a POVM to ρ⊗Σρ(u), and child nodes record the resulting outcome and updated memory state.Source: §G.2 · pp. 50–51
• The tree supports adaptive protocols because prior measurement outcomes determine later POVMs, while tr(Σρ(u)) gives transcript probability and normalization gives the memory state.Alternating quantum processes and measurements can be consolidated into a single POVM at each round.Source: §G.2 · pp. 50–51

Theorem 13

• Any algorithm using n+k qubits needs T≥Ω(2^(n−k)/3) copies of ρ to determine |tr(Oρ)| with probability at least 2/3.This is Theorem 13 for shadow tomography with partial reveal using a bounded quantum memory.Source: §G.3 · pp. 51–52

Proof framework

• Good Paulis correspond to states hard to distinguish from I/2^n along a learning-tree path, whereas bad Paulis reveal too much information [12].This distinction controls how much a POVM can change the memory’s distinguishing ability at each node.Source: §G.3 · p. 51
• For any learning-tree edge, at most 2^−(n−k)/3·(4^n−1) Pauli operators are bad, yielding at most T·2^−(n−k)/3·(4^n−1) bad Paulis along a root-to-leaf path.This bound is Lemma 7, cited as Fact 6.5 of [12].Source: §G.3 · p. 51