Complexity Limitations on One-turn Quantum Refereed Games

Abstract

This paper studies complexity theoretic aspects of quantum refereed games, which are abstract games between two competing players that send quantum states to a referee, who performs an efficiently implementable joint measurement on the two states to determine which of the player wins. The complexity class QRG(1) contains those decision problems for which one of the players can always win with high probability on yes-instances and the other player can always win with high probability on no-instances, regardless of the opposing player’s strategy. This class trivially contains QMA ∪co-QMA and is known to be contained in PSPACE. We prove stronger containments on two restricted variants of this class. Specifically, if one of the players is limited to sending a classical (probabilistic) state rather than a quantum state, the resulting complexity class CQRG(1) is contained in ∃⋅PP (the nondeterministic polynomial-time operator applied to PP); while if both players send quantum states but the referee is forced to measure one of the states first, and incorporates the classical outcome of this measurement into a measurement of the second state, the resulting class MQRG(1) is contained in P ⋅PP (the unbounded-error probabilistic polynomial-time operator applied to PP).

1 Introduction

Abstract notions of games have long played an important role in complexity theory. For example, combinatorial games provide complete problems for various complexity classes [14], the notion of alternation is naturally described in game-theoretic terms [12], and interactive proof systems [3, 5, 22, 23] and many variants of them are naturally formulated as games [13, 18].

This paper is concerned with games between two competing, computationally unbounded players, administered by a computationally bounded referee. In the classical setting, complexity theoretic aspects of games of this form were investigated in the 1990s by Koller and Megiddo [29], Feigenbaum, Koller, and Shor [18], Condon, Feigenbaum, Lund, and Shor [10, 11], and Feige and Kilian [17]. Quantum computational analogues of these games were later considered in [24,25,26], and [28].

Our focus will be on one-turn refereed games, in which the players and the referee first receive a common input string, and then each player sends a single polynomial-length (quantum or classical) message to the referee, who then decides which player has won. We will refer to the two competing players as Alice and Bob for convenience. In the classical case Alice and Bob’s messages may in general be described by probability distributions over strings, while in the quantum case Alice and Bob’s messages are described by mixed quantum states, which are represented by density operators. In both cases, the referee’s decision process must be specified by a polynomial-time generated family of (quantum or classical) circuits. Two complexity classes are defined—RG(1) in the classical setting¹ and QRG(1) in the quantum setting—consisting of all promise problems A = (A_yes, A_no) for which there exists a game (either classical or quantum, respectively) such that Alice can win with high probability on inputs x ∈ A_yes and Bob can win with high probability on inputs x ∈ A_no, regardless of the other player’s behavior.

In essence, the complexity classes RG(1) and QRG(1) may be viewed as extensions of the classes MA and QMA in which two competing Merlins, one whose aim is to convince the referee (whose role is analogous to Arthur, also called the verifier, in the case of MA and QMA) that the input string is a yes-instance of a given problem, and the other whose aim is to convince the referee that the input string is a no-instance.

It is known that the complexity class RG(1) is equal to $\mathrm {S}_{2}^{p}$, which refers to the second level of the symmetric polynomial-time hierarchy introduced by Canetti [9] and Russell and Sundaram [35]. This class is most typically defined in terms of quantifiers that suggest games in which Alice and Bob choose polynomial-length strings (as opposed to probability distributions of strings) to send to the referee, but the class does not change if one adopts a bounded-error definition in which Alice and Bob are allowed to make use of randomness [16]. Moreover, the class does not change if the referee is permitted the use of randomness, again assuming a bounded-error definition. An essential fact through which these equivalences may be proved, due to Althöfer [2] and Lipton and Young [32], is that non-interactive randomized games always admit near-optimal strategies that are uniform over polynomial-size sets of strings. It is also known that RG(1) is closed under Cook reductions [35] and satisfies $\text {RG}(1) \subseteq \text {ZPP}^{\text {NP}}$ [8].

In contrast to the containment $\text {RG}(1) \subseteq \text {ZPP}^{\text {NP}}$, the best upper-bound known for QRG(1) is that this class is contained in PSPACE [28]. It is reasonable to conjecture that a stronger upper-bound on QRG(1) can be proved.

Indeed, Gutoski and Wu [27] proved that even the class QRG(2), which is analogous to QRG(1) except that the referee first sends a message to Alice and Bob and then receives responses from them, is contained in PSPACE. The two classes are in fact equal, meaning QRG(2) = PSPACE, as a consequence of the trivial containment $\text {RG}(2) \subseteq \text {QRG}(2)$ together with the known equality RG(2) = PSPACE [17]. While not directly relevant to our results, we note that the classes RG = RG(poly) and QRG = QRG(poly) defined in an analogous way, but allowing any polynomial number of messages between the referee and Alice and Bob are both equal to EXP [17, 26].

In this work we consider two restricted variants of QRG(1), and prove stronger upper-bounds than PSPACE on these restricted variants. The first variant is one in which Alice is limited to sending a classical message to the referee, while Bob is free to send a quantum state. The resulting class, which we call CQRG(1), is proved to be contained in ∃⋅PP (the class obtained when the nondeterministic polynomial-time operator is applied to PP). This containment follows from an application of the Althöfer–Lipton–Young technique mentioned above, although in the quantum setting the proof requires relatively recent tail bounds on sums of matrix-valued random variables, as opposed to a more standard Hoeffding–Chernoff type of bound that suffices in the classical case. In particular, we make use of a tail bound of this sort due to Tropp [36]. The second variant we consider is one in which both Alice and Bob are free to send quantum states, but where the referee must first measure Alice’s state and then incorporate the classical outcome of this measurement into a measurement of Bob’s state. We call the corresponding class MQRG(1), and prove the containment $\text {MQRG}(1)\subseteq \mathrm {P}\cdot \text {PP}$ (the class obtained when the unbounded error probabilistic polynomial-time operator is applied to PP). Note that ∃⋅PP is contained in P ⋅PP, which is, in turn, contained in PSPACE.

2 Preliminaries

We assume the reader is familiar with basic aspects of computational complexity theory and quantum information and computation. There are four subsections included in this preliminaries section, the first of which clarifies a few specific concepts, conventions, and definitions concerning complexity theory. The second subsection is concerned specifically with counting complexity, and presents a development of some results on this topic that are central to this paper. Proofs are included because these results represent minor generalizations of known results on counting complexity. The third subsection discusses a few specific definitions and concepts from quantum information and computation, along with a proof of a fact that may be considered a known result, but for which a complete proof does not appear in published form. The final subsection states the tail bound due to Tropp mentioned above.

2.1 Complexity theory basics

Throughout this paper, languages, promise problems, and functions on strings are assumed to be over the binary alphabet Σ = {0,1}. The set of natural numbers, including 0, is denoted $\mathbb {N}$.

A function of the form $p:\mathbb {N}\rightarrow \mathbb {N}$ is said to be polynomially bounded if there exists a deterministic Turing machine that runs in polynomial time and outputs 0^p(n) on input 0ⁿ for all $n\in \mathbb {N}$. Unless it is explicitly indicated otherwise, the input of a given polynomially bounded function p is assumed to be the natural number |x|, for whatever input string x ∈ Σ^∗ is being considered at that moment. With this understanding in mind, we will write p in place of p(|x|) when referring to the natural number output that is determined in this way. For example, in Definition 1 below, all of the occurrences of p in the displayed equations are short for p(|x|). This convention helps to make formulas and equations more clear and less cluttered.

A promise problem is a pair A = (A_yes, A_no) of sets of strings $A_{\text {yes}},A_{\text {no}}\subseteq {\Sigma }^{\ast }$ with $A_{\text {yes}} \cap A_{\text {no}} = \varnothing$. Strings in A_yes represent yes-instances of a decision problem, strings in A_no represent no-instances, and all other strings represent “don’t care” inputs for which no restrictions are placed on a hypothetical computation for that problem.

We fix a pairing function that efficiently encodes two strings x, y ∈Σ^∗ into a single binary string denoted 〈x, y〉 ∈ Σ^∗, and we assume that this function satisfies some simple properties:

• 1. The length of the pair 〈x, y〉 depends only on the lengths |x| and |y|, and is polynomial in these lengths.

• 2. The computation of x and y from 〈x, y〉, as well as the computation of 〈x, y〉 from x and y, can be performed deterministically in polynomial time.

One suitable choice for such a function is suggested by the equation

$$ \langle a_{1} a_{2} {\cdots} a_{n}, b_{1} b_{2} {\cdots} b_{m} \rangle = 0 a_{1} 0 a_{2} {\cdots} 0 a_{n} 1 b_{1} b_{2} {\cdots} b_{m} $$

(1)

for a₁,a₂,…,a_n,b₁,b₂,…,b_m ∈Σ. Any such pairing function may be extended recursively to obtain a tuple function for any fixed number of inputs by taking

$$ \langle x_{1},x_{2},x_{3},\ldots,x_{k}\rangle = \langle \langle x_{1},x_{2}\rangle, x_{3}, \ldots, x_{k}\rangle $$

(2)

for strings $x_{1},\ldots ,x_{k}\in {\Sigma }^{\ast }$, where k ≥ 3. Hereafter, when we refer to the computation of any function taking multiple string-valued arguments, we assume that these input strings have been encoded into a single string using this tuple function. For instance, when f is a function that represents a computation, we write f(x, y, z) rather than f(〈x, y, z〉).

Finally, we define the nondeterministic and probabilistic polynomial-time operators, which may be applied to an arbitrary complexity class, as follows.

Definition 1

For a given complexity class of languages $\mathcal {C}$, the complexity classes $\exists \cdot \mathcal {C}$ and $\mathrm {P}\cdot \mathcal {C}$ are defined as follows.

• 1. The complexity class $\exists \cdot \mathcal {C}$ contains all promise problems A = (A_yes,A_no) for which there exists a language $B\in \mathcal {C}$ and a polynomially bounded function p such that these two implications hold:

  $$ \begin{array}{@{}rcl@{}} x\in A_{\text{yes}} &\Rightarrow& \Bigl\{y\in{\Sigma}^{p} : \langle x,y\rangle\in B\Bigr\} \not=\varnothing, \\ x\in A_{\text{no}} &\Rightarrow& \Bigl\{y\in{\Sigma}^{p} : \langle x,y\rangle\in B\Bigr\} =\varnothing. \end{array} $$

  (3)

