The Compressed Oracle Is A Worthy (Multiplicative) Adversary

The original adversary method ${\mathrm{𝖠𝖣𝖵}}_{ϵ}$ for proving quantum query lower bounds was first introduced in [3]. Applying this method reduces to mostly combinatorial arguments, which makes it very convenient to use, as shown by its many applications [8, 18, 13, 17]. However, this method does have some technical limitations, one of which is the certificate complexity barrier [33], which shows that there are problems for which this method cannot be tight. This limitation is addressed by the strictly stronger negative-weights adversary method ${\mathrm{𝖠𝖣𝖵}}_{ϵ}^{\pm }$ by [21], now usually just referred to as the adversary method. This method is capable of proving tight lower bounds on the quantum query complexity of any $𝖥$ in the bounded-error regime [28], but this power comes at the cost of making it more complicated to apply, as its greater abstraction removes the primarily combinatorial reasoning suggested by the constraints of the original adversary method. This means that even for very symmetric problems such as the collision problem [1], it is highly difficult to come up with a non-trivial lower bound using the adversary method, and the only known construction relies on studying the symmetries of the problem via representation theory [11]. Lower bounds on $Q_{ϵ}(𝖥)$ proven using the adversary method are proportional to $1-ϵ$, the algorithm’s success probability, making them negligible for exponentially small success probabilities. It is therefore only suitable for proving lower bounds in the bounded-error regime.

The latest and most powerful iteration in adversary methods, and the one most central to this work, is the multiplicative adversary method ${\mathrm{𝖬𝖠𝖣𝖵}}_{ϵ}$ formalized in [31, 24], as a generalisation of an ad-hoc technique proposed in [7, 5]. This method is shown to be strictly stronger than the adversary method [6]. Since the adversary method is already tight in the bounded-error regime, this generalisation is particularly relevant in the low success probability regime, where it works even for exponentially small probabilities of success. This is a necessary condition for the method to exhibit a strong direct product theorem (SDPT), which intuitively states that to solve $k$ independent instances of a function, one needs $\mathrm{\Omega }(k)$ times as many queries to achieve even an exponentially small (in $k$) probability of success. It was already shown in [31] that the multiplicative adversary method satisfies a SDPT, which allowed [24] to prove a SDPT for quantum query complexity. The multiplicative adversary’s applicability to the small success probability regime has also proven useful in proving quantum time-space tradeoff lower bounds [7]. However, just as the (negative-weights) adversary method is more complicated to apply than the original adversary method, the powerful multiplicative adversary method is even more complicated and, as a result, still has relatively few applications.

Another technique for proving quantum query lower bounds is the polynomial method [9], which predates the adversary method. The method relies on the principle that for any $T$-query quantum algorithm, its acceptance probability can be expressed as a multivariate polynomial of degree $2T$ in the input variables. In any algorithm that computes $𝖥$ with error $ϵ$, this polynomial gives an $ϵ$-approximation to $𝖥$, and so its degree, $2T$, is at least ${\widetilde{\mathrm{deg}}}_{ϵ}(𝖥)$, the minimum degree of any polynomial that $ϵ$-approximates $𝖥$. This allows one to prove lower bounds on $Q_{ϵ}(𝖥)$ using results about polynomials. For example, the fact that a polynomial that changes value many times must have high degree implies a lower bound on problems like parity, that change value many times. Using much more involved reasoning, the polynomial method was used to give a tight lower bound on the collision problem [1], whereas an adversary lower bound for this problem was only constructed much later [11].

While the polynomial method is incomparable to the original adversary method [33, 4], the (negative-weights) adversary method subsumes it in the bounded-error regime; a reduction recently made constructive by [10]. The polynomial method does, however, work for small success probabilities, which makes it possible to prove SDPTs [23, 30]. Furthermore, as shown by [27], it can be reduced to the multiplicative adversary method.

