$$ \newcommand{\QSZK}{\textsf{QSZK}} \newcommand{\SZK}{\textsf{SZK}} \newcommand{\NP}{\textsf{NP}} \newcommand{\P}{\textsf{P}} \newcommand{\coNP}{\textsf{coNP}} \newcommand{\UP}{\textsf{UP}} \newcommand{\coUP}{\textsf{coUP}} \newcommand{\BQP}{\textsf{BQP}} \newcommand{\BPP}{\textsf{BPP}} $$ $$ \newcommand{\N}{\mathbb{N}} $$ $$ \newcommand{\A}{\mathcal{A}} \newcommand{\poly}{\text{poly}} \newcommand{\polylog}{\text{polylog}} $$ $$ \newcommand{\ket}[1]{\lvert #1 \rangle} \newcommand{\bra}[1]{\langle #1 \rvert} \newcommand{\coloneqq}{\mathrel{:=}} \newcommand{\dim}{\text{dim}} $$

[Moved from my previous blog.]

John Watrous and I finally put our paper “Oracle Separations for Quantum Statistical Zero-Knowledge” on the arXiv. This post hopes to motivate and put our work in context. In what follows, I assume that you are familiar with quantum computing, but if you see something you do not quite understand, feel free to ask about it in the comments.

\(\BQP\) is the class of problems a quantum computer can efficiently solve; that is, there exists a polynomial-time uniform family of quantum circuits that accepts with high probability if the answer is yes and rejects with high probability if the answer is no. This class generalizes \( \BPP \). See Deutsch (1985), Bernstein and Vazirani (1997) or the survey of Watrous (2008) for more on this.

Before we proceed, I wanna stress a technical point: we are only interested in promise problems! These are pairs \( (A_{\text{yes}}, A_{\text{no}}) \) of sets which correspond to yes and no inputs. Most people in theoretical computer science are familiar with languages, but promise problems are more general and better, trust me, or see Goldreich (2005). tl;dr: When you are dealing with probability distributions or more generally quantum states, one tends to run into edge problems. For instance, consider this meta problem: accept if the probability of acceptance of a circuit is greater than \( \frac{3}{4} \). What is the circuit supposed to do for \( \frac{3}{4} - \epsilon \) where \( \epsilon \) is insanely small? The behavior is clearly undefined. So, in the world of promise problems we say something like: accept if it accepts with probability greater than \( \frac{3}{4} \) (the \(A_{\text{yes}}\)) and reject if it accepts with probability less than \( \frac{1}{4} \) (the \(A_{\text{no}}\)). And, we don’t care about inputs which are not in \( A_{\text{yes}} \cup A_{\text{no}} \).

So, what is \( \UP \)? It is the class of problems for which one has a unique witness or proof (Recall, that \( \NP \) just requires a witness). An example of a \( \UP \) problem is Factoring (in a UFD, if you know what that is), as one always has a unique factorization. But, let me put it in this promise problem framework: Given \( x \in \N \), accept if it has a factor less than \( 17 \) and reject if it does not. The witness would be the prime factorization of \( x \). This class naturally arises in the context of counting complexity (Valiant, 1976). It is also known that one-way functions exist if and only if \( \P \neq \UP \) (Grollmann and Selman, 1988) (Ko, 1985). I will also add that one-way permutations exist if and only if \( \P \neq (\UP \cap \coUP) \) (Homan and Thakur, 2003).

Finally, \( \QSZK \) is the class of problems that have quantum statistical zero-knowledge interactive proofs (hence the name). Watrous (2002) gave a natural complete problem for this class, which is similar to Sahai and Vadhan’s (2003) Statistical Difference. Watrous’ complete problem goes like this: given two quantum states \( \rho \) and \( \sigma \), accept if the states are close to each other and reject if they are far apart. When I first saw this problem, I was like “Can’t you just measure and output the result?” Well, you cannot always do that because the closeness and farness only guarantee that a measurement exists but says nothing about the complexity of the measurement. This class naturally arises in the context of quantum error correction and separability testing (Gutoski, Hayden, Milner and Wilde, 2013). I also can’t not mention the beautiful paper of Harlow and Hayden (2013). For more on QSZK, see Watrous (2002) and Watrous (2009).

We believe that \( \QSZK \) is strictly larger than \( \BQP \). Intuitively, it also seems that \( \SZK \) (replace the quantum states above with probability distributions) is not contained in \( \BQP \). But even constructing an oracle such that they were distinct was a big open problem in quantum query complexity for a while before Aaronson resolved it in 2002. See, also, Aaronson and Shi (2004).

As I noted in an earlier post, Bennett, Bernstein, Brassard and Vazirani (1997) proved the existence an oracle such that \( (\NP \cap \coNP) \not\subseteq \BQP \) and of a random oracle such that \( \NP \not\subseteq \BQP \). Shortly afterward, Fornow and Rogers (1998) proved the existence an oracle such that \( (\UP \cap \coUP) \not\subseteq \BQP \). In this work, we generalized these results to \( \QSZK \). Specifically, we proved the existence of an oracle such that \( (\UP \cap \coUP) \not\subseteq \QSZK \) and that with respect to a random oracle \( \UP\not\subseteq \BQP \).

I hope that is enough motivation to read the paper. :-D