A Survey of Quantum Property Testing
arXiv:1310.2035
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.
arXiv comment67 pages, 165 references; v4: essentially published version
References in corpus (55)
- Quantum entanglement
- Measurement-based quantum computation with cluster states
- Strengths and Weaknesses of Quantum Computing
- Scalable multi-particle entanglement of trapped ions
- Quantum state tomography via compressed sensing
- No Signalling and Quantum Key Distribution
- Efficient quantum state tomography
- Fully device independent quantum key distribution
- Coding Theorem and Strong Converse for Quantum Channels
- Direct Fidelity Estimation from Few Pauli Measurements
- Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
- Practical characterization of quantum devices without tomography
- Statistical distinguishability between unitary operations
- Asymptotic Error Rates in Quantum Hypothesis Testing
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- Concurrence of mixed multi-partite quantum states
- Robust Self Testing of the Singlet
- Optimal discrimination of quantum operations
- Estimating the spectrum of a density operator
- All entangled states are useful for channel discrimination
- Optimal state estimation for d-dimensional quantum systems
- Quantum query complexity of state conversion
- Robust Self Testing of Unknown Quantum Systems into Any Entangled Two-Qubit States
- The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
- The Perfect Distinguishability of Quantum Operations
- Physical characterization of quantum devices from nonlocal correlations
- Quantum And Relativistic Protocols For Secure Multi-Party Computation
- Optimal Algorithms for Testing Closeness of Discrete Distributions
- Continuity bounds for entanglement
- Applications of coherent classical communication and the Schur transform to quantum information theory
- Quantum boolean functions
- Quantum algorithms for testing properties of distributions
- Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
- Learning and Testing Algorithms for the Clifford Group
- Property testing of unitary operators
- 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
- Optimal robust quantum self-testing by binary nonlocal XOR games
- Quantum tests for the linearity and permutation invariance of Boolean functions
- Quantum walk based search algorithms
- The Need for Structure in Quantum Speedups
- Certifiable Quantum Dice - Or, testable exponential randomness expansion
- The non-adaptive query complexity of testing k-parities
- The Efficiency of Quantum Identity Testing of Multiple States
- Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
- Improved quantum test for linearity of a Boolean function
- New Results on Quantum Property Testing
- Quantum Property Testing of Group Solvability
- A quantum lower bound for the query complexity of Simon's problem
- Symmetric functions of qubits in an unknown basis
- Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
- 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