Testing Classical Properties from Quantum Data

A Boolean function is symmetric if $f(x)=f(y)$ when $x$ is a permutation of $y$. We show that projecting $|f⟩$ onto the symmetric subspace yields an $𝒪(1)$-copy quantum test. For comparison, classical passive symmetry testing requires $\mathrm{\Omega }(n^{1/4})$ samples [4].

A Boolean function $f$ is monotone if $f(x)\le f(y)$ when $x\prec y$ in the standard partial order $\prec$ on the hypercube. Monotonicity has been of central importance in the classical property testing literature [58, 18, 74]. We give a quantum algorithm that tests monotonicity with $\widetilde{𝒪}(n^2)$ copies of $|f⟩$, in comparison to the lower bound of $2^{\mathrm{\Omega }(\sqrt{n})}$ samples for classical passive testing [24].

The algorithm appeals to a characterization of monotonicity in terms of the Fourier spectrum of $f$. In particular, let $\epsilon$ be the $L^1$ distance between a Boolean function $f$ and the set of all monotone functions. Then we may relate $\epsilon$ to the Fourier spectrum of $f$ via

Here $𝐈[f]$ is the total influence of $f$ and is equal to the expected size of a subset $S\subseteq [n]$ sampled according to the Fourier distribution of $f$. $𝐈[f]$ can thus be easily estimated with Fourier sampling, and the Fourier coefficients $\widehat{f}(\{i\})$ estimated with classical samples. The bounds above follow from a reinterpretation of the “pair tester” characterization of monotonicity [58], which was not originally Fourier-based.

A Boolean function $f$ is triangle-free if there are no $x,y$ such that $(x,y,x+y)$ form a triangle: $f(x)=f(y)=f(x+y)=1$. We give a passive quantum triangle-freeness tester that uses only $𝒪(1)$ copies of $|f⟩$. This is to be contrasted with the $\mathrm{\Omega }(2^{n/3})$ samples required classically.³³3This lower bound, the proof of which we outline in [37, Appendix A.2], arises from the requirement of seeing a linearly dependent triple $(x,y,x+y)$ among the sampled inputs.

It is known that to test triangle-freeness, it suffices to estimate the probability that $(x,y,x+y)$ forms a triangle for uniformly random $x,y$ [54, 66]. Our test estimates this probability by repeating the following subroutine. First, measuring copies of $|f⟩$ in the computational basis allows us to find a uniformly random $y\in f^{-1}(1)$. Then by measuring the output register of copies of $|f⟩$, we obtain copies of the entire $1$-preimage state

Applying the unitary transformation $U_y|x⟩=|x+y⟩$ then allows us to transform copies of $|f^{-1}(1)⟩$ into copies of

The overlap $|⟨f^{-1}(1)|f^{-1}(1)+y⟩|={\mathrm{Pr}}_{x\sim {\{0,1\}}^n}[f(x)=f(x+y)=1]$ can now be estimated with a SWAP test [32].

We have established upper bounds for passive quantum testing of monotonicity, symmetry, and triangle-freeness from function states. These three properties together with linearity testing [19] and junta testing [13, 6] already demonstrate the power of quantum data for testing a variety of quite different properties, and it seems important to explore quantum datasets in the context of other testing problems. As highlighted in Table 1, quantum low-degree testing of Boolean functions is a natural next challenge, with the more general class of locally characterized affine-invariant properties [20] as a longer-term goal.

One may aim to tighten our bounds to precisely pin down the power of quantum data for these testing tasks. Here, having established that the constructions from classical passive monotonicity testing lower bounds are inadequate for the quantum case, we consider it especially interesting to obtain a $n$-dependent lower bound for passive quantum monotonicity testing in the constant $\epsilon$ regime. Settling the $n$-dependence of the quantum sample complexity for passive quantum monotonicity testing is a tantalizing question for future work.

In the classical case, [27] gave a complete characterization of those properties that can be tested with a constant number of samples. Achieving an analogous characterization for properties that can be tested from constantly-many function state copies would help demarcate the boundary of quantum advantage for this model.

The quantum case raises a further question about the constant complexity regime: For properties that admit a constant-copy passive quantum testers, can this always be achieved by algorithms that do not use entangled multi-copy measurements? The role of single- versus multi-copy quantum processing has recently been explored in the literature on learning and testing for quantum objects (see, e.g., [42, 68, 36, 67]) and in quantum computational learning theory [10], but the picture is far from clear for properties of function states (and of pure states more generally). Concretely, while our testers for monotonicity and symmetry are single-copy algorithms, our triangle-freeness tester uses two-copy SWAP tests and there does not seem to be an immediate way of replacing this by single-copy quantum processing.