For cryptographic security proofs, lower bounds on bounded-error quantum query complexity make little sense. Ruling out adversaries that succeed with a high probability of success (at least $2/3$) is not enough, and it is necessary to rule out adversaries with very small success probabilities as well. Moreover, worst-case query complexity, as captured by $Q_{ϵ}(𝖥)$, is not the relevant quantity. Imagine an adversary whose task $𝖥$ is to break some cryptosystem using its public key as input. A lower bound on $Q_{ϵ}(𝖥)$ only proves that there is some key on which the adversary requires many queries; it says nothing about the adversary’s resource requirements on a random key. This is instead captured by average-case quantum query complexity, which is defined with respect to some distribution of interest (often the uniform distribution).

The compressed oracle technique [32], introduced in the context of cryptographic security proofs, does precisely this, as it yields an upper bound on the probability of success for any quantum algorithm interacting with a random oracle, giving an average-case lower bound²²2Adversary methods also work by giving an average-case lower bound with respect to some distribution of inputs, which then implies a lower bound on the worst-case complexity. However, as the goal in using these is usually a worst-case lower bound, generally a deliberately hard distribution is chosen, rather than a uniform one. that holds even for exponentially small probabilities of success. Moreover, its analysis works via mostly combinatorial arguments that look quite similar to the types of reasoning one would use to prove classical lower bounds, which makes it straightforward to apply and has quickly resulted in many results [25, 15, 26, 14, 19, 16]. It also satisfies a SDPT, and has even been used to prove quantum time-space tradeoffs [20]. The limitation of this technique, however, is that it is not known how to apply it on input distributions where the values $f(x)$ for different $x$ are not independent [15, 20]. This limitation makes it difficult to prove worst-case lower bounds, as the hardest input distributions often have some global structure. It also rules out applications involving certain interesting cryptographic primitives such as random permutations. For that specific case, an ad-hoc workaround has recently been devised by [2], extending the indifferentiability of the Sponge construction [12] to the quantum setting. From the standpoint of quantum query lower bounds, however, this remedy is no longer tight.

All methods discussed above operate by tracking some progress measure that must change significantly over the course of the algorithm, but can only change a small amount using a single query. For the polynomial method, this is the degree of the polynomials representing the amplitudes of the algorithm’s states. For the compressed oracle and the adversary methods, the measure of progress is somehow measuring the amount of entanglement between the algorithm and the input, when instantiated as a coherent superposition. Since the adversary and compressed oracle techniques have different drawbacks that do not seem to exist in the other, it is interesting to see what the explicit relationship between these techniques is. This could aid in the ongoing search for a fusion of both techniques: a compressed oracle technique that can be applied to input distributions where each $f(x)$ is not necessarily assigned independently. On the cryptographic side, this could lead to (better) quantum security proofs for schemes using random permutations, such as the sponge construction [12]. On the quantum query lower bounds side, this might result in a technique that marries the power of the multiplicative adversary method – which works for all input distributions – with the intuitive combinatorial reasoning of the compressed oracle technique. Currently, the most promising result towards this “holy grail” has been a representation theory approach by [29] that allows for tackling the problem of inverting a random permutation.

In this work, we demonstrate that a generalised compressed oracle technique – one that accommodates distributions beyond random functions and permutations – must fall somewhere between the compressed oracle technique and the multiplicative adversary method. We explicitly show this by proving that the compressed oracle technique reduces to the multiplicative adversary method. We achieve this by defining a weaker version of the multiplicative adversary method, the multiplicative ladder adversary ${\mathrm{𝖬𝖫𝖠𝖣𝖵}}_{ϵ}$. An adversary lower bound (multiplicative or standard) is proven by exhibiting an adversary matrix that satisfies certain properties. In the ${\mathrm{𝖬𝖫𝖠𝖣𝖵}}_{ϵ}$ technique, we restrict adversary matrices to those whose eigenvalues are increasing powers of some constant larger than $1$, and whose eigenspaces form a “ladder” in the sense that a query can move the state up or down at most one eigenspace. This ladder structure makes reasoning about an algorithm’s progress much more tractable.

The ${\mathrm{𝖬𝖫𝖠𝖣𝖵}}_{ϵ}$ method still satisfies a strong direct product theorem (SDPT, see Section 6) and remains more powerful than the compressed oracle technique. Additionally, we show that this new version also still encompasses the polynomial method (see Section 7). These results are summarized in Figure 1. We hope that this new intermediate technique will aid in the search for an extended compressed oracle technique, as we show that it incorporates the approach from [29] to random permutations as a special case.

