Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1310.2035 · Theory of Computing

A Survey of Quantum Property Testing

Ashley Montanaro, Ronald de Wolf

Published Jan 1, 2016• 247 citations
arXivHTMLPDF

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. These arise 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.

DOI
10.4086/toc.gs.2016.007

Related papers

New Results on Quantum Property Testing

Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1 more

We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $P_f(j)$ of an outcome $j$ in $[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $epsilon$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow showed that if $P_f$ and $P_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson.

Leibniz international proceedings in informatics•Jan 1, 2010•36 citations

New Results on Quantum Property Testing

Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1 more

We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $\PP_f(j)$ of an outcome $j\in[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $ε$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $\sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $\sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.

arXiv:1005.0523•May 4, 2010•16 citations

Quantum property testing

Harry Buhrman, Lance Fortnow, Ilan Newman +1 more

A language $L$ has a property tester if there exists a probabilistic algorithm that given an input $x$ queries only a small number of bits of $x$ and distinguishes the cases as to whether $x$ is in $L$ and $x$ has large Hamming distance from all $y$ in $L$. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.

Symposium on Discrete Algorithms•Jan 12, 2003•15 citations

Coherence in Property Testing: Quantum-Classical Collapses and Separations

Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote +1 more

Understanding the power and limitations of classical and quantum information and how they differ is a fundamental endeavor. In property testing of distributions, a tester is given samples over a typically large domain $\{0,1\}^n$. An important property is the support size both of distributions [Valiant and Valiant, STOC'11], as well, as of quantum states. Classically, even given $2^{n/16}$ samples, no tester can distinguish distributions of support size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-Θ(n)}$, even promised they are flat. Quantum states can be in a coherent superposition of states of $\{0,1\}^n$, so one may ask if coherence can enhance property testing. Flat distributions naturally correspond to subset states, $|ϕ_S \rangle=1/\sqrt{|S|}\sum_{i\in S}|i\rangle$. We show that coherence alone is not enough, Coherence limitations: Given $2^{n/16}$ copies, no tester can distinguish subset states of size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-Θ(n)}$. The hardness persists even with multiple public-coin AM provers, Classical hardness with provers: Given $2^{O(n)}$ samples from a distribution and $2^{O(n)}$ communication with AM provers, no tester can estimate the support size up to factors $2^{Ω(n)}$ with probability better than $2^{-Θ(n)}$. Our result is tight. In contrast, coherent subset state proofs suffice to improve testability exponentially, Quantum advantage with certificates: With poly-many copies and subset state proofs, a tester can approximate the support size of a subset state of arbitrary size. Some structural assumption on the quantum proofs is required since we show, Collapse of QMA: A general proof cannot improve testability of any quantum property whatsoever. We also show connections to disentangler and quantum-to-quantum transformation lower bounds.

arXiv:2411.15148•Nov 6, 2024•1 citation

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting

Kean Chen, Qisheng Wang, Zhicheng Zhang

Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.

quant-pharXiv:2512.01971•Dec 2, 2025•22 citations

Property Testing of Quantum Measurements

Guoming Wang

In this paper, we study the following question: given a black box performing some unknown quantum measurement on a multi-qudit system, how do we test whether this measurement has certain property or is far away from having this property. We call this task \textit{property testing} of quantum measurement. We first introduce a metric for quantum measurements, and show that it possesses many nice features. Then we show that, with respect to this metric, the following classes of measurements can be efficiently tested: 1. the stabilizer measurements, which play a crucial role for quantum error correction; 2. the $k$-local measurements, i.e. measurements whose outcomes depend on a subsystem of at most $k$ qudits; 3. the permutation-invariant measurements, which include those measurements used in quantum data compression, state estimation and entanglement concentration. In fact, all of them can be tested with query complexity independent of the system's dimension. Furthermore, we also present an algorithm that can test any finite set of measurements. Finally, we consider the following natural question: given two black-box measurement devices, how do we estimate their distance? We give an efficient algorithm for this task, and its query complexity is also independent of the system's dimension. As a consequence, we can easily test whether two unknown measurements are identical or very different.

arXiv:1205.0828•May 3, 2012•4 citations
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. These arise 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.
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]f:[n]\to[m]f:[n]→[m]. Here the probability Pf(j)P_f(j)Pf​(j) of an outcome jjj in [m][m][m] is the fraction of its domain that fff maps to jjj. We give quantum algorithms for testing whether two such distributions are identical or epsilonepsilonepsilon-far in L1L_1L1​-norm. Recently, Bravyi, Hassidim, and Harrow showed that if PfP_fPf​ and PgP_gPg​ are both unknown (i.e., given by oracles fff and ggg), then this testing can be done in roughly sqrtmsqrt{m}sqrtm quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3m^{1/3}m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3m^{2/3}m2/3 queries in the unknown-unknown case and about sqrtmsqrt{m}sqrtm queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson.
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]f:[n]\to[m]f:[n]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[m]j\in[m]j∈[m] is the fraction of its domain that fff maps to jjj. We give quantum algorithms for testing whether two such distributions are identical or εεε-far in L1L_1L1​-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles fff and ggg), then this testing can be done in roughly m\sqrt{m}m​ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3m^{1/3}m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3m^{2/3}m2/3 queries in the unknown-unknown case and about m\sqrt{m}m​ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
A language LLL has a property tester if there exists a probabilistic algorithm that given an input xxx queries only a small number of bits of xxx and distinguishes the cases as to whether xxx is in LLL and xxx has large Hamming distance from all yyy in LLL. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
Understanding the power and limitations of classical and quantum information and how they differ is a fundamental endeavor. In property testing of distributions, a tester is given samples over a typically large domain {0,1}n\{0,1\}^n{0,1}n. An important property is the support size both of distributions [Valiant and Valiant, STOC'11], as well, as of quantum states. Classically, even given 2n/162^{n/16}2n/16 samples, no tester can distinguish distributions of support size 2n/82^{n/8}2n/8 from 2n/42^{n/4}2n/4 with probability better than 2−Θ(n)2^{-Θ(n)}2−Θ(n), even promised they are flat. Quantum states can be in a coherent superposition of states of {0,1}n\{0,1\}^n{0,1}n, so one may ask if coherence can enhance property testing. Flat distributions naturally correspond to subset states, ∣ϕS⟩=1/∣S∣∑i∈S∣i⟩|ϕ_S \rangle=1/\sqrt{|S|}\sum_{i\in S}|i\rangle∣ϕS​⟩=1/∣S∣​∑i∈S​∣i⟩. We show that coherence alone is not enough, Coherence limitations: Given 2n/162^{n/16}2n/16 copies, no tester can distinguish subset states of size 2n/82^{n/8}2n/8 from 2n/42^{n/4}2n/4 with probability better than 2−Θ(n)2^{-Θ(n)}2−Θ(n). The hardness persists even with multiple public-coin AM provers, Classical hardness with provers: Given 2O(n)2^{O(n)}2O(n) samples from a distribution and 2O(n)2^{O(n)}2O(n) communication with AM provers, no tester can estimate the support size up to factors 2Ω(n)2^{Ω(n)}2Ω(n) with probability better than 2−Θ(n)2^{-Θ(n)}2−Θ(n). Our result is tight. In contrast, coherent subset state proofs suffice to improve testability exponentially, Quantum advantage with certificates: With poly-many copies and subset state proofs, a tester can approximate the support size of a subset state of arbitrary size. Some structural assumption on the quantum proofs is required since we show, Collapse of QMA: A general proof cannot improve testability of any quantum property whatsoever. We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.
In this paper, we study the following question: given a black box performing some unknown quantum measurement on a multi-qudit system, how do we test whether this measurement has certain property or is far away from having this property. We call this task \textit{property testing} of quantum measurement. We first introduce a metric for quantum measurements, and show that it possesses many nice features. Then we show that, with respect to this metric, the following classes of measurements can be efficiently tested: 1. the stabilizer measurements, which play a crucial role for quantum error correction; 2. the kkk-local measurements, i.e. measurements whose outcomes depend on a subsystem of at most kkk qudits; 3. the permutation-invariant measurements, which include those measurements used in quantum data compression, state estimation and entanglement concentration. In fact, all of them can be tested with query complexity independent of the system's dimension. Furthermore, we also present an algorithm that can test any finite set of measurements. Finally, we consider the following natural question: given two black-box measurement devices, how do we estimate their distance? We give an efficient algorithm for this task, and its query complexity is also independent of the system's dimension. As a consequence, we can easily test whether two unknown measurements are identical or very different.