One may also ask about the necessity of auxiliary systems in quantum sample-based testers with constant sample complexity; for example, our symmetry tester relied on auxiliary systems to implement the symmetric subspace projector. The number of available auxiliary systems is already known to play an important role in, for instance, Pauli channel learning [41, 40, 43], and exploring its relevance for constant-complexity passive quantum testing may shed new light on how these quantum testers achieve their better-than-classical performance.

We have considered only one kind of quantum representation of classical functions: coherent superpositions of evaluations of $f$ (as function states). Already these are enough to gain major advantages over testing from classical data, but one could ask for more. Are there other, better quantum datasets that lead to even faster testers or extend quantum advantage to more properties? To keep this question interesting, one would require that the dataset be not too tailored to any property.

In fact, this question may be best phrased as a sort of “compression game”: we are first given a very long list of questions that we might be asked regarding some black-box function $f$. We then have $T(n)$ time to interact with an oracle for $f$, during which period we generate whatever data we would like. What is the best quantum dataset to generate, so that we are best prepared to answer a random (or perhaps worst-case) question from the list?

Recently there is a growing interest in property testing for quantum objects, such as states [64, 83, 63, 35, 15, 62, 92, 42, 61, 11, 45, 9, 16], unitaries [49, 46, 90], channels [42, 3, 17], and Hamiltonians [76, 28, 12]. It is an interesting challenge to design datasets to enable passive versions of these tasks. Just as above, we would want quantum datasets that are agnostic to the property to be tested.

Some existing work can be viewed as advocating for quantum datasets. When restricting ourselves to collecting classical data, classical shadows [70, 69] serve as a useful representation, but place restrictions on the properties that can be tested after-the-fact. Shadow tomography procedures [1, 14, 36] can remove such restrictions but use multi-copy measurements that depend on the properties of interest, and thus in general seem to require quantum data storage to enable passivity.⁵⁵5(Non-adaptive) Pauli shadow tomography [71, 36, 75, 44] in some sense interpolates between the (dis-)advantages of classical shadows and shadow tomography for the current discussion: When promised in advance that the properties in question are characterized by expectation values of arbitrary Pauli observables, some of the relevant data can be collected and stored classically in advance, without knowing which specific Pauli observables matter. However, part of the quantum processing still requires knowing the specific Paulis of interest, so to achieve passivity, it seems that some data still has to be stored quantumly. The relevance of data storage in a quantum memory for certain quantum process learning tasks has also been explored in [22, 23, 89, 78, 77]. In this context, our work can be viewed as investigating the power of quantum data, stored in quantum memory, for testing properties of diagonal unitary processes arising from classical Boolean functions. We hope that this will inspire future attempts at using quantum data as a resource for passively quantumly testing properties of more general quantum processes.

We begin with a useful rewriting of the probability from Equation 2. To this end, as is commonly done in the analysis of Boolean functions, consider the induced function $g:{\{-1,1\}}^n\to \{-1,1\}$ obtained from $f$ via the relabeling $0\leftrightarrow 1$ and $1\leftrightarrow -1$. Next, we recall the definition of the $i$th derivative in Boolean analysis (compare, e.g., [82, Definition 2.16]): For $i\in [n]$,

where we used the notation $x^{(i\mapsto b)}$ to denote the $n$-bit string obtained from $x$ by replacing the $i$th bit with $b$. Consequently, we can compute

Therefore, we can now rewrite our probability of interest as

where the second-to-last step used the definition of the $i$th influence (compare [82, Definition 2.17]) as well as [82, Proposition 2.19], and where the last step used the definition of the total influence (compare [82, Definition 2.27]).

With this rewriting established, let us first analyze the probabilities that the different steps of Algorithm 1 succeed and discuss what this implies for the estimator $\widehat{p}$. Then, we will see how this gives rise to completeness and soundness. We have the following:

• $\mathrm{■}$

  Using the procedure of [19], one copy of $|f⟩$ suffices to produce one Fourier sample from $g={(-1)}^f$ – an $n$-bit string sampled from the probability distribution ${\{{|\widehat{g}(S)|}^2\}}_{S\subseteq [n]}$ – with success probability $1/2$. Additionally, one knows whether the sampling attempt was successful.⁶⁶6To see this, note that the procedure works as follows: Apply $H^{\otimes (n+1)}$; measure the last qubit; abort if that produces a $0$, continue if produces a $1$; measure the first $n$ qubits to produce an $n$-bit string. So, by simply repeating the above $m_1$ many times, we see that Step 1 succeeds in producing $m_2$ Fourier samples with success probability $\ge 1-{\delta }_1$.

