Measuring properties of quantum systems is a fundamental problem in quantum mechanics. We provide a simple method for estimating the expectation value of observables with an unknown quantum state. The idea is to use a data structure to sample the terms of observables based on the Pauli decomposition proportionally to their importance. We call this technique operator shadow as a shorthand for the procedure of preparing a sketch of an operator to estimate properties. Only when the numbers of observables are small for multiple local observables, the sample complexity of this method is better than the classical shadow technique. However, if we want to estimate the expectation value of a linear combination of local observables, for example the energy of a local Hamiltonian, the sample complexity is better on all parameters. The time complexity to construct the data structure is $2^{O(k)}$ for $k$-local observables, similar to the post-processing time of classical shadows.
Measuring properties of quantum systems is a fundamental problem in quantum mechanics. We provide a simple method for estimating the expectation value of observables with an unknown quantum state. The idea is to use a data structure to sample the terms of observables based on the Pauli decomposition proportionally to their importance. We call this technique operator shadow as a shorthand for the procedure of preparing a sketch of an operator to estimate properties. Only when the numbers of observables are small for multiple local observables, the sample complexity of this method is better than the classical shadow technique. However, if we want to estimate the expectation value of a linear combination of local observables, for example the energy of a local Hamiltonian, the sample complexity is better on all parameters. The time complexity to construct the data structure is 2O(k) for k-local observables, similar to the post-processing time of classical shadows.
Efficiently learning expectation values of a quantum state using classical shadow tomography has become a fundamental task in quantum information theory. In a classical shadows protocol, one measures a state in a chosen basis W after it has evolved under a unitary transformation randomly sampled from a chosen distribution U. In this work we study the case where U corresponds to either local or global orthogonal Clifford gates, and W consists of real-valued vectors. Our results show that for various situations of interest, this ``real'' classical shadow protocol improves the sample complexity over the standard scheme based on general Clifford unitaries. For example, when one is interested in estimating the expectation values of arbitrary real-valued observables, global orthogonal Cliffords decrease the required number of samples by a factor of two. More dramatically, for k-local observables composed only of real-valued Pauli operators, sampling local orthogonal Cliffords leads to a reduction by an exponential-in-k factor in the sample complexity over local unitary Cliffords. Finally, we show that by measuring in a basis containing complex-valued vectors, orthogonal shadows can, in the limit of large system size, exactly reproduce the original unitary shadows protocol.
Abstract Efficiently learning expectation values of a quantum state using classical shadow tomography has become a fundamental task in quantum information theory. In a classical shadows protocol, one measures a state in a chosen basis W after it has evolved under a unitary transformation randomly sampled from a chosen distribution U . In this work we study the case where U corresponds to either local or global orthogonal Clifford gates, and W consists of real-valued vectors. Our results show that for various situations of interest, this ‘real’ classical shadow protocol improves the sample complexity over the standard scheme based on general Clifford unitaries. For example, when one is interested in estimating the expectation values of arbitrary real-valued observables, global orthogonal Cliffords typically decrease the required number of samples by a factor of two. More dramatically, for k -local observables composed only of real-valued Pauli operators, sampling local orthogonal Cliffords leads to a reduction by an exponential-in- k factor in the sample complexity over local unitary Cliffords. Finally, we show that by measuring in a basis containing complex-valued vectors, orthogonal shadows can, in the limit of large system size, exactly reproduce the original unitary shadows protocol.
Classical shadows are a powerful method for learning many properties of quantum states in a sample-efficient manner, by making use of randomized measurements. Here we study the sample complexity of learning the expectation value of Pauli operators via "shallow shadows," a recently proposed version of classical shadows in which the randomization step is effected by a local unitary circuit of variable depth t. We show that the shadow norm (the quantity controlling the sample complexity) is expressed in terms of properties of the Heisenberg time evolution of operators under the randomizing ("twirling") circuit-namely the evolution of the weight distribution characterizing the number of sites on which an operator acts nontrivially. For spatially contiguous Pauli operators of weight k, this entails a competition between two processes: operator spreading (whereby the support of an operator grows over time, increasing its weight) and operator relaxation (whereby the bulk of the operator develops an equilibrium density of identity operators, decreasing its weight). From this simple picture we derive (i) an upper bound on the shadow norm which, for depth t∼log(k), guarantees an exponential gain in sample complexity over the t=0 protocol in any spatial dimension, and (ii) quantitative results in one dimension within a mean-field approximation, including a universal subleading correction to the optimal depth, found to be in excellent agreement with infinite matrix product state numerical simulations. Our Letter connects fundamental ideas in quantum many-body dynamics to applications in quantum information science, and paves the way to highly optimized protocols for learning different properties of quantum states.
There is growing interest in constructing quantum devices that control increasingly large numbers of quantum systems. There is a tremendous need for methods that can measure the quality and other properties of these devices. Such measurements often amount to learning the expectation value of a quantum observable with respect to the quantum state of the device. Learning expectation values is also a key component in many well-known applications such as quantum machine learning and quantum optimization algorithms. Because of the large system sizes involved, it is essential to find methods for learning expectation values that are efficient with respect to the system size. Existing methods that have rigorous guarantees and are practical to implement are often not optimal for observables of interest. Other methods are heuristic, or require the use measurement protocols that are challenging to implement experimentally with current technology. In this study, we propose an estimation procedure, The Optimal Observable expectation value Learner or TOOL, that can learn the expectation values of observables using the outcomes of any given measurement protocol. We show that there is a seminorm on the set of all observables, which we call the minimax norm, that characterizes the smallest possible estimation error for learning a given observable using the outcomes of a given non-adaptive measurement protocol to a specified confidence level in the worst case over all states. We prove that TOOL is minimax optimal for every observable by showing that it can achieve an estimation error to within a small constant factor of the minimax norm. For many applications, one wishes to learn the expectation value of more than one observable from the same experiment. A popular method for learning the expectation values of one or many observables with rigorous guarantees is classical shadows. Classical shadows has near-optimal performance in the worst case over all observables. We prove that TOOL always performs at least as well as classical shadows. Moreover, we show by example that TOOL dramatically outperforms classical shadows for many observables of interest. This highlights the need to characterize the optimal performance for the task of simultaneously learning the expectation values of many observables. Under a mild assumption, we give such a characterization using the minimax norm and prove that TOOL is nearly minimax optimal for this task. We also study the applications of TOOL to fidelity estimation. Using experimental data from a trapped-ion quantum computer, we show that TOOL performs well in practice and matches the estimates obtained from Maximum Likelihood Estimation (MLE), but with rigorous guarantees on the estimation error unlike MLE. We also compare TOOL with another popular method called direct fidelity estimation, which estimates the fidelity by judiciously sampling Pauli observables and measuring them. We show that there is a different importance sampling scheme for Pauli measurements for which TOOL performs as well as, or better than, direct fidelity estimation. Since TOOL constructs an estimator using only the observable, the measurement protocol, and the confidence level, it provides the flexibility to perform estimation for experiments that have already been performed and experiments that will be performed in the future. Similarly, since the minimax norm can be computed beforehand, it can be used to compare the performance of different measurement protocols and allow minimax optimal design of experiments.
Estimating the fidelity between an unknown quantum state and a fixed target is a fundamental task in quantum information science. Direct fidelity estimation (DFE) enables this without full tomography by sampling observables according to a target-dependent distribution. However, existing approaches face notable trade-offs. Grouping-based DFE achieves strong accuracy for small systems but suffers from exponential scaling, and its applicability is restricted to Pauli measurements. In contrast, classical-shadow-based DFE offers scalability but yields lower accuracy on structured states. In this work, we address these limitations by developing two classes of operator-aware shadow importance sampling algorithms using informationally overcomplete positive operator-valued measures. Instantiated with local Pauli measurements, our algorithm improves upon the grouping-based algorithms for Haar-random states. For structured states such as the GHZ and W states, our algorithm also eliminates the exponential memory requirements of previous grouping-based methods. Numerical experiments confirm that our methods achieve state-of-the-art performance across Haar-random, GHZ, and W targets.
A crucial subroutine for various quantum computing and communication algorithms is to efficiently extract different classical properties of quantum states. In a notable recent theoretical work by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)NPAHAX1745-247310.1038/s41567-020-0932-7], a thrifty scheme showed how to project the quantum state into classical shadows and simultaneously predict M different functions of a state with only O(log_{2}M) measurements, independent of the system size and saturating the information-theoretical limit. Here, we experimentally explore the feasibility of the scheme in the realistic scenario with a finite number of measurements and noisy operations. We prepare a four-qubit GHZ state and show how to estimate expectation values of multiple observables and Hamiltonians. We compare the measurement strategies with uniform, biased, and derandomized classical shadows to conventional ones that sequentially measure each state function exploiting either importance sampling or observable grouping. We next demonstrate the estimation of nonlinear functions using classical shadows and analyze the entanglement of the prepared quantum state. Our experiment verifies the efficacy of exploiting (derandomized) classical shadows and sheds light on efficient quantum computing with noisy intermediate-scale quantum hardware.