PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Quantum Property Testing

Ashley Montanaro, Ronald de Wolf

arXiv:1310.2035v4quant-ph

TL;DR

Property testing asks how to distinguish large objects having a property from objects far from it using efficient tests. This survey synthesizes quantum property-testing results across classical and quantum objects, emphasizing speed-ups, testing frameworks, lower bounds, connections, and open questions. It covers quantum testers for classical properties, classical tests of quantum objects, and quantum tests of quantum states and operations.

  • Problem

    Property testing seeks efficient ways to distinguish large objects with a property from objects that are far from having it, while quantum systems also require certification of states and operations.

  • Method

    The survey organizes prior quantum property-testing work into three settings and explains representative algorithms, lower-bound methods, connections, and open questions.

  • Results

    The survey reports quantum testers that can be substantially more efficient than classical testers, including an O(log N)-query quantum 1/4-tester for Simon’s property versus Ω(√N) classical queries.

  • Takeaways & Limitations

    Quantum property testing connects query algorithms and quantum-information tasks such as testing equality, separability, rank, and whether operations commute.

  • Takeaways & Limitations

    The survey is not comprehensive, emphasizes computer-science perspectives, and leaves many natural classical and quantum properties with unknown complexity.

Abstract

from arXiv · show

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.

1 Introduction

Property testing efficiently distinguishes objects possessing a property from objects that are far from it using few local checks. The survey organizes quantum property testing into quantum tests of classical objects, classical tests of quantum objects, and quantum tests of quantum objects.

  • Foundations: Property testing assumes the input either has a property or is ǫ-far from having it, enabling efficient decisions from limited checks.An ǫ-tester accepts property-having inputs and rejects ǫ-far inputs with probability at least 2/3.
  • Foundations: Θ(1/ǫ) queries are optimal for testing whether a binary string equals the all-zero string using normalized Hamming distance.Randomly sampling k positions fails to detect an ǫ-far string with probability (1 − ǫ)^k, so k = Θ(1/ǫ) suffices and is optimal.
  • Three settings: Quantum testing of classical objects seeks query-complexity speed-ups by extracting global information through superposition queries.The survey covers examples based on algorithms including Simon’s, Shor’s, Grover’s, and Ambainis’s algorithms.
  • Three settings: Quantum testing of quantum objects applies quantum procedures to black-box states or operations, while the survey focuses on quantum presentations rather than classical descriptions.The survey also discusses properties such as entanglement, equality, separability, rank, and commutation, and identifies open questions.
  • Survey scope: The survey emphasizes intuition over detailed proofs, includes some results based on combining or improving prior work, and points out open questions.Its scope excludes a comprehensive treatment of classical testers for classical properties and emphasizes computer-science aspects over primarily physics-oriented work.
  • Three settings: Classical testing of quantum objects uses classical inputs and measurement outcomes to assess whether a claimed quantum state or operation meets its specification.The setting avoids assuming reliable auxiliary quantum operations, which would otherwise create an infinite regress of certification.

2.1 Preliminaries

Quantum query algorithms access classical inputs through unitary oracle queries, interleaved with fixed unitaries and followed by measurement. Their distinctive capability is querying superpositions of input indices.

  • Quantum query model: A query reads x_i through a unitary oracle whose first register indexes positions and whose second register receives x_i modulo m.The oracle can be tensored with identity on workspace qubits.
  • Quantum query model: Superposition queries let one oracle call access multiple input indices coherently, providing a source of power for quantum query algorithms.The input is accessed globally through a superposition of different indices rather than by querying one index at a time.
  • Quantum query model: A phase-query encodes a binary answer as a phase: +1 when x_i = 0 and −1 when x_i = 1.This encoding arises when the second register is prepared in a suitable superposition state.
  • Quantum query model: A T-query quantum algorithm alternates T oracle queries with T + 1 fixed unitaries, starting from an initial state and ending with a measurement.The final state depends on the input through the queries, and measurement produces the classical output.

2.2 Upper bounds