In this work we consider finite-dimensional complex inner product spaces $\mathscr{H}={ℂ}^d$ for some dimension $d$. We use standard bra-ket notation for column and row vectors in ${ℂ}^d$. We consider all bra-ket vectors to be normalised unless specified otherwise. For a finite set $S$, we let

using whichever notation is most convenient given the complexity of writing $S$. For any two Hermitian operators $A,B$, we write $A⪰B$ if their difference $A-B$ is positive semidefinite.

We will make use of the following standard result.

In the quantum query model, we are generally interested in computing a function $𝖥:\mathrm{𝖥𝗎𝗇𝖼}\to \mathrm{\Sigma }$ on an input $f\in \mathrm{𝖥𝗎𝗇𝖼}$. We consider the case where $\mathrm{𝖥𝗎𝗇𝖼}$ is a subset of $Y^X$, so each $f$ can itself also be viewed as a function from $X$ to $Y$. For example, if $Y=\{0,1\}$ and $X=[n]:=\{1,\mathrm{\dots },n\}$, then $f\in \mathrm{𝖥𝗎𝗇𝖼}$ is an $n$-bit string (which might have a promise defined by the subset $\mathrm{𝖥𝗎𝗇𝖼}$). In this work, we usually restrict ourselves to $X$ being any finite set of size $N$ and consider $Y$ to be the finite set ${[M-1]}_0:=\{0,\mathrm{\dots },M-1\}$.

The memory of our quantum algorithm $𝒜$, tasked with computing $𝖥$ on an input $f$, is described without loss of generality by the registers $𝒲$, $𝒳$, and $𝒴$. Here, the input oracle acts on $𝒳\times 𝒴$ (as detailed below), while $𝒲$ represents an additional workspace. The input function $f\in \mathrm{𝖥𝗎𝗇𝖼}$ can be accessed by $𝒜$ via an oracle, defined as follows:

The input $f$ is typically drawn from some (hard) input distribution $\delta$ over $\mathrm{𝖥𝗎𝗇𝖼}$, denoted $f\sim \delta$. Consequently, ${𝒪}_f$ is a random variable. In adversary methods and the compressed oracle technique, this randomness is avoided by introducing an additional input register $ℐ$, which stores a superposition of function tables representing the input $f$. In quantum information theory, this is known as purification. If $f\sim \delta$, the register $ℐ$ will be initialised as

Here, $|\delta ⟩$ represents the initial state of the input register. It is important to note that this should not be confused with the initial state of the algorithm, which is the all-zero state. This purification of the input leads to the following purified oracle:

From the perspective of the algorithm, it is indistinguishable whether it interacts with the random variable ${𝒪}_f$ or the purified oracle $𝒪$ with input register initialised to $|\delta ⟩$. The relationship between the two is captured by the following expression:

It is equivalent, and in this work more convenient, to encode the query into the phase by viewing the $𝒴$ register in the Fourier basis ${\{|\widehat{y}⟩\}}_{y\in Y}$ instead of the computational basis ${\{|y⟩\}}_{y\in Y}$.

In this Fourier basis, the oracle from Definition 4 acts on any basis state ${|x⟩}_{𝒳}{|\widehat{y}⟩}_{𝒴}{|f⟩}_{ℐ}$ as

Additionally, it will often be convenient to decompose the oracle $𝒪$ into diagonal unitary matrices ${𝒪}_{x,y}$ given by

where each ${𝒪}_{x,y}$ acts on the basis state ${|f⟩}_{ℐ}$ as

In the definition of $|{\psi }_t(𝒜,\delta )⟩$, both the queries $𝒪$ and the unitaries $U_1,\mathrm{\dots },U_t$ act on a larger Hilbert space than originally defined, but each operator is implicitly understood to act tensored with the identity operator on any unaffected registers.

In this work, we compare various techniques designed to lower bound the quantum query complexity of a problem $𝖥$:

