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:1205.0828

Property Testing of Quantum Measurements

Guoming Wang

Published May 3, 2012• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1205.0828

Related papers

Quantum Algorithms for Testing Properties of Distributions

Sergey B. Bravyi, Aram W. Harrow, Avinatan Hassidim

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).

arXiv:0907.3920•IEEE Transactions on Information Theory•May 25, 2011•59 citations

A Unified Complexity Framework for Quantum Property Testing

Qisheng Wang

We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.

quant-pharXiv:2608.02600•Aug 4, 2026•10 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

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or $\varepsilon$-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of $Θ(1/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$-close to a target unitary or $\varepsilon_2$-far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

quant-pharXiv:2606.10730•Jun 10, 2026•1 citation

Unitary Property Testing Lower Bounds by Polynomials

Adrian She, Henry Yuen

We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between $\mathsf{QMA}$ and $\mathsf{QMA(2)}$, a long standing question in quantum complexity theory.

arXiv:2210.05885•Leibniz international proceedings in informatics•Oct 12, 2022•31 citations

Property testing of unitary operators

Guoming Wang

In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general.

arXiv:1110.1133•Physical Review A•Nov 28, 2011•41 citations
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.
Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr⁡(φ(dρ))/d\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/dLφ​(ρ)=tr(φ(dρ))/d, where ρρρ is an unknown ddd-dimensional quantum state and φφφ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ)\mathcal{L}_φ(ρ)Lφ​(ρ) from properties of φφφ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ ⁣(d2εlog⁡2(d)max⁡{1,εlog⁡2(d)}+log⁡2(d)ε2), Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), Θ(εlog2(d)max{1,εlog2(d)}d2​+ε2log2(d)​), and the sample complexity of spectrum estimation is Θ ⁣(d2ε2log⁡2(d)max⁡{1,ε2log⁡2(d)}). Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). Θ(ε2log2(d)max{1,ε2log2(d)}d2​). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
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}.
We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or ε\varepsilonε-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of Θ(1/ε).Θ(1/\varepsilon).Θ(1/ε). The query complexity of the relaxed problem of testing whether the black-box channel is ε1\varepsilon_1ε1​-close to a target unitary or ε2\varepsilon_2ε2​-far in the diamond distance is Θ(ε2/(ε2−ε1)2).Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).Θ(ε2​/(ε2​−ε1​)2). In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.
We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between QMA\mathsf{QMA}QMA and QMA(2)\mathsf{QMA(2)}QMA(2), a long standing question in quantum complexity theory.
In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general.