The survey studies quantum speed-ups for testing classical properties under normalized Hamming distance, measuring complexity by the number of input queries.

  • Model and scope: Quantum and classical property-test complexity are measured by the number of queries to x, typically using normalized Hamming distance.The distance is d(x, y) = |{i : x_i ≠ y_i}|/N unless stated otherwise.
  • Model and scope: The upper-bound results primarily apply existing quantum algorithms to classical property-testing problems.The surveyed examples target properties where quantum testers use substantially fewer queries than classical testers.
  • Model and scope: The survey’s upper-bound examples cover quantum testers for classical properties rather than the broader body of classical property-testing results.The section focuses on query complexity under the stated distance measure.

2.2.1 Using amplitude amplification

Amplitude amplification converts perfect-completeness classical testers into quantum testers with a square-root reduction in the dependence on their rejection probability. This immediately yields O(1/√ǫ) testers for Linearity and Symmetry.

  • Amplitude amplification: O(q/√p) quantum queries replace q classical queries when a perfect-completeness tester finds a rejecting witness with probability p.The amplified tester retains perfect completeness and rejects with constant probability.
  • Linearity and Symmetry: O(1/√ǫ) queries test ǫ-farness from Linearity using a three-query perfect-completeness classical test that rejects with probability at least ǫ.The classical test checks f(x) ⊕ f(y) = f(x ⊕ y) for uniformly random x and y.
  • Linearity and Symmetry: O(1/√ǫ) queries test ǫ-farness from Symmetry by amplifying a two-query perfect-completeness classical tester.The classical tester rejects functions far from symmetric with probability at least ǫ.
  • Comparisons: Earlier testers for Linearity and Symmetry used O(ǫ^−2/3) queries, which is worse than the amplitude-amplification bounds.A related tester for Affineness also achieves O(1/√ǫ) queries.

2.2.2 Using the Bernstein-Vazirani algorithm

The Bernstein–Vazirani algorithm identifies a hidden linear function with one quantum query, enabling strong separations for testing selected Hadamard codewords. For most subsets of codewords, the quantum tester uses O(1/√ε) queries, while classical testing requires logarithmically many queries.

  • Hadamard codewords: The Hadamard encoding maps s ∈ {0,1}^n to the truth table h(s)_i = s · i mod 2, viewed as a binary string of length N = 2^n.The paper identifies [N] with {0,1}^n to index the truth-table positions.
  • Consequence: The separation is described as an unbounded quantum speed-up for testing most subsets of Hadamard codewords.A general classical tester with perfect completeness gives an essentially optimal upper bound based on the size of the property.
  • Quantum tester: For every A ⊆ {0,1}^n, there is an O(1/√ε)-query quantum ε-tester for the property of belonging to the Hadamard codewords indexed by A.The tester rejects immediately when the recovered s is outside A, and otherwise uses random checking plus amplitude amplification to detect ε-far inputs.
  • Classical lower bound: For a 1−o(1) fraction of sets A, every classical 1/2-tester requires Ω(log N) queries.The lower bound uses random subsets A and the fact that nonmember Hadamard codewords are exactly 1/2-far from the property.
  • Quantum procedure: One Bernstein–Vazirani query recovers the corresponding s with certainty when the input is exactly a Hadamard codeword.The circuit applies a uniform superposition, a phase query, Hadamard transforms, and measurement.

2.2.3 Testing juntas

Quantum junta testing uses Fourier Sampling to collect variables on which a Boolean function depends. The resulting tester improves the dependence on ε, while later work gives a stronger bound and leaves the exact quantum query complexity open.

  • Junta property: A Boolean function is a k-junta if it depends on at most k variables.The junta property consists of functions f:{0,1}^n→{+1,−1} with at most k relevant variables.
  • Quantum complexity: O(k/√ε) quantum queries suffice for testing k-juntas, improving the ε-dependence of the earlier O(k/ε) bound through amplitude amplification.The procedure repeats the variable-discovery step at most k+1 times.
  • Fourier Sampling: Fourier Sampling uses one query to sample a subset of variables from the distribution given by squared Fourier coefficients.The sampled support is always contained in the function’s relevant-variable set.
  • Testing strategy: If the function is a k-junta, the accumulated variable set W never exceeds k elements; if it is far from every k-junta, sampling can enlarge W beyond k.The tester constructs a k-junta from the Fourier coefficients supported on W and uses its distance from f to find a new variable.
  • Later bounds: A later algorithm uses eO(√(k/ε)) queries and proves a quantum lower bound of Ω(k^1/3) queries.The eO notation hides logarithmic factors in k, and the algorithm uses the adversary bound.
  • Open question: The quantum query complexity of testing juntas remains open.The survey explicitly states this as Question 1 after presenting the upper and lower bounds.