• 2. The complexity class $\textup {P}\cdot \mathcal {C}$ contains all promise problems A = (A_yes,A_no) for which there exists a language $B\in \mathcal {C}$ and a polynomially bounded function p such that these two implications hold:

  $$ \begin{array}{@{}rcl@{}} x\in A_{\text{yes}} &\Rightarrow& \Bigl| \Bigl\{y\in{\Sigma}^{p} : \langle x,y\rangle\in B\Bigr\} \Bigr| > \frac{1}{2} \cdot 2^{p}, \\ x\in A_{\text{no}} &\Rightarrow& \Bigl| \Bigl\{y\in{\Sigma}^{p} : \langle x,y\rangle\in B\Bigr\} \Bigr| \leq \frac{1}{2} \cdot 2^{p}. \end{array} $$

  (4)

2.2 Counting complexity

Counting complexity is principally concerned with the number of solutions to certain computational problems. Readers interested in learning more about counting complexity and some of its applications are referred to the survey paper of Fortnow [19]. As was suggested at the beginning of the current section, we will require some basic results on counting complexity that represent minor generalizations of known results. We begin with the following definition.

Definition 2

Let $\mathcal {C}$ be any complexity class of languages over the alphabet Σ. A function $f:{\Sigma }^{\ast } \rightarrow \mathbb {Z}$ is a $\textup {Gap}\cdot \mathcal {C}$ function if there exist languages $A,B\in \mathcal {C}$ and a polynomially bounded function p such that

$$ f(x) = \bigl| \bigl\{ y\in{\Sigma}^{p} : \langle x,y\rangle \in A\bigr\} \bigr| -\bigl| \bigl\{y\in{\Sigma}^{p} : \langle x,y\rangle \in B\bigr\} \bigr| $$

(5)

for all x ∈Σ^∗.

We observe that this definition is slightly non-standard, as gap functions are usually defined in terms of differences between the number of accepting and rejecting computations of nondeterministic machines (as opposed to a difference involving two potentially unrelated languages A and B). It is also typical that one focuses on specific choices for $\mathcal {C}$, particularly $\mathcal {C} = \mathrm {P}$. Our definition is, however, equivalent to the traditional definition in this case, and we will write GapP rather than Gap ⋅P so as to be consistent with the standard name for this class of functions. We will also be interested in the case $\mathcal {C} = \text {PP}$, which yields a class of functions Gap ⋅PP that is less commonly considered.

A key feature of the class of GapP functions that facilitates its use is that it possesses strong closure properties. This is true more generally for the class $\text {Gap}\cdot \mathcal {C}$ provided that $\mathcal {C}$ itself possesses certain properties. For the closure properties we require, it suffices that $\mathcal {C}$ is nontrivial (meaning that $\mathcal {C}$ contains at least one language that is not equal to $\varnothing$ or Σ^∗) and is closed under the join operation as well as polynomial-time truth-table reductions. (The join of languages A and B is defined as {x0 : x ∈ A}∪{x1 : x ∈ B}.) These properties are, of course, possessed by both P and PP, with the closure of PP under truth table reductions having been proved by Fortnow and Reingold [20] based on methods developed by Beigel, Reingold, and Spielman [6].

The following proposition is immediate from the definitions of $\text {Gap}\cdot \mathcal {C}$ and $\mathrm {P}\cdot \mathcal {C}$.

Proposition 3

Let $\mathcal {C}$ be a complexity class of languages that is closed under complementation and joins. A promise problem A = (A_yes,A_no) is contained in $\mathrm {P}\cdot \mathcal {C}$ if and only if there exists a $\text {Gap}\cdot \mathcal {C}$ function f such that

$$ \begin{array}{@{}rcl@{}} x\in A_{\text{yes}} & \Rightarrow f(x) > 0, \\ x\in A_{\text{no}} & \Rightarrow f(x) \leq 0. \end{array} $$

(6)

The lemmas that follow establish the specific closure properties we require. For the first property the assumption that $\mathcal {C}$ is closed under joins and polynomial-time truth-table reductions is not required; closure under Karp reductions suffices.

Lemma 4

Let $\mathcal {C}$ be a nontrivial complexity class of languages that is closed under Karp reductions. Let $f\in \text {Gap}\cdot \mathcal {C}$ and let p be a polynomially bounded function. The function

$$ g(x) = \sum\limits_{y\in{\Sigma}^{p}} f(x,y) $$

(7)

is a $\text {Gap}\cdot \mathcal {C}$ function.

Proof

By the assumption that $f\in \text {Gap}\cdot \mathcal {C}$, there exists a polynomially bounded function q and languages $A_{0},A_{1}\in \mathcal {C}$ such that

$$ f(x,y) = \bigl| \bigl\{ z\in{\Sigma}^{q(| \langle x,y\rangle |)} : \langle x,y,z\rangle \in A_{0}\bigr\} \bigr| -\bigl| \bigl\{ z\in{\Sigma}^{q(| \langle x,y\rangle |)} : \langle x,y,z\rangle \in A_{1}\bigr\} \bigr| $$

(8)

for all x ∈Σ^∗ and y ∈Σ^p. By the assumptions on our pairing function described above, it is the case that |〈x, y〉| depends only on |x| and |y|, and therefore there exists a (necessarily polynomially bounded) function r such that r(|x|) = p(|x|) + q(|〈x, y〉|) for all x ∈Σ^∗ and y ∈Σ^p. Define

$$ \begin{array}{@{}rcl@{}} B_{0} & = \bigl\{ \langle x,yz\rangle : y \in {\Sigma}^{p}, z \in {\Sigma}^{q(| \langle x,y\rangle |)}, \langle x,y,z\rangle \in A_{0}\bigr\}, \\ B_{1} & = \bigl\{ (x,yz) : y \in {\Sigma}^{p}, z \in {\Sigma}^{q(| \langle x,y\rangle |)}, \langle x,y,z\rangle \in A_{1}\bigr\}. \end{array} $$

(9)

By the nontriviality and closure of $\mathcal {C}$ under Karp reductions, it is evident that $B_{0},B_{1}\in \mathcal {C}$. It may be verified that

$$ g(x) = \bigl| \bigl\{w\in{\Sigma}^{r} : \langle x,w\rangle \in B_{0}\bigr\} \bigr| - \bigl| \bigl\{w\in{\Sigma}^{r} : \langle x,w\rangle \in B_{1}\bigr\} \bigr| $$

(10)

for all x ∈Σ^∗, and therefore $g\in \text {Gap}\cdot \mathcal {C}$. □

For the next lemma, and elsewhere in the paper, we will use the following notation for convenience: ${{\Sigma }^{n}_{1}}$ denotes the set of all strings over the binary alphabet Σ that have length n and contain exactly one occurrence of the symbol 1. It is therefore the case that $| {{\Sigma }^{n}_{1}} | = n$.

Lemma 5

Let $\mathcal {C}$ be a nontrivial complexity class of languages that is closed under joins and polynomial-time truth table reductions. Let $f\in \text {Gap}\cdot \mathcal {C}$ and let p be a polynomially bounded function. The function

$$ g(x) = {\prod}_{y{\in{\Sigma}_{1}^{p}}} f(x,y) $$

(11)

is a $\text {Gap}\cdot \mathcal {C}$ function.

Proof

Given that $f\in \text {Gap}\cdot \mathcal {C}$, there exists a polynomially bounded function q and languages $A_{0},A_{1}\in \mathcal {C}$ such that

$$ f(x,y) = \Bigl| \Bigl\{z \in {\Sigma}^{q(| (x,y) |)} : \langle x,y,z \rangle\in A_{0}\Bigr\} \Bigr| - \Bigl| \Bigl\{z\in{\Sigma}^{q(| (x,y) |)} : \langle x,y,z \rangle \in A_{1}\Bigr\} \Bigr| $$

(12)

for all x, y ∈Σ^∗. We may assume further that A₀ and A₁ are disjoint languages, for if they are not, we may replace A₀ and A₁ with $A_{0} \cap \overline {A_{1}}$ and $A_{1} \cap \overline {A_{0}}$, respectively; this does not change the value of the right-hand side of the (12), and the languages $A_{0} \cap \overline {A_{1}}$ and $A_{1} \cap \overline {A_{0}}$ must both be contained in $\mathcal {C}$ for $A_{0},A_{1}\in \mathcal {C}$ by the closure of $\mathcal {C}$ under joins and truth-table reductions.

By the assumptions on our pairing function described above, there exists a polynomially bounded function r such that r(|x|) = q(|(x, y)|) for all x ∈Σ^∗ and y ∈Σ^p. We will write y₁,…,y_p to denote the elements of ${{\Sigma }^{p}_{1}}$ sorted in lexicographic order. Define two languages B₀ and B₁ as follows:

• B₀ is the language of all pairs 〈x, z₁⋯z_p〉, where x ∈Σ^∗ and $z_{1},\ldots ,z_{p}\in {\Sigma }^{r}$, for which there exists a string w ∈Σ^p having even parity such that

  $$ \langle x,y_{1},z_{1}\rangle\in A_{w_{1}},\ldots,\langle x,y_{p},z_{p}\rangle \in A_{w_{p}}. $$

  (13)

• B₁ is the language of all pairs 〈x, z₁⋯z_p〉, where x ∈Σ^∗ and $z_{1},\ldots ,z_{p}\in {\Sigma }^{r}$, for which there exists a string w ∈Σ^p having odd parity such that

  $$ \langle x,y_{1},z_{1}\rangle\in A_{w_{1}},\ldots,\langle x,y_{p},z_{p}\rangle \in A_{w_{p}}. $$

  (14)

Given that A₀ and A₁ are disjoint and contained in $\mathcal {C}$, along with the fact that $\mathcal {C}$ is closed under joins and truth-table reductions, it follows that $B_{0},B_{1}\in \mathcal {C}$. The lemma now follows from the observation that

$$ g(x) = \Bigl| \Bigl\{z \in {\Sigma}^{s} : \langle x,z\rangle\in B_{0} \Bigr\} \Bigr| - \Bigl| \Bigl\{z \in {\Sigma}^{s} : \langle x,z\rangle\in B_{1}\Bigr\} \Bigr| $$

