Quantum Advantage and Lower Bounds in Parallel Query Complexity

Prior work on parallel quantum algorithms in the query model has primarily demonstrated the need for quantum depth in solving certain problems.

The cheatsheet framework [3] lifts a partial function $f$, potentially with an exponential quantum query advantage to a total function that retains some of the advantage (although now polynomial). The natural way to do this is to define a total function such that when the input is in the domain of $f$, answer as $f$ does, and when it is not answer $0$. The cheat sheet framework does this “domain check” in a clever way so that the quantum advantage is not lost in the process. As shown in Figure 2, the input for the total function $f_{\text{ccs}}$ is divided into two components, the Address section and the Data section. The partial function $f$ is composed with a total function that has low certificate complexity, which in this case is $\text{And}\circ \text{Or}$. This composition $f\circ \text{And}\circ \text{Or}$ produces a single bit. This is repeated such that enough bits to address a block in the data component are obtained. If this block contains the certificate (or “cheatsheet”) for the $\text{And}\circ \text{Or}$’s, and these certify that the input of $f$ is in its domain, then the output of $f_{\text{ccs}}$ is $1$, else, the output is $0$. As the data component is large, an algorithm is forced to solve the partial function $f$ to obtain the address of the block, and can use the certificate present there to check whether the input of $f$ is in the domain (and thus does not need to read the full Address to perform the domain check).

Thus, computing a cheatsheet function involves

1. 1.

   Solving $f\circ \text{And}\circ \text{Or}$ to get the certificate location,

2. 2.

   Reading out the certificate,

3. 3.

   Checking the validity of the input of $f$.

For concreteness, consider the canonical cheatsheet function defined by Aaronson et al [3] composing $f=\text{Forrelation}$ [1, 2] on $N$ bits with $\text{And}\circ \text{Or}$ on $N^2$ bits. This function was originally constructed to exhibit a superquadratic separation between sequential quantum and randomized query complexities. Observe that with $p=N^2$ parallelism, solving any given instance of the internal $\text{And}\circ \text{Or}$ can be done in a single $p$-parallel query by reading out all the inputs. A quantum algorithm can utilize this to quickly solve the whole composition, as Forrelation is quantumly easy. However, any classical algorithm would seem to need $\text{R}(\text{Forrelation})$ $p$-parallel queries to solve this composition since it requires at least $p\cdot \text{R}(\text{Forrelation})$ sequential queries. Thus, with $p$ parallelism, step (1) is quantum efficient but not classically efficient. We show that for the canonical choice of parameters, steps (2) and (3) are also possible with few $p$-parallel queries, resulting in the desired separation.

The same technique can be used to give an exponential total function separation between randomized and deterministic parallel query complexity.

Our result, combined with an aforementioned result of [27], which states that ${\text{D}}^{p\parallel }(h)=\text{poly}({\text{Q}}^{p\parallel }(h))$ for all total $h$ and $p=O(\text{bs}{(h)}^{1-ϵ})$ with $ϵ>0$, provides a new way of upper bounding the block sensitivity of total Boolean functions. In particular, using our separation and a lower bound argument for the canonical cheatsheet function, we characterize its block sensitivity.

Is some polynomial sequential separation necessary for unbounded parallel quantum speedup, or can the advantage emerge purely from a quantum algorithm’s ability to utilize parallelism (which we call a genuine parallel advantage)? We argue that the latter can indeed be the case, by first describing our construction for the partial function $h$ that allows proving Theorem 3. As shown in Figure 3, the input to $h$ here involves two components $X$ and $Y$. The function $f$ requires a sequence of adaptive queries to solve (in either model) whereas the function $g$ achieves quantum-randomized separation and can be fully parallelized. We are promised that the output of both will be the same, so any algorithm can choose to solve either. We then argue that any algorithm will require solving at least one of $f$ and $g$.

For concreteness, let $ϵ>0$ and suppose that $\text{Q}(f)=\mathrm{\Theta }(\text{R}(f))=\mathrm{\Theta }(N^{ϵ})$ and ${\text{R}}^{p\parallel }(f)=\mathrm{\Omega }(N^{ϵ})$, and ${\text{Q}}^{p\parallel }(g)=\mathrm{\Theta }(N^{ϵ})/p$ and ${\text{R}}^{p\parallel }(g)=\mathrm{\Theta }(N^{2ϵ})/p$ for small enough $p$.⁴⁴4For more concreteness, one may think of $f$ as the pointer chasing function with chain length $N^{ϵ}$ and $g$ as the composition of parity on $N^{ϵ}$ bits composed with Forrelation on $N^{2ϵ}$ bits as shown in Figure 3. Then, a randomized sequential algorithm can choose to solve $f$, while a quantum sequential algorithm will not benefit from choosing to solve either $f$ or $g$. Thus, $\text{R}(h)=O(N^{ϵ})$ and we would have $\text{Q}(h)=\mathrm{\Omega }(N^{ϵ})$. Similarly, for $p=\text{Q}(g)$, a $p$-parallel quantum algorithm can choose to solve $g$, while a $p$-parallel randomized algorithm will not benefit from choosing to solve either $f$ or $g$. Therefore, ${\text{Q}}^{p\parallel }(h)=1$ and we would have ${\text{R}}^{p\parallel }=\mathrm{\Omega }(N^{ϵ})$.