2.2.4 Using Simon’s algorithm

Simon’s algorithm yields a logarithmic-query quantum tester for a collision-based property, while classical testers require linearly many queries. The classical lower bound follows because short query transcripts rarely reveal collisions under either distribution.

  • Quantum procedure: The quantum procedure repeatedly obtains strings y satisfying s·y=0 mod 2, then solves the resulting linear constraints to recover s.After Θ(n) repetitions, high probability of n−1 linearly independent constraints enables classical Gaussian elimination.
  • Simon property: The Simon property contains strings x∈[N]^N with a nonzero mask s such that x_i=x_j whenever j=i⊕s.Unlike Simon’s original promise, equality may also occur for other distinct index pairs.
  • Quantum tester: O(log N) quantum queries suffice for a quantum 1/4-property tester for the Simon property.The tester recovers a candidate s, samples i, and checks whether x_i=x_{i⊕s}.
  • Classical lower bound: Every classical 1/4-property tester requires Ω(√N) queries.The proof compares uniform inputs with inputs uniformly drawn from the Simon property and from inputs 1/4-far from it.
  • Distribution argument: A T-query classical algorithm has distinguishing advantage O(T^2/N), because useful collisions occur with that probability under both distributions.Conditioned on no collision, the observed outputs form a uniformly random sequence of T distinct values.

2.2.5 Using Shor’s algorithm

Shor’s period-finding algorithm gives a constant-query quantum tester for a periodicity property. Classical testing requires a polynomial number of queries, while binary alphabets rule out a constant-versus-linear separation of this form.

  • Periodicity property: The periodicity property consists of strings that are 1-1-p-periodic for some period p in a specified range.For 1-1-p-periodicity, the first p entries are distinct and the sequence then repeats.
  • Periodicity property: Testing one fixed period is easy classically, but allowing r/2+1 possible periods makes the property hard for classical testers.The construction sets q=r/2, leaving many candidate periods while retaining an efficient quantum test.
  • Quantum-classical separation: O(1) quantum queries suffice to test the periodicity property, whereas every classical tester needs Ω(N^1/4/log N) queries.The quantum algorithm finds a period with Shor’s algorithm and verifies it using O(1) additional queries.
  • Quantum-classical separation: This is an O(1) versus N^Ω(1) separation over a polynomial-sized alphabet, where each input entry contains O(log N) bits.The result motivates asking whether an O(1)-versus-Ω(N) separation is possible over moderately sized alphabets.
  • Limits of separation: For binary alphabets, any property testable with k=O(1) quantum queries has a classical randomized tester using O(N^(1−1/(2k)))=o(N) queries.The corresponding linear classical lower-bound question remains open when the alphabet size is N.

2.2.6 Using quantum counting

Quantum counting improves distribution-testing query complexity by estimating frequencies more efficiently than classical sampling. The survey applies this approach to equality and uniformity testing.

  • Quantum approximate counting: Quantum approximate counting estimates the fraction of string positions whose values lie in a set using T queries with additive error C(√(p/T) + 1/T).Here p is the fraction of positions containing elements from the queried set.
  • Equality testing: Θ(m^2/3/ε^4/3) classical queries are needed for distribution equality testing, whereas the quantum tester improves the dependence on m and ε.The classical bound is tight for ε ≥ m^-1/4; the quantum theorem gives the stated square-root-in-m form, with ε-dependence noted as improvable.
  • Equality testing: O(√(m/ε^8)) quantum queries suffice to test whether two distributions are equal or ε-far in total variation distance.The method estimates total variation distance by sampling an element and estimating its probabilities under both distributions.
  • Uniformity testing: O(m^1/3/ε^2) quantum queries test whether a distribution equals the uniform distribution or is ε-far from it.The tester samples distinct values, then uses quantum counting to estimate their total frequency and detect excess mass.
  • Uniformity testing: Ω(m^1/3) quantum queries are necessary for uniformity testing, making the result essentially tight in its dependence on m.The lower bound follows by reduction from the collision problem; related testers handle equality to fixed distributions and disjoint support.