The general idea behind the adversary methods is that any algorithm for $𝖥$, run on a superposition of different inputs $|\delta ⟩$ with different values of $𝖥$, must entangle the algorithm’s workspace $𝒲𝒳𝒴$ (which must eventually contain the answer) with the input register $ℐ$, resulting in the reduced density matrix on $ℐ$, which is initially the pure state ${\rho }_{ℐ}^0(𝒜,\delta )=|\delta ⟩⟨\delta |$, becoming some mixed state ${\rho }_{ℐ}^T(𝒜,\delta )$.

This idea was already present in the original quantum adversary method [3], which was later generalised to the stronger negative-weights adversary method [21] (now often called the adversary method), which is tight in the bounded-error regime, i.e. $ϵ\le 1/3$. We will be interested in the even more powerful multiplicative adversary method, first formalised in [31] and further developed in [6, 24, 27]. We now describe this method.

Any multiplicative adversary matrix gives rise to a progress measure, which is a way of quantifying how much progress a quantum algorithm $𝒜$ has made after $t$ queries towards solving a particular problem $𝖥$.

Theorem 10 quantifies in what way we can think of $W^t(\mathrm{\Gamma },𝒜)$ as a “progress measure.” After 0 queries, we have made no progress, which is indicated by $W^0(\mathrm{\Gamma },𝒜)=1$ (Item 1). After $T$ queries, if we want to claim that the algorithm actually solves $𝖥$ with probability $1-ϵ$, then it must be the case that the progress $W^T(\mathrm{\Gamma },𝒜)$ has increased sufficiently above 1 (Item 3). Item 2 bounds the amount of progress that can be made in a single query.

By Definition 7, we aim to lower bound the number of queries that any quantum query algorithm makes to successfully output $𝖥(f)\in \mathrm{\Sigma }$ for any input $f\in \mathrm{𝖥𝗎𝗇𝖼}$. All decision problems can be phrased in this form, where the set $\mathrm{\Sigma }$ is equal to $\{0,1\}$. However, it is not always possible to interpret more general search problems as computing a single-valued function $𝖥(f)$.

For instance, consider the simplest search problem, known as Search. If we restrict to the hardest inputs, all goes well: we have that each $f\in \mathrm{𝖥𝗎𝗇𝖼}$ is an $n$-bit string with Hamming weight $1$, and $𝖥(f)$ is defined to be the unique index $i\in \mathrm{\Sigma }=[n]$ such that $f(i)=1$. However, if we relax $\mathrm{𝖥𝗎𝗇𝖼}$ to include all $n$-bit strings with Hamming weight at least $1$, then there are multiple correct indices $i$ such that $f(i)=1$. Consequently, there is no longer a single correct value for $𝖥(f)$ for each $f\in \mathrm{𝖥𝗎𝗇𝖼}$. Further generalising $\mathrm{𝖥𝗎𝗇𝖼}$ to include all $n$-bit strings leads to cases where some inputs contain no indices mapping to $1$, making $𝖥(f)$ undefined for such inputs.

In search problems, the problem is therefore characterised by a relation $ℛ\subset \mathrm{𝖥𝗎𝗇𝖼}\times \mathrm{\Sigma }$, and the algorithm must output some $z\in \mathrm{\Sigma }$ on input $f$ such that $(f,z)\in ℛ$. This formulation generalises the concept of computing a function $𝖥$, as we can define the relation $ℛ$ corresponding to $𝖥$ as the set $\{(f,𝖥(f)):f\in \mathrm{𝖥𝗎𝗇𝖼}\}$. We shall see in Theorem 14 that the compressed oracle framework solves such search problems.

To remain closer to the notation used in Theorem 20, we still choose to frame search problems in terms of computing a function $𝖥$. To accommodate the fact that search problems can have multiple, or even no, correct outputs, we define that a quantum query algorithm $𝒜$ has successfully computed a function $𝖥$ on an input $f\in \mathrm{𝖥𝗎𝗇𝖼}$ if it outputs $z$ such that $z\in 𝖥(f)$ (now allowed to be a set of valid outputs). Consequently, if $\mathrm{\Sigma }$ is the set of possible outputs, then each $𝖥(f)$ is a subset of $\mathrm{\Sigma }$. To distinguish this from the earlier case where $𝖥(f)$ is a single value, we now write $𝖥:\mathrm{𝖥𝗎𝗇𝖼}\to 2^{\mathrm{\Sigma }}$ for such search problems, where $2^{\mathrm{\Sigma }}$ denotes the power set of $\mathrm{\Sigma }$.