(15)

for all x ∈Σ^∗, where s = p ⋅ r. □

Lemma 6

Let $\mathcal {C}$ be a nontrivial complexity class of languages that is closed under joins and polynomial-time truth table reductions, let $f_{0},f_{1}\in \text {Gap}\cdot \mathcal {C}$, and let p and q be polynomially bounded functions. For every string x ∈Σ^∗ and $y{\in {\Sigma }^{q}_{1}}$, define the matrix M_{x, y} as

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle z |M_{x,y}| w \rangle\bigr) &=& f_{0}(x,y,z,w), \\ \text{Im}\bigl(\langle z |M_{x,y}| w \rangle\bigr) &=& f_{1}(x,y,z,w), \end{array} $$

(16)

for all z, w ∈Σ^p. In other words, each M_{x, y} is a matrix whose entries are indexed by z, w ∈Σ^p. There exist $\textup {Gap}\cdot \mathcal {C}$ functions g₀ and g₁ satisfying

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle z |M_{x,y_{1}}{\cdots} M_{x,y_{q}}| w \rangle\bigr) &=& g_{0}(x,z,w), \\ \text{Im}\bigl(\langle z |M_{x,y_{1}}{\cdots} M_{x,y_{q}}| w \rangle\bigr) &=& g_{1}(x,z,w), \end{array} $$

(17)

for all x ∈Σ^∗ and z, w ∈Σ^p, where y₁,…,y_q denote the elements of ${{\Sigma }^{q}_{1}}$ sorted in lexicographic order.

Proof

By the assumptions on $\mathcal {C}$ stated in the lemma, there must exist a $\textup {Gap}\cdot \mathcal {C}$ function h satisfying

$$ \begin{array}{@{}rcl@{}} h(x,y,0z,0w) &=& f_{0}(x,y,z,w),\\ h(x,y,0z,1w) &=& f_{1}(x,y,z,w),\\ h(x,y,1z,0w) &=& -f_{1}(x,y,z,w),\\ h(x,y,1z,1w) &=& f_{0}(x,y,z,w), \end{array} $$

(18)

for all x ∈Σ^∗, $y{\in {\Sigma }^{q}_{1}}$, and z, w ∈Σ^p. The matrix N_{x, y} defined as

$$ \langle u | N_{x,y} | v \rangle = h(x,y,u,v) $$

(19)

for all x ∈Σ^∗, $y{\in {\Sigma }^{q}_{1}}$ and u, v ∈Σ^p+ 1 may be visualized as a 2 × 2 block matrix:

$$ N_{x,y} = \left( \begin{array}{cc} \text{Re}(M_{x,y}) & \text{Im}(M_{x,y})\\ -\text{Im}(M_{x,y}) & \text{Re}(M_{x,y}) \end{array}\right). $$

(20)

We observe that

$$ N_{x,y_{1}} {\cdots} N_{x,y_{q}} = \left( \begin{array}{cc} \text{Re}\left( M_{x,y_{1}} {\cdots} M_{x,y_{q}}\right) & \text{Im}\left( M_{x,y_{1}} {\cdots} M_{x,y_{q}}\right)\\ -\text{Im}\left( M_{x,y_{1}} {\cdots} M_{x,y_{q}}\right) & \text{Re}\left( M_{x,y_{1}} {\cdots} M_{x,y_{q}}\right) \end{array}\right). $$

(21)

Given that h is a $\text {Gap}\cdot \mathcal {C}$ function, there must exist a $\text {Gap}\cdot \mathcal {C}$ function F for which

$$ F(x,u_{0}{\cdots} u_{q},y_{k}) = h(x,y_{k},u_{k-1},u_{k}) $$

(22)

for all x ∈Σ^∗, $u_{0},\ldots ,u_{q}\in {\Sigma }^{p+1}$, and k ∈{1,…,q}.

Finally, define

$$ G(x,u_{0} {\cdots} u_{q}) = \prod\limits_{y{\in{\Sigma}^{q}_{1}}} F(x,u_{0}{\cdots} u_{q},y) = h(x,y_{1},u_{0},u_{1}) {\cdots} h(x,y_{q},u_{q-1},u_{q}) $$

(23)

for all x ∈Σ^∗ and $u_{0},\ldots ,u_{q}\in {\Sigma }^{p+1}$, as well as

$$ \begin{array}{@{}rcl@{}} g_{0}(x,z,w) & = \sum\limits_{u\in{\Sigma}^{(q-1)(p+1)}} G(x,0zu0w), \\ g_{1}(x,z,w) & = \sum\limits_{u\in{\Sigma}^{(q-1)(p+1)}} G(x,0zu1w), \end{array} $$

(24)

for all x ∈Σ^∗ and z, w ∈Σ^p. It follows by Lemmas 4 and 5 that $g_{0},g_{1}\in \text {Gap}\cdot \mathcal {C}$.

Observing that g₀ and g₁ satisfy the (17), which is perhaps most evident from the (21), the proof of the lemma is complete. □

2.3 Quantum information and quantum circuits

The notation we use when discussing quantum information is standard for the subject, and we refer the reader to the books [30, 34, 38, 39] for further details. A couple of points concerning quantum information notation and conventions that may be helpful to some readers follow.

First, when we refer to a register X, we mean a collection of qubits that we wish to view as a single entity, and we then use the same letter $\mathcal {X}$ in a scripted font to denote the finite-dimensional complex Hilbert space associated with X (i.e., the space of complex vectors having entries indexed by binary strings of length equal to the number of qubits in X). The set of density operators acting on such a space is denoted $\mathrm {D}(\mathcal {X})$.

Second, a channel transforming a register X into a register Y is a completely positive and trace-preserving linear map $\mathcal {P}hi$ that transforms each density operator $\rho \in \mathrm {D}(\mathcal {X})$ into a density operator $\mathcal {P}hi(\rho )\in \mathrm {D}(\mathcal {Y})$. (More generally, such a mapping $\mathcal {P}hi$ transforms arbitrary linear operators acting on $\mathcal {X}$ into linear operators acting on $\mathcal {Y}$.) The adjoint of such a channel $\mathcal {P}hi$ is the uniquely determined linear map $\mathcal {P}hi^{\ast }$ transforming linear operators acting on $\mathcal {Y}$ into linear operators acting on $\mathcal {X}$ that satisfies the equation

$$ \text{Tr}\bigl(P \mathcal{P}hi(\rho)\bigr) = \text{Tr}\bigl(\mathcal{P}hi^{\ast}(P) \rho\bigr) $$

(25)

for all density operators $\rho \in \mathrm {D}(\mathcal {X})$ and all positive semidefinite operators P acting on $\mathcal {Y}$. The adjoint $\mathcal {P}hi^{\ast }$ of a channel $\mathcal {P}hi$ is not necessarily itself a channel, but rather is a completely positive and unital linear map, which means that (for and denoting the identity operators acting on $\mathcal {X}$ and $\mathcal {Y}$, respectively). Intuitively speaking, if P is a measurement operator in the equation above, one can think of $\mathcal {P}hi^{\ast }$ as transforming the measurement operator P into a new measurement operator $\mathcal {P}hi^{\ast }(P)$, with the probability of this outcome for the state ρ being the same as if one first applied $\mathcal {P}hi$ to ρ and then measured with respect to P.

Now we will move on to quantum circuits, which are acyclic networks of quantum gates connected by qubit wires. We choose to use the standard, general model of quantum information based on density operators and quantum channels, as opposed to the restricted model of pure state vectors and unitary operations, when discussing quantum circuits. In this general model, each gate represents a quantum channel acting on a constant number of qubits—including nonunitary gates, such as gates that introduce fresh initialized qubits or gates that discard qubits. Through this model, ordinary classical circuits, as well as classical circuits that introduce randomness into computations, can be viewed as special cases of quantum circuits. One may also represent measurements directly as quantum gates or circuits.

It is well-known that this general model is equivalent to the purely unitary model, as is explained in [1] and [37], for instance. The main benefits of using the general model in the context of this paper are that (i) it allows us to avoid having to constantly distinguish between input qubits and ancillary qubits, or output qubits and garbage qubits, and (ii) it has the minor but nevertheless positive side effect of eliminating the appearance of the irrational number $1/\sqrt {2}$ in many of the formulas that will appear.

We choose a universal gate set from which all quantum circuits are assumed to be composed. The gates in this set include Hadamard, Toffoli, and phase-shift gates (which induce the single-qubit unitary transformation determined by the actions |0〉↦|0〉 and |1〉↦i|1〉), as well as ancillary gates and erasure gates. Ancillary gates take no input qubits and output a single qubit in the |0〉 state, while erasure gates take one input qubit and produce no output qubits, and are described by the partial trace. Any other choice for the unitary gates that is universal for quantum computing could be taken instead, but the gate set just specified is both simple and convenient.

The size of a quantum circuit is defined to be the number of gates in the circuit plus the total number of input and output qubits. Thus, if a quantum circuit were to be represented in a standard way as a directed acyclic graph, its size would simply be the number of vertices, including a vertex for each input and output qubit, of the corresponding graph.

A collection $\{Q_{x} : x \in {\Sigma }^{*}\}$ of quantum circuits is said to be polynomial-time generated if there exists a polynomial-time deterministic Turing machine that, on input x ∈Σ^∗, outputs an encoding of the circuit Q_x. When such a family is parameterized by tuples of strings, it is to be understood that we are implicitly referring to one of the tuple-functions discussed previously. We will not have any need to discuss the specifics of the encoding scheme that we use, but naturally it is assumed to be efficient, with the size of a circuit and its encoding length being polynomially related.

The following lemma relates the complexity of computing circuit transition amplitudes to GapP functions. The essential idea it expresses is due to Fortnow and Rogers [21], who proved a variant of it for unitary computations by quantum Turing machines. An idea, similar in spirit, also appears in [15]. While a result along the lines of the lemma that follows is suggested in the survey paper [37], that paper does not include a proof, and so we include one below.

Lemma 7