2.2.7 Using Ambainis’s algorithm

Ambainis’s element-distinctness algorithm lets quantum testers detect collision patterns in bounded-degree graphs. This yields sublinear testers for bipartiteness and expansion, while leaving exponential speed-ups unresolved.

  • Motivation: Graph properties are a useful test case because their relabelling symmetry may constrain possible quantum speed-ups.The survey notes that these are the only quantum graph-property testing results it is aware of in this discussion.
  • Main results: O(N^1/3)̃ quantum queries suffice to test whether a bounded-degree N-vertex graph is bipartite or an expander.The graph is accessed through an adjacency list, with degree d treated as constant.
  • Bipartiteness: Collision detection identifies odd cycles in graphs far from bipartite by comparing parity of short random walks from a common starting vertex.A variation of element distinctness detects these collisions using O(N^1/3) queries to the walk encoding, corresponding to O(N^1/3 log N) graph queries.
  • Expansion: For expansion testing, quantum counting estimates collisions among endpoints of short random walks, whose rate differs between expanders and graphs far from every expander.The resulting tester uses eO(N^1/3) graph queries.
  • Lower bounds and open questions: eΩ(N^1/4) quantum queries are necessary for testing expanders, while no N^Ω(1) lower bound is known for testing bipartiteness.The survey poses whether any graph property admits an exponential quantum speed-up.

2.2.8 Quantum speed-ups for testing group-theoretic properties

Quantum property testing extends beyond strings and graphs to group-theoretic structures. The surveyed results use quantum Fourier transforms, dequantization, and quantum algorithms for group multiplication tables.

  • Group properties: Quantum Fourier transforms yield efficient testers for periodic functions on groups and several other group-theoretic properties.The testers are time-efficient for Abelian groups.
  • Group multiplication tables: Classical testers with poly(log N, 1/ε) queries test multiplication tables of N-element Abelian groups using a dequantized quantum tester.The distance measure is edit distance.
  • Group multiplication tables: Quantum testers with poly(log N, 1/ε) queries test multiplication tables corresponding to N-element solvable groups, for which no efficient classical tester is known.This extends the Abelian-group result to solvable groups.
  • Quantum speed-ups: Testing whether an input is an Abelian group generated by fixed k elements exhibits an exponential separation between classical and quantum complexities.The result follows from classical lower bounds for group-testing problems.

2.3 Lower bounds

Quantum property-testing lower bounds mainly use the polynomial method, while the adversary method can characterize optimal query complexity in principle. Communication-complexity reductions face a substantial obstacle for quantum testers.

  • Polynomial method: A T-query quantum algorithm has an acceptance probability representable as an N-variate multilinear polynomial of degree at most 2T.Lower bounds follow by proving that no low-degree polynomial can satisfy the tester’s required acceptance behavior.
  • Polynomial method: If random members of a property are indistinguishable from random strings on every set of at most k bits, testing requires Ω(k) quantum queries.The formal theorem gives a lower bound of at least (k + 1)/2 queries under additional closeness and moment conditions.
  • Applications: The polynomial method gives tight or strong bounds for Reed–Muller codes, most properties, Simon’s problem, and bounded-degree expander testing.For Reed–Muller codes, it implies Ω(2^d) queries and no asymptotic speed-up in dependence on d.
  • Applications: For a random property of size 2^N/20, any quantum ε-tester requires Ω(N) queries except with exponentially small probability.This counting argument reflects the scarcity of low-degree polynomials relative to the number of properties.
  • Adversary method: The negative-weights adversary bound is a valid quantum lower bound and is essentially tight for every Boolean function, hence in principle characterizes testing complexity.Its practical limitation is that calculating the bound is often difficult, and the survey reports few property-testing applications.
  • Communication-complexity method: Communication-complexity reductions that are effective classically incur O(n) qubits of communication per quantum query, yielding only trivial query lower bounds.For k-linear functions, this reflects a genuine O(1)-query quantum tester via Bernstein–Vazirani.