To reflect the modified definition of “success”, we also update the projector $F_z$ for each $z\in \mathrm{\Sigma }$ in Theorem 10 to:

We show that these modifications do not impact Item $3$ in Theorem 10, thereby generalising Theorem 10 to search problems:

In the compressed oracle technique [32], Zhandry observes that in query problems where the algorithm interacts with a quantum random oracle, it is equivalent (by applying a purification) to assume that the algorithm is run on a uniform superposition over all possible functions from the set $X$ to the set $Y$. In this picture, a quantum adversary interacting with the quantum random oracle towards some nefarious end is analogous to a quantum algorithm run on input distribution $\delta$, which is initialised to the uniform distribution over all functions from $X$ to $Y$:

We refrain from discussing the compressed oracle in depth here. For more details, see [32, 15, 20, 14]. Instead, we summarise the necessary parts needed to show how the compressed oracle technique can be used to derive quantum query lower bounds whenever $\mathrm{𝖥𝗎𝗇𝖼}=Y^X$. The input register $ℐ$ holding any computational basis state ${|f⟩}_{ℐ}$, where $f\in Y^X$, can be viewed as a tensor product of the different function values for $f$ for different values of $x\in X$:

This can be interpreted as a look-up table that fully describes the action of $f$. We can also consider a Fourier basis (see Definition 5) for this register that represents a function in $Y^X$. Let ${\{|\widehat{f}⟩\}}_{f\in Y^X}$ be the Fourier basis of $ℐ\equiv {𝒴}^{\otimes N}$, where each $|\widehat{f}⟩$ is defined as

From this look-up table perspective, this means that we change the basis of all our entries in the look-up table. The key insight that Zhandry makes is that if we view both the input register $ℐ$ in this Fourier basis, as well as the $𝒴$ register, then a query (as in Definition 4) acts on a basis state ${|x⟩}_{𝒳}{|\widehat{y}⟩}_{𝒴}{|\widehat{f}⟩}_{ℐ}$ as follows:

Here, ${\delta }_x$ denotes the point function satisfying ${\delta }_x(x)=1$ and ${\delta }_x(x^{\prime })=0$ for all $x^{\prime }\ne x$, so $f-y\cdot {\delta }_x$ is the function that agrees with $f$ on all values except possibly $x$, where it takes value $f(x)-y$. This change of perspective is quite peculiar: where in a regular query (as in Definition 4) the information stored in the ${ℐ}_x$ register is “copied” into the $𝒴$ register, this interaction is mirrored when viewing the ${ℐ}_x$ register in the Fourier basis. Another added benefit of this basis change is that the initial state $|\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}⟩$ simplifies to

The action of the oracle in Equation 3, combined with Equation 4, implies the following consequence, which is the cornerstone of the compressed oracle technique:

In Lemma 18, we will establish a stronger relationship that directly implies Fact 13.

We can construct an isometry ${\mathrm{𝖢𝗈𝗆𝗉}}_x:ℂ[Y]\to ℂ[Y\cup \{\perp \}]$, for every $x\in X$, that maps the ${ℐ}_x$ register to $|\perp ⟩$ if and only if this register contains $|\widehat{0}⟩$, which represents the algorithm knowing nothing about the value stored in register ${ℐ}_x$:

By doing this for every $x\in X$ we obtain the isometry

This isometry $\mathrm{𝖢𝗈𝗆𝗉}$ compresses the information of each of the basis vectors $|\widehat{f}⟩$, for $f=y_1{\delta }_{x_1}+\mathrm{\cdots }+y_s{\delta }_{x_s}$, in the support of ${\rho }_{ℐ}^t(𝒜,\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆})$, since $\mathrm{𝖢𝗈𝗆𝗉}|\widehat{f}⟩\in ℂ[{(Y\cup \{\perp \})}^X]$ has $|\perp ⟩$ everywhere except for those $s\le t$ registers indexed by $x_1,\mathrm{\dots },x_s$. Let us extend ${\mathrm{𝖰𝖥𝖳}}_M$ to $ℂ[{\left(Y\cup \{\perp \}\right)}^X]$ by defining ${\mathrm{𝖰𝖥𝖳}}_M|\perp ⟩=|\perp ⟩$. We can view