Let $\{Q_{x} : x\in {\Sigma }^{\ast }\}$ be a polynomial-time generated family of quantum circuits, where each circuit Q_x takes n input qubits and outputs k qubits, for polynomially bounded functions n and k. There exists a polynomially bounded function r and GapP functions f₀ and f₁ such that

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle u | Q_{x} \bigl(| z \rangle\langle w | \bigr) | v \rangle\bigr) &=& 2^{-r} f_{0}(x,z,w,u,v), \\ \text{Im}\bigl(\langle u | Q_{x} \bigl(| z \rangle\langle w | \bigr) | v \rangle\bigr) &=& 2^{-r} f_{1}(x,z,w,u,v), \end{array} $$

(26)

for all x ∈Σ^∗, z, w ∈Σⁿ, and u, v ∈Σ^k.

Proof

Consider first an arbitrary channel $\mathcal {P}hi$ that maps n-qubit density operators to k-qubit density operators. The action of $\mathcal {P}hi$ on density operators is linear, and can therefore be represented through matrix multiplication. One concrete way to do this is to use the so-called natural representation (also known as the linear representation) of quantum channels.

A description of the natural representation of a quantum channel begins with the vectorization mapping: assuming M is a matrix whose rows and columns are indexed by strings of some length m, the corresponding vector vec(M) is indexed by strings of length 2m according to the following definition:

$$ \text{vec}(M) = \sum\limits_{y,z\in{\Sigma}^{m}} \langle y | M | z \rangle | yz \rangle. $$

(27)

In words, the vectorization map reshapes a matrix into a vector by transposing the rows of the matrix into column vectors and stacking them on top of one another.

With respect to the vectorization mapping, the action of the channel $\mathcal {P}hi$ is described by its natural representation $K(\mathcal {P}hi)$, which is a linear mapping that acts as

$$ K(\mathcal{P}hi) \text{vec}(\rho) = \text{vec}(\mathcal{P}hi(\rho)) $$

(28)

for every n-qubit density operator ρ. As a matrix, $K(\mathcal {P}hi)$ has columns indexed by strings of length 2n and rows indexed by strings of length 2k. Its entries are described explicitly by the equation

$$ \langle uv | K(\mathcal{P}hi) | zw \rangle = \langle u | \mathcal{P}hi(| z \rangle\langle w |) | v \rangle $$

(29)

holding for every z, w ∈Σⁿ and u, v ∈Σ^k. The (26) may therefore be equivalently written as

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle uv | K(Q_{x})| zw \rangle\bigr) &=& 2^{-r} f_{0}(x,z,w,u,v), \\ \text{Im}\bigl(\langle uv | K(Q_{x})| zw \rangle\bigr) &=& 2^{-r} f_{1}(x,z,w,u,v). \end{array} $$

(30)

It must be observed that the natural representation is multiplicative, in the sense that channel composition corresponds to matrix multiplication: $K(\mathcal {P}hi \mathcal {P}si) = K(\mathcal {P}hi) K(\mathcal {P}si)$ for all channels $\mathcal {P}hi$ and $\mathcal {P}si$ for which the composition $\mathcal {P}hi\mathcal {P}si$ makes sense. It is also helpful to note that a channel $\mathcal {P}hi(\rho ) = U \rho U^{\ast }$ corresponding to a unitary operation has as its natural representation the operator

$$ K(\mathcal{P}hi) = U \otimes \overline{U}. $$

(31)

Now let us turn to the family $\{Q_{x} : x\in {\Sigma }^{\ast }\}$. Because this family is polynomial-time generated, there must exist a polynomially bounded function r for which size(Q_x) ≤ r for all x ∈Σ^∗. We may therefore write

$$ Q_{x} = Q_{x,r} {\cdots} Q_{x,1} $$

(32)

for Q_x,1,…,Q_{x, r} being either identity channels or channels that describe the action of a single gate of Q_x tensored with the identity channel on all of the qubits besides the inputs of the corresponding gate that exist at the moment that the gate is applied. We also observe that the number of input qubits and output qubits of each Q_{x, k} must be bounded by r.

Given that

$$ K(Q_{x}) = K(Q_{x,r}) {\cdots} K(Q_{x,1}), $$

(33)

we are led to consider the natural representation of each channel Q_{x, k}. It will be convenient to identify each operator K(Q_{x, k}) with the matrix indexed by strings of length 2r, as opposed to being indexed by strings whose lengths depend on the number of qubits in existence before and after Q_{x, k} is applied, simply by padding K(Q_{x, k}) with rows and columns of zero entries.

The natural representations of the individual gates in the universal gate set we have selected are as follows:

• 1. Hadamard gate:

  $$ \frac{1}{2} \left( \begin{array}{lrrr} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{array}\right) $$

  (34)

• 2. Phase gate:

  $$ \left( \begin{array}{lrll} 1 & 0 & 0 & 0\\ 0 & -i & 0 & 0\\ 0 & 0 & i & 0\\ 0 & 0 & 0 & 1 \end{array}\right) $$

  (35)

• 3. Toffoli gate:

  $$ \left( \begin{array}{llllllll} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right) \otimes \left( \begin{array}{llllllll} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array}\right) $$

  (36)

• 4. Ancillary qubit gate:

  $$ \left( \begin{array}{l} 1 \\ 0 \\ 0 \\ 0 \end{array}\right) $$

  (37)

• 5. Erasure gate:

  $$ (1\quad 0\quad 0\quad 1) $$

  (38)

Based on these representations, it is straightforward to define GapP functions (or, in fact, FP functions) g₀ and g₁ such that

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle uv | K(Q_{x,k})| zw \rangle\bigr) &=& \frac{1}{2} g_{0}(x,z,w,u,v,y_{k}), \\ \text{Im}\bigl(\langle uv | K(Q_{x,k})| zw \rangle\bigr) &=& \frac{1}{2} g_{1}(x,z,w,u,v,y_{k}), \end{array} $$

(39)

for all x ∈Σ^∗, k ∈{1,…,r}, and u, v, z, w ∈Σ^r, where we write y₁,…,y_r to denote the elements of ${{\Sigma }^{r}_{1}}$ sorted in lexicographic order. It now follows through a straightforward application of Lemma 6 there must exist GapP functions f₀ and f₁ satisfying (26) and therefore (30), for all x ∈Σ^∗, z, w ∈Σⁿ, and u, v ∈Σ^k, as required. □

2.4 A tail bound for operator-valued random variables

We will make use of the following tail bound on the minimum eigenvalue of the average of a collection of operator-valued random variables. This bound follows from a more general result due to Tropp. In particular, the bound stated in the theorem below follows from Theorem 5.1 of [36] together with Pinsker’s inequality, which relates the relative entropy of two distributions to their total variation distance.

Theorem 8 (Tropp)

Let d and N be positive integers, let η ∈ [0,1] and ε > 0 be real numbers, and let X₁,…,X_N be independent and identically distributed operator-valued random variables having the following properties:

• 1. Each X_k takes d × d positive semidefinite operator values satisfying .

• 2. The minimum eigenvalue of the expected operator E(X_k) satisfies $\lambda _{\min \limits }(\mathrm {E}(X_{k})) \geq \eta$.

It is the case that

$$ \text{Pr}\biggl(\lambda_{\min}\biggl(\frac{X_{1} + {\cdots} + X_{N}}{N} \biggr) < \eta - \varepsilon\biggr) \leq d \exp(-2N\varepsilon^{2}). $$

(40)

3 Complexity classes for one-turn quantum refereed games

In this section we define the complexity classes to be considered in this paper: QRG(1), CQRG(1), and MQRG(1). The definitions of these classes all refer to the notion of a referee, which (in this paper) is a polynomial-time generated family

$$ R = \{R_{x} : x\in{\Sigma}^{\ast}\} $$

(41)

of quantum circuits having the following special form

• 1. For each x ∈Σ^∗, the inputs to the circuit R_x are grouped into two registers: an n-qubit register A and an m-qubit register B, for polynomially bounded functions n and m.

• 2. The output of each circuit R_x is a single qubit, which is to be measured with respect to the standard basis immediately after the circuit is run.

Given that classical probabilistic states may be viewed as special cases of quantum states (corresponding to diagonal density operators), this definition of a referee can still be used in the situation in which either or both of the registers A and B is constrained to initially store a classical state.

We are interested in the situation that, for a given choice of an input string x ∈Σ^∗, the input to the circuit R_x is a product state of the form ρ ⊗ σ, where $\rho \in \mathrm {D}(\mathcal {A})$ is a state of the register A and $\sigma \in \mathrm {D}({\mathscr{B}})$ is a state of the register B. The state $\rho \in \mathrm {D}(\mathcal {A})$ is to be viewed as representing the state that Alice plays, while $\sigma \in \mathrm {D}({\mathscr{B}})$ represents the state Bob plays. When the single output qubit of the circuit R_x is measured with respect to the standard basis, the outcome 1 is interpreted as “Alice wins,” while the outcome 0 is interpreted as “Bob wins.”

Now, consider the quantity defined as

$$ \omega(R_{x}) = \max_{\rho\in\mathrm{D}(\mathcal{A})} \min_{\sigma\in\mathrm{D}(\mathcal{B})} \langle 1 | R_{x} (\rho \otimes \sigma) | 1 \rangle. $$

(42)

Given that $\mathrm {D}(\mathcal {A})$ and $\mathrm {D}({\mathscr{B}})$ are compact and convex sets, and the value 〈1|R_x(ρ ⊗ σ)|1〉 is bilinear in ρ and σ, Sion’s min-max theorem implies that changing the order of the minimum and maximum does not change the value of the expression. That is, this quantity may alternatively be written

$$ \omega(R_{x}) = \min_{\sigma\in\mathrm{D}(\mathcal{B})} \max_{\rho\in\mathrm{D}(\mathcal{A})} \langle 1 | R_{x} (\rho \otimes \sigma) | 1 \rangle. $$

(43)

This value represents the probability that Alice wins the game defined by the circuit R_x, assuming both Alice and Bob play optimally. With that definition in hand, we may now define the complexity class QRG(1), which is short for one-turn quantum refereed games.

Definition 9

A promise problem A = (A_yes,A_no) is contained in the complexity class QRG(1)_{α, β} if there exists a referee $R = \{R_{x} : x\in {\Sigma }^{\ast }\}$ such that the following properties are satisfied:

