A Converse to the Polynomial Method (Arunachalam et al. 2017)

One of the most famous models for quantum computation is the black-box model, in which one is given a black-box called oracle encoding a unitary operation. With this oracle one can probe the bits of an unknown bit string $x \in\{-1,1\}^n$ (the paper uses the set $\{-1,1\}$ instead of $\{0,1\}$ , which I will keep here) . The main aim of the model is to use the oracle to learn some property given by a Boolean function $f$ of the bit string $x$ , for example, its parity. One use of the oracle is usually referred as a query, and the number of queries a certain algorithm performs reflects its efficiency. Quite obviously, we want to minimize the number of queries. In more precise words, the bounded-error quantum query complexity of a Boolean function $f : \{-1,1\}^n \to \{-1,1\}$ is denoted by $Q_\epsilon (f)$ and refers to the minimum number of queries a quantum algorithm must make on the worst-case input x in order to compute $f(x)$ with probability $1 - \epsilon$ .

Looking at the model and the definition for the quantum query complexity, one might ask “but how can we find the query complexity of a certain function? Is there an easy way to do so?”. As usual in this kind of problem, finding the optimal performance of an algorithm for a certain problem or an useful lower bound for it is easier said than done. Nonetheless, there are some methods for tackling the problem of determining $Q_\epsilon (f)$ . There are two main methods for proving lower bounds, known as the polynomial method and the adversary method. In this post we shall talk about the first, the polynomial method, and how it was improved in the work of Arunachalam et al.

The polynomial method

The polynomial method is a lower bound method based on a connection between quantum query algorithms and, as the name suggests, polynomials. The connection comes from the fact that for every t-query quantum algorithm $A$ that returns a random sign $A(x)$ (i.e. $\{-1,1\}$ ) on input $x$ , there exists a degree– $2t$ polynomial $p$ such that $p(x)$ equals the expected value of $A(x)$ . From this it follows that if $A$ computes a Boolean function $f : \{-1,1\}^n \to \{-1,1\}$ with probability at least $1 - \epsilon$ , then the polynomial $p$ satisfies $|p(x) - f(x)| \leq 2\epsilon$ for every $x$ (the factor of $2$ comes from the image being $\{-1,1\}$ instead of $\{0,1\}$ ). Therefore we can see that the minimum degree of a polynomial $p$ that satisfies $|p(x) - f(x)| \leq 2\epsilon$ for every $x$ , called the approximate (polynomial) degree and denoted by $deg_\epsilon(f)$ , serves as a lower bound for the query complexity $Q_\epsilon (f)$ . Hence the problem of finding a lower bound for the query complexity is converted into the problem of lower bounding the degree of such polynomials.

Converse to the polynomial method

We now have a method for proving lower bounds for quantum query algorithms by using polynomials. A natural question that can arise is whether the polynomial method has a converse, that is, if a degree- $2t$ polynomial leads to a $t$ –query quantum algorithm. This would in turn imply a sufficient characterization of quantum query algorithms. Unfortunately, Ambainis showed in 2006 that this is not the case, by proving that for infinitely many $n$ , there is a function $f$ with $deg_\epsilon(f) \leq n^\alpha$ and $Q_\epsilon (f) \geq n^\beta$ for some positive constants $\beta > \alpha$ . Hence the approximate degree is not such a precise measure for quantum query complexity in most cases.

In the view of these negative results, the question that stays is, is there some refinement to the approximate polynomial that approximates $Q_\epsilon(f)$ up to a constant factor? Aaronson et al. tried to answer this question around 2016 by introducing a refined degree measure, called block-multilinear approximate polynomial degree and denoted by $bm\text{-}deg_\epsilon(f)$ , which comes from polynomials with a so-called block-multilinear structure. This refined degree lies between $deg_\epsilon(f)$ and $2Q_\epsilon(f)$ , which leads to the question of how well that approximates $Q_\epsilon(f)$ . Once again, it was later shown that for infinitely many $n$ , there is a function $f$ with $bm\text{-}deg_\epsilon(f) = O(\sqrt{n})$ and $Q_\epsilon(f) = \Omega(n)$ , ruling out the converse for the polynomial method based on the degree $bm\text{-}deg_\epsilon(f)$ and leaving the question open until now, when it was answered by Arunachalam et al., who gave a new notion of polynomial degree that tightly characterizes quantum query complexity.

Characterization of quantum algorithms

In few words, it turns out that $t$ -query quantum algorithms can be fully characterized using the polynomial method if we restrict the set of degree- $2t$ polynomials to forms that are completely bounded. A form is a homogeneous polynomial, that is, a polynomial whose non-zero terms all have the same degree, e.g. $x^2 + 3xy + 2y^2$ is a form of degree $2$ . And the notion of completely bounded involves the idea of a very specific norm, the completely bounded norm (denoted by $\|\cdot\|_{cb}$ ), which was originally introduced in the general context of tensor products of operator spaces. But before we venture ourselves into this norm, which involves symmetric tensors and other norms, let us state the main result of the quantum query algorithms characterization.