as a database, where we have applied ${\mathrm{𝖰𝖥𝖳}}_M^{†}$ to bring the databases back to the computational basis. We say that $D$ has size $s$ if $\left|\{x\in X:D(x)\ne \perp \}\right|=s$, which we denote by $\left|D\right|=s$, and remark that by ${\mathrm{𝖰𝖥𝖳}}_M|\perp ⟩=|\perp ⟩$, this basis conversion leaves the size of the database unaffected. We write

for the sets of all databases of size $s$ and at most $s$, respectively. We let $𝒟={(Y\cup \{\perp \})}^X$ denote the set of all databases of any size. In this work, we use set notation when working with databases:

• $\mathrm{■}$

  For any $x\in X,y\in Y$ and $D\in {\left(Y\cup \{\perp \}\right)}^X$ such that $D(x)=\perp$, we can add a new entry $(x,y)$ to $D$, to obtain $D^{\prime }=D\cup (x,y)$. This means that the resulting database $D^{\prime }$ satisfies $D(x^{\prime })=D^{\prime }(x^{\prime })$ for every $x^{\prime }\in X\setminus \{x\}$ and $D^{\prime }(x)=y$.

• $\mathrm{■}$

  For any $x\in X,y\in Y$ and $D\in {\left(Y\cup \{\perp \}\right)}^X$ such that $D(x)=y$, we can delete the entry $(x,y)$ from $D$, to obtain $D^{\prime }=D\setminus (x,y)$. This means that the resulting database $D^{\prime }$ satisfies $D(x^{\prime })=D^{\prime }(x^{\prime })$ for every $x^{\prime }\in X\setminus \{x\}$ and $D^{\prime }(x)=\perp$.

The compressed oracle gets its name from the fact that each database $D$ of size $s$ can be efficiently represented by the list of pairs $(x_1,D(x_1)),\mathrm{\dots },(x_s,D(x_s))$, which is bounded in size due to Fact 13. Hence, the oracle operation ${𝒪}_{x,y}$ can be efficiently computed by a quantum algorithm that lazy samples from the uniform distribution, and this circuit (see [15] for its explicit construction) is referred to as the compressed (Fourier) oracle:

This framework has many applications in cryptography [15, 26, 19, 16] by being able to analyse the interaction of an adversary with a random oracle, which as we have seen is equivalent to where the input register $ℐ$ is initialised to the uniform superposition over all functions (see Equation 2). In [15, 20], it was shown that this can be generalised to superpositions over distributions where there is no correlation between the values in the registers ${ℐ}_x$ and ${ℐ}_{x^{\prime }}$ for distinct $x,x^{\prime }\in X$. In this work, we focus only on the application of the compressed oracle technique to quantum query lower bounds. A rigorous framework of this application has been given in [14], where the main ingredient of this lower bound (see Theorem 14 for the full statement) is of the following form:

Here, the property $𝒫\subseteq {(X\times Y)}^k$ defines a set of tuples of size $k$ over $X\times Y$. Each tuple $p\in 𝒫$ is an element of ${(X\times Y)}^k$ and represents a list of input-output pairs $((x_1,y_1),\mathrm{\dots },(x_k,y_k))$. A property $𝒫$ induces a relation $ℛ$ on the input $f\in \mathrm{𝖥𝗎𝗇𝖼}$, as discussed in Section 3.2, by saying that for $p=(x_1,y_1),\mathrm{\dots },(x_k,y_k)\in 𝒫$, we have $(f,p)\in ℛ$ if and only if the input-output pairs in $p$ are consistent with the input $f$. As an example, consider the collision problem, where for any input $f\in Y^X$, the goal is to output a pair $(x_1,y)$, $(x_2,y)$ such that $f(x_1)=f(x_2)=y$, referred to as a collision. The corresponding property $𝒫$ in this case would be