3 Classical testing of quantum properties

Classical self-testing uses only classical input-output data to certify quantum gates and protocols. The survey shows that experimental equations can characterize universal gate sets up to unavoidable freedoms, while near-optimal CHSH performance certifies EPR-pair structure and standard measurements.

  • Self-testing gates: Classical self-testers certify quantum gates using experimental equations derived from classical states, operations, and measurement outcomes.These equations specify outcome probabilities for experiments applying sequences of available superoperators.
  • Self-testing gates: The experimental-equation approach cannot fully determine a gate: Hadamard implementations differing by a phase satisfy exactly the same equations.This limitation is intrinsic to classical input-output experiments, although the equations can still essentially characterize universal gate sets.
  • Self-testing gates: Three experimental equations characterize the Hadamard gate up to a phase φ, while seven equations characterize H and T up to phase and T inversion.The phase corresponds to replacing |1⟩ by e^iφ|1⟩, and the T ambiguity is whether the gate or its inverse is implemented.
  • Self-testing gates: Sixteen experimental equations robustly self-test the gate triple H, T, C, identifying it up to phase and T inversion when the equations are approximately satisfied.The resulting triples are universal and fault-tolerant sets of elementary gates.
  • Self-testing protocols: cos(π/8)^2 is the optimal CHSH winning probability, and any protocol attaining it must use an EPR-pair up to local basis transformations.The corresponding observables are constrained to the standard CHSH structure, with robustness extending this conclusion to near-optimal protocols.
  • Self-testing protocols: Near-optimal CHSH performance certifies, through a local isometry, an EPR-pair tensored with junk and measurements close to standard Pauli operators.For many CHSH instances, most blocks similarly behave like collections of EPR-pairs running independent standard protocols.

4 Quantum testing of quantum properties: States

Quantum testing of quantum states studies black-box tests distinguishing states with a property from states far from it. The survey covers equality, productness, finite state sets, stabilizer states, and mixed-state properties, including upper and lower bounds and open questions.

  • Equality: Testing whether a pure state lies in a known subspace uses repeated projection onto that subspace, requiring O(1/ε^2) repetitions.Permutation invariance is an example, because permutation-invariant states form the symmetric subspace.
  • Equality: Equality testing for two unknown pure states uses the swap test and requires O(1/ε^2) copies, which is optimal for perfect-completeness testers using one copy of each state.The swap test projects onto the symmetric subspace; a matching lower bound follows from distinguishing tensor powers of states at distance ε.
  • Productness: A product state is a tensor product of local states, while a non-product state is entangled; with two copies, the product test rejects ε-far states with probability Ω(ε^2).The test applies swap tests to corresponding subsystem pairs and accepts only when all pass, yielding an O(1/ε^2)-copy tester.
  • Productness: Product testing has a structural interpretation: a pure state that remains fairly pure after randomly discarding subsystems must have been close to product.The product test also supports the complexity-theoretic consequence QMA(k) = QMA(2).
  • Finite state sets: For a finite set P of pure states with minimum pairwise distance δ, testing uses O(log |P| max{ε^-2, δ^-2}) copies while accepting P with certainty.The logarithmic dependence on |P| reflects approximate orthogonality of tensor powers of well-separated states; permutations can be tested with O((n log n)/ε^2) copies.
  • Open questions: Stabilizer states can be learned with O(n) copies and require Ω(n) copies for learning, but whether they can be tested with substantially fewer copies remains open.Stabilizer states are important in quantum error correction and measurement-based quantum computation.
  • Mixed states: For mixed states, arbitrary properties have an O(d^4/ε^2)-copy upper bound, while purity needs O(1/ε) copies and maximal mixedness can require Ω(r) copies.The maximal-mixedness lower bound is matched by an O(r)-copy algorithm for distinguishing I/d from a maximally mixed state on a random r-dimensional subspace.

5 Quantum testing of quantum properties: Dynamics

