Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.15501 · PRX Quantum

Predicting Adaptively Chosen Observables in Quantum Systems

Jerry Huang, Laura Lewis, Hsin-Yuan Huang, John P. Preskill

Published Jan 28, 2026• 2 citations
arXivHTMLPDF

Abstract

Recent advances have demonstrated that O ( log  M ) measurements suffice to predict M properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω ( M ) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of M adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in M , respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only O ( log  M ) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.

DOI
10.1103/xhn1-vnp9

Related papers

Finite-Size Limits of Adaptive Pauli Prediction

Luofei Wang, Boyu Liu, Zihe Wang +1 more

The expectation values of a predetermined set of Pauli observables can be predicted using only a few copies of a quantum state. However, when later observables depend on earlier predictions, how the system size constrains the required number of copies remains unclear. We use classical interactive fingerprinting codes to establish this constraint. A compact Pauli-parity encoding embeds the fingerprinting interaction into the quantum prediction task, allowing any quantum prediction mechanism on the constructed diagonal states to be simulated by a classical response strategy subject to the same information constraints. We show that accurate prediction from too few copies would violate the guarantees of the fingerprinting code. For $n$ qubits and $M$ adaptively chosen Pauli observables, requiring all predictions to be simultaneously accurate to a fixed additive error with probability at least $2/3$ yields the worst-case lower bound $N^*(n,M)=Ω(\sqrt{\min\{n,M\}})$ on the required number of copies. For $M\le n$, this lower bound matches known upper bounds. In particular, $n$ adaptive predictions require $Θ(\sqrt{n})$ copies, whereas the same number of predetermined queries requires only $O(\log n)$ copies. This separation persists even for diagonal states and commuting observables.

quant-pharXiv:2610.13652•Oct 12, 2026•0 citations

Heisenberg-Limited Adaptive Gradient Estimation for Multiple Observables

Kaito Wada, Naoki Yamamoto, Nobuyuki Yoshioka

In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of nontrivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of M general observables within root mean squared error ε simultaneously, using O ( ε − 1 M log  M ) queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit 1 / ε , a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables M . The proposed method is an adaptive version of the quantum gradient-estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is O ( M ) , which is independent from the estimation precision ε unlike noniterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., ε ≪ 1 in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.

arXiv:2406.03306•PRX Quantum•Apr 10, 2025•5 citations

Lower Bounds for Learning Quantum States with Single-Copy Measurements

Angus Lowe, Ashwin Nayak

We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of \(\Omega (r^2 d/\epsilon ^2)\) and \(\Omega (r^2 d^2/\epsilon ^2)\) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of \(\exp (O(d))\) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.

arXiv:2207.14438•ACM Transactions on Computation Theory•Feb 13, 2025•35 citations

Exponential quantum advantages in learning quantum observables from classical data

Riccardo Molteni, Casper Gyurik, Vedran Dunjko

Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that $$BQP$$ B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.

arXiv:2405.02027•npj Quantum Information•Jan 10, 2026•38 citations

Learning Quantum States Without Entangled Measurements

Angus Lowe

How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.

•Oct 22, 2021•4 citations

Lower Bounds on Learning Pauli Channels With Individual Measurements