To show our desired randomized parallel and quantum lower bounds, we consider the general problem, which we call cor, where we are given inputs $X$ and $Y$ to arbitrary functions $f$ and $g$ respectively along with the promise that $f(X)=g(Y)$, our goal is to output $f(X)=g(Y)$. We use the hybrid argument to establish that any randomized parallel algorithm that solves $\text{cor}(f,g)$ will be able to either distinguish an input sampled from a hard $0$-distribution for $f$ from an input sampled from a hard $1$-distribution for $f$, or will succeed at a similar distinguishing task for $g$. Therefore, we must have ${\text{R}}^{p\parallel }(\text{cor}(f,g))=\mathrm{\Omega }(\min ({\text{R}}^{p\parallel }(f),{\text{R}}^{p\parallel }(g)))$. For the quantum lower bound, we show that that for any adversary matrices ${\mathrm{\Gamma }}^{(f)}$ and ${\mathrm{\Gamma }}^{(g)}$ for $f$ and $g$ respectively, the matrix $\mathrm{\Gamma }={\mathrm{\Gamma }}^{(f)}\otimes {\mathrm{\Gamma }}^{(g)}$ is an adversary matrix for $\text{cor}(f,g)$ and ${\max }_i\Vert {\mathrm{\Gamma }}_i\Vert =\max ({\max }_i\Vert {\mathrm{\Gamma }}_i^{(f)}\Vert ,{\max }_i\Vert {\mathrm{\Gamma }}_i^{(g)}\Vert )$⁵⁵5All the $\max$ are over relevant indices. It follows that $\text{Adv}(\text{cor}(f,g))=\mathrm{\Omega }(\min (\text{Adv}(f),\text{Adv}(g)))$, which implies the desired lower bound.

Next, we describe a way to totalize the partial function $h$ that we constructed in the previous section while maintaining some of its properties. We will use the cheatsheet framework. However, we will need a function with relatively small certificate complexity that does not admit any significant quantum speed-up so $\text{And}\circ \text{Or}$ will not work. Fortunately, [3] found a function, which they called Bkk, that satisfies $\text{Q}({\text{Bkk}}_N)=\tilde{\mathrm{\Theta }}({\text{Bkk}}_N)=\tilde{\mathrm{\Theta }}(N)$ and $\text{C}({\text{Bkk}}_N)=\tilde{O}(\sqrt{N})$. We compose $h$ on $N$ bits with Bkk on $N^2$ bits, and then plug it into the cheatsheet framework. The desired upper bounds for ${\text{Q}}^{p\parallel }$ and R in Theorem 4 are relatively straightforward and follows from the discussion in the previous sections. The quantum lower bound follows from quantum query complexity composition theorem and results in [3]. For the randomized parallel lower bound, we show a composition theorem where the inner function is Bkk.

The same lower bound techniques do not follow for the analogous separation between the randomized and deterministic query complexity measures. In particular, there is no general randomized composition theorem. Fortunately, for our constructions, the known randomized composition theorems suffice. For the deterministic parallel lower bound, we show a general composition theorem when the degree of the inner function is almost full, which might be of independent interest.

As we noted earlier (see Theorem 2), the cheat sheet framework can be employed to show a polynomial separation between ${\text{Q}}^{3⟂}$ and ${\text{R}}^{3⟂}$. We modify this framework to show a polynomial separation between ${\text{Q}}^{2⟂}$ and ${\text{R}}^{2⟂}$. As shown in Figure 4, our strategy is essentially to separate the cheatsheet into two parts: the first part contains the certificate, and the second just contains a long data string with one relevant index. Let $f$ be a partial function with a polynomial separation between ${\text{Q}}^{1⟂}(f)$ and ${\text{R}}^{1⟂}(f)$. Informally, embedding $f$ in our framework results in a function that requires (1) verifying the input to the $f$ is in the domain (using the certificate) and if so, (2) outputting the bit of the data string present at the address obtained by solving the $f$.