Let $\beta: \{-1,1\}^n \to [-1,1]$ and $t$ a positive integer. Then, the following are equivalent.

1. There exists a form $p$ of degree $2t$ such that $\|p\|_{cb} \leq 1$ and $p((x,\boldsymbol{1})) = \beta(x)$ for every $x \in \{-1,1\}^n$ , where $\boldsymbol{1}$ is the all-ones vector.

2. There exists a $t$ -query quantum algorithm that returns a random sign with expected value $\beta(x)$ on input $x \in \{-1,1\}^n$ .

In short, if we find a form of degree $2t$ which is completely bounded ( $\|p\|_{cb} \leq 1$ ) and approximates a function $f$ that we are trying to solve, then there is a quantum algorithm which makes $t$ queries and solves the function. Hence we have a characterization of quantum algorithms in terms of forms that are completely bounded. But we still haven’t talked about the norm itself, which we should do now. It will involve a lot of definitions, some extra norms and a bit of C*-algebra, but fear not, we will go slowly.

The completely bounded norm

For $\alpha \in \{0,1,2, \dotsc \}^{2n}$ , we write $|\alpha| = \alpha_1 + \dotsc + \alpha_{2n}$ . Any form $p$ of degree $t$ can be written as

$p(x) = \sum_{|\alpha| = t} c_{\alpha} x^\alpha$ ,

where $c_{\alpha}$ are real coefficients. The first step towards the completely bounded norm of a form is to define the completely bounded norm of a tensor, and the tensor we use is the symmetric $t$ -tensor $T_p$ defined as

$(T_p)_\alpha = c_\alpha/|\{\alpha\}|!$

where $|\{\alpha\}|!$ denotes the number of distinct elements in the set formed by the coordinates of $\alpha$ .

The relevant norm of $T_p$ is given in terms of an infimum over decompositions of the form $T_p = \sum_\sigma T^\sigma \circ\sigma$ , where $\sigma$ is a permutation of the set $\{1,\dotsc,t\}$ and $(T^\sigma\circ\sigma)_\alpha = T^\sigma_{\sigma(\alpha)}$ is the permuted element of the multilinear form $T^\sigma$ . So that the completely bounded norm of $p$ is kind of transferred to $T_p$ via the definition

$\|p\|_{cb} = \text{inf }\{\sum_\sigma \|T^\sigma\|_{cb} : T_p = \sum_\sigma T^\sigma\circ\sigma\}$ .

Just to recap, with the coefficients of the polynomial $p$ we define the symmetric $t$ -tensor $T_p$ , which is then decomposed into the sum of permuted tensor (multilinear form) $T^\sigma$ . We then define the completely bounded norm of $p$ as the infimum of the sum of the completely bounded norm of such tensor, but now without permuting it. Of course, we haven’t yet defined the completely bounded norm of such tensor, that is, what is $\|T^\sigma\|_{cb}$ ? We will explain it now.

The idea is to get a bunch of collections of $d \times d$ unitary matrices $U_1(i), U_2(i), \dotsc, U_t(i)$ for $i \in \{1, \dotsc ,2n\}$ and consider the quantity

$\|\sum_{i,j,\dotsc,k} T^\sigma_{i,j,\dotsc,k} U_1(i)U_2(j)\dotsc U_t(k)\|$ .

We multiply the unitaries from these collections and sum them using the tensor $T^\sigma$ as weight, and then take the norm of the resulting quantity. But here we are using a different norm, the usual operator norm defined for a given operator $A$ as $\|A\| = \text{inf }\{c\geq 0 : \|Av\| \leq c\|v\| \text{ for all vectors } v\}$ . Finally, with these ingredients in hand, we can define the completely bounded norm for $T^\sigma$ , which is just the supremum over the positive integer $d$ and the unitary matrices, that is,

$\|T^\sigma\|_{cb} = \text{sup }\{\|\sum_{i,j,\dotsc,k} T^\sigma_{i,j,\dotsc,k} U_1(i)U_2(j)\dotsc U_t(k)\| : d \in \mathbb{N}, d \times d \text{ unitary matrices } U_i\}$ .

If we can obtain the supremum of such norm over the size of the unitary matrices and the unitary matrices themselves, then we obtain the completely bounded norm of the tensor $T^\sigma$ , and from this we get the completely bounded norm of the associated form $p$ . Is there such a degree- $2t$ form with $\|p\|_{cb} \leq 1$ that approximates the function $f$ we want to solve? If yes, then there is a $t$ -query quantum algorithm that solves $f$ .

The proof

Let us briefly explain the proof of the quantum algorithms characterization that we stated above. Their proof involves three main ingredients. The first one is a theorem by Christensen and Sinclair showing that the completely-boundedness of a multilinear form is equivalent to a nice decomposition of such multilinear form. In other words, for a multilinear form $T$ , we have that $\|T\|_{cb} \leq 1$ if and only if we can write $T$ as

$T(x_1,\dotsc,x_t) = V_1\pi(x_1)V_2\pi(x_2)V_3\dotsc V_t\pi(x_t)V_{t+1}$ , (1)