Omar Fawzi, Aadil Oufkir, Daniel Stilck França

Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Ω(23nε−2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by [1] is essentially optimal. In the adaptive setting, we show a lower bound of Ω(22.5nε−2) for ε = O(2−n), and a lower bound of Ω(22nε−2) for any ε > 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.

arXiv:2301.09192•IEEE Transactions on Information Theory•Jan 9, 2025•25 citations
Recent advances have demonstrated that O ( log  M ) measurements suffice to predict M properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω ( M ) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of M adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in M , respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only O ( log  M ) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.
The expectation values of a predetermined set of Pauli observables can be predicted using only a few copies of a quantum state. However, when later observables depend on earlier predictions, how the system size constrains the required number of copies remains unclear. We use classical interactive fingerprinting codes to establish this constraint. A compact Pauli-parity encoding embeds the fingerprinting interaction into the quantum prediction task, allowing any quantum prediction mechanism on the constructed diagonal states to be simulated by a classical response strategy subject to the same information constraints. We show that accurate prediction from too few copies would violate the guarantees of the fingerprinting code. For nnn qubits and MMM adaptively chosen Pauli observables, requiring all predictions to be simultaneously accurate to a fixed additive error with probability at least 2/32/32/3 yields the worst-case lower bound N∗(n,M)=Ω(min⁡{n,M})N^*(n,M)=Ω(\sqrt{\min\{n,M\}})N∗(n,M)=Ω(min{n,M}​) on the required number of copies. For M≤nM\le nM≤n, this lower bound matches known upper bounds. In particular, nnn adaptive predictions require Θ(n)Θ(\sqrt{n})Θ(n​) copies, whereas the same number of predetermined queries requires only O(log⁡n)O(\log n)O(logn) copies. This separation persists even for diagonal states and commuting observables.
In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty that is quantified by variance or mean squared error of measurement outcome. While the uncertainty can be reduced by averaging several samples, the number of samples should be minimized when each sample is very costly. This is especially the case for fault-tolerant quantum computing that involves measurement of multiple observables of nontrivial states in large quantum systems that exceed the capabilities of classical computers. In this work, we provide an adaptive quantum algorithm for estimating the expectation values of M general observables within root mean squared error ε simultaneously, using O ( ε − 1 M log  M ) queries to a state preparation oracle of a target state. This remarkably achieves the scaling of Heisenberg limit 1 / ε , a fundamental bound on the estimation precision in terms of mean squared error, together with the sublinear scaling of the number of observables M . The proposed method is an adaptive version of the quantum gradient-estimation algorithm and has a resource-efficient implementation due to its adaptiveness. Specifically, the space overhead in the proposed method is O ( M ) , which is independent from the estimation precision ε unlike noniterative algorithms. In addition, our method can avoid the numerical instability problem for constructing quantum circuits in a large-scale task (e.g., ε ≪ 1 in our case), which appears in the actual implementation of many algorithms relying on quantum signal processing techniques. Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
We study the problems of quantum tomography and shadow tomography using measurements performed on individual, identical copies of an unknown d -dimensional state. We first revisit known lower bounds [ 23 ] on quantum tomography with accuracy ε in trace distance, when the measurement choices are independent of previously observed outcomes, i.e., they are nonadaptive. We give a succinct proof of these results through the χ 2 -divergence between suitable distributions. Unlike prior work, we do not require that the measurements be given by rank-one operators. This leads to stronger lower bounds when the learner uses measurements with a constant number of outcomes (e.g., two-outcome measurements). In particular, this rigorously establishes the optimality of the folklore “Pauli tomography” algorithm in terms of its sample complexity. We also derive novel bounds of Ω(r2d/ϵ2)\Omega (r^2 d/\epsilon ^2)Ω(r2d/ϵ2) and Ω(r2d2/ϵ2)\Omega (r^2 d^2/\epsilon ^2)Ω(r2d2/ϵ2) for learning rank r states using arbitrary and constant-outcome measurements, respectively, in the nonadaptive case. In addition to the sample complexity, a resource of practical significance for learning quantum states is the number of unique measurement settings required (i.e., the number of different measurements used by an algorithm, each possibly with an arbitrary number of outcomes). Motivated by this consideration, we employ concentration of measure of χ 2 -divergence of suitable distributions to extend our lower bounds to the case where the learner performs possibly adaptive measurements from a fixed set of exp⁡(O(d))\exp (O(d))exp(O(d)) possible measurements. This implies in particular that adaptivity does not give us any advantage using single-copy measurements that are efficiently implementable. We also obtain a similar bound in the case where the goal is to predict the expectation values of a given sequence of observables, a task known as shadow tomography. Finally, in the case of adaptive, single-copy measurements implementable with polynomial-size circuits, we prove that a straightforward strategy based on computing sample means of the given observables is optimal.
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQPBQPBQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Ω(23nε−2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by [1] is essentially optimal. In the adaptive setting, we show a lower bound of Ω(22.5nε−2) for ε = O(2−n), and a lower bound of Ω(22nε−2) for any ε > 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.