The quantum algorithm easily succeeds as follows. In the first round, it can read the certificate as well as solve $f$ to obtain the address. In the second round, it verifies the certificate and queries the bit at the right address in the data string, hence is able to output the result. The randomized algorithm is unable to succeed in the same amount of parallelism because after the first round, it cannot compute $f$, so it would not find the right address by the first round, and can only make a query to the right address by the second round if it guesses the location correctly, which happens with very low probability. We also note that there is a caveat: the structure of a zero-certificate might be easy to distinguish from the structure of a one-certificate, allowing the algorithm to infer the inputs to the partial function from just the structure of the certificates. In that case, the randomized algorithm can use this to compute the partial function in the first round itself. To prevent this from happening, we use “bi-certificates” instead of certificates, where a “bi-certificate” corresponds to a set of indices that could certify both a zero and a one instance. This prevents the randomized algorithm from learning any information just by knowing the certificate.

Therefore, we present a framework to lift a partial function ${\text{Q}}^{1⟂}$ vs ${\text{R}}^{1⟂}$ separation to a total function ${\text{Q}}^{2⟂}$ vs ${\text{R}}^{2⟂}$ separation. The analogous result holds for randomized vs deterministic algorithms.

There are few known techniques for lower bounding parallel quantum query complexity. Consider for instance lower bounding the quantum parallel query complexity for the balanced $\text{And}\circ \text{Or}$ function,

which is an example of a read-once formula. It is well known that this function has sequential quantum query complexity $\mathrm{\Theta }(\sqrt{N})$ [9, 29]. Since both ${\text{Q}}^{p\parallel }(\text{And})$ and ${\text{Q}}^{p\parallel }(\text{Or})$ are $\mathrm{\Omega }\left(\sqrt{N/p}\right)$, a natural guess for ${\text{Q}}^{p\parallel }(\text{And}\circ \text{Or})$ is $\mathrm{\Omega }\left(\sqrt{N/p}\right)$.

The bound $\text{Q}(\text{And}\circ \text{Or})=\mathrm{\Omega }(\sqrt{N})$ was shown using the (sequential) combinatorial adversary method. However, as mentioned in Section 1.1.4, the corresponding parallel version fails to show a lower bound better than $\mathrm{\Omega }\left(\sqrt{\lceil \frac{{\text{C}}_0(f)}{p}\rceil \lceil \frac{{\text{C}}_1(f)}{p}\rceil }\right)$ for any function $f$. This means that the best lower bound this method could help prove for $\text{And}\circ \text{Or}$ is $\mathrm{\Omega }(\sqrt{N}/p)$, since ${\text{C}}_0(\text{And}\circ \text{Or})={\text{C}}_1(\text{And}\circ \text{Or})=\sqrt{N}$.

We use the parallel spectral adversary method of [27], which is known to be optimal, to derive a method that is easier to apply and is sometimes stronger than the combinatorial adversary method (see Theorem 6). For the case of read-once formulas, we use the adversary sets of [9] to construct an adversary matrix $\mathrm{\Gamma }$. It is easy to lower bound $\Vert \mathrm{\Gamma }\Vert$ by a simple counting argument, but upper bounding $\Vert {\mathrm{\Gamma }}_S\Vert$ for all $S\subseteq [N]$ with $|S|=p$ can be challenging. We show that if $\mathrm{\Gamma }$ satisfies the property that $\mathrm{\Gamma }[x,y]=0$ for all $x,y$ that differs in more than 1 bit, then all the induced ${\mathrm{\Gamma }}_S$ can be rearranged to form block-diagonal matrices with blocks of size $2^p\times 2^p$. Moreover, each of these blocks are adversary matrices for some restricted function $g\in {ℱ}_{p-\text{res}}^{(f)}$ (Figure 5), where a restricted version of $f$ is one where all but $p$ input bits are fixed and known by the algorithm. Thus, we know that the spectral norm of these blocks is upper bounded by $\text{Q}(g)$ (up to the normalizing factor of ${\max }_{i\in [2^p]}\Vert {\mathrm{\Gamma }}_i\Vert$, and with a max taken over all $g\in {ℱ}_{p-\text{res}}^{(f)}$), which we can use to upper bound the spectral norm of any ${\mathrm{\Gamma }}_S$. In our case, noting that $g$ is a read-once formula of size $p$, we have $Q(g)=O(\sqrt{p})$ and we obtain the desired lower bound of $\mathrm{\Omega }\left(\sqrt{N/p}\right)$. Hence, we are able to reduce the task of finding parallel lower bounds to the potentially easier task of finding sequential upper bounds.