• 1. For every string x ∈ A_yes, it is the case that ω(R_x) ≥ α.

• 2. For every string x ∈ A_no, it is the case that ω(R_x) ≤ β.

We also define QRG(1) = QRG(1)_2/3,1/3.

In this definition, α and β may be constants, or they may be functions of the length of the input x. A short summary of known facts and observations concerning the complexity class QRG(1) follows.

• $\text {QMA}\subseteq \text {QRG}(1)$. This is because the referee’s measurement may simply ignore Bob’s state σ and treat Alice’s state ρ as a quantum proof in a QMA proof system.

• QRG(1) is closed under complementation: QRG(1) = co-QRG(1). For a promise problem (A_yes,A_no) ∈QRG(1), one may obtain a one-turn quantum refereed game for (A_no,A_yes) by simply exchanging the roles of Alice and Bob.

• It is the case that QRG(1) = QRG(1)_{α, β} for a wide range of choices of α and β, similar to error bounds for BPP, BQP, and QMA. In particular, QRG(1) = QRG(1)_{α, β} provided that α and β are polynomial-time computable and satisfy

  $$ \alpha \leq 1 - 2^{-p},\quad \beta \geq 2^{-p}, \quad \text{and} \quad \alpha - \beta \geq \frac{1}{p} $$

  (44)

  for some choice of a strictly positive polynomially bounded function p.²

• $\text {QRG}(1) \subseteq \text {PSPACE}$ [28].

3.1 Definitions of new complexity classes

The first variant of QRG(1) we define is one in which Alice’s state is restricted to be a classical state. We will call this class CQRG(1).

Definition 10

A promise problem A = (A_yes,A_no) is contained in the complexity class CQRG(1)_{α, β} if there exists a referee $R = \{R_{x} : x\in {\Sigma }^{\ast }\}$ such that the following properties are satisfied:

• 1. For every string x ∈Σ^∗, the circuit R_x takes the form illustrated in Fig. 1. That is, R_x takes an n-qubit register A and an m-qubit register B as input, measures each qubit of A with respect to the standard basis, leaving it in a classical state, and then runs the circuit Q_x on the pair (A,B), producing a single output qubit.

• 2. For every string x ∈ A_yes, it is the case that ω(R_x) ≥ α.

• 3. For every string x ∈ A_no, it is the case that ω(R_x) ≤ β.

We also define CQRG(1) = CQRG(1)_2/3,1/3.

Fig. 1

A CQRG(1) referee. The register A is initially measured (or, equivalently, dephased) with respect to the standard basis, causing a classical state to be input into Q_x, along with the register B, which is unaffected by this standard basis measurement

Formally speaking, the standard basis measurement suggested by Definition 10 can be implemented by independently performing the completely dephasing channel on each qubit of A. This channel can be constructed using the universal gate set we have selected using a Toffoli gate with suitably initialized inputs as follows:

Here the square labeled |0〉 is an ancillary gate, the square labeled |1〉 denotes an ancillary gate composed with a not-gate X = HPPH (for H and P denoting Hadamard and phase-shift gates), and the square labeled Tr denotes an erasure gate.

In effect, a referee R that satisfies the first requirement of Definition 10 forces the state Alice plays to be a classical state (i.e., a state represented by a diagonal density operator). That is, for any density operator ρ that Alice might choose to play, the state of A that is input into Q_x takes the form

$$ \sum\limits_{y\in{\Sigma}^{n}} p(y) | y \rangle\langle y | $$

(45)

for some probability vector p over n-bit strings, and therefore the state that is plugged into the top n qubits of the circuit Q_x represents a classical state. Given that the standard basis measurement acts trivially on all diagonal states, we observe that Alice may cause an arbitrary diagonal density operator of the form (45) to be input into Q_x. In short, the set of possible states that may be input into the top n qubits of the circuit Q_x is precisely the set of diagonal n-qubit density operators.

The second variant of QRG(1) we define is one in which Alice and Bob both send quantum states to the referee, but the referee first measures Alice’s state, obtaining a classical outcome, which is then measured together with Bob’s state (as illustrated in Fig. 2).

Fig. 2

An MQRG(1) referee

Definition 11

A promise problem A = (A_yes,A_no) is contained in the complexity class MQRG(1)_{α, β} if there exists a referee $R = \{R_{x} : x\in {\Sigma }^{\ast }\}$ such that the following properties are satisfied:

• 1. For every string x ∈Σ^∗, the circuit R_x takes the form illustrated in Fig. 2. That is, R_x takes an n-qubit register A and an m-qubit register B as input, and first applies a quantum circuit P_x to A, yielding a k-qubit register Y, for k a polynomially bounded function. The register Y is then measured with respect to the standard basis, so that it then contains a classical state, and finally a quantum circuit Q_x is applied to the pair (Y,B), yielding a single qubit.

• 2. For every string x ∈ A_yes, it is the case that ω(R_x) ≥ α.

• 3. For every string x ∈ A_no, it is the case that ω(R_x) ≤ β.

We also define MQRG(1) = MQRG(1)_2/3,1/3.

In essence, an MQRG(1) referee measures Alice’s qubits with respect to a general, efficiently implementable measurement, which yields a k-bit classical outcome, which is then plugged into Q_x along with Bob’s quantum state.

It is of course immediate that

$$ \text{CQRG(1)} \subseteq \text{MQRG(1)} \subseteq \text{QRG(1)}; $$

(46)

a CQRG(1) referee is a special case of an MQRG(1) referee in which P_x is the identity map on n qubits, while an MQRG(1) referee is a special case of a QRG(1) referee. We also observe that both CQRG(1) and MQRG(1) are robust with respect to error bounds in the same way as was described above for QRG(1).

4 Upper-bound on CQRG(1)

In this section, we prove that CQRG(1) is contained in ∃⋅PP. The proof represents a fairly direct application of the Althöfer–Lipton–Young [2, 32] technique, although (as was suggested above) the quantum setting places a new demand on this technique that requires the use of a tail bound on sums of matrix-valued random variables. We will split the proof of this containment into two lemmas, followed by a short proof of the main theorem—this is done primarily because the lemmas will also be useful for proving $\text {MQRG(1)} \subseteq \mathrm {P} \cdot \text {PP}$ in the section following this one. Some readers may wish to skip to the statement and proof of Theorem 14 below, as it explains the purpose of these two lemmas within the context of that theorem.

The first lemma represents an implication of Theorem 8 due to Tropp to the setting at hand.

Lemma 12

Let k and m be positive integers, let $p\in \mathcal {P}({\Sigma }^{k})$ be a probability distribution on k-bit strings, let S_y be a 2^m × 2^m positive semidefinite operator satisfying for each y ∈Σ^k, and let N ≥ 72(m + 2). For strings $y_{1},\ldots ,y_{N}\in {\Sigma }^{k}$ sampled independently from the distribution p, it is the case that

$$ \text{Pr}\Biggl(\lambda_{\min}\Biggl(\frac{S_{y_{1}} + {\cdots} + S_{y_{N}}}{N}\Biggr) < \lambda_{\min}\Biggl(\sum\limits_{y\in{\Sigma}^{k}}p(y)S_{y}\Biggr) - \frac{1}{12}\Biggr) < \frac{1}{3}. $$

(47)

Proof

Define X₁,…,X_N to be independent and identically distributed operator-valued random variables, each taking the (operator) value S_y with probability p(y), for every y ∈Σ^k. The expected value of each of these random variables is therefore given by

$$ P = \sum\limits_{y\in{\Sigma}^{k}}p(y)S_{y}. $$

(48)

By taking $\eta = \lambda _{\min \limits }(P)$ and ε = 1/12 in Theorem 8, we find that

$$ \text{Pr}\biggl(\lambda_{\min}\biggl(\frac{X_{1} + {\cdots} + X_{N}}{N} \biggr) < \lambda_{\min}(P) - \frac{1}{12}\biggr) \leq 2^{m} \exp\biggl(-\frac{N}{72}\biggr) < \frac{1}{3}, $$

(49)

which is equivalent to the bound stated in the lemma. □

The second lemma uses counting complexity to relate the minimum eigenvalue of measurement operators defined by quantum circuits to PP languages. We note that the technique of weakly estimating the largest eigenvalue of a measurement operator using the trace of a power of that operator, through the relations (53) appearing in the proof below, is the essential idea behind the unpublished proof of the containment $\text {QMA}\subseteq \text {PP}$ claimed in [31].

Lemma 13

Let $\{Q_{x} : x\in {\Sigma }^{\ast }\}$ be a polynomial-time generated family of quantum circuits, where each circuit Q_x takes as input a k-qubit register Y and an m-qubit register B, for polynomially bounded functions k and m, and outputs a single qubit. For each x ∈Σ^∗ and y ∈Σ^k, define an operator

(50)

For every polynomially bounded function N, there exists a language B ∈PP for which the following implications are true for all x ∈Σ^∗ and $y_{1},\ldots ,y_{N}\in {\Sigma }^{k}$:

$$ \begin{array}{@{}rcl@{}} \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) \geq \frac{2}{3} \quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \in B, \end{array} $$

(51)

$$ \begin{array}{@{}rcl@{}} \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) \leq \frac{1}{3} \quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \not\in B.\end{array} $$

(52)

Proof

The essence of the proof is that if P is an operator whose entries have real and imaginary parts proportional to GapP functions, and r is a polynomially bounded function, then there exists a GapP function that is proportional to the real part of Tr(P^r). When P is a 2^m × 2^m positive semidefinite operator, this allows one to choose r to be sufficiently large, but still polynomially bounded, so that a GapP function is obtained that takes positive or negative values in accordance with the required implications (51) and (52), through the use of the following bounds relating the largest eigenvalue and the trace of any such P:

$$ \lambda_{\max}(P)^{r} = \lambda_{\max}(P^{r}) \leq \text{Tr}(P^{r}) \leq 2^{m} \lambda_{\max}(P^{r}) = 2^{m} \lambda_{\max}(P)^{r}. $$

(53)

In the case at hand, it will suffice to take r = 2m.

In greater detail, let us begin by defining

(54)

for each x ∈Σ^∗ and y ∈Σ^k. Observe that S_{x, y} and T_{x, y} are positive semidefinite operators satisfying , so that the implication in the statement of the lemma may alternatively be written as