A property $𝒫$ also induces a subset ${𝒟}_{𝒫}\subseteq 𝒟$, where $D\in {𝒟}_{𝒫}$ if and only if it is consistent with one of the tuples in $𝒫$, meaning that there exists a $k\in [N]$ and $p=((x_1,y_1),\mathrm{\dots },(x_k,y_k))\in 𝒫$ such that $D(x_1)=y_1,\mathrm{\dots },D(x_k)=y_k$. For any subset $A\subseteq 𝒟$, we denote the projection onto this subset as

Since these projectors project onto computational basis states, we have the added benefit that they commute for distinct choices of $A$.

The form of Theorem 14 is restricted compared to that of Theorem 10. We saw that we cannot run $𝒜$ on any input distribution, but only on $\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}$, since Theorem 14 requires the register $ℐ$ to be initialised with a uniformly random function $f$ in $Y^X$. Since $𝒜$ has to output $((x_1,y_1),\mathrm{\dots },(x_1,y_k))\in 𝒫\subseteq {\left(X\times Y\right)}^k$, the technique always deals with search problems instead of decision problems. Despite this restriction, it does seem to come with a large advantage compared to the adversary methods. In practice, it appears to be much more straightforward, or at least more intuitive, to come up with a good bound on $\Vert {𝖯}_{{𝒟}_{\le t}\cap {𝒟}_{𝒫}}{\mathrm{𝖼𝖮}}_{x,y}{𝖯}_{{𝒟}_{\le t-1}\setminus {𝒟}_{𝒫}}\Vert$ than it is to derive a good multiplicative adversary matrix $\mathrm{\Gamma }$ and accompanying constants $\lambda ,\eta$, and bound its progress $\Vert {𝒪}_{x,y}^{†}{\mathrm{\Gamma }}^{1/2}{𝒪}_{x,y}{\mathrm{\Gamma }}^{-1/2}\Vert$. Furthermore, like the multiplicative adversary method, it also works well when one considers exponentially small success probabilities, whereas the negative-weights adversary method fails in this regime.

Theorem 14, as stated, does not explicitly give a lower bound on $Q_{ϵ}(𝖥)$, but it does imply one: Recall from Definition 7 and Section 3.2 that $Q_{ϵ}(𝖥)$ captures the number of queries required for any quantum query algorithm $𝒜$ to successfully output $z\in 𝖥(f)$ for any input $f\in \mathrm{𝖥𝗎𝗇𝖼}$ with success probability at least $1-ϵ$. By convexity, $Q_{ϵ}(𝖥)$ is lower bounded by the number of queries required for any input distribution $\delta$, since:

However, $Q_{ϵ}(𝖥)$ is not an interesting metric in the case where ${\min }_{f\in \mathrm{𝖥𝗎𝗇𝖼}}\mathrm{Pr}[𝒜\text{ outputs }z\in 𝖥(f)]$ could be $0$, i.e. when there exists an input $f\in \mathrm{𝖥𝗎𝗇𝖼}$ when the algorithm can’t successfully output $z\in 𝖥(f)$ for any input $f\in \mathrm{𝖥𝗎𝗇𝖼}$. This can occur in Theorem 14, as the input distribution $\delta$ is $\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}$. For instance, recall the collision problem. Some inputs $f\in Y^X$ may contain no collisions, making it impossible for the quantum algorithm to output $z\in 𝖥(f)$.

Additionally, even if the worst-case input admits a non-zero probability of success, it can often be more meaningful to show that the problem is hard on average rather than merely demonstrating the existence of an input where the problem is hard. This is particularly relevant in the context of cryptography, where it is more desirable to know that a randomly chosen security key yields a secure construction than to prove that there exists a single specific key ensuring security. Therefore, in the remainder of this work, we focus on deriving a lower bound for the average-case complexity $Q_{ϵ}^{\delta }(𝖥)$ rather than the worst-case complexity $Q_{ϵ}(𝖥)$:

We can now use Theorem 14 to lower bound $Q_{ϵ}^{\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}(𝖥)$:

