Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for predicting a large number of linear features using classical shadows obtained from very few quantum measurements. This approach is guaranteed to accurately predict @math linear functions with bounded Hilbert-Schmidt norm from only @math measurement repetitions. This sampling rate is completely independent of the system size and saturates fundamental lower bounds from information theory. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches.
The task of reconstructing a full classical description -- the density matrix @math -- of a @math -dimensional quantum system from experimental data is one of the most fundamental problems in quantum statistics, see e.g. @cite_52 @cite_13 @cite_12 @cite_31 and references therein. Sample-optimal protocols, i.e. estimation techniques that get by with a minimal number of measurement repetitions, have only been developed recently. Information-theoretic bounds assert that an order of @math state copies are necessary to fully reconstruct @math @cite_26 . Constructive protocols @cite_29 @cite_26 saturate this bound, but require entangled circuits and measurements that act on all state copies simultaneously. More tractable measurement procedures, where each copy of the state is measured independently, require an order of @math measurements @cite_26 . This more stringent bound is saturated by low rank matrix recovery @cite_4 @cite_44 @cite_40 and projected least squares estimation @cite_18 .
@cite_18 @cite_26 @cite_4 @cite_29 @cite_52 @cite_44 @cite_40 @cite_31 @cite_13 @cite_12
2649051464 2963583445 1529624360 2797355014
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error @math in trace distance required @math copies for a @math -dimensional density matrix of rank @math . Here, we give a theoretical measurement scheme (POVM) that requires @math copies to estimate @math to error @math in infidelity, and a matching lower bound up to logarithmic factors. This implies @math copies suffice to achieve error @math in trace distance. We also prove that for independent (product) measurements, @math copies are necessary in order to achieve error @math in infidelity. For fixed @math , our measurement can be implemented on a quantum computer in time polynomial in @math . Abstract We study the recovery of Hermitian low rank matrices X ∈ C n × n from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form a j a j ⁎ for some measurement vectors a 1 , … , a m , i.e., the measurements are given by b j = tr ( X a j a j ⁎ ) . The case where the matrix X = x x ⁎ to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements b j = | 〈 x , a j 〉 | 2 ) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number m of measurements that guarantee successful uniform recovery of Hermitian rank r matrices, either for the vectors a j , j = 1 , … , m , being chosen independently at random according to a standard Gaussian distribution, or a j being sampled independently from an (approximate) complex projective t-design with t = 4 . In the Gaussian case, we require m ≥ C r n measurements, while in the case of 4-designs we need m ≥ Cr n log ⁡ ( n ) . Our results are uniform in the sense that one random choice of the measurement vectors a j guarantees recovery of all rank r-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to Gross, Krahmer and Kueng. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii. We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rdlog^2d) measurement settings, compared to standard methods that require d^2 settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed. We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with @math constraint matrices, each of dimension @math , rank @math , and sparsity @math . The first algorithm assumes an input model where one is given access to entries of the matrices at unit cost. We show that it has run time @math , where @math is the error. This gives an optimal dependence in terms of @math and quadratic improvement over previous quantum algorithms when @math . The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is @math , with @math an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in @math and polynomially in @math . We apply the second SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given @math measurements and copies of an unknown state @math , we show we can find in time @math a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as @math on the @math measurements, up to error @math . The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest.