A Survey of Quantum Property Testing

Abstract

The area of property testing tries to design algorithms that can efficiently handle very large amounts of data: given a large object that either has a certain property or is somehow "far" from having that property, a tester should efficiently distinguish between these two cases. In this survey we describe recent results obtained for quantum property testing. This area naturally falls into three parts. First, we may consider quantum testers for properties of classical objects. We survey the main examples known where quantum testers can be much (sometimes exponentially) more efficient than classical testers. Second, we may consider classical testers of quantum objects. This is the situation that arises for instance when one is trying to determine if quantum states or operations do what they are supposed to do, based only on classical input-output behavior. Finally, we may also consider quantum testers for properties of quantum objects, such as states or operations. We survey known bounds on testing various natural properties, such as whether two states are equal, whether a state is separable, whether two operations commute, etc. We also highlight connections to other areas of quantum information theory and mention a number of open questions.

67 pages, 165 references; v4: essentially published version

References in corpus (25)

• Scalable multi-particle entanglement of trapped ions
• Efficient quantum state tomography
• Direct Fidelity Estimation from Few Pauli Measurements
• Coding Theorem and Strong Converse for Quantum Channels
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Robust Self Testing of the Singlet
• All entangled states are useful for channel discrimination
• The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
• Physical characterization of quantum devices from nonlocal correlations
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Learning and Testing Algorithms for the Clifford Group
• The Quantum PCP Conjecture
• Local tests of global entanglement and a counterexample to the generalized area law
• Almost commuting matrices with respect to normalized Hilbert-Schmidt norm
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Quantum walk based search algorithms
• The Efficiency of Quantum Identity Testing of Multiple States
• Improved quantum test for linearity of a Boolean function
• New Results on Quantum Property Testing
• A quantum lower bound for the query complexity of Simon's problem
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Symmetric functions of qubits in an unknown basis
• Property Testing of Quantum Measurements
• Attribute Estimation and Testing Quasi-Symmetry

Cited by in corpus (20)

• Breaking Symmetric Cryptosystems using Quantum Period Finding
• Information-theoretic bounds on quantum advantage in machine learning
• Robust self-testing of many-qubit states
• Quantum union bounds for sequential projective measurements
• Quantum Algorithm for Fidelity Estimation
• Measuring Quantum Entropy
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Quantum and classical bounds for two-state overlaps
• Pseudorandom density matrices
• Unitarity estimation for quantum channels
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Constant-Soundness Interactive Proofs for Local Hamiltonians
• Entanglement Verification, with or without tomography
• Quantum Proofs of Proximity
• Quantum query complexity of entropy estimation
• A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure
• Quantum Spectrum Testing
• Quantum pattern matching fast on average
• Quantum Miss-in-the-Middle Attack
• Quantum Algorithm for Monotonicity Testing on the Hypercube