The survey develops quantum tests for unitary properties, often by representing operators as states and using average-case distance measures. It gives testing bounds for equality, inverses, products, group membership, commutativity, juntas, and diagonality, while noting important soundness and access-model caveats.

  • Distance measures: Dmax-based identity testing requires Ω(√n) quantum queries, via a reduction from OR on n promised bits.The identity property asks whether U=e^iθI, while the alternatives Ui differ by a phase on one basis state.
  • Distance measures: Average-case 2-norm distance is presented as a more suitable alternative to the best-case Dmax measure for property testing.With controlled unitaries, tests can detect distinctions such as U versus −U that are impossible using U alone.
  • Basic unitary properties: Equality, inverse, and equality-to-V properties are testable with O(1/ε^2) uses, while inverse testing needs only one use each of U and V per trial.The inverse test creates |UV⟩ and tests equality with |Φ⟩; its rejection probability is ε^2 when D(U,V^-1)=ε.
  • Group membership and diagonality: Membership in an operator basis and diagonality are both testable with O(1/ε^2) uses under the stated testing procedures.The operator-basis test repeats measurements and rejects when individual tests reject; diagonality follows from closeness to a diagonal unitary.
  • Commutativity: Commutativity testing rejects pairs ε-far from commuting matrices with probability Ω(ε^18), yielding constant success after poly(1/ε) repetitions.The bound uses Glebsky’s theorem that approximately commuting unitaries are close to exactly commuting unitaries, with distance at most 30ε^1/9.
  • Juntas: Unitary k-junta testing uses T=Θ(k/ε^2) measurements, improved to Θ(k/ε) when U^-1 is available through amplitude amplification.The procedure finds k+1 measurement outcomes whose supports extend beyond a candidate k-subset.

6 Quantum properties and computational complexity

The survey connects quantum property testing with computational complexity by contrasting efficient average-case testers with hardness for succinctly described quantum circuits. It also presents property testing as a tool for upper bounds, complexity-class characterizations, and quantum PCP-related questions.

  • Hardness of circuit properties: Many properties of quantum circuits given by concise classical descriptions are QMA-complete, contrasting with positive results in average-case property testing.Non-identity-check is a prototypical example involving a circuit implementing a unitary and thresholds for distance from the identity up to phase.
  • Hardness of circuit properties: Replacing operator norm with normalized 2-norm places the non-identity-check problem in BQP via an efficient equality-to-V tester.The promise distinguishes circuits whose phase-adjusted distance from identity is at most a or at least b, with b−a≥1/poly(n).
  • Hardness of circuit properties: Mixed-state circuit distinguishability is PSPACE-complete, including restrictions to logarithmic depth and degradable or anti-degradable circuits.The relevant distance is the diamond norm, a best-case distinguishability measure for channels.
  • Upper bounds and characterizations: Property-testing techniques can yield positive complexity results: testing whether a pure-circuit output is a product state is in BQP.Gutoski et al. generalize this approach to separability-testing problems complete for almost every quantum interactive-proof complexity class.
  • The quantum PCP conjecture: The quantum PCP conjecture asks whether local Hamiltonian remains hard when the yes-no energy gap is constant-scale rather than inverse-polynomial.This reframes the conjecture as hardness in a property-testing-type setting with a large gap between yes and no instances.
  • Quantum locally testable codes: Stabilizer qLTCs have upper bounds on soundness showing that such codes do not exist in certain parameter regimes where classical LTCs do.qLTCs test containment in the kernel of a k-local Hamiltonian using measurements of only a few local terms.

7 Conclusion

The conclusion presents quantum property testing as a framework for efficient approximate decision procedures across classical and quantum objects. It highlights open problems in unexplored properties and in characterizing which properties admit efficient quantum testers.

  • Conclusion: The survey organizes quantum property testing into quantum testers for classical properties, classical testers for quantum properties, and quantum testers for quantum properties.These settings cover quantum speedups, classical access to quantum systems, and direct quantum testing of states or operations.
  • Open questions: Many important classical properties remain open for quantum complexity, including Boolean monotonicity, error-correcting-code membership, and almost all graph properties.The conclusion also notes unresolved natural properties in the quantum setting.
  • Open questions: A broad open question is whether classical or quantum properties admitting efficient quantum testers can be characterized.The survey notes that analogous characterizations already exist for some classical cases, including graph properties and symmetric probability-distribution properties.
Loading 1310.2035v4…