Corollary 17 is slightly less conveniently phrased compared to Corollary 11 due to its dependence on $t$ in the term

Before we define these MLA matrices in Definition 19, we first provide some motivation behind their definition. In Section 3.3, we saw that the compressed oracle seems to make more explicit use of the number of queries to compute the incremental progress by decomposing the set of all possible databases $𝒟={⨆}_{t=0}^N{𝒟}_t$ based on their sizes and integrating these into the projection ${𝖯}_{{𝒟}_{𝒫}}$. We generalise this notion by introducing the following construction, that captures the subspace of $ℂ[Y^X]$ that is reachable from $|\delta ⟩$ after a fixed number of queries.

First, we define a few components necessary for our construction. Let $\delta$ be an initial distribution on $\mathrm{𝖥𝗎𝗇𝖼}\subseteq Y^X$. For any $t\in [N]$ and any choice of $x_1,\mathrm{\dots },x_t\in X$ and $y_1,\mathrm{\dots },y_t\in Y$, define

where ${\alpha }_{x_1,\mathrm{\dots },x_t}^{y_1,\mathrm{\dots },y_t}$ is the normalisation factor, defined as

Before we prove the lemma, we discuss some of its implications. First of all, we find that ${\mathrm{𝖲𝗉𝖺𝖼𝖾}}_N(\delta )=\mathrm{span}\{|f⟩:f\in \mathrm{supp}(\delta )\}$. Moreover, in the special case where $|\delta ⟩=|\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}⟩$, we have that

which recovers Fact 13.

We can combine $\mathrm{\Gamma }$ with the projection ${\mathrm{\Pi }}_{\le t}$ that projects onto ${\mathrm{𝖲𝗉𝖺𝖼𝖾}}_t(\delta )$, to ensure that the progress keeps track of the number of queries done by the algorithm. The “$\le$” in the subscript of each of the projectors ${\mathrm{\Pi }}_{\le t}$ is there to emphasise that ${\mathrm{\Pi }}_{\le t-1}⪯{\mathrm{\Pi }}_{\le t}$. This is due to the fact that we can let $(x_t,y_t)=(x_{t-1},y_{t-1})$ in $|v_{x_1,\mathrm{\dots },x_t}^{y_1,\mathrm{\dots },y_t}⟩$. For any $T$-quantum algorithm $𝒜$, initial distribution $\delta$, $t\in {[T]}_0$, and multiplicative adversary matrix $\mathrm{\Gamma }$, we have

The structure of the database projections ${𝖯}_{{𝒟}_{\le t}\cap {𝒟}_{𝒫}}$ and ${𝖯}_{{𝒟}_{\le t-1}\setminus {𝒟}_{𝒫}}$ in the compressed oracle technique (see Theorem 14) is, in practice, more convenient to work with than the more abstract projections ${\mathrm{\Lambda }}_i$. This is because these projections are built from the database basis states, which are more intuitive and allow for easy tracking of their sizes with each query (see Fact 13).

We aim to establish a similar structure on the eigenspaces of $\mathrm{\Gamma }$. These eigenspaces should resemble steps on a ladder, where each query moves the state up or down by at most one step. Additionally, these steps should be evenly spaced. To formalise this idea, we impose structural constraints on the spectral decomposition of $\mathrm{\Gamma }$:

Here, $\mathrm{\ell }+1$ denotes the number of distinct eigenvalues of $\mathrm{\Gamma }$, which are sorted in ascending order, and each ${\mathrm{\Lambda }}_i$ is the projector onto the eigenspace associated with the eigenvalue ${\lambda }_i$.

The condition expressed in Equation 13 ensures that each query can move the state up or down by at most a single eigenspace. Meanwhile, the construction $\mathrm{\Gamma }={\sum }_{i=0}^{\mathrm{\ell }}{\kappa }^i{\mathrm{\Lambda }}_i$ ensures that the multiplicative progress between successive eigenspaces is constant, specifically a factor of $\kappa$.

This new definition allows us to prove an MLA-version of Theorem 10. This result is strictly weaker, as it only considers a subset of all possible multiplicative adversary matrices, but it greatly simplifies the upper bound on the progress achievable in a single query (Item 2).