$$ \begin{array}{@{}rcl@{}} \lambda_{\max}\biggl(\frac{T_{x,y_{1}} + {\cdots} + T_{x,y_{N}}}{N}\biggr) \leq \frac{1}{3}\quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \in B, \end{array} $$

(55)

$$ \begin{array}{@{}rcl@{}} \lambda_{\max}\biggl(\frac{T_{x,y_{1}} + {\cdots} + T_{x,y_{N}}}{N}\biggr) \geq \frac{2}{3}\quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \not\in B. \end{array} $$

(56)

Thus, if the operator

$$ P_{x,y_{1}{\cdots} y_{N}} = \frac{T_{x,y_{1}} + {\cdots} + T_{x,y_{N}}}{N} $$

(57)

satisfies $\lambda _{\max \limits }(P_{x,y_{1}{\cdots } y_{N}})\leq 1/3$, then

$$ \text{Tr}(P_{x,y_{1}{\cdots} y_{N}}^{2m}) \leq \frac{2^{m}}{3^{2m}} < \frac{1}{3^{m}} $$

(58)

while if $\lambda _{\max \limits }(P_{x,y_{1}{\cdots } y_{N}})\geq 2/3$, then

$$ \text{Tr}(P_{x,y_{1}{\cdots} y_{N}}^{2m}) \geq \Bigl(\frac{2}{3}\Bigr)^{2m} > \frac{1}{3^{m}}. $$

(59)

By Lemma 7 there exists a polynomially bounded function r along with GapP functions f and g satisfying

$$ \begin{array}{@{}rcl@{}} \text{Re}(\langle z | T_{x,y} | w \rangle) &=& \text{Re}\bigl(\langle 0 | Q_{x} \bigl(| yz \rangle\langle yw | \bigr) | 0 \rangle\bigr) = 2^{-r} f(x,y,z,w), \\ \text{Im}(\langle z | T_{x,y} | w \rangle) &=& -\text{Im}\bigl(\langle 0 | Q_{x} \bigl(| yz \rangle\langle yw | \bigr) | 0 \rangle\bigr) = 2^{-r} g(x,y,z,w), \end{array} $$

(60)

for all x ∈Σ^∗, y ∈Σ^k, and z, w ∈Σ^m. Define functions F and G as follows:

$$ \begin{array}{@{}rcl@{}} F(x,y_{1}{\cdots} y_{N},z,w) &=& f(x,y_{1},z,w) + {\cdots} + f(x,y_{N},z,w), \\ G(x,y_{1}{\cdots} y_{N},z,w) &=& g(x,y_{1},z,w) + {\cdots} + g(x,y_{N},z,w), \end{array} $$

(61)

for all x ∈Σ^∗, $y_{1},\ldots ,y_{N}\in {\Sigma }^{k}$, and z, w ∈Σ^m. It is the case that F and G are GapP functions satisfying

$$ \begin{array}{@{}rcl@{}} F(x,y_{1}{\cdots} y_{N},z,w) &=& 2^{r}\cdot N \cdot \text{Re}(\langle z |P_{x,y_{1}{\cdots} y_{N}}| w \rangle),\\ G(x,y_{1}{\cdots} y_{N},z,w) &=& 2^{r}\cdot N \cdot \text{Im}(\langle z |P_{x,y_{1}{\cdots} y_{N}}| w \rangle). \end{array} $$

(62)

Through an application of Lemmas 4 and 6, we conclude that there must exist a GapP function H satisfying

$$ H(x,y_{1}{\cdots} y_{N}) = 2^{2 r m} \cdot N^{2m} \cdot \text{Tr}\bigl(P_{x,y_{1}{\cdots} y_{N}}^{2m}\bigr). $$

(63)

The GapP function

$$ K(x,y_{1}{\cdots} y_{N}) = 2^{2rm} \cdot N^{2m} - 3^{m} \cdot H(x,y_{1}{\cdots} y_{N}) $$

(64)

therefore takes positive values if $\lambda _{\max \limits }(P_{x,y_{1}{\cdots } y_{N}})\leq 1/3$, and takes negative values if $\lambda _{\max \limits }(P_{x,y_{1}{\cdots } y_{N}})\geq 2/3$, implying the existence of a PP language B as claimed. □

Theorem 14

$\text {CQRG}(1) \subseteq \exists \cdot \text {PP}$.

Proof

Let A = (A_yes,A_no) be any promise problem contained in CQRG(1), let a referee be fixed that establishes the inclusion A ∈CQRG(1)_3/4,1/4, and let $\{Q_{x} : x\in {\Sigma }^{\ast }\}$ be the collection of circuits that describes this referee, in accordance with Definition 10.

Let x ∈ A_yes ∪ A_no be any input string. Consider first the situation that Alice plays deterministically, sending a string y ∈Σⁿ to the referee, so that ρ = |y〉〈y|. Having selected a state ρ representing Alice’s play, we are effectively left with a binary-valued measurement being performed on the state sent to the referee by Bob. We observe that, for any choice of a state $\sigma \in \mathrm {D}({\mathscr{B}})$ representing Bob’s play, the probabilities that the referee’s measurement generates the outcomes 0 and 1 are given by

$$ \langle 0 | Q_{x} (| y \rangle\langle y | \otimes \sigma) | 0 \rangle \quad\text{and}\quad \langle 1 | Q_{x} (| y \rangle\langle y | \otimes \sigma) | 1 \rangle, $$

(65)

respectively. By defining an operator $S_{x,y} \in \text {Pos}({\mathscr{B}})$ as

(66)

we therefore obtain the measurement operator corresponding to the 1 outcome of this measurement, as

$$ \text{Tr}\bigl(S_{x,y} \sigma\bigr) = \langle 1 | Q_{x} (| y \rangle\langle y | \otimes \sigma) | 1 \rangle $$

(67)

and

(68)

for all $\sigma \in \mathrm {D}({\mathscr{B}})$.

Now, as Bob aims to minimize the probability for outcome 1 to appear, the relevant property of the operator S_{x, y} is its minimum eigenvalue $\lambda _{\min \limits }(S_{x,y})$. A large minimum eigenvalue means that Alice has managed to force the outcome 1 to appear, regardless of what state Bob plays, whereas a small minimum eigenvalue means that Bob has at least one choice of a state that causes the outcome 1 to appear with small probability. Stated in more precise terms, Bob’s optimal strategy in the case that Alice plays ρ = |y〉〈y| is to play any state $\sigma \in \text {D}({\mathscr{B}})$ whose image is contained in the eigenspace of S_{x, y} corresponding to the minimum eigenvalue $\lambda _{\min \limits }(S_{x,y})$, which leads to a win for Alice with probability equal to this minimum eigenvalue and a win for Bob with probability $1 - \lambda _{\min \limits }(S_{x,y})$.

In general, Alice will not play deterministically, but will instead play a distribution of strings $p\in \mathcal {P}({\Sigma }^{n})$. In this case, the resulting measurement operator on Bob’s space becomes

$$ \sum\limits_{y\in{\Sigma}^{n}} p(y) S_{x,y}. $$

(69)

That is to say, the probability that Alice wins when she plays a distribution $p\in \mathcal {P}({\Sigma }^{n})$, and Bob plays optimally against this distribution, is given by the expression

$$ \lambda_{\min}\Biggl(\sum\limits_{y\in{\Sigma}^{n}} p(y) S_{x,y}\Biggr). $$

(70)

Determining whether x is a yes-instance or a no-instance of A is therefore equivalent to discriminating between the case that there exists a distribution $p\in \mathcal {P}({\Sigma }^{n})$ for which the minimum eigenvalue (70) is at least 3/4 and the case in which this minimum eigenvalue is at most 1/4 for all choices of $p\in \mathcal {P}({\Sigma }^{n})$.

The goal of the proof is to show that this decision problem is contained in ∃⋅PP. The ∃ operator will represent the existence or non-existence of a distribution $p\in \mathcal {P}({\Sigma }^{n})$ for which the minimum eigenvalue (70) is large, while a PP predicate will allow for an estimation of this minimum eigenvalue itself. A challenge that must be overcome in making this approach work is that using the ∃ operator in this way requires Alice’s strategy to have a polynomial-length representation. However, given that a distribution $p\in \mathcal {P}({\Sigma }^{n})$ may have support that is exponentially large in n, an explicit description of p will generally have exponential size, assuming that the individual probabilities p(y) are represented with a polynomial number of bits of precision.

This obstacle may be overcome using the Althöfer–Lipton–Young [2, 32] technique mentioned in the introduction: in place of a distribution $p\in \mathcal {P}({\Sigma }^{n})$, we consider an N-tuple of strings (y₁,…,y_N), representing N possible deterministic plays for Alice, for N = N(|x|) being a suitable polynomially bounded function of the input length. This N-tuple will represent the distribution $q\in \mathcal {P}({\Sigma }^{n})$ obtained by selecting j ∈{1,…,N} uniformly at random and then outputting the string y_j. That is, the distribution $q\in \mathcal {P}({\Sigma }^{n})$ represented by the N-tuple (y₁,…,y_N) is given by

$$ q(y) = \frac{\bigl| \{j\in\{1,\ldots,N\} : y = y_{j}\} \bigr|}{N} $$

(71)

for each y ∈Σⁿ. Naturally, most choices of a distribution $p\in \mathcal {P}({\Sigma }^{n})$ are far away from any such distribution q. Nevertheless, the existence of a distribution $p\in \mathcal {P}({\Sigma }^{n})$ for which the minimum eigenvalue (70) is large does in fact imply the existence of an N-tuple (y₁,…,y_N) for which the distribution $q\in \mathcal {P}({\Sigma }^{n})$ defined by (71) is still a good play for Alice, meaning that the minimum eigenvalue

$$ \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) $$

(72)

is also large, provided N is sufficiently large. This is precisely the content of Lemma 12.

In particular, by choosing N = 72(m + 2), where m is the number of qubits of B, we find that if the minimum eigenvalue (70) is at least 3/4, then with probability at least 2/3 (over the random choices of y₁,…,y_N) the minimum eigenvalue (72) is at least 2/3. Of course, this implies the existence of an N-tuple (y₁,…,y_N) for which the minimum eigenvalue (72) is at least 2/3.

