Agnostic Tomography of Stabilizer Product States

Abstract

We define a quantum learning task called agnostic tomography, where given copies of an arbitrary state $\rho$ and a class of quantum states $\mathcal{C}$, the goal is to output a succinct description of a state that approximates $\rho$ at least as well as any state in $\mathcal{C}$ (up to some small error $\epsilon$). This task generalizes ordinary quantum tomography of states in $\mathcal{C}$ and is more challenging because the learning algorithm must be robust to perturbations of $\rho$. We give an efficient agnostic tomography algorithm for the class $\mathcal{C}$ of $n$-qubit stabilizer product states. Assuming $\rho$ has fidelity at least $\tau$ with a stabilizer product state, the algorithm runs in time $n^{O(\log (2/\tau ))}/{\epsilon }^2$, which is $\mathsf{poly}(n/\epsilon )$ for any constant $\tau$.

arXiv comment20 pages. V2: minor corrections. V3: addition of new references. V4: reworked the algorithm and presentation. V5: accepted to Quantum

References in corpus (19)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Efficient quantum state tomography
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Entanglement on mixed stabiliser states--I: Normal Forms and Reduction Procedures
• Learning t-doped stabilizer states
• Bell sampling from quantum circuits
• Learning shallow quantum circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• On the Hardness of PAC-learning Stabilizer States with Noise
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Learning quantum graph states with product measurements
• Agnostic Process Tomography
• Learning the closest product state
• Complexity Classification of Product State Problems for Local Hamiltonians