Sample-optimal tomography of quantum states

Abstract

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 $\epsilon$ in trace distance required $O(d{r}^2/{\epsilon }^2)$ copies for a $d$-dimensional density matrix of rank $r$. Here, we give a theoretical measurement scheme (POVM) that requires $O(dr/\delta )\ln (d/\delta )$ copies of $\rho$ to error $\delta$ in infidelity, and a matching lower bound up to logarithmic factors. This implies $O((dr/{\epsilon }^2)\ln (d/\epsilon ))$ copies suffice to achieve error $\epsilon$ in trace distance. We also prove that for independent (product) measurements, $\Omega (d{r}^2/{\delta }^2)/\ln (1/\delta )$ copies are necessary in order to achieve error $\delta$ in infidelity. For fixed $d$, our measurement can be implemented on a quantum computer in time polynomial in $n$.

revtex, 16 pages, 3 figures. (v1) in STOC 2016, 913-925. (v2) improved lower bound for independent measurements

References in corpus (13)

• The Quantum Chernoff Bound
• Direct Fidelity Estimation from Few Pauli Measurements
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Aspects of generic entanglement
• Randomizing quantum states: Constructions and applications
• Quantum Circuits for Isometries
• The Chernoff lower bound for symmetric quantum hypothesis testing
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• On quantum estimation, quantum cloning and finite quantum de Finetti theorems
• Error rates of Belavkin weighted quantum measurements and a converse to Holevo's asymptotic optimality theorem
• Minimax quantum tomography: the ultimate bounds on accuracy
• Quantum Minimax Theorem

Cited by in corpus (121)

• Machine learning and the physical sciences
• The Variational Quantum Eigensolver: a review of methods and best practices
• Mixed-state entanglement from local randomized measurements
• Provably efficient machine learning for quantum many-body problems
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Gate Set Tomography
• Tomography and Generative Data Modeling via Quantum Boltzmann Training
• Quantum Overlapping Tomography
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Efficient estimation of Pauli channels
• Attaining the ultimate precision limit in quantum state estimation
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Classical Shadows With Noise
• Machine learning non-Markovian quantum dynamics
• Quantum Algorithmic Measurement
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• Quantum Fisher information from randomized measurements
• Experimental single-setting quantum state tomography
• Hamiltonian Simulation with Optimal Sample Complexity
• Fast quantum circuit cutting with randomized measurements
• Entanglement barrier and its symmetry resolution: theory and experiment
• Optimal Verification of Two-Qubit Pure States
• Recovering quantum gates from few average gate fidelities
• Scalable and Flexible Classical Shadow Tomography with Tensor Networks
• Quantum advantages for Pauli channel estimation
• Thermodynamic Capacity of Quantum Processes
• Measuring Arbitrary Physical Properties in Analog Quantum Simulation
• Hamiltonian-Driven Shadow Tomography of Quantum States
• A Survey of Quantum Learning Theory
• Quantum Algorithm for Fidelity Estimation
• Projected Least-Squares Quantum Process Tomography
• Detecting entanglement in quantum many-body systems via permutation moments
• An efficient high dimensional quantum Schur transform
• Operator relaxation and the optimal depth of classical shadows
• Learning quantum circuits of some $T$ gates
• Measuring Quantum Entropy
• Classical shadow tomography for continuous variables quantum systems
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Verification of phased Dicke states
• Learning quantum states and unitaries of bounded gate complexity
• Quantum Mixed State Compiling
• Guaranteed recovery of quantum processes from few measurements
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Distributed quantum inner product estimation
• Performance analysis of multi-shot shadow estimation
• Robust estimation of the Quantum Fisher Information on a quantum processor
• Scalable Quantum Tomography with Fidelity Estimation
• Query-optimal estimation of unitary channels in diamond distance
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Characterizing correlation within multipartite quantum systems via local randomized measurements
• Learning quantum many-body systems from a few copies
• Demonstration of Robust and Efficient Quantum Property Learning with Shallow Shadows
• Online Learning of Quantum States
• Fast Quantum Algorithms for Trace Distance Estimation
• Two-stage Estimation for Quantum Detector Tomography: Error Analysis, Numerical and Experimental Results
• Efficient online quantum state estimation using a matrix-exponentiated gradient method
• Witnessing non-objectivity in the framework of strong quantum Darwinism
• Machine learning on quantum experimental data toward solving quantum many-body problems
• Quantifying information scrambling via Classical Shadow Tomography on Programmable Quantum Simulators
• Ultimate limits for quickest quantum change-point detection
• Quantum State Tomography for Matrix Product Density Operators
• On exploring the potential of quantum auto-encoder for learning quantum systems
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Validating and Certifying Stabilizer States
• Krylov shadow tomography: Efficient estimation of quantum Fisher information
• Multipartite entanglement measures via Bell basis measurements
• On the Hardness of PAC-learning Stabilizer States with Noise
• Thermodynamic Implementations of Quantum Processes
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Determination of Multi-mode Motional Quantum States in a Trapped Ion System
• Generation of scalable many-body Bell correlations in spin chains with short-range two-body interactions
• Interplay between time and energy in bosonic noisy quantum metrology
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• Quantum chi-squared tomography and mutual information testing
• Streaming quantum state purification
• Direct estimation of minimum gate fidelity
• Entanglement phase diagrams from partial transpose moments
• Secure Software Leasing
• Predicting Features of Quantum Systems from Very Few Measurements
• Fast and robust quantum state tomography from few basis measurements
• Private learning implies quantum stability
• Improved quantum data analysis
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Linear programming with unitary-equivariant constraints
• Quantum Tensor Product Decomposition from Choi State Tomography
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Bounding the fidelity of quantum many-body states from partial information
• Toward Instance-Optimal State Certification With Incoherent Measurements
• Exact Quantum Algorithms for Quantum Phase Recognition: Renormalization Group and Error Correction
• Classical shadows meet quantum optimal mass transport
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• Learning topological states from randomized measurements using variational tensor network tomography
• Inferring Hidden Symmetries of Exotic Magnets from Detecting Explicit Order Parameters
• On the connection between least squares, regularization, and classical shadows
• Cosine series quantum sampling method with applications in signal and image processing
• Efficient Quantum State Tracking in Noisy Environments
• Efficient learning of ground & thermal states within phases of matter
• Tunable Quantum Neural Networks for Boolean Functions
• Nondestructive Verification of Entangled States via Fidelity Witnessing
• PAC-learning of free-fermionic states is NP-hard
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$
• Local measurement strategies for multipartite entanglement quantification
• Learning quantum graph states with product measurements
• Conditional Independence of 1D Gibbs States with Applications to Efficient Learning
• Quantum Proofs of Proximity
• Measuring quantum relative entropy with finite-size effect
• Holographic Classical Shadow Tomography
• Simulation-assisted learning of open quantum systems
• Fourier-style Quantum State Tomography and Purity Measurement of a Multi-qubit System from Bloch Rotations
• Singular value transformation for unknown quantum channels
• A condition under which classical simulability implies efficient state learnability
• Performance Guarantees for Quantum Neural Estimation of Entropies
• Analytically Continuing the Randomized Measurement Toolbox
• Sample Optimal and Memory Efficient Quantum State Tomography
• Diagnosing crosstalk in large-scale QPUs using zero-entropy classical shadows
• Online learning of a panoply of quantum objects
• Testing identity of collections of quantum states: sample complexity analysis
• Tunable Quantum Neural Networks in the QPAC-Learning Framework
• Classical Shadows with Improved Median-of-Means Estimation