Naturally, if x ∈ A_no, then the minimum eigenvalue (70) is at most 1/4 for all choices of $p\in \mathcal {P}({\Sigma }^{n})$, and therefore it must be that

$$ \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) \leq \frac{1}{4} < \frac{1}{3} $$

(73)

for all N-tuples (y₁,…,y_N). This is because the distribution q defined by (71) is simply one example of a distribution in $\mathcal {P}({\Sigma }^{n})$.

The purpose of Lemma 13 is now evident, for it states that there exists a language B ∈PP such that if the minimum eigenvalue (72) is at least 2/3, then (x, y₁⋯y_N) ∈ B, while if this minimum eigenvalue is at most 1/3, then (x, y₁⋯y_N)∉B. Consequently, if x ∈ A_yes, then there exists a string $y_{1}{\cdots } y_{N}\in {\Sigma }^{nN}$ such that (x, y₁⋯y_N) ∈ B, while if x ∈ A_no, then for every string $y_{1}{\cdots } y_{N}\in {\Sigma }^{nN}$ it is the case that (x, y₁⋯y_N)∉B. It has therefore been proved that A ∈∃⋅PP as required. □

5 Upper-bound on MQRG(1)

We now turn to the complexity class MQRG(1), and prove the containment $\text {MQRG}(1) \subseteq \mathrm {P}\cdot \text {PP}$. In order to do this, we will first introduce a QMA-operator that, in some sense, functions in a way that is similar to the ∃ and P operators previously discussed.

Definition 15

For a given complexity class $\mathcal {C}$, the complexity class $\text {QMA}\cdot \mathcal {C}$ contains all promise problems A = (A_yes,A_no) for which there exists a polynomial-time generated family of quantum circuits $\{P_{x} : x\in {\Sigma }^{\ast }\}$, where each P_x takes n = n(|x|) input qubits and outputs k = k(|x|) qubits, along with a language $B\in \mathcal {C}$, such that the following implications hold.

• 1. If x ∈ A_yes, then there exists a density operator ρ on n qubits for which

  $$ \text{Pr}\bigl(P_{x}(\rho) \in B\bigr) \geq \frac{2}{3}. $$

  (74)

• 2. If x ∈ A_no, then for every density operator ρ on n qubits,

  $$ \text{Pr}\bigl(P_{x}(\rho) \in B\bigr) \leq \frac{1}{3}. $$

  (75)

Here, the notation P_x(ρ) ∈ B refers to the event that P_x is applied to the state ρ, the output qubits are measured with respect to the standard basis, and the resulting string is contained in the language B. Figure 3 illustrates the associated process, with χ_B being the characteristic function of B on inputs of length k.

Fig. 3

Definition 15 is concerned with the probability that the output of a circuit P_x, measured with respect to the standard basis, is contained in the language B, assuming the input is ρ

Theorem 16

If $\mathcal {C}$ is nontrivial complexity class of languages that is closed under joins and truth-table reductions, then $\text {QMA}\cdot \mathcal {C} \subseteq \textup {P}\cdot \mathcal {C}$.

Proof

Let $A = (A_{\text {yes}},A_{\text {no}})\in \text {QMA}\cdot \mathcal {C}$, and let $\{P_{x} : x\in {\Sigma }^{\ast }\}$ be a polynomial-time generated family of quantum circuits that, together with a language $B\in \mathcal {C}$, establishes this inclusion according to Definition 15.

By Lemma 7 there exists a polynomially bounded function r and GapP functions f₀ and f₁ such that

$$ \begin{array}{@{}rcl@{}} \text{Re}\bigl(\langle u | P_{x} \bigl(| z \rangle\langle w | \bigr) | v \rangle\bigr) &=& 2^{-r} f_{0}(x,z,w,u,v), \\ \text{Im}\bigl(\langle u | P_{x} \bigl(| z \rangle\langle w | \bigr) | v \rangle\bigr) &=& 2^{-r} f_{1}(x,z,w,u,v), \end{array} $$

(76)

for all x ∈Σ^∗, z, w ∈Σⁿ, and u, v ∈Σ^k. Define

$$ \begin{array}{@{}rcl@{}} g_{0}(x,z,w,u) &=& \left\{\begin{array}{ll} f_{0}(x,z,w,u,u) & \text{if $u\in B$}\\ 0 & \text{if $u\not\in B$}, \end{array}\right. \\ g_{1}(x,z,w,u) &=& \left\{\begin{array}{ll} f_{1}(x,z,w,u,u) & \text{if $u\in B$}\\ 0 & \text{if $u\not\in B$}, \end{array}\right. \end{array} $$

(77)

for all x ∈Σ^∗, z, w ∈Σⁿ, and u ∈Σ^k. By the properties of $\mathcal {C}$, it is the case that $g_{0},g_{1}\in \text {Gap}\cdot \mathcal {C}$.

Next, define

$$ \begin{array}{@{}rcl@{}} F_{0}(x,z,w) &=& \sum\limits_{u\in{\Sigma}^{k}} g_{0}(x,z,w,u),\\ F_{1}(x,z,w) &=& -\sum\limits_{u\in{\Sigma}^{k}} g_{1}(x,z,w,u), \end{array} $$

(78)

for all x ∈Σ^∗ and z, w ∈Σⁿ. By Lemma 4 we have that $F_{0},F_{1}\in \text {Gap}\cdot \mathcal {C}$. We observe that

$$ \begin{array}{@{}rcl@{}} \text{Re} \bigl(\langle w | R_{x} | z \rangle \bigr) &=& 2^{-r} F_{0}(x,z,w),\\ \text{Im} \bigl(\langle w | R_{x} | z \rangle \bigr) &=& 2^{-r} F_{1}(x,z,w) \end{array} $$

(79)

for all x ∈Σ^∗ and z, w ∈Σⁿ, where

$$ R_{x} = \sum\limits_{u\in{\Sigma}^{k}\cap B} P_{x}^{\ast} \bigl(| u \rangle\langle u | \bigr). $$

(80)

Now let us consider the cases x ∈ A_yes and x ∈ A_no. If x ∈ A_yes then $\lambda _{\max \limits }(R_{x}) \geq 2/3$, while if x ∈ A_no then $\lambda _{\max \limits }(R_{x}) \leq 1/3$. Observing that R_x is a positive semidefinite operator on a 2ⁿ dimensional space, we have that

$$ \lambda_{\max}(R_{x})^{n+1} = \lambda_{\max}(R_{x}^{n+1}) \leq \text{Tr}(R_{x}^{n+1}) \leq 2^{n} \lambda_{\max}(R_{x}^{n+1}) = 2^{n} \lambda_{\max}(R_{x})^{n+1}, $$

(81)

similar to (53) in the proof of Lemma 13. By Lemma 6 it follows that there exists a $\textup {Gap}\cdot \mathcal {C}$ function G possessing the following properties.

• 1. If x ∈ A_yes then

  $$ G(x) = 2^{(n+1)r} \text{tr}(R_{x}^{n+1}) \geq \frac{2^{(n+1)r+n+1}}{3^{n+1}} $$

  (82)

• 2. If x ∈ A_no then

  $$ G(x) = 2^{(n+1)r} \text{tr}(R_{x}^{n+1}) \leq \frac{2^{(n+1)r + n}}{3^{n+1}}. $$

  (83)

The $\text {Gap}\cdot \mathcal {C}$ function

$$ H(x) = 3^{n+1} G(x) - 2^{(n+1)r + n} $$

(84)

therefore satisfies H(x) > 0 when x ∈ A_yes and H(x) ≤ 0 when x ∈ A_no. By Proposition 3 it follows that $A\in \textup {P}\cdot \mathcal {C}$. □

Next, we prove that MQRG(1) is contained in QMA ⋅PP. Combining this fact with the previous theorem will establish the main result as an immediate corollary.

Theorem 17

$\text {MQRG}(1) \subseteq \text {QMA}\cdot \text {PP}$.

Proof

Consider any promise problem A = (A_yes,A_no) in MQRG(1), and fix a referee that establishes the inclusion A ∈MQRG(1)_3/4,1/4. Let $\{P_{x} : x\in {\Sigma }^{\ast }\}$ and $\{Q_{x} : x\in {\Sigma }^{\ast }\}$ be a collection of circuits that describe this referee, in accordance with Definition 11. As in the proof of Theorem 14, define an operator

(85)

for each x ∈Σ^∗ and y ∈Σ^k. If x ∈ A_yes, there must exists a state $\rho \in \mathrm {D}(\mathcal {A})$ such that

$$ \lambda_{\min} \Biggl(\sum\limits_{y\in{\Sigma}^{k}} \langle y |P_{x}(\rho)| y \rangle S_{x,y}\Biggr)\geq \frac{3}{4}, $$

(86)

while if x ∈ A_no, it is the case that

$$ \lambda_{\min} \Biggl(\sum\limits_{y\in{\Sigma}^{k}} \langle y |P_{x}(\rho)| y \rangle S_{x,y}\Biggr) \leq \frac{1}{4} $$

(87)

for every $\rho \in \mathrm {D}(\mathcal {A})$.

Now define a function N = 72(m + 2) and observe that N is polynomially bounded in |x|. By Lemma 13, there exists a language B ∈PP for which these implications hold for all x ∈Σ^∗ and $y_{1},\ldots ,y_{N}\in {\Sigma }^{k}$:

$$ \begin{array}{@{}rcl@{}} \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) \geq \frac{2}{3} \quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \in B, \end{array} $$

(88)

$$ \begin{array}{@{}rcl@{}} \lambda_{\min}\biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N}\biggr) \leq \frac{1}{3} \quad &\Rightarrow& \quad (x,y_{1}{\cdots} y_{N}) \not\in B. \end{array} $$

(89)

Finally, for each input x, define a circuit K_x that takes as input N registers (A₁,…,A_N), each consisting of n qubits, and outputs N + 1 registers (X,Y₁,…,Y_N). The register X is initialized to the state |x〉〈x|, so that it simply echoes the input string x, and each register Y_j is obtained by independently applying the circuit P_x to A_j. Alternatively, one could write

$$ K_{x} = | x \rangle\langle x | \otimes P_{x}^{\otimes N}, $$

(90)