where $V_i$ are contractions ( $\|V_ix\| \leq \|x\|$ for every $x$ ) and $\pi_i$ are *-representations (linear maps that preserve multiplication operations, $\pi(xy) = \pi(x)\pi(y)$ ).

The second ingredient gives an upper bound on the completely bounded norm of a certain linear map if it has a specific form. More specifically, if $\sigma$ is a linear map such that $\sigma(x) = U\pi(x)V$ , where $U$ and $V$ are also linear maps and $\pi$ is a *-representation, then $\|\sigma\|_{cb} \leq \|U\|\|V\|$ .

The third ingredient is the famous Fundamental Factorization Theorem that “factorizes” a linear map in terms of other linear maps if its completely bounded norm is upper bounded by these linear maps. In other words, if $\sigma$ is a linear map and exists other linear maps $U$ and $V$ such that $\|U\|\|V\| \leq \|\sigma\|_{cb}$ , then, for every matrix $M$ , we have $\sigma(M) = U^\ast(M\otimes I)V$ .

With these ingredients, they proved an alternative decomposition of equation (1) which was later used to come up with a quantum circuit implementing the tensor $T_p$ and using $t$ queries, and then showed that this tensor $T_p$ matched the initial form $p$ . This alternative decomposition is

$T(x_1,\dotsc,x_t) = u^\ast U_1^\ast (\text{Diag}(x_1)\otimes I)V_1 \dotsc U_t^\ast (\text{Diag}(x_t)\otimes I)V_tv$ , (2)

where $U_i, V_i$ are contractions, $u,v$ are unit vectors, $\text{Diag}(x)$ is the diagonal matrix whose diagonal forms $x$ . The above decomposition is valid if, similarly to (1), $\|T\|_{cb} \leq 1$ .

We can see that the decomposition involves the operator $\text{Diag}(x)$ intercalated by unitaries $t$ times. Having $\text{Diag}(x)$ as the query operator, it is possible then to come up with a quantum circuit implementing the decomposition (2). If we look more closely, decomposition (2) has unit vectors on both the left and right sides, which looks like an expectation value. So what is going on is that decomposition (2) can be used to construct a quantum circuit whose expectation value matches $T_p$ , and hence the polynomial $p$ used to construct $T_p$ . We won’t get into much details, but we will leave the quantum circuit so that the reader can have a glimpse of what is going on.

In the above figure representing a quantum circuit that has $T_p$ as its expectation value, the registers C, Q, W denote control, query and workspace registers. The unitaries $W_i$ are defined by $W_i = V_{i-1}U_i^\ast$ , the unitaries $U, V$ have $W_1V_0 u$ and $W_{2t+1}U_{2t+1}v$ as their first rows, where $V_0$ and $U_{2t+1}$ are isometries ( $A$ is an isometry iff $\|Ax\| = \|x\|$ for every $x$ ).

Application of the characterization: separation for quartic polynomials

A couple of years ago, in 2016, Aaronson et al. showed that the bounded norm (and also the completely bounded norm that we spent some time describing) is sufficient to characterize quadratic polynomials. More specifically, they showed that for every bounded quadratic polynomial $p$ , there exists a one-query quantum algorithm that returns a random sign with expectation $Cp(x)$ on input $x$ , where $C$ is an absolute constant. This readily prompted the question of whether the same is valid for higher-degree polynomials, that is, if the bounded norm suffices to characterize quantum query algorithms.

As you might expect by now, the answer is no, since it is the completely bounded norm that suffices, and Arunachalam et al. used their characterization to give a counterexample for bounded quartic polynomials. What they showed is the existence of a bounded (not completely bounded) quartic polynomial p that for any two-query quantum algorithm whose expectation value is $Cp(x)$ , one must have $C = O(n^{-1/2})$ , thus showing that $C$ is not an absolute constant. The way they showed this is by using a random cubic form that is bounded, but whose completely bounded norm is $poly(n)$ and then embedded this form into a quartic form.

Conclusions

The characterization they found is, in my opinion, apart from the obvious point that it answers the open question of the converse of the polynomial method, quite interesting in the sense that the set of polynomials we should look at is the ones that are bounded by a particular norm, the completely bounded norm. The interesting point is exactly this one, the connection between quantum query algorithms and the completely bounded norm that was first introduced in the general context of tensor products of operator spaces as mentioned before. The norm itself looks quite exotic and complicated, which is linked to a question that Scott Aaronson made at the end of Arunachalam’s talk in QIP 2019, “sure, we could define a particular norm as one that restricts the set of polynomials to the ones that admit a converse to the polynomial method”. Of course, such a norm would not be quite an interesting one. He carries on with something like “In what is this completely bounded norm different compared to that?”. If I remember correctly, Arunachalam gave an answer on the lines of the completely bounded norm appearing in a completely different context. But I still find it surprising that you would go through all the exotic definitions we mentioned above for the completely bounded norm and discover that it is what is needed for the converse of the polynomial method.

Leave a Reply Cancel reply