• $\mathrm{■}$

  By a Chernoff-Hoeffding bound, we have $|\widehat{𝐈}-{𝔼}_{S\sim {𝒮}_g}[|S|]|\le {\epsilon }_2$ with success probability $\ge 1-{\delta }_2$. Here, ${𝒮}_g$ denotes the Fourier distribution of $g$, defined via ${𝒮}_g(S)={|\widehat{g}(S)|}^2$.

• $\mathrm{■}$

  For any $1\le i\le n$, by a standard Chernoff-Hoeffding bound, Step 5 produces a ${\epsilon }_5$-accurate estimate ${\tilde{g}}_i$ of $\widehat{g}(\{i\})$ with probability $\ge 1-{\delta }_5$.

Therefore, by a union bound, we have that, with overall success probability $\ge 1-({\delta }_1+{\delta }_2+n{\delta }_5)=1-\delta$, the estimates $\widehat{𝐈}$ and ${\tilde{g}}_i$ simultaneously satisfy $|\widehat{𝐈}-{𝔼}_{S\sim {𝒮}_g}[|S|]|\le {\epsilon }_2$ and $|{\tilde{g}}_i-\widehat{g}(\{i\})|\le {\epsilon }_5$ for all $1\le i\le n$. We condition on this high probability success event for the rest of the proof. In this event, our rewriting of the probability of interest from the beginning of the proof implies:

where we used the identity $𝐈[g]={𝔼}_{S\sim {𝒮}_g}[|S|]$ (compare [82, Theorem 2.38]). So, we see that $\widehat{p}$ is a $(\epsilon /3n)$-accurate estimate for our probability of interest.

To prove completeness of Algorithm 1, assume $f$ to be monotone. Then, Theorem 8 together with the above inequality imply that $\widehat{p}\le \epsilon /3n\le \epsilon /2n$, and thus the final step in Algorithm 1 correctly concludes that $f$ is monotone and accepts.

To prove soundness, assume $f$ to be $\epsilon$-far from monotone. Then, the lower bound in Theorem 8 together with the above inequality implies that $\widehat{p}\ge 2\epsilon /3n$, and thus the final step in Algorithm 1 correctly concludes that $f$ is $\epsilon$-far from monotone and rejects.

The overall number of copies of $|f⟩$ used by the algorithm is $m_1+m_4$. Plugging in the choices of the different $m_i$, we see that

where the $\widetilde{𝒪}$ hides a logarithmic dependence on $n$.

The quantum computational efficiency of Algorithm 1 follows immediately from the efficiency of quantum Fourier sampling. The classical computational efficiency is immediately apparent from our sample complexity bounds and the fact that the classical computation is dominated by the complexity of computing the empirical averages in Steps 2 and 4. $◀$

We note that because of the second inequality in Theorem 8, the above procedure and proofs can be modified to quantumly efficiently solve the tolerant version (as defined in [84]) of the monotonicity testing problem – i.e., distinguishing between $f$ being ${\epsilon }_1$-close or ${\epsilon }_2$-far from monotone – using $\widetilde{𝒪}\left(\frac{n^2\log (1/\delta )}{{({\epsilon }_2-{\epsilon }_1)}^2}\right)$ copies of a quantum function state, assuming that ${\epsilon }_2>Cn{\epsilon }_1$ holds with $C>1$ some constant.⁷⁷7In more generality, one can see: If an inequality like Equation 2 holds with lower bound ${\mathrm{\ell }}_n(\epsilon )$ and upper bound $u_n(\epsilon )$, satisfying ${\mathrm{\ell }}_n(0)=0=u_n(0)$, then estimating the relevant probability to accuracy $\sim {\mathrm{\ell }}_n({\epsilon }_2-{\epsilon }_1)$ suffices for tolerant property testing in the parameter range where there is a constant $c\in (0,1/2)$ such that ${\mathrm{\ell }}_n({\epsilon }_2)-c\cdot {\mathrm{\ell }}_n({\epsilon }_2-{\epsilon }_1)>u_n({\epsilon }_1)+c\cdot {\mathrm{\ell }}_n({\epsilon }_2-{\epsilon }_1)$. Because of this assumption on how ${\epsilon }_1$ and ${\epsilon }_2$ relate, this still falls short of a general tolerant passive quantum monotonicity tester.

Let us also note room for a qualitative improvement in our passive quantum monotonicity tester. Classical query-based testers typically enjoy perfect completeness, i.e., accept monotone functions with unit probability. In contrast, our tester can be made to accept monotone functions with probability arbitrarily close but not equal to $1$. We leave open whether our passive quantum monotonicity tester can be modified to achieve perfect completeness, while enjoying similar guarantees on the quantum sample and time complexity of the procedure.