with the understanding that we are identifying the state |x〉〈x| with the channel that inputs nothing and outputs the state |x〉〈x|.

To prove that the promise problem A is contained in QMA ⋅PP, it suffices to prove two things:

Completeness :

If it is the case that x ∈ A_yes, then there must exist a state $\xi \in \mathrm {D}(\mathcal {A}^{\otimes N})$ such that

$$ \text{Pr}(K_{x}(\xi)\in B) \geq \frac{2}{3}. $$

(91)

Soundness :

If it is the case that x ∈ A_no, then for every state $\xi \in \mathrm {D}(\mathcal {A}^{\otimes N})$ it must be that

$$ \text{Pr}(K_{x}(\xi)\in B) \leq \frac{1}{3}. $$

(92)

The proof of completeness follows a similar argument to the proof of Theorem 14. Let $\rho \in \mathrm {D}(\mathcal {A})$ be any state for which (86) is satisfied, and let ξ = ρ^⊗N. It is evident that the output of K_x(ξ) is given by (x, y₁⋯y_N), for $y_{1},\ldots ,y_{N}\in {\Sigma }^{k}$ sampled independently from the distribution

$$ p(y) = \langle y |P_{x}(\rho)| y \rangle. $$

(93)

It follows by Lemma 12 that

$$ \text{Pr}(K_{x}(\xi)\in B) \geq \frac{2}{3}. $$

(94)

For the proof of soundness, the possibility that the state $\xi \in \mathrm {D}(\mathcal {A}^{\otimes N})$ does not take product form must be considered. Our aim is to prove that if y₁,…,y_N are randomly selected according to the distribution that assigns the probability

$$ \bigl\langle y_{1} {\cdots} y_{N} \bigr| P_{x}^{\otimes N} (\xi) \bigl| y_{1}{\cdots} y_{N} \bigr\rangle $$

(95)

to each tuple (y₁,…,y_N), then

$$ \text{Pr}\Biggl(\lambda_{\min} \Biggl(\frac{S_{x,y_{1}} + {\cdots} + S_{x,y_{N}}}{N} \Biggr) \leq \frac{1}{3}\Biggr) \geq \frac{2}{3} , $$

(96)

for this implies that Pr(K_x(ξ) ∈ B) ≤ 1/3 by (89). Toward this goal, choose a density operator $\sigma \in \mathrm {D}({\mathscr{B}})$ for which

$$ \sum\limits_{y\in{\Sigma}^{k}}\langle y |P_{x}(\rho)| y \rangle \text{Tr}\bigl(S_{x,y} \sigma\bigr) \leq \frac{1}{4} $$

(97)

for all $\rho \in \mathrm {D}(\mathcal {A})$, which is possible by Sion’s min-max theorem under the assumption (87), and define random variables Z₁,…,Z_N as

$$ Z_{j} = \text{Tr} \bigl(S_{x,y_{j}} \sigma\bigr) $$

(98)

for every j ∈{1,…,N}, assuming that y₁,…,y_N are chosen at random as above. It suffices to prove that

$$ \text{Pr}\Biggl(\frac{Z_{1} + {\cdots} + Z_{N}}{N} \leq \frac{1}{3}\Biggr) \geq \frac{2}{3} , $$

(99)

as we have $\lambda _{\min \limits }(H) \leq \text {Tr}(H \sigma )$ for all Hermitian operators H.

The complication we face at this point is that the random variables Z₁,…,Z_N are not necessarily independent (because ξ does not necessarily have product form), so the most standard form of Hoeffding’s inequality will not suffice to establish the required bound (99). However, we observe that Z₁,…,Z_N are discrete random variables that take values in the interval [0,1] and satisfy the inequality

$$ \text{E}(Z_{j} | Z_{1} = \alpha_{1},\ldots,Z_{j-1} = \alpha_{j-1}) \leq \frac{1}{4} $$

(100)

for all j ∈{2,…,N} and α₁,…,α_j− 1 ∈ [0,1] for which Pr(Z₁ = α₁,…,Z_j− 1 = α_j− 1) is nonzero. This is evident from the inequality (97), for it must hold when ρ is equal to the reduced state of register A_j, conditioned on any choice of y₁,…,y_j− 1 (and therefore on any choice of values Z₁ = α₁,…,Z_j− 1 = α_j− 1) that appear with nonzero probability. While the standard statement of Hoeffding’s inequality does not suffice for our needs, the standard proof of Hoeffding’s inequality does establish that

$$ \text{Pr}\Biggl(\frac{Z_{1} + {\cdots} + Z_{N}}{N} \geq \frac{1}{3}\Biggr) = \text{Pr}\Biggl(\frac{Z_{1} + {\cdots} + Z_{N}}{N} \geq \frac{1}{4} + \frac{1}{12}\Biggr) \leq \exp\biggl(-\frac{2N}{144}\biggr) < \frac{1}{3}, $$

(101)

as explained in an appendix at the end of the paper. Having obtained this bound, the proof is complete. □

Corollary 18

$\text {MQRG}(1) \subseteq \mathrm {P}\cdot \text {PP}$.

6 Conclusion

We have proved containments on two restricted versions of QRG(1), which we have called CQRG(1) and MQRG(1) (Fig. 4). A diagram illustrating the containments is provided.

Fig. 4

Hasse diagram showing the relationships between CQRG(1), MQRG(1), and other complexity classes

The question that originally motivated the work reported in this paper is whether the containment $\text {QRG}(1) \subseteq \text {PSPACE}$ can be improved. We did not succeed in this endeavor, and so we leave this as an open question. Observing that the containments we prove establish that CQRG(1) and MQRG(1) are contained in the counting hierarchy, we ask specifically: is QRG(1) also contained in the counting hierarchy?

Appendix A: Hoeffding’s inequality for dependent random variables with bounded conditional expectation

In the proof of Theorem 17 we used a slight variant of Hoeffding’s inequality, where the assumption of independence is replaced by a bound on conditional expectation. We expect that a bound along these lines has been observed before, but we have not found a suitable reference. (A similar bound is proved in [4] for Bernoulli random variables, but we require the bound to hold more generally for discrete random variables.)

It is, however, straightforward to adapt the most typical proof of Hoeffding’s inequality to obtain this bound, as we now explain. We begin with Hoeffding’s lemma, which is the essential ingredient in the proof, and which we state without proof. (A proof may be found in [7], among many other references).

Lemma 19

Let X be a random variable taking values in [α, β], for real numbers α < β, and assume E(X) ≤ 0. For every λ > 0 it is the case that

$$ \text{E}\bigl(\exp(\lambda X)\bigr) \leq \exp\biggl(\frac{\lambda^{2}}{8(\beta - \alpha)^{2}}\biggr). $$

(102)

Remark 20

The more typical assumption for this lemma is that E(X) = 0, but (as is not surprising) it is true assuming instead that E(X) ≤ 0. This follows immediately from the observation that if E(X) ≤ 0, then

$$ \text{E}(\exp(\lambda X)) \leq \text{E}(\exp(\lambda(X - \text{E}(X)))). $$

(103)

The next lemma provides the inequality in the proof of Hoeffding’s inequality that would ordinarily follow from the assumption of independence. For simplicity we prove this lemma for discrete random variables, which suffices for our needs.

Lemma 21

Let X and Y be discrete random variables taking values in [α, β] for real numbers α < β, and assume that E(Y |X) ≤ 0. For every λ > 0 it is the case that

$$ \text{E}\left( \exp(\lambda (X + Y))\right. \leq \exp\biggl(\frac{\lambda^{2}}{8(\beta - \alpha)^{2}}\biggr) \text{E}(\exp(\lambda X)). $$

(104)

Proof

We may write

$$ \text{E}\left( \exp(\lambda (X + Y))\right. = \sum\limits_{x} \exp(\lambda x) \text{E}(\exp(\lambda Y) | X = x) \text{Pr}(X = x), $$

(105)

where the sum ranges over all possible values of X. By the assumption E(Y |X) ≤ 0, Hoeffding’s lemma implies

$$ \begin{array}{@{}rcl@{}} &&\sum\limits_{x} \exp(\lambda x) \text{E}(\exp(\lambda Y) | X = x) \text{Pr}(X = x) \\ && \leq \exp\biggl(\frac{\lambda^{2}}{8(\beta - \alpha)^{2}}\biggr) \sum\limits_{x} \exp(\lambda x) \text{Pr}(X = x)\\ &&= \exp\biggl(\frac{\lambda^{2}}{8(\beta - \alpha)^{2}}\biggr) \text{E}(\exp(\lambda X)), \end{array} $$

(106)

as required. □

Finally, we state and prove the variant of Hoeffding’s inequality we have used (again for discrete random variables).

Theorem 22

Let X₁,…,X_n be discrete random variables taking values in [0, 1], let γ ∈ [0, 1], and assume that

$$ \text{E}(X_{k} | X_{1},\ldots,X_{k-1}) \leq \gamma $$

(107)

for all k ∈{1,…,n}. For all ε > 0 it is the case that

$$ \text{Pr}\bigl(X_{1}+\cdots+X_{n} \geq (\gamma + \varepsilon)n\bigr) \leq \exp(-2n\varepsilon^{2}). $$

(108)

Proof

For every λ > 0 we have that

$$ \begin{array}{@{}rcl@{}} &&\text{Pr}\bigl(X_{1}+\cdots+X_{n} \geq (\gamma + \varepsilon)n\bigr) \\ &&= \text{Pr}\bigl(\exp\bigl(\lambda (X_{1} + {\cdots} + X_{n} - \gamma n)\bigr) \geq \exp(\lambda\varepsilon n)\bigr) \\ &&\leq \frac{\text{E}\bigl(\exp\bigl(\lambda (X_{1} + {\cdots} + X_{n} - \gamma n)\bigr)\bigr)}{ \exp(\lambda\varepsilon n)} \end{array} $$

(109)

by Markov’s inequality. Applying Lemma 21 iteratively yields

$$ \text{E}\bigl(\exp\bigl(\lambda (X_{1} + {\cdots} + X_{n} - \gamma n)\bigr)\bigr) \leq \exp\biggl(\frac{n\lambda^{2}}{8}\biggr). $$

(110)

Choosing λ = 4ε yields the claimed bound. □