# Permutation Superposition Oracles for Quantum Query Lower Bounds

Christian Majenz111Department of Applied Mathematics and Computer Science,
Technical University of Denmark. _Email:_<EMAIL_ADDRESS>Giulio
Malavolta222Department of Computing Sciences, Bocconi University, Italy.
_Email:_<EMAIL_ADDRESS>333Max Planck Institute for Security
and Privacy, Germany. Michael Walter444Faculty of Computer Science, Ruhr-
Universität Bochum, Germany. _Email:_<EMAIL_ADDRESS>
###### Abstract

We propose a generalization of Zhandry’s compressed oracle method to random
permutations, where an algorithm can query both the permutation and its
inverse. We show how to use the resulting oracle simulation to bound the
success probability of an algorithm for any predicate on input-output pairs, a
key feature of Zhandry’s technique that had hitherto resisted attempts at
generalization to random permutations. One key technical ingredient is to use
_strictly monotone factorizations_ to represent the permutation in the
oracle’s database. As an application of our framework, we show that the one-
round sponge construction is unconditionally preimage resistant in the random
permutation model. This proves a conjecture by Unruh.

###### Contents

  1. 1 Introduction
    1. 1.1 Summary of Contributions
    2. 1.2 Key Challenges and Techniques
    3. 1.3 Concurrent Independent Work
  2. 2 Preliminaries
  3. 3 Random Permutations
    1. 3.1 Random Permutations from Independent Transpositions
    2. 3.2 Active Transpositions
  4. 4 Quantum Random Permutations Oracles
    1. 4.1 Superposition Permutation Oracle
    2. 4.2 Twirled Superposition Permutation Oracle
  5. 5 The Fundamental Lemma of the Permutation Oracle
  6. 6 Bounding the Success Probability for Search
    1. 6.1 Bounding the Success Probability in the Worst Case
    2. 6.2 Bounding the Success Probability in Expectation
    3. 6.3 Sparsity Analysis
    4. 6.4 Main Theorem
  7. 7 Application to One-Round Sponge and Unruh’s Conjecture

##  1 Introduction

The random oracle model [BR93] is a popular heuristic in the analysis of
cryptographic protocols, that abstracts cryptographic objects as random
functions and provides oracle access to other algorithms. From a theoretical
standpoint, the random oracle model allows one to prove unconditional
statements about cryptographic protocols, in a clean and well-defined model.
On the practical side, the random oracle model enables efficient cryptographic
schemes and essentially every construction (be it a digital signature or a
public-key encryption) used in practice relies, in one way or another, on this
heuristic in order to analyze security.555Note however that the ROM (and QROM)
are both fundamentally uninstantiable [CGH04]. When considering security
against quantum algorithms, it is natural to extend this model to allow the
algorithms to query the random function on a superposition of inputs. This is
commonly referred to as the quantum random oracle model (QROM) [BDF+11].
However, many of the techniques (and proofs) developed in the (classical)
random oracle model do not immediately carry over to the QROM. To illustrate
the difference, it suffices to note that in the classical settings the
reduction can read the queries of the algorithm, whereas the same action in
the QROM may arbitrarily disturb the state of the algorithm.

To cope with this, the community has developed a series of new techniques to
analyze quantum algorithm in these settings. An important method in these
settings is the _compressed oracle_ technique [Zha19]. Conceptually, this
technique is the quantum analogue of the classical lazy-sampling method, which
allows the reduction to define the random function only on the inputs queried
by the attacker. At a more technical level, the technique considers a purified
version of the random function, that allows the reduction to directly inspect
the internal state of the compressed oracle simulation (the so-called
_database_), in order to gain partial/approximate knowledge about the queries
made by the algorithm. An extremely useful property in this context is that
the compressed oracle simulation stores (a superposition of) a list of input-
output pairs, so to learn something about the value $H(x)$, and whether $H(x)$
is known to the adversary, it is only necessary to inspect one register. This
technique has proven extremely successful in analyzing indifferentiability of
cryptographic schemes [Zha19], security reductions for the Fiat-Shamir
transformation [LZ19b, DFMS21, DFMS21] and the Fujisaki-Okamoto transformation
[BHH+19, DFMS21, HHM22], and even new lower bounds on the query complexity of
quantum algorithms [Zha19, LZ19a, CFHL21] and space-time trade-offs [HM23].

#### The Random Permutation Model.

In the random permutation model, algorithms are given oracle access to a
uniformly sampled permutation $\pi\in S_{N}$, as well as its inverse
$\pi^{-1}$. This variant of the random oracle model is motivated by
cryptographic schemes, such as the Feistel construction for pseudorandom
permutations [LR88] or the industry-standard SHA-3 hash function [Dwo15],
where an attacker has access to both the permutation and its inverse. When
considering quantum attackers, it is therefore equally natural to assume that
such a permutation can be implemented on a quantum computer (as it is publicly
known), and hence queried in superposition. Accordingly, it is natural to
model this situation by a _quantum-accessible random permutation oracle_ ,
where one considers the unitary666Alternatively, one can consider the _in-
place_ permutation $V^{\pi}$ defined as $V^{\pi}\ket{x}=\ket{\pi(x)}$, which
is well defined since $\pi$ is a bijection, and give the adversary query
access to $V^{\pi}$ and $V^{\pi^{-1}}=(V^{\pi})^{\dagger}$. For the purposes
of query bounds both models are equivalent, since either can be simulated
using two queries to the other. We discuss this in more detail in Section 4.

$\displaystyle U^{\pi}\ket{x}\ket{y}=\ket{x}\ket{y\oplus\pi(x)}$

and one gives the adversary query access to $U^{\pi}$ and $U^{\pi^{-1}}$.
Classically, the random oracle and the random permutation model are
essentially equivalent. This is in stark contrast to the quantum setting where
no such connection is known. So far, it has proven difficult to repeat the
success of Zhandry’s compressed oracle technique for analyzing quantum query
access to a uniformly random permutation: Despite several attempts to come up
with a full-fledged compressed permutation oracle [CMSZ19, Unr21, Cza21] the
problem is still open. On the other hand, few existing results rely on a bare-
bones, “un-compressed” superposition oracle for permutations [ABKM22, ABK+,
ABPS23], whereas recent works [Ros21, Unr23] have made partial progress on
this problem but without being able to apply the formalism towards new query
bounds.

Arguably, the main reason for the lack of progress is, that the compressed
oracle technique relies on the statistical independence of the output values
of a random function, but the output values of a random permutation are, of
course, not independent (more discussion on this later). The purpose of this
work is to make progress on this front, and expand our technical toolkit in
the analysis of random permutation oracles.

###  1.1 Summary of Contributions

In this work we propose a new approach to analyze quantumly-accessible
permutation and prove query lower bounds in this setting. Our main ingredient
is a new analysis of a representation of a permutation, known as its _strictly
monotone factorization_ , which may be of independent interest. At a technical
level, we prove a series of lemmas that facilitate proofs of query lower bound
in the random permutation model. Specifically:

  * •

We present a _permutation_ oracle (Section 4), that is the permutation
analogue of Zhandry’s compressed oracle technique. Our oracle makes crucial
use of a particular representation of a permutation, known as its strictly
monotone factorization (Section 3).

  * •

We prove a _fundamental lemma_ for permutation oracles (Section 5), where we
describe a procedure to (approximately) determine whether an input was queried
by the adversary, and we give a bound on the precision of its output.

  * •

We propose a _progress measure_ for permutation oracles (Section 6), that
bounds the success probability of an algorithm after $q$ queries to find an
input/output pair that satisfies a given relation.

  * •

We prove, as our _main theorem_ , a general bound (Theorem 6.11) for any
adversary to produce an input-output pair satisfying some relation $R$, for
any $R$. This bound states the following:

######  Theorem 1.1 (Informal).

Let $\mathcal{A}$ be an algorithm with quantum query access to a random
permutation $\pi\in S_{N}$ and its inverse $\pi^{-1}$, and let $R$ be a
relation. If $\mathcal{A}$ makes at most $q$ queries and outputs $x$, then

$\Pr[(x,\pi(x))\in R]\leq O\left(\frac{q^{3}r_{\max}\ln(N)}{N}\right),$

where $r_{\max}=\max\left\\{\max_{x}\,\lvert R_{x}\rvert,\max_{y}\,\lvert
R^{\mathrm{inv}}_{y}\rvert\right\\}$, with $R_{x}=\\{y:(x,y)\in R\\}$ and
$R^{\mathrm{inv}}_{y}=\\{x:(x,y)\in R\\}$.

Illustrating the power of the new approach, we obtain as special cases the
pre-image resistance of the sponge construction for the special case of one
absorption round (see Fig. 1), and the double-sided zero-search conjecture
[Unr23]. The former is the problem of finding an $x$ such that
$\pi(x\|0^{c})=y\|0^{c}$ for some $y$; it was the original motivation of our
work. Thus (Section 7):

Figure 1: The 1-round sponge.

######  Corollary 1.2 (One-Round Sponge, informal).

Let $\mathcal{A}$ be an algorithm with quantum query access to a random
permutation $\pi\in S_{\\{0,1\\}^{n}}$ and its inverse $\pi^{-1}$, let
$c\in[n]$, and let $y\in\\{0,1\\}^{n-c}$. If $\mathcal{A}$ makes at most $q$
queries and outputs $x$, then

$\Pr[\exists y^{\prime}\in\\{0,1\\}^{c}:\pi(x\|0^{c})=y\|y^{\prime}]\leq
O\left(\frac{q^{3}n}{2^{\min(c,n-c)}}\right).$

######  Corollary 1.3 (Double-Sided Zero-Search, informal).

Let $\mathcal{A}$ be an algorithm with quantum query access to a random
permutation $\pi\in S_{\\{0,1\\}^{n}}$ and its inverse $\pi^{-1}$ and let
$c\in[n]$. If $\mathcal{A}$ makes at most $q$ queries and outputs $x$, then

$\Pr[\exists y\in\\{0,1\\}^{n-c}:\pi(x\|0^{c})=y\|0^{c}]\leq
O\left(\frac{q^{3}n}{2^{c}}\right).$

###  1.2 Key Challenges and Techniques

To understand the main challenges of extending Zhandry’s method to
permutations, and how we overcome these to prove our results, it is useful to
recall the key properties of the compressed oracle method, and see why they
fail for the case of permutation. The output values of a random function are
independent as random variables. The crucial implication of this fact is that
there exists a list of random variables that are

  1. (i)

independent, and

  2. (ii)

learning one output requires looking at only one of the random variables, and

  3. (iii)

each variable stores only information about one output.

It is easy to find a representation of a random permutation as a list of
random variables that has some of the properties, but it is manifestly
impossible to find one that has all, as the outputs are not independent. For
instance, by knowing that $\pi(x)=y$ we can also infer that
$\pi(x^{\prime})\neq y$, for all $x^{\prime}\neq x$.

One can therefore parameterize the set of approaches by which of the
properties is given up on. In [Unr21], for example, a formalization using lazy
sampling of permutations as partial functions is used, giving up on
independence. In [Ros21], an analysis via the representation theory of the
permutation group is conducted, which yields independent data via the
decomposition into irreducible representation and symmetries, but gives up at
least partially on locality.

#### Random Permutations from Independent Transpositions.

Our main idea is to use the well-known fact that any permutation $\pi\in
S_{N}$ admits a unique decomposition

$\pi=\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(2\;t_{2}\right)\left(1\;t_{1}\right)$
(1.1)

where we denote by $\left(k\;t_{k}\right)$ the transposition that sends $k$ to
$t_{k}$ and viceversa. If one leaves out trivial transpositions (i.e., the
factors with $k=t_{k}$), one obtains a so-called _strictly monotone_
factorization of a permutation. It is well-known that any permutation $\pi\in
S_{N}$ has a unique strictly monotone factorization, with number of terms
equal to the Cayley distance between $\pi$ and the identity permutation, that
is, the minimum number of transpositions (of arbitrary type) in any
factorization of $\pi$.

A useful property of this representation is that the transpositions making up
a uniformly random permutation via the strictly monotone factorization are
independent; $t_{k}$ is uniformly chosen from the set $\\{1,\dots,k\\}$. The
main, less easy-to-see, property of this decomposition that we are going to
use, is the fact that we can “track” the set of transpositions that act non-
trivially on a given input $x$ (which we refer to as being _active_ for $x$).
Crucial to our analysis is the fact that, for any given input $x$, the
expected number of active transpositions is _small_ , i.e., at most about
$\ln(N)$. To compute the random permutation, only a small amount of
information about non-active transpositions is retrieved, namely that they are
not active. On the other hand, the output sensitively depends on the value
$t_{k}$ for an active location $k$, in the sense that changing $t_{k}$ to any
other value changes the output. This gives us a way to quantify the _sparsity_
of the (quantum analogue of the) list of transposition that has been read.
Although this means we only have an approximate _and_ relaxed variant of the
second property above, we will be able to show that this quantity is small
enough to emulate the functionality of the compressed oracle method for the
case of permutations.

#### The Permutation Oracle.

With the above discussion in mind, let us now describe (a simplified version
of) our permutation oracle. The simulation initializes a _database_ of $N$
registers $D=D_{1}\dots D_{N}$ and the $k$-th register $D_{k}$ is initialized
with the state

$\ket{+_{k}}=\frac{1}{\sqrt{k}}\sum_{t=1}^{k}\ket{t}$

which will be interpreted as the uniform superposition over all possible
values $t_{k}$ in Eq. 1.1. Since any given permutation $\pi\in S_{N}$ uniquely
determines a basis state $\ket{\pi}=\ket{t_{1},\dots,t_{N}}$, it is easy to
see that the initial state of the database corresponds to a uniform
superposition over all possible permutations:

$\bigotimes_{k=1}^{N}\ket{+_{k}}_{D_{k}}=\frac{1}{\sqrt{N!}}\sum_{\pi\in
S_{N}}\ket{\pi}_{D}.$

We can then define the forward query oracle ($O^{\mathsf{SPO}}_{XYD}$) and the
inverse query oracle ($O^{\mathsf{SPO},\mathrm{inv}}_{XYD}$) provided to the
adversary by their actions of the basis states $\ket{x}_{X}$, $\ket{y}_{Y}$,
and $\ket{\pi}_{D}$ as:

$\displaystyle O^{\mathsf{SPO}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\pi(x),\pi}_{XYD},$ $\displaystyle
O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\pi^{-1}(x),\pi}_{XYD}.$

In other words, the oracles apply a series of transpositions controlled on the
current state of the database.

#### A Fundamental Lemma for Permutation Oracles.

What makes the Zhandry’s framework so useful is the ability to read off the
database information about the adversary’s state.777Although the analogy with
Zahndry’s technique is helpful for understanding our framework, the direct
comparison is somewhat inaccurate. In particular, contrary to Zhandry’s
method, we will not attempt to _compress_ the database in any way. As a
consequence of this, our simulation will not be computationally efficient,
which is sufficient to prove query lower bounds. We leave the development for
an efficient version of our framework as ground for future work. Thus our next
task is to develop the necessary machinery for doing so. The first step is to
prove a _fundamental lemma_ , a statement akin to the existing bound for
random functions [Zha19, CFHL21]. Fix an input $x$ and an output $y$,
simplifying a bit, the content of the fundamental lemma is the approximate
equivalence of the following two experiments:

  * _Exp. I:_

Read the value $\pi(x)$ off the database state and accept if $\pi(x)=y$,
reject otherwise.

  * _Exp. II:_

Check if the adversary has queried $x$, and reject if this is not the case.
Else proceed as above.

The (approximate) equivalence of these two experiments is useful to implement
a somewhat “gentle” measurement on the database state, for a given input $x$,
since if we detect that the adversary never queried $x$, there is no need to
disturb the state any further.

Of course at this point it is not clear what we exactly mean by “the adversary
has queried $x$”, and so the next step is to make this notion more precise. We
observe that querying the superposition oracle on a basis state $\ket{x}$ must
have a non-trivial effect on database location $D_{x}$ in the computational
basis, since it is determining the value of the first transposition, which is
always active for $x$. Thus, we can formally define this quantity via a
binary-outcome projective measurement

$\mathcal{M}_{D_{x}}:=\left\\{\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}},I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\\}$

and conditioning on the second outcome occurring. As a sanity check, note that
if the first outcome is observed instead, then the database state is in its
initial condition. With some routine calculation, we can then derive a bound

$\left|\Pr[\text{Exp.\leavevmode\nobreak\ I
accepts}]-\Pr[\text{Exp.\leavevmode\nobreak\ II
accepts}]\right|\leq\sqrt{\frac{1}{x}}$

where the term $1/x$ comes from the non-commutativity of the measurement
$\mathcal{M}_{D_{x}}$ and the standard basis measurement used to determine
$\pi$.

Unfortunately this bound on its own is not very meaningful: To see why, simply
take $x=1$ where we obtain a trivial bound. The source of this problem is the
_asymmetric_ treatment of different registers in the representation of the
permutation, where lower registers have a much smaller set of possible
transpositions. To deal with this, we introduce our next idea.

#### Twirling the Oracle.

We overcome the challenge by randomizing the order in which we apply the
strictly monotone decomposition. We address this by pre- and post-composing,
or “twirling”, the permutation oracle with two random permutations $\tau$ and
$\sigma$. In other words, we define the _twirled_ version of the permutation
oracle as

$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\tau^{-1}(\pi(\sigma(x))),\pi}_{XYD}$
$\displaystyle
O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\sigma^{-1}(\pi^{-1}(\tau(x))),\pi}_{XYD}$

for forward and inverse queries, respectively. This yields our final
construction, which we call the _twirled superposition permutation oracle_.
Note that the permutations $\tau$ and $\sigma$ are treated differently than
$\pi$ in the simulation, since we do not require any special property from
their representation and their sole purpose is to randomize the view of the
adversary in the sense that the adversary does not know which inputs
correspond to small values $x$ in the untwirled oracle. Another way to
describe the twirled superposition permutation oracle is that it is
constructed based on the strictly monotone factorization _in a random order_.
This technique renders the permutation actually stored in a quantum register
independent from the view of the algorithm interacting with the twirled
superposition permutation oracle.

Equipped with this oracle, our bound obtained in the analysis of the
fundamental lemma translates into an _expectation_ over the random choice of
the register $x$. Considering the _square_ of the difference between the
success probability of the two experiments, and taking the expectation over
$x$, we obtain the bound

$\frac{1}{N}\sum_{x=1}^{N}\frac{1}{x}\leq\frac{\ln(N)+1}{N}$

using a standard bound on the harmonic sum. Note that the final bound is
independent of $x$.

#### The Progress Measure.

Once we have established a procedure to read information off the database,
what is left to be decided is _what_ we want to read from the database. Due to
the challenge described above, we cannot straightforwardly implement a
predicate that checks whether there exist an input-output pair $(x,\pi(x))$
that was read by the adversary, such that $(x,\pi(x))\in R$, for some relation
$R$. Instead, for a given input $x$, our progress measure is defined in terms
of the following two-step procedure:

  1. (i)

Apply the projective measurement $\mathcal{M}_{x}$ defined above, and reject
unless the second outcome is obtained (intuitively, this rejects unless the
permutation was queried on input $x$ by the adversary).

  2. (ii)

Check if $(x,\pi(x))$ indeed satisfies the relation $R$, which can be
implemented by the following predicate:

$\Pi_{D}^{R,x}:=\sum_{\pi\in S_{N}:(x,\pi(x))\in
R}\lvert\pi\rangle\langle\pi\rvert_{D}.$

This procedure can be summarized by the following measurement operator:

$E^{R,x}_{D}:=\Pi^{R,x}_{D}(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}).$

It is easy to bound the progress measure if the adversary makes no query,
since the above projection is acting on a uniform superposition. The
challenge, which is the technically most involved part of our work, is to
track the bound on the progress measure as the adversary queries the oracles
in the forward and inverse direction. At a very high-level, we achieve this by
splitting the effect of the action of the oracle
$Q^{\mathsf{SPO}}_{XYD}=\\{O^{\mathsf{SPO}}_{XYD},O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\\}$
in two terms

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\ket{\phi}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi}\right\rVert$ $\displaystyle\leq\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}(I-E^{R,x}_{D})\ket{\phi}\right\rVert$
$\displaystyle\leq\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}(I-\Pi_{D}^{R,x})(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert+\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert$

for any state $\ket{\phi}$. We bound the two summands separately.

The RHS summand is bounded with a delicate analysis on the effect of the query
unitary on the joint database-adversary state. We refer the reader to the
technical sections for the calculations and we only mention here that the
bound that one obtains with such analysis will not be sufficient for our main
theorem. Instead, we will once again use the _randomization_ of the register
$x$ and the twirling of the permutation $\pi$ to transform the worst-case
bound in a much sharper _average-case_ bound

$\frac{1}{N}\sum_{x=1}^{N}\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert^{2}\leq
O\left(\frac{q^{2}r_{\max}\ln(N)}{N^{2}}\right)$

where $r_{\max}$ is the maximum number of $y$ such that $(x,y)\in R$, for all
$x$. We can then turn this inequality back to a _worst-case_ bound over $x$
with a pidgeonhole argument, at the cost of losing a factor $N$ in the bound.
Fortunately, the resulting term is still small enough to obtain a good bound.
Next, we deal with the LHS summand of the above bound.

#### Sparsity Analysis.

To bound the LHS of the summand, let us first manipulate the expression

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}(I-\Pi_{D}^{R,x})(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert$
$\displaystyle=\left\lVert
E^{R,x}_{D}(I-\Pi_{D}^{R,x})Q^{\mathsf{SPO}}_{XYD}(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert$
$\displaystyle\leq\left\lVert
E^{R,x}_{D}(I-\Pi_{D}^{R,x})Q^{\mathsf{SPO}}_{XYD}\right\rVert\cdot\left\lVert(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert$
$\displaystyle=\left\lVert
E^{R,x}_{D}(I-\Pi_{D}^{R,x})\right\rVert\cdot\left\lVert(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert$
$\displaystyle\leq\sqrt{\frac{r_{\max}}{x}}\left\lVert(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert$

where the first inequality follows by the submultiplicativity of the operator
norm and the second inequality is obtained by observing that

$\left\lVert
E^{R,x}_{D}(I-\Pi_{D}^{R,x})\right\rVert=\left\lVert\Pi_{D}^{R,x}(I-\left|+_{x}\right\rangle\\!\\!\left\langle+_{x}\right|_{D_{x}})(I-\Pi_{D}^{R,x})\right\rVert=\left\lVert\Pi_{D}^{R,x}\left|+_{x}\right\rangle\\!\\!\left\langle+_{x}\right|_{D_{x}}(I-\Pi_{D}^{R,x})\right\rVert\leq\left\lVert\Pi_{D}^{R,x}\left|+_{x}\right\rangle\\!\\!\left\langle+_{x}\right|_{D_{x}}\right\rVert$

which can be bound to $\sqrt{r_{\max}/x}$ using the same argument as in the
fundamental lemma. Thus, bounding this term boils down to bounding the amount
of locations read by the adversary, i.e., the number of _active_ registers in
the database. Once again, the number of active locations on the initial state
of the database is zero, so bounding this term involves analyzing the effect
of the query unitary $Q_{XYD}$ on the joint database-adversary state. A
delicate analysis leads to a bound of

$\displaystyle\frac{1}{N}\sum_{x=1}^{N}\frac{\lvert
R\rvert}{x}\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\right\rVert^{2}\leq
O\left(\frac{q^{3}r_{\max}\ln(N)}{N^{2}}\right)$

in expectation over $x$, which we can once again turn into a worst-case bound
on every $x$ at the cost of an extra $1/N$ factor. We refer the reader to the
technical sections for more details.

#### Putting Things Together.

Overall, the above analysis allow us to bound, via our _progress measure_ ,
how the success probability of the predicate $E^{R,x}$ evolves as the
adversary performs more queries. The final but crucial observation is that if
$x$ is the output of the algorithm $\mathcal{A}$, the measurement $E^{R,x}$
accepts precisely if Exp. II accepts. Applying the fundamental lemma to this
bound, we obtain a bound on the acceptance probability of Exp. I (as defined
above), which is the quantity that we are interested in.

This outline ignores many subtle aspects of the proof, but it contains the
main ideas. Putting the bounds on the two main terms together, we obtain
Theorem 1.1 and hence Corollaries 1.2 and 1.3.

###  1.3 Concurrent Independent Work

A recent manuscript by Carolan and Poremba [CP24], developed concurrently and
independently from our work, also shows a proof for the double-sided zero-
search conjecture of Unruh and the one-wayness of the one-round sponge. The
techniques used to prove the bound are quite different and their work achieves
the result using a worst-case to average-case reduction for random
permutation, then appealing to known bounds. The advantage of their approach
is that the bound obtained is _tight_. In contrast, our paper proposes a new
framework to analyze permutation oracles and a theorem that applies to
arbitrary relations on (single) input-output pairs, promising opportunities
for generalization.

##  2 Preliminaries

We abbreviate $[N]:=\\{1,2,\dots,N\\}$. For convenience, we assume that
$N=2^{n}$, so we can identify $[N]\cong\\{0,1\\}^{n}$ and use $\oplus$ to mean
bitwise addition. For a set $S$, a probability distribution $\mu$ and a
(classical or quantum) algorithm $\mathcal{A}$, we write $x\leftarrow S$,
$x\leftarrow D$, and $x\leftarrow\mathcal{A}$ for sampling a uniformly random
element $x$ from $S$, sampling $x$ according to the distribution $D$, or
running an algorithm $\mathcal{A}$ to produce an output $x$. If the output is
quantum, we usually use upper-case letters, following our conventions for
quantum registers discussed below.

#### Combinatorics.

We will also use the fact that for the _harmonic numbers_

$\displaystyle H_{N}:=\sum_{k=1}^{N}\frac{1}{k},$ (2.1)

the quantity $H_{N}-\ln N$ is monotonically decreasing with $N$. In
particular, it holds that

$\displaystyle H_{N}\leq\ln(N)+1$ (2.2)

for every $N\geq 1$.

#### Quantum Information.

Here we provide some preliminary background on quantum mechanics and quantum
information. For more in-depth accounts we refer the reader to [NC00, Wat18].

We will label quantum systems by $A,B,X,Y,$ etc. Any quantum system $A$ is
characterized by a Hilbert space $\mathcal{H}_{A}$. When
$\mathcal{H}_{A}=\mathbbm{C}^{\Sigma_{A}}$ for some finite set $\Sigma_{A}$,
we call $A$ a _quantum register_. This means that $\mathcal{H}_{A}$ has an
orthonormal _standard basis_ $\ket{a}$ labeled by the elements
$a\in\Sigma_{A}$. When $\Sigma=[N]$, we can identify
$\mathcal{H}=\mathbbm{C}^{N}$ with its standard basis $\ket{a}$ for
$a\in\mathbbm{Z}_{N}$. If we have quantum system composed of two registers,
say $A$ and $B$, then the corresponding Hilbert space is the tensor product of
the individual Hilbert spaces
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}\cong\mathbbm{C}^{\Sigma_{AB}}$,
with $\Sigma_{AB}=\Sigma_{A}\times\Sigma_{B}$ labeling the standard product
basis. Accordingly, we may think of the composite system $AB=(A,B)$ as a
register, and similarly for any collection $S$ of registers.

States of a quantum system are given by _density operators_ , that is,
positive semi-definite operators of trace one. We call a state _pure_ if this
operator is a rank-one orthogonal projector, i.e., equal to
$\lvert\phi\rangle\langle\phi\rvert$, where $\ket{\phi}$ is a unit vector. We
will often identify pure states with unit vectors. The _trace distance_
between two states $\rho$ and $\tau$, denoted by $\mathsf{Td}(\rho,\tau)$ is
defined as

$\mathsf{Td}(\rho,\tau)=\frac{1}{2}\left\lVert\rho-\tau\right\rVert_{1}=\frac{1}{2}\operatorname{tr}\left(\sqrt{(\rho-\tau)^{\dagger}(\rho-\tau)}\right).$

The operational meaning of the trace distance is that
$\frac{1}{2}(1+\mathsf{Td}(\rho,\tau))$ is the maximal probability that two
states $\rho$ and $\tau$ can be distinguished by any (possibly unbounded)
quantum channel, when given one or the other with equal probability.

There are two basic kinds of quantum operations. The first is to apply unitary
operators, or _unitaries_. If $U$ is a unitary on $\mathcal{H}$ and we apply
it to a state $\rho$, the result is $U\rho U^{\dagger}$, which is again a
state. We denote by $\mathcal{U}(\mathcal{H})$ the group of unitary operators
on $\mathcal{H}$, and abbreviate
$\mathcal{U}(N)=\mathcal{U}(\mathbbm{C}^{N})$. The second is to measure the
quantum state. We will only require _projective measurements_ , which are
given by a family of orthogonal projections
$\\{P_{\omega}\\}_{\omega\in\Omega}$, labeled by some finite index set
$\Omega$, such that $\sum_{\omega\in\Omega}P_{\omega}=I$. If one applies such
a measurement to a system in state $\rho$, then the probability of seeing
outcome $\omega\in\Omega$ is $p_{\omega}=\operatorname{tr}(P_{\omega}\rho)$,
in which case the state changes to $P_{\omega}\rho P_{\omega}/p_{\omega}$. If
$\\{P_{a}\\}=\\{\lvert a\rangle\langle a\rvert\\}$ consists of the projections
onto the standard basis of some register, this is called a _standard basis
measurement_.

We will use subscripts to denote the corresponding quantum system or tensor
factors, e.g., $\rho_{AB}$ denotes a density operator on
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, and
$\rho_{AB}=\lvert\Psi\rangle\langle\Psi\rvert_{AB}$ in the case of a pure
state, with $\ket{\Psi}_{AB}\in\mathcal{H}_{AB}$. Similarly, we write $U_{A}$
in the case of a unitary on $\mathcal{H}_{A}$. In particular, $I_{A}$ denotes
the identity operator on $\mathcal{H}_{A}$.

For unitaries and measurement operators (but never for states), it will be
useful to identify operators on some Hilbert space with operators on some any
other Hilbert space which includes the former as a tensor factor, by tensoring
with the identity operator. For example, we will often abbreviate the operator
$U_{A}\otimes I_{B}$ on $\mathcal{H}_{AB}$ simply by $U_{A}$ if no confusion
can arise. This is useful if we want to quantum operations to a subset of
registers. For example, if $U_{A}$ is a unitary and $\rho_{AB}$ a state, then
$U_{A}\rho_{AB}U_{A}^{\dagger}=(U_{A}\otimes
I_{B})\rho_{AB}(U_{A}^{\dagger}\otimes I_{B})$ is the result of applying the
unitary $U_{A}$ to the first register $A$ when the overall system starts out
in state $\rho_{AB}$, and similarly for measurements.

We also recall the gentle measurement lemma [Wil19, Lemma 9.4.2].

######  Fact 2.1 (Gentle measurement).

Let $\rho$ be a quantum state, and let $\\{P,I-P\\}$ be any projective
measurement with two outcomes. If $\operatorname{tr}(P\rho)\geq 1-\delta$, the
post-measurement state $\rho^{\prime}:=P\rho P/\operatorname{tr}(P\rho)$
satisfies

$\mathsf{Td}(\rho,\rho^{\prime})\leq\sqrt{\delta}.$

#### Quantum Algorithms.

In this work we consider the query complexity of algorithms with quantum
access to oracles. An oracle is modeled by one or more unitaries $O$ operating
on an input/output register $Z$ and possibly some internal register $D$ (which
will always be initialized explicitly). A quantum algorithm $\mathcal{A}$
making queries to this oracle has, without loss of generality, two registers –
the oracle’s input/output register $Z$ and an internal work register $A$. It
takes the following form: First, the algorithm’s registers are initialized in
the initial state $\ket{0}_{AZ}$. Then the algorithm alternatingly applies
oracle-independent unitaries and query unitaries:

$\displaystyle U^{(q)}_{AZ}O_{ZD}U^{(q-1)}_{AZ}O_{ZD}\ldots
U^{(1)}_{AZ}O_{ZD}U^{(0)}_{AZ}$ (2.3)

Note that $\mathcal{A}$ can be given access to any oracle with input/output
register $Z$. Finally, some (sub)registers might be measured or returned
directly to obtain the classical and quantum outcomes of the algorithm. We
write $\mathcal{A}^{O}$ for such an application of a query algorithm to an
oracle $O$. In the above situation, we say that the algorithm makes $q$
queries to the oracle. Thus we only consider the query complexity of an
algorithm, but not the time complexity of the unitaries $U^{(k)}$. In other
words, these unitaries need not be efficient. In particular, any advice state
can be placed in the adversary’s quantum memory by using the first unitary
$U^{(0)}$.

##  3 Random Permutations

We denote by $S_{N}$ the permutation group on $N$ elements, that is, the group
of bijections of $[N]$. We have a chain of subgroups $S_{1}\subset
S_{2}\subset\dots\subset S_{N}$, where for each $j\in[N\\!-\\!1]$ we think of
$S_{j}$ as those permutations in $S_{j+1}$ that fix the element $j+1$. For
$k,l\in[N]$, we denote by $\tau=\left(k\;l\right)$ the _transposition_ that
sends $\tau(k)=l$ and $\tau(l)=k$. It will be convenient to allow $k=l$, in
which case $\left(k\;l\right)=\left(k\;k\right)$ is the identity permutation.

###  3.1 Random Permutations from Independent Transpositions

The starting point for our work is the following representation of
permutations.

######  Lemma 3.1.

For any $\pi\in S_{N}$, there exist unique numbers $t_{k}\in[k]$ for $k\in[N]$
such that

$\displaystyle\pi=\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(2\;t_{2}\right)\left(1\;t_{1}\right).$
(3.1)

While we always have $t_{1}=1$, it is useful to include this term to obtain
simpler formulas below.

###### Proof.

Any permutation $\pi\in S_{N}$ has a unique decomposition of the form

$\displaystyle\pi=\left(N\;t\right)\sigma,$ (3.2)

where $t\in[N]$ and $\sigma\in S_{N-1}$. Indeed, for (3.2) to hold we must
have $t=\pi(N)$ and hence $\sigma=\left(N\;t\right)\pi$, but these formulas
always define a valid decomposition of the form of Eq. 3.2. The lemma follows
by induction. ∎

If one leaves out trivial transpositions in Eq. 3.1 (i.e., the factors with
$k=t_{k}$), one obtains a so-called _strictly monotone_ factorization. It is
well-known that any permutation $\pi\in S_{N}$ has a unique strictly monotone
factorization, with number of terms equal to the Cayley distance between $\pi$
to the identity permutation, that is, the minimum number of transpositions (of
arbitrary type) in any factorization of $\pi$.

######  Corollary 3.2.

A random permutation $\pi\in S_{N}$ is uniformly random if and only if the
numbers $t_{k}\in[k]$ for $k\in[N]$ in Eq. 3.1 are independent and uniformly
random.

Given a permutation in the form of Eq. 3.1, it is easy to compute the inverse:

$\displaystyle\pi^{-1}=\left(1\;t_{1}\right)\left(2\;t_{2}\right)\cdots\left(N\\!-\\!1\;t_{N-1}\right)\left(N\;t_{N}\right).$
(3.3)

Note however that this decomposition is in general _not_ of the form of Eq.
3.1. It will also be convenient to introduce the following notation:

$\displaystyle\pi_{>k}$
$\displaystyle=\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(k+1\;t_{k+1}\right),$
(3.4) $\displaystyle\pi_{<k}$
$\displaystyle=\left(k-1\;t_{k-1}\right)\cdots\left(2\;t_{2}\right)\left(1\;t_{1}\right).$

Note that $\pi=\pi_{>k}\left(k\;t_{k}\right)\pi_{<k}$ and
$\pi^{-1}=(\pi_{<k})^{-1}\left(k\;t_{k}\right)(\pi_{>k})^{-1}$. We use the
convention that the subset-of-transpositions subscripts take precedence before
other operations modifying a permutation, e.g.
$\pi_{<k}^{-1}\coloneqq\left(\pi_{<k}\right)^{-1}$.

The following lemma will be useful in Section 6.2.

######  Lemma 3.3.

Let $\pi\in S_{N}$ be uniformly random and $k\in[N]$.

  1. (i)

If $\xi\in S_{k}$ is uniformly random and independent from $\pi$, then
$\pi_{>k}\xi$ is uniformly random in $S_{N}$.

  2. (ii)

If $\xi\in S_{k}$ is uniformly random and independent from $\pi$, then
$\xi\pi_{>k}$ is uniformly random in $S_{N}$.

  3. (iii)

For every $\ell\in\\{k+1,\dots,N\\}$, it holds that
$\Pr\left(\pi_{>k}(k)=\ell\right)=\frac{1}{N}$.

###### Proof.

  1. (i)

This is clear from Corollary 3.2.

  2. (ii)

Using the notation of Eq. 3.4, we have

$\displaystyle\xi\pi_{>k}$
$\displaystyle=\xi\left(N\;t_{N}\right)\xi^{-1}\xi\left(N\\!-\\!1\;t_{N-1}\right)\xi^{-1}\cdots\xi\left(k+1\;t_{k+1}\right)\xi^{-1}\xi$
$\displaystyle=\left(N\;\xi(t_{N})\right)\left(N\\!-\\!1\;\xi(t_{N-1})\right)\cdots\left(k+1\;\xi(t_{k+1})\right)\xi,$

where we used that $\xi\in S_{k}$ and hence it fixes $k+1,\dots,N$, Now, the
$t_{\ell}\in[\ell]$ for $\ell>k$ are uniformly random and independent from
$\xi$, so the same is true for the $\xi(t_{\ell})\in[\ell]$ for $\ell>k$. Thus
we see that the distribution of $\xi\pi_{>k}$ is the same as the distribution
of $\pi_{>k}\xi$, and the claim follows from part (i).

  3. (iii)

This follows from the preceding:

$\displaystyle\Pr\left(\pi_{>k}(k)=\ell\right)=\Pr\left((\xi\pi_{>k})(k)=\ell\right)=\frac{1}{N}.$

with $\xi$ as in part (ii).

∎

###  3.2 Active Transpositions

In the following we characterize the transpositions that, in the above
decomposition of a permutation, are relevant to determine the action of the
permutation on a given element. The results of this section will not be needed
to prove our main theorem, but we include them here for the purpose of
building up an intuition.

Given a permutation $\pi\in S_{N}$, consider its unique decomposition as in
Lemma 3.1:

$\displaystyle\pi=\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(2\;t_{2}\right)\left(1\;t_{1}\right),$

When does a given transposition $\left(k\;t_{k}\right)$ impact the computation
of $\pi(x)$ for some given $x\in[N]$? To study this we introduce the following
definitions:

######  Definition 3.4 (Active sets).

Given a permutation $\pi\in S_{N}$ and $x,k\in[N]$, we say $k$ is _active for
$\pi$ and $x$_ if $\pi_{<k}(x)\in\\{k,t_{k}\\}$. Similarly, for $y\in[N]$ we
say that $k$ is _inverse-active for $\pi$ and $y$_ if
$(\pi_{>k})^{-1}(y)\in\\{k,t_{k}\\}$.888Note that this is in general _not_
equivalent to saying that $k$ is active for $\pi^{-1}$ and $y$, as the latter
would refer to the decomposition of $\pi^{-1}$ in the form of Eq. 3.1, rather
than to Eq. 3.3. We denote by $A(\pi,x),A^{\mathrm{inv}}(\pi,y)\subseteq[N]$
the set of active and inverse-active $k$, respectively, defined as above.

If $k$ is active for $\pi$ and $x$ then changing $t_{k}$ to any other value
will lead to a different $\pi(x)$. Similarly, if $k$ is inverse-active for
$\pi$ and $y$ then changing $t_{k}$ (in the decomposition of $\pi$) to any
other value will lead to a different $\pi^{-1}(y)$. (The converses of these
statements are in general not true.) Note that $\pi_{<k}(x)=k$ if and only if
$x=k$, since $\pi_{<k}\in S_{k-1}$.

It is clear that the action of a permutation or its inverse on some element
only depends on the corresponding active set:

######  Lemma 3.5.

Let $\pi\in S_{N}$ be a permutation. For any $x\in[N]$, let
$A(\pi,x)=\\{k_{1}<\cdots<k_{\ell}\\}$ denote the active locations, sorted in
increasing order. Then we have:

$\displaystyle\pi(x)=\left(k_{\ell}\;t_{k_{\ell}}\right)\left(k_{\ell-1}\;t_{k_{\ell-1}}\right)\cdots\left(k_{2}\;t_{k_{2}}\right)\left(k_{1}\;t_{k_{1}}\right)(x).$

Similarly, if $y\in[N]$ and
$A^{\mathrm{inv}}(\pi,y)=\\{k_{1}<\cdots<k_{\ell}\\}$ are the corresponding
inverse-active locations, then:

$\displaystyle\pi^{-1}(y)=\left(k_{1}\;t_{k_{1}}\right)\left(k_{2}\;t_{k_{2}}\right)\cdots\left(k_{\ell-1}\;t_{k_{\ell-1}}\right)\left(k_{\ell}\;t_{k_{\ell}}\right)(y).$

We now show that the event that $k$ is active for a random permutation (and
fixed $x$) is independent of the numbers $t_{1},\dots,t_{k-1}$, and compute
the probability with which this happens:

######  Lemma 3.6.

Let $x\in[N]$. Then, for a uniformly random $\pi\in S_{N}$, we have:

$\displaystyle\Pr\left(k\in A(\pi,x)\mid
t_{1},\dots,t_{k-1}\right)=\begin{cases}\frac{1}{k}&\text{ if $x<k$,}\\\
1&\text{ if $x=k$,}\\\ 0&\text{ if $x>k$,}\end{cases}$

hence this is also equal to $\Pr(k\in A(\pi,x))$. In particular, the events
$k\in A(\pi,x)$ for $k\in[N]$ are independent.

###### Proof.

Recall that $k\in A(\pi,x)$ means that $\pi_{<k}(x)\in\\{k,t_{k}\\}$. For
$x<k$, we have $\pi_{<k}(x)\in[k-1]$, hence the event
$\pi_{<k}(x)\in\\{k,t_{k}\\}$ is equivalent to $\pi_{<k}(x)=t_{k}$. For a
uniformly random $\pi$, the numbers $t_{1},t_{2},\dots,t_{k}$ are independent
and uniformly random (by Corollary 3.2). Hence $t_{k}\in[k]$ is uniformly
random given $t_{1},\dots,t_{k-1}$. As $\pi_{<k}(x)\in[k-1]$ only depends on
the latter, it follows that it coincides with $t_{k}$ with probability
$\frac{1}{k}$. For $x\geq k$ we have $\pi_{<k}(x)=x$, hence the event
$\pi_{<k}(x)\in\\{k,t_{k}\\}$ is equivalent to $x=k$. ∎

Next we are going to bound the expected number of active locations for a
random choice of the permutation.

######  Lemma 3.7.

Let $x\in[N]$. Then, for a uniformly random $\pi\in S_{N}$, we have:
$\mathop{\bf E\/}\lvert A(\pi,x)\rvert\leq 1+\ln(N/x)$.

###### Proof.

Recall that we denote by $H_{n}=\sum_{k=1}^{n}\frac{1}{k}$ the harmonic
numbers. Then, using Lemma 3.6, we have

$\displaystyle\mathop{\bf E\/}\lvert A(\pi,x)\rvert$
$\displaystyle=1+\sum_{k=x+1}^{N}\frac{1}{k}=1+H_{N}-H_{x}\leq 1+\ln N-\ln x.$

where the inequality holds as $H_{n}-\ln n$ is monotonically decreasing with
$n$. This completes the proof. ∎

We also provide a bound on the expected number of inverse-active locations.
Since this is not the same as the expected number of active locations for the
inverse, the bound differs from Lemma 3.7.

######  Lemma 3.8.

Let $y\in[N]$. Then, for a uniformly random $\pi\in S_{N}$, we have:
$\mathop{\bf E\/}\lvert A^{\mathrm{inv}}(\pi,y)\rvert\leq 1+\frac{2y-2}{N}<3$.

###### Proof.

Suppose first that there is some $k\in[N]$ such that $t_{k}=y$. Let
$k^{*}\in[N]$ denote the largest such $k$. Since $t_{k^{*}}\in[k^{*}]$, we
clearly must have $k^{*}\geq y$. Then we have
$(\pi_{>k})^{-1}(y)=y\notin\\{k,t_{k}\\}$ for all $k>k^{*}$,
$(\pi_{>k^{*}})^{-1}(y)=y=t_{k^{*}}$, and
$(\pi_{>k})^{-1}(y)=k^{*}\notin\\{k,t_{k}\\}$ for all $k<k^{*}$. Together, we
see that $A^{\mathrm{inv}}(\pi,y)=\\{k^{*}\\}$. On the other hand, if
$t_{k}\neq y$ for all $k\in[N]$ then $(\pi_{>k})^{-1}(y)=y$ for all $k\geq y$
and hence $A^{\mathrm{inv}}(\pi,y)=\\{y\\}\cup
A^{\mathrm{inv}}(\pi_{<y},t_{y})$. Combining the above observations, we find
that

$\displaystyle\mathop{\bf E\/}\lvert A^{\mathrm{inv}}(\pi,y)\rvert$
$\displaystyle=1+\Pr(t_{y}\neq y,\dots,t_{N}\neq y)\,\mathop{\bf
E\/}\left[A^{\mathrm{inv}}(\pi_{<y},t_{y})\mid t_{y}\neq y,\dots,t_{N}\neq
y\right]$ $\displaystyle=1+\frac{y-1}{N}\mathop{\bf
E\/}\left[A^{\mathrm{inv}}(\pi_{<y},t_{y})\mid t_{y}\neq y\right]$
$\displaystyle=1+\frac{1}{N}\sum_{z=1}^{y-1}\mathop{\bf
E\/}\left[A^{\mathrm{inv}}(\pi_{<y},z)\right],$

where we first used that $\pi_{<y}$ is independent from $t_{y},\dots,t_{N}$,
and the last step holds because $t_{y}$ is uniformly random in $[y-1]$
conditional on $t_{y}\neq y$. Since $\pi_{<y}$ is uniformly random in
$S_{y-1}$, we obtain the following recurrence for $e(N,y):=\mathop{\bf
E\/}_{\pi\leftarrow S_{N}}\lvert A^{\mathrm{inv}}(\pi,y)\rvert$:

$\displaystyle
e(N,y)=1+\frac{1}{N}\sum_{z=1}^{y-1}e(y-1,z)=1+\frac{1}{N}f(y-1),$ (3.5)

where we introduced the notation $f(n):=\sum_{y=1}^{n}e(n,y)$, with $f(0)=0$,
which in turn satisfies the recurrence

$\displaystyle f(n)=\sum_{y=1}^{n}\left\lparen
1+\frac{1}{n}f(y-1)\right\rparen=n+\frac{1}{n}\sum_{k=0}^{n-1}f(k)$

for all $n>0$. It is easy to see that $f(n)\leq 2n$ for all $n\geq 0$ by using
induction. Indeed, this is clearly true for $n=0$, and if it holds that
$f(k)\leq 2k$ for all $k<n$ then also $f(n)\leq
n+\frac{1}{n}\sum_{k=0}^{n-1}2k=n+n-1\leq 2n$. Using this estimate in Eq. 3.5
we obtain the desired result:

$\mathop{\bf E\/}\lvert
A^{\mathrm{inv}}(\pi,y)\rvert=e(N,y)=1+\frac{1}{N}f(y-1)\leq
1+\frac{2y-2}{N}.\qed$

##  4 Quantum Random Permutations Oracles

The decomposition of a random permutation introduced in Section 3.1 provides a
way of sampling a random permutation by sampling many _independent and
smaller_ random data, namely the individual transpositions that make up the
permutation (Corollary 3.2). Importantly, typical input-output pairs of the
random permutation only depend on a few of them (Lemmas 3.7 and 3.8). In this
section we will use this idea to construct an oracle that exactly simulate a
quantum-accessible random permutation, but has an internal state that can be
used to analyze quantum query algorithms. We first introduce some notation.
Given any permutation $\pi\in S_{N}$, we denote by $U^{\pi}$ the corresponding
permutation operator on $\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$, that is,

$\displaystyle U^{\pi}\ket{x,y}=\ket{x,y\oplus\pi(x)}\qquad\forall x,y\in[N].$

This defines a unitary representation of $S_{N}$ on
$\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$.

######  Definition 4.1 (Quantum-accessible random permutation).

A _quantum-accessible random permutation_ consists of query access to
$U^{\pi}$ and to $U^{\pi^{-1}}$, for a permutation $\pi\in S_{N}$ chosen
uniformly at random.

When $\mathcal{A}$ is a query algorithm that gets query access to two oracles
that act on $\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$ and $\pi\in S_{N}$ is a
permutation, we write $\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}$ to indicate that we
use the unitaries $U^{\pi}$ and $U^{\pi^{-1}}$ as the two oracles.

Above we defined $U^{\pi}$ by the usual formula for a quantum oracle
corresponding to a Boolean function, but because $\pi$ is a bijection we could
also instead work with oracles that modify their input in-place, that is,

$\displaystyle V^{\pi}\ket{x}=\ket{\pi(x)}\qquad\forall x\in[N].$

However, to prove a query lower bound we will be able to consider either type
of oracles. This is because the standard and the in-place variants can
simulate each other at the cost of doubling the number of queries, if one is
given access to the permutation as well as its inverse: it holds that

$\displaystyle U^{\pi}_{XY}$
$\displaystyle=V^{\pi^{-1}}_{X}\operatorname{CNOT}_{X\to Y}V^{\pi}_{X},$
$\displaystyle U^{\pi^{-1}}_{XY}$
$\displaystyle=V^{\pi}_{X}\operatorname{CNOT}_{X\to Y}V^{\pi^{-1}}_{X},$

as well as

$\displaystyle V^{\pi}_{X}\ket{0}_{Y}$
$\displaystyle=U^{\pi^{-1}}_{XY}\operatorname{SWAP}_{X\leftrightarrow
Y}U^{\pi}_{XY}\ket{0}_{Y},$ $\displaystyle V^{\pi^{-1}}_{X}\ket{0}_{Y}$
$\displaystyle=U^{\pi}_{XY}\operatorname{SWAP}_{X\leftrightarrow
Y}U^{\pi^{-1}}_{XY}\ket{0}_{Y}.$

###  4.1 Superposition Permutation Oracle

We first construct a _superposition oracle_ for random permutations. Like
those for random functions, it is obtained by replacing the random (classical)
choice of permutation by a uniform (quantum) superposition. Our oracle is
specified by an internal quantum state space, an initial state, query
unitaries (one for the random permutation and one for its inverse), and a
recovery routine. The query unitaries will be constructed by applying the
transpositions $\left(k\;t_{k}\right)$ in the right order, with each $t_{j}$
obtained from the internal state of the oracle. Generalizing the approach of
[CFHL21], we propose the following definition.

######  Definition 4.2 (Superposition permutation oracle).

The _superposition permutation oracle_ ($\mathsf{SPO}$) is defined as follows:

  * •

The state space, called the _database_ , consists of $N$ registers,
$D=D_{1}\cdots D_{N}$ with the $k$-th register $D_{k}$ having dimension $k$
and computational basis $\ket{1},\dots,\ket{k}$. Any permutation $\pi\in
S_{N}$, determines a basis state $\ket{\pi}_{D}=\ket{t_{1},\dots,t_{N}}_{D}$,
where the numbers $t_{k}\in[k]$ are chosen as in Eq. 3.1.

  * •

The initialization routine $\mathsf{Init}^{\mathsf{SPO}}_{D}$ initializes each
register in a uniform superposition over the basis states. That is, the
initial state of the database is

$\displaystyle\ket{\Phi_{\mathsf{SPO}}}_{D}=\frac{1}{\sqrt{N!}}\sum_{\pi\in
S_{N}}\ket{\pi}_{D}=\bigotimes_{k=1}^{N}\ket{+_{k}}_{D_{k}},\text{ where
}\ket{+_{k}}_{D_{k}}=\frac{1}{\sqrt{k}}\sum_{t=1}^{k}\ket{t}_{D_{k}}.$

  * •

There are two query unitaries, $O^{\mathsf{SPO}}_{XYD}$ and
$O^{\mathsf{SPO},\mathrm{inv}}_{XYD}$, that define the two interfaces
available to the query algorithm and that simulate oracles for a random
permutation and its inverse. They are defined as follows: For all $x,y\in[N]$
and $\pi\in S_{N}$,

$\displaystyle O^{\mathsf{SPO}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\pi(x),\pi}_{XYD},$ $\displaystyle
O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\pi^{-1}(x),\pi}_{XYD}.$

  * •

The recovery routine $\mathsf{Rec}^{\mathsf{SPO}}_{D}$ simplify measures all
registers $D_{1},\dots,D_{N}$ in the computational basis to obtain
$t_{k}\in[k]$ for $k\in[N]$. It outputs the corresponding permutation
according to Eq. 3.1.

When $\mathcal{A}$ is a query algorithm that gets query access to two oracles
acting on two $N$-dimensional register $X$ and $Y$, and if $D$ is the database
register of a superposition permutation oracle, we write
$\mathcal{A}^{\mathsf{SPO}_{D}}$ to indicate that we use the interfaces
$O^{\mathsf{SPO}}_{XYD}$ and $O^{\mathsf{SPO},\mathrm{inv}}_{XYD}$,
respectively, to implement the two types of oracles queries. It is
straightforward to verify that the $\mathsf{SPO}$ then exactly simulates a
quantum-accessible random permutation.

######  Lemma 4.3.

Let $\mathcal{A}$ be a query algorithm that gets query access to two oracles
that act on $\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$. Then the joint state of
the classical random variable $\pi$ and the quantum register $B$ is the same
for the following two experiments:

  1. (i)

Sample $\pi\leftarrow S_{N}$ uniformly at random and run
$B\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}$.

  2. (ii)

Run $\mathsf{Init}^{\mathsf{SPO}}_{D}$, then
$B\leftarrow\mathcal{A}^{\mathsf{SPO}_{D}}$, and finally
$\pi\leftarrow\mathsf{Rec}^{\mathsf{SPO}}_{D}$.

###### Proof.

We show that both experiments give rise to the same joint state as the
following:

  1. (iii)

Run $\mathsf{Init}^{\mathsf{SPO}}_{D}$, then
$\pi\leftarrow\mathsf{Rec}^{\mathsf{SPO}}_{D}$, and finally
$B\leftarrow\mathcal{A}^{\mathsf{SPO}_{D}}$.

Indeed, (i) and (iii) are equivalent by Corollary 3.2 and the fact that
measuring a uniform superposition yields a uniformly random sample, while
(iii) and (ii) are equivalent because measuring in the computational basis
commutes with unitaries that are controlled on this basis. ∎

A consequence of LABEL:{lem:towerdecomposition} is that $\pi(x)=\pi_{\geq
x}(x)$, so in particular $\pi(x)$ does not depend on $t_{x^{\prime}}$ for
$x^{\prime}<x$. For the $\mathsf{SPO}$, this means that when a query is made
with input $x$, the registers $D_{x^{\prime}}$ for $x^{\prime}<x$ are not
used, i.e., the query operator acts as the identity on them.

######  Lemma 4.4.

The $\mathsf{SPO}$ query operator fulfils the equation

$\displaystyle O^{\mathsf{SPO}}_{XYD}\ket{x}_{X}\ket{y}_{Y}\ket{\pi_{\geq
x}}_{D_{\geq x}}=\ket{x}_{X}\ket{y\oplus\pi_{\geq}(x)}_{Y}\ket{\pi_{\geq
x}}_{D_{\geq x}}\otimes I_{D_{<x}}.$

###### Proof.

This follows directly from 4.2 and LABEL:{lem:towerdecomposition}. ∎

###  4.2 Twirled Superposition Permutation Oracle

Just like is the case for Zhandry’s compressed oracle for random functions, we
would like to be able to inspect the internal state of the oracle (that is,
the database) to gain partial, approximate knowledge about the queries made by
the algorithm. However, there are two important caveats in the permutation
case.

First, Zhandry’s compressed oracle satisfies the extremely useful property
that the compressed oracle stores (superpositions of) input-output pairs. This
means that in order to learn something about the value $H(x)$ of the random
function $H$ at some point $x\in[N]$, and whether this value is known to the
adversary, it is only necessary to measure one register. In contrast, we
represent permutations as a product of transpositions and hence the database
of our permutation oracle stores the analogous information in a less localized
fashion. If we want to determine the value $\pi(x)$ of the random permutation
$\pi$ at some point $x\in[N]$, in general we may need to inspect all registers
$D_{k}$ for $k\geq x$. On the other hand, recall that for any fixed $x$,
typically only $\tilde{O}(1)$ permutations are active and suffice to determine
$\pi(x)$ (see Lemmas 3.5, 3.7 and 3.8).

Second, Zhandry’s compressed oracle has the desirable feature that one can
“jointly measure” whether a query algorithm has accessed a register _and_ what
function value it holds, with only a small error. In our permutation oracle
the analogous procedure is to apply the binary measurement
$\mathcal{M}_{k}:=\\{I-\lvert+_{k}\rangle\langle+_{k}\rvert_{D_{k}},\lvert+_{k}\rangle\langle+_{k}\rvert_{D_{k}}\\}$
to learn whether the $k$-th transposition has been accessed and, if so,
measure in the computational basis to learn what its value is. However, since
the size of the support of the uniform superposition $\ket{+_{k}}_{D_{k}}$
depends on $k$, the error in this “joint measurement” depends on $k$. For
example, suppose an algorithm managed through some combination of queries and
measurements to learn $t_{k}$ with certainty for some particular $k\in[N]$.
Then, conditional on this event, the database register $D_{k}$ is in state
$\ket{t_{k}}$. Applying the measurement $\mathcal{M}_{k}$ in this state will,
however, return outcome $\ket{+_{k}}_{D_{k}}$ with probability
$\lvert\braket{+_{k}}{t_{k}}\rvert^{2}=\frac{1}{k}$, which need not be small!

Both challenges can be addressed by pre- and post-composing, or “twirling”,
the $\mathsf{SPO}$ with two random permutations. This yields our final
construction, which we call the _twirled superposition permutation oracle_.
For convenience we first define a version where the twirls are fixed.

######  Definition 4.5 (Twirled superposition permutation oracle).

For any two fixed permutations $\sigma,\tau\in S_{N}$, the _$(\sigma,\tau)$
-twirled superposition permutation oracle_ ($\mathsf{TSPO}^{\sigma,\tau}$) is
defined as follows:

  * •

The state space consists of the same _database_ $D$ as the superposition
permutation oracle.

  * •

The initialization routine is the same as for the superposition permutation
oracle and hence we will continue to denote it by
$\mathsf{Init}^{\mathsf{SPO}}_{D}$.

  * •

There are two query unitaries, $O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}$ and
$O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}$, that define the two
interfaces available to the query algorithm and that simulate oracles for a
random permutation and its inverse. They are defined as follows. For all
$x,y\in[N]$ and $\pi\in S_{N}$

$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\tau^{-1}(\pi(\sigma(x))),\pi}_{XYD},$
$\displaystyle
O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}\ket{x,y,\pi}_{XYD}$
$\displaystyle=\ket{x,y\oplus\sigma^{-1}(\pi^{-1}(\tau(x))),\pi}_{XYD}.$

where $X$ and $Y$ are the $N$-dimensional target register of the oracles.

  * •

The recovery routine $\mathsf{Rec}^{\mathsf{TSPO}^{\sigma,\tau}}_{D}$ first
applies the recovery routine $\mathsf{Rec}^{\mathsf{SPO}}$ to obtain a
permutation $\pi\in S_{N}$, and then returns $\tau^{-1}\pi\sigma$.

When $\mathcal{A}$ is a query algorithm that gets query access to two oracles
acting on two $N$-dimensional register $X$ and $Y$, and if $D$ is the database
register of a superposition permutation oracle, we write
$\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$ to indicate that we use the
interfaces $O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}$ and
$O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}$, respectively, to
implement the two types of oracles queries.

It is easy to see that the twirled superposition permutation oracles exactly
simulate the ordinary one (whether the twirls are fixed or randomly sampled).
Hence it also exactly simulates a quantum-accessible random permutation.

######  Lemma 4.6.

Let $\mathcal{A}$ be a query algorithm that gets query access to two oracles
that act on two $N$-dimensional registers, and let $\sigma_{0},\tau_{0}\in
S_{N}$ be fixed permutations. Then the joint classical-quantum state of the
random variable $\pi$ and the register $B$ is the same for the following three
experiments:

  1. (i)

Run $\mathsf{Init}^{\mathsf{SPO}}_{D}$, then
$B\leftarrow\mathcal{A}^{\mathsf{SPO}_{D}}$, and finally
$\pi\leftarrow\mathsf{Rec}^{\mathsf{SPO}}_{D}$.

  2. (ii)

Run $\mathsf{Init}^{\mathsf{SPO}}_{D}$, then
$B\leftarrow\mathcal{A}^{\mathsf{TSPO}^{\sigma_{0},\tau_{0}}_{D}}$, and
finally $\pi\leftarrow\mathsf{Rec}^{\mathsf{TSPO}^{\sigma_{0},\tau_{0}}}_{D}$.

  3. (iii)

Sample $\sigma\leftarrow S_{N}$ and $\tau\leftarrow S_{N}$, run
$\mathsf{Init}^{\mathsf{SPO}}_{D}$, then
$B\leftarrow\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$, and finally
$\pi\leftarrow\mathsf{Rec}^{\mathsf{TSPO}^{\sigma,\tau}}_{D}$.

Moreover, in part (iii), $\sigma$, $\tau$, and $(\pi,B)$ are independent, and
the three permutations $\sigma,\tau,\pi$ are independent and uniformly
distributed.

###### Proof.

It suffices to argue that (i) and (ii) result in the same joint state. By
using Lemma 4.3 twice, we see that it suffices to compare the following two
experiments:

  1. (i’)

Sample $\pi\leftarrow S_{N}$ uniformly at random and run
$B\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}$.

  2. (ii’)

Sample $\pi\leftarrow S_{N}$ uniformly at random, run
$B\leftarrow\mathcal{A}^{U^{\tau_{0}^{-1}}U^{\pi}U^{\sigma_{0}},U^{\sigma_{0}^{-1}}U^{\pi^{-1}}U^{\tau_{0}}}=\mathcal{A}^{U^{\tau_{0}^{-1}\pi\sigma_{0}},U^{(\tau_{0}^{-1}\pi\sigma_{0})^{-1}}}$,
and update $\pi\leftarrow\sigma_{0}^{-1}\pi\sigma_{0}$.

These are indeed equivalent, since if $\pi\in S_{N}$ is uniformly random then
so is $\tau_{0}^{-1}\pi\sigma_{0}$, for fixed $\sigma_{0},\tau_{0}\in S_{N}$.
∎

It will be convenient to relate the twirled superposition oracle to the
untwirled one by viewing the twirling as an action on the database $D$. To
this end, define the left and right actions of $S_{N}$ on $D$ as

$\displaystyle L^{\tau}\ket{\pi}$ $\displaystyle=\ket{\tau\pi},$
$\displaystyle R^{\sigma}\ket{\pi}$ $\displaystyle=\ket{\pi\sigma^{-1}}.$

Then we have the following lemma, which states that the superposition oracle
can be expressed in terms of the untwirled one, sandwiched by a basis change
implemented by the operators $L_{\tau}$ and $R_{\sigma}$ as defined above.

######  Lemma 4.7.

For all $\sigma,\tau\in S_{N}$, it holds that

$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}$
$\displaystyle=\big{\lparen}L^{\tau}_{D}R^{\sigma}_{D}\big{\rparen}O^{\mathsf{SPO}}_{XYD}\big{\lparen}L^{\tau^{-1}}_{D}R^{\sigma^{-1}}_{D}\big{\rparen},$
$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}$
$\displaystyle=\big{\lparen}L^{\tau}_{D}R^{\sigma}_{D}\big{\rparen}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\big{\lparen}L^{\tau^{-1}}_{D}R^{\sigma^{-1}}_{D}\big{\rparen}.$

###### Proof.

For all $\pi\in S_{N}$ and $x,y\in[N]$, we have

$\displaystyle\big{\lparen}L^{\tau}_{D}R^{\sigma}_{D}\big{\rparen}O^{\mathsf{SPO}}_{XYD}\big{\lparen}L^{\tau^{-1}}_{D}R^{\sigma^{-1}}_{D}\big{\rparen}\ket{x,y,\pi}$
$\displaystyle=\big{\lparen}L^{\tau}_{D}R^{\sigma}_{D}\big{\rparen}O^{\mathsf{SPO}}_{XYD}\ket{x,y,\tau^{-1}\pi\sigma}$
$\displaystyle=\big{\lparen}L^{\tau}_{D}R^{\sigma}_{D}\big{\rparen}\ket{x,y\oplus\tau^{-1}\pi\sigma(x),\tau^{-1}\pi\sigma}$
$\displaystyle=\ket{x,y\oplus\tau^{-1}(\pi(\sigma(x))),\pi}=O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\ket{x,y,\pi},$

which establishes the first equation. The second one is proved in the same
way. ∎

Clearly, these two operations commute with each other, and they leave the
initial state $\ket{\Phi_{\mathsf{SPO}}}_{D}$ of the oracle invariant:

$L_{\sigma}\ket{\Phi_{\mathsf{SPO}}}=R_{\sigma}\ket{\Phi_{\mathsf{SPO}}}_{D}=\ket{\Phi_{\mathsf{SPO}}}_{D}.$
(4.1)

Thus we obtain the following lemma that allows us to compare the behavior of
an algorithm when using either the twirled or the ordinary oracle,
strengthening Lemma 4.6.

######  Lemma 4.8.

Let $\mathcal{A}$ be a unitary query algorithm on registers $AXY$, where $X$
and $Y$ are $N$-dimensional registers, that gets query access to two oracles
that each act on $XY$. For every $\sigma,\tau\in S_{N}$, let
$\ket{\phi^{\sigma,\tau}}_{AXYD}$ be the joint state of algorithm and oracle
defined by running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Moreover, let
$\ket{\phi}_{AXYD}$ denote the joint state of algorithm and oracle defined by
running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{SPO}_{D}}$. Then,

$\displaystyle\ket{\phi^{\sigma,\tau}}_{AXYD}=L^{\tau}_{D}R^{\sigma}_{D}\ket{\phi}_{AXYD}.$

###### Proof.

Without loss of generality, the quantum query algorithm takes the form (cf.
Eq. 2.3)

$\displaystyle U^{(q)}_{AXY}Q^{(q)}_{XYD}U^{(q-1)}_{AXY}Q^{(q-1)}_{XYD}\ldots
U^{(1)}_{AXY}Q^{(1)}_{XYD}U^{(0)}_{AXY},$

where each $Q_{XYD}^{(j)}$ is either a forward or an inverse query, and is
applied to the initial state
$\ket{0}_{AXY}\otimes\ket{\Phi_{\mathsf{SPO}}}_{D}$. When expressing the
twirled oracles in terms of the ordinary ones using Lemma 4.7, we see that the
“twirls” $L^{\tau}_{D}R^{\sigma}_{D}$ and
$L^{\tau^{-1}}_{D}R^{\sigma^{-1}}_{D}$ in-between any pair of queries cancel
(note that they commute with the unitaries $U^{(j)}_{AXY}$). Moreover, by Eq.
4.1 the initial twirl leaves the initial state $\ket{\Phi_{\mathsf{SPO}}}_{D}$
of the database invariant. Accordingly, the output state in the two scenarios
only differs by an application of $L^{\tau}_{D}R^{\sigma}_{D}$, as claimed. ∎

Lemma 4.7 simulates queries to the twirled superposition oracle (for known
$\sigma$ and $\tau$) by a single query to the ordinary one but requires access
to the database. This can also be achieved by acting on the input/output
registers $X$ and $Y$, but in this case more than one query is required. The
following lemma shows that an algorithm can always be converted into a
“standard form” such that an analogous replacement is possible, at the cost of
doubling the number of queries, which will be useful in Section 6.

######  Lemma 4.9.

Let $\mathcal{A}$ be a unitary query algorithm on registers $AXY$, where $X$
and $Y$ are $N$-dimensional registers, that gets query access to two oracles
that each act on $XY$. Then there exists a unitary query algorithm
$\mathcal{C}$ on registers $BXY$, with $B=AZ$ and $Z$ an $N$-dimensional
register, that gets query access to _four_ oracles acting on $XY$ such that,
for every $\sigma,\tau\in S_{N}$ (and for any initial state of the database
register $D$), the following three experiments result in the same state of the
registers $BXYD$:

  1. (i)

Run $\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$ and initialize the
register $Z$ in state $\ket{0}_{Z}$.

  2. (ii)

Run $\mathcal{B}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$, where the query algorithm
$\mathcal{B}$ gets access to two oracles on $XY$ and is defined as follows:

$\displaystyle\mathcal{B}^{O_{XY},O_{XY}^{\mathrm{inv}}}:=\mathcal{C}^{O_{XY},\;O_{XY},\;O_{XY}^{\mathrm{inv}},\;O_{XY}^{\mathrm{inv}}}.$

  3. (iii)

Run $\mathcal{B}_{\sigma,\tau}^{\mathsf{SPO}_{D}}$, where the query algorithm
$\mathcal{B}_{\sigma,\tau}$ gets access to two oracles on $XY$ and is defined
as follows:

$\displaystyle\mathcal{B}_{\sigma,\tau}^{O_{XY},O_{XY}^{\mathrm{inv}}}:=\mathcal{C}^{(V_{X}^{\sigma^{-1}}V_{Y}^{\tau^{-1}}O_{XY}V_{X}^{\sigma}),\;(V_{X}^{\sigma^{-1}}O_{XY}V_{X}^{\sigma}V_{Y}^{\tau}),\;(V_{X}^{\tau^{-1}}V_{Y}^{\sigma^{-1}}O_{XY}^{\mathrm{inv}}V_{X}^{\tau}),\;(V_{X}^{\tau^{-1}}O_{XY}^{\mathrm{inv}}V_{X}^{\tau}V_{Y}^{\sigma})}$

Moreover, if $\mathcal{A}$ makes in total $q$ oracle queries then
$\mathcal{C}$ (and hence $\mathcal{B}$ and $\mathcal{B}_{\sigma,\tau}$) makes
in total $2q$ oracle queries.

###### Proof.

Note that

$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\ket{0}_{Z}$
$\displaystyle=\operatorname{SWAP}_{Y\leftrightarrow
Z}O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\operatorname{CNOT}_{Y\to
Z}O^{\mathsf{TSPO}^{\sigma,\tau}}_{XYD}\operatorname{SWAP}_{Y\leftrightarrow
Z}\ket{0}_{Z}$ $\displaystyle=\operatorname{SWAP}_{Y\leftrightarrow
Z}\left\lparen
V_{X}^{\sigma^{-1}}O^{\mathsf{SPO}}_{XYD}V_{X}^{\sigma}V_{Y}^{\tau}\right\rparen\operatorname{CNOT}_{Y\to
Z}\left\lparen
V_{X}^{\sigma^{-1}}V_{Y}^{\tau^{-1}}O^{\mathsf{SPO}}_{XYD}V_{X}^{\sigma}\right\rparen\operatorname{SWAP}_{Y\leftrightarrow
Z}\ket{0}_{Z}$

and

$\displaystyle O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}\ket{0}_{Z}$
$\displaystyle=\operatorname{SWAP}_{Y\leftrightarrow
Z}O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}\operatorname{CNOT}_{Y\to
Z}O^{\mathsf{TSPO}^{\sigma,\tau},\mathrm{inv}}_{XYD}\operatorname{SWAP}_{Y\leftrightarrow
Z}\ket{0}_{Z}$ $\displaystyle=\operatorname{SWAP}_{Y\leftrightarrow
Z}\left\lparen
V_{X}^{\tau^{-1}}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}V_{X}^{\tau}V_{Y}^{\sigma}\right\rparen\operatorname{CNOT}_{Y\to
Z}\left\lparen
V_{X}^{\tau^{-1}}V_{Y}^{\sigma^{-1}}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}V_{X}^{\tau}\right\rparen\operatorname{SWAP}_{Y\leftrightarrow
Z}\ket{0}_{Z}$

Thus we see that if we define the query algorithm $\mathcal{C}$ as follows,

$\displaystyle\mathcal{C}^{O_{XY},O^{\prime}_{XY},O_{XY}^{\mathrm{inv}},{O^{\prime}}_{XY}^{\mathrm{inv}}}:=$
$\displaystyle\qquad\mathcal{A}^{(\operatorname{SWAP}_{Y\leftrightarrow
Z}O^{\prime}_{XY}\operatorname{CNOT}_{Y\to
Z}O_{XY}\operatorname{SWAP}_{Y\leftrightarrow
Z}),\;(\operatorname{SWAP}_{Y\leftrightarrow
Z}{O^{\prime}}_{XY}^{\mathrm{inv}}\operatorname{CNOT}_{Y\to
Z}O_{XY}^{\mathrm{inv}}\operatorname{SWAP}_{Y\leftrightarrow Z})}\ket{0}_{Z},$

then the claim follows. ∎

##  5 The Fundamental Lemma of the Permutation Oracle

We know from the preceding section that the superposition permutation oracles
exactly simulate a quantum-accessible permutation, with the permutation being
obtained by measuring the database in the computational basis. However, to
learn about queries made by the adversary, we wish to also measure whether
database registers are in the uniform superposition states. The following
result, which we call the _Fundamental Lemma_ , shows that this only slightly
changes the statistics. It resembles [CFHL21, Corollary 4.2] which goes back
to Zhandry, but our result applies to random permutations rather than random
functions. We state and prove it for arbitrary relations involving a single
input-output pair.

######  Lemma 5.1 (Fundamental Lemma of the Permutation Oracle).

Let $R\subseteq[N]\times[N]$ be a relation. Let $\mathcal{A}$ be a quantum
algorithm that gets query access to two oracles that each act on
$\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$, and which returns a pair
$(x,y)\in[N]\times[N]$. We consider the following two experiments:

  1. (i)

Sample $\pi\leftarrow S_{N}$ uniformly at random, and run
$(x,y)\leftarrow\mathcal{A}^{U^{\pi},U^{\pi^{-1}}}$.
If $\pi(x)=y$ and $(x,y)\in R$ then return 1. Otherwise return 0.

  2. (ii)

Sample $\sigma\leftarrow S_{N}$ and $\tau\leftarrow S_{N}$, run
$\mathsf{Init}^{\mathsf{SPO}}_{D}$, and then
$(x,y)\leftarrow\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Next, apply to
register $D_{\sigma(x)}$ the projective measurement
$\\{\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert,I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert\\}$.
If the second outcome is observed, run
$\pi\leftarrow\mathsf{Rec}^{\mathsf{TSPO}^{\sigma,\tau}}_{D}$. If $\pi(x)=y$
and $(x,y)\in R$, return 1. In all other cases, return 0.

Let $p_{\text{(i)}}$, $p_{\text{(ii)}}$ denote the probability that first or
second experiment returns 1, respectively. Then:

$\displaystyle\sqrt{p_{\text{(i)}}}\leq\sqrt{p_{\text{(ii)}}}+\sqrt{\frac{\ln(N)+1}{N}}.$

Thus, if we want to upper bound the probability that the algorithm learned a
pair $(x,y)$ such that $\pi(x)=y$ satisfying some relation $R$, then we can
just imagine first measuring whether $D_{\sigma(x)}$ is not
$\ket{+_{\sigma(x)}}$, without significantly increasing the error – we will
see that this typically yields a quantity that is easier to upper bound. This
bound is essentially identical to the one known for random functions, except
for the extra term $\ln(N)+1$, which is due to the varying dimensions of the
database registers.

The idea of the proof is to recall that, by Lemmas 4.3 and 4.6, the first
experiment is exactly simulated by the following:

  1. (i’)[it:real prime]

Sample $\sigma\leftarrow S_{N}$ and $\tau\leftarrow S_{N}$, run
$\mathsf{Init}^{\mathsf{SPO}}_{D}$, and then
$(x,y)\leftarrow\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Measure the
entire database in the computational basis and interpret the outcome as a
permutation $\pi\in S_{N}$. If $\pi(\sigma(x))=\tau(y)$ and $(x,y)\in R$, then
return 1. Otherwise return 0.

For comparison, expanding the definition of the recovery routine
$\mathsf{Rec}^{\mathsf{TSPO}^{\sigma,\tau}}_{D}$, the second experiment can be
written as follows:

  1. (ii’)[it:forensic prime]

Sample $\sigma\leftarrow S_{N}$ and $\tau\leftarrow S_{N}$, run
$\mathsf{Init}^{\mathsf{SPO}}_{D}$, and then
$(x,y)\leftarrow\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Next, apply to
register $D_{\sigma(x)}$ the projective measurement
$\\{\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert,I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert\\}$.
If the second outcome is observed, measure the entire database in the
computational basis and interpret the outcome as a permutation $\pi\in S_{N}$.
If $\pi(\sigma(x))=\tau(y)$ and $(x,y)\in R$, then return 1. In all other
cases, return 0.

Note that LABEL:it:real_prime and LABEL:it:forensic_prime only differ in that
the latter contains the additional measurement of the register $D_{\sigma(x)}$
and subsequent check that the desired (second) outcome occurred. To prove the
fundamental lemma, we therefore need to argue that this “postselection” does
not impact the probability of acceptance much. We first state and prove a
technical lemma that contains the core argument, and then use it establish
Lemma 5.1.

######  Lemma 5.2.

Let $x\in[N]$ and $Y\subseteq[N]$. Then it holds that:

$\displaystyle\left\lVert\sum_{\pi\in S_{N}:\pi(x)\in
Y}\lvert\pi\rangle\langle\pi\rvert_{D}-\sum_{\pi\in S_{N}:\pi(x)\in
Y}\lvert\pi\rangle\langle\pi\rvert_{D}\left\lparen
I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rparen\right\rVert=\left\lVert\sum_{\pi\in
S_{N}:\pi(x)\in
Y}\lvert\pi\rangle\langle\pi\rvert_{D}\ket{+_{x}}_{D_{x}}\right\rVert\leq\sqrt{\frac{\lvert
Y\rvert}{x}}.$

###### Proof.

The first equality is clear. Now, for any operator $X$ the operator norm can
be computed as $\lVert X\rVert=\max_{\lVert\phi\rVert=1}\lVert
X\ket{\phi}\rVert$. Thus there exists a vector
$\ket{\Delta}\in\mathcal{H}_{D_{x^{c}}}=\bigotimes_{k=1:k\neq
x}^{n}\mathcal{H}_{D_{k}}$ such that

$\displaystyle\left\lVert\sum_{\pi\in S_{N}:\pi(x)\in
Y}\lvert\pi\rangle\langle\pi\rvert_{D}\ket{+_{x}}_{D_{x}}\right\rVert^{2}$
$\displaystyle=\left\lVert\sum_{\pi\in S_{N}:\pi(x)\in
Y}\lvert\pi\rangle\langle\pi\rvert_{D}\left\lparen\ket{+_{x}}_{D_{x}}\otimes\ket{\Delta}_{D_{x^{c}}}\right\rparen\right\rVert^{2}$
$\displaystyle=\sum_{\pi\in S_{N}:\pi(x)\in
Y}\left\lvert\bra{\pi}_{D}\left\lparen\ket{+_{x}}_{D_{x}}\otimes\ket{\Delta}_{D_{x^{c}}}\right\rparen\right\rvert^{2}.$

This can be upper bounded by

$\displaystyle\Pr\bigl{(}\pi(x)\in Y\mid
t_{x}\leftarrow[x],\;(t_{1},\dots,t_{x-1},t_{x+1},\dots,t_{N})\leftarrow
Q\bigr{)},$

where the permutation $\pi\in S_{N}$ is defined in terms of the numbers
$t_{1},\dots,t_{N}$ via Eq. 3.1, and where $Q$ is some probability
distribution on $\prod_{k=1:k\neq x}^{n}[k]$ (namely the distribution obtained
by measuring $\ket{\Delta}_{D_{x^{c}}}$ in the standard basis). Now,

$\displaystyle\pi(x)\in
Y\quad\Leftrightarrow\quad\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(2\;t_{2}\right)\left(1\;t_{1}\right)(x)\in
Y\quad\Leftrightarrow\quad\pi_{>x}(t_{x})\in Y\quad\Leftrightarrow\quad
t_{x}\in\pi_{>x}^{-1}(Y),$

where we recall the notation
$\pi_{>x}=\left(N\;t_{N}\right)\left(N\\!-\\!1\;t_{N-1}\right)\cdots\left(x+1\;t_{x+1}\right)$.
Thus, whatever $\pi_{>x}$, there are at most $\lvert Y\rvert$ choices of
$t_{x}\in[x]$ such that $\pi(x)\in Y$. Since $\pi_{>x}$ and $t_{x}$ are
independent and the latter is chosen uniformly at random in $[x]$, we have

$\displaystyle\Pr\bigl{(}\pi(x)\in
Y\;\big{|}\;t_{x}\leftarrow[x],\;(t_{1},\dots,t_{x-1},t_{x+1},\dots,t_{N})\leftarrow
Q\bigr{)}\leq\frac{\lvert Y\rvert}{x}.$

This concludes the proof. ∎

We now prove the fundamental lemma.

###### Proof of Lemma 5.1.

As discussed it suffices to compare the two experiments LABEL:it:real_prime
and LABEL:it:forensic_prime. Let $p(\sigma,\tau,x,y)$ denote the joint
distribution of the uniformly random choices of $\sigma,\tau\in S_{N}$ and the
output $(x,y)$ of $\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$ and choose,
for each $\sigma,\tau,x,y$, a purification
$\ket{\Delta(\sigma,\tau,x,y)}_{DE}$ of the corresponding state of the
database. Then:

$\displaystyle p_{\text{(i')}}=\sum_{\sigma,\tau\in S_{N},(x,y)\in
R}p(\sigma,\tau,x,y)\,p_{\text{(i')}}(\sigma,\tau,x,y)\qquad\text{and}\qquad
p_{\text{(ii')}}=\sum_{\sigma,\tau\in S_{N},(x,y)\in
R}p(\sigma,\tau,x,y)\,p_{\text{(ii')}}(\sigma,\tau,x,y),$

where

$\displaystyle p_{\text{(i')}}(\sigma,\tau,x,y)$
$\displaystyle:=\left\lVert\sum_{\pi\in
S_{N}:\pi(\sigma(x))=\tau(y)}\lvert\pi\rangle\langle\pi\rvert_{D}\ket{\Delta(\sigma,\tau,x,y)}_{DE}\right\rVert^{2},$
$\displaystyle p_{\text{(ii')}}(\sigma,\tau,x,y)$
$\displaystyle:=\left\lVert\sum_{\pi\in
S_{N}:\pi(\sigma(x))=\tau(y)}\lvert\pi\rangle\langle\pi\rvert_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\Delta(\sigma,\tau,x,y)}_{DE}\right\rVert^{2}.$

Using Lemma 5.2 (with $Y=\\{\tau(y)\\}$) and the Cauchy-Schwarz inequality, it
follows that

$\displaystyle p_{\text{(i')}}$ $\displaystyle\leq\sum_{\sigma,\tau\in
S_{N},(x,y)\in
R}p(\sigma,\tau,x,y)\left\lparen\sqrt{p_{\text{(ii')}}(\sigma,\tau,x,y)}+\sqrt{\frac{1}{\sigma(x)}}\right\rparen^{2}$
$\displaystyle=p_{\text{(ii')}}+2\sum_{\sigma,\tau\in S_{N},(x,y)\in
R}p(\sigma,\tau,x,y)\sqrt{p_{\text{(ii')}}(\sigma,\tau,x,y)}\sqrt{\frac{1}{\sigma(x)}}+\sum_{\sigma,\tau\in
S_{N},(x,y)\in R}p(\sigma,\tau,x,y)\frac{1}{\sigma(x)}$ $\displaystyle\leq
p_{\text{(ii')}}+2\sqrt{p_{\text{(ii')}}}\sqrt{\sum_{\sigma,\tau\in
S_{N},(x,y)\in R}p(\sigma,\tau,x,y)\frac{1}{\sigma(x)}}+\sum_{\sigma,\tau\in
S_{N},(x,y)\in R}p(\sigma,\tau,x,y)\frac{1}{\sigma(x)}.$

Thus,

$\displaystyle\sqrt{p_{\text{(i')}}}\leq\sqrt{p_{\text{(ii')}}}+\sqrt{\sum_{\sigma,\tau\in
S_{N},(x,y)\in R}p(\sigma,\tau,x,y)\frac{1}{\sigma(x)}}.$

Finally, we note that as a consequence of Lemma 4.6, $\sigma$, $\tau$, and
$(x,y)$ are independent with respect to the distribution $p(\sigma,\tau,x,y)$.
Thus,

$\displaystyle\sum_{\sigma,\tau\in S_{N},(x,y)\in
R}p(\sigma,\tau,x,y)\frac{1}{\sigma(x)}\leq\frac{1}{N}\sum_{k=1}^{N}\frac{1}{k}\leq\frac{\ln(N)+1}{N}.$

∎

In order to apply the fundamental lemma, it is useful to upper bound the
probability $p_{\text{(ii)}}$ in way that only refers to the state of the
database. This is achieved by the following lemma.

######  Lemma 5.3.

Let $R\subseteq[N]\times[N]$ be a relation. Let $\mathcal{A}$ be a quantum
algorithm that gets query access to two oracles that each act on
$\mathbbm{C}^{N}\otimes\mathbbm{C}^{N}$, and which returns a pair
$(x,y)\in[N]\times[N]$. For $\sigma,\tau\in S_{N}$, let
$\ket{\phi^{\sigma,\tau}}$ denote a purification of the state of the database
after running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Then, the quantity
$p_{\text{(ii)}}$ in Lemma 5.1 can be upper bounded as

$\displaystyle p_{\text{(ii)}}\leq\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}\sum_{(x,y)\in R}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
\tau^{-1}(\pi(\sigma(x)))=y\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\phi^{\sigma,\tau}}\right\rVert^{2}.$

###### Proof.

Without loss of generality we can assume that $\mathcal{A}$ is a unitary query
algorithm on registers $AXY$ such that the classical outcomes $x$ and $y$ can
be obtained by measuring the $X$ and $Y$ registers. For every $\sigma,\tau\in
S_{N}$, let $\ket{\phi^{\sigma,\tau}}_{AXYD}$ be the joint state of algorithm
and oracle defined by running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{TSPO}^{\sigma,\tau}_{D}}$. Then:

$\displaystyle p_{\text{(ii)}}$ $\displaystyle=\mathop{\bf
E\/}_{\sigma,\tau\leftarrow S_{N}}\sum_{(x,y)\in
R}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
\tau^{-1}(\pi(\sigma(x)))=y\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\bra{xy}_{XY}\ket{\phi^{\sigma,\tau}}_{AXYD}\right\rVert^{2}.$

Because the projection $\bra{xy}$ commutes with the operators on $D$ and never
increases the norm, we can upper bound the above as

$\displaystyle p_{\text{(ii)}}$ $\displaystyle\leq\mathop{\bf
E\/}_{\sigma,\tau\leftarrow S_{N}}\sum_{(x,y)\in
R}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
\tau^{-1}(\pi(\sigma(x)))=y\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\phi^{\sigma,\tau}}_{AXYD}\right\rVert^{2}.$

Since this expression only depends on the reduced state on $D$, the claim
follows. ∎

##  6 Bounding the Success Probability for Search

In this section we generalize Zhandry’s compressed oracle technique [Zha19] to
the case of random permutations, but using our (twirled) permutation oracle.
The high-level strategy for proving such theorems is as follows: For the
compressed oracle for a random function $H$, it can be approximately
determined whether a certain input $x$ has been queried, and if so whether
$x$, together with the corresponding function output $y=H(x)$, fulfils a
certain relation. This test is performed by a measurement acting on the
database register $D_{x}$ only. For different inputs $x$, these tests commute,
and hence there exists a projective measurement answering the question whether
there _exists_ an input $x$ such that the described test would trigger. The
probability that this measurement outputs yes after $q$ queries then serves as
a convenient _progress measure_. This is reminiscent to the progress measures
used in the so-called “hybrid method” that was introduced earlier to prove the
query lower bound for the unstructured search problem [BBBV97].

We would like to generalize this technique to the case of random permutations.
We follow a similar strategy, and begin by devising a generalization of the
test for a single input. To test whether a certain input $x$ has been queried
in forward direction or output in an inverse query, and if so, whether,
together with the corresponding function output $y=\pi(x)$, it fulfils a
certain relation $R\subseteq[N]\times[N]$, we define the following operators:

$\displaystyle\Pi^{R,x}_{D}$ $\displaystyle:=\sum_{\pi\in S_{N}:\pi(x)\in
R_{x}}\lvert\pi\rangle\langle\pi\rvert_{D},$ $\displaystyle E^{R,x}_{D}$
$\displaystyle:=\Pi^{R,x}_{D}(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}).$

where we have defined $R_{x}:=\\{y\in[N]:(x,y)\in R\\}$. For later use, we
also set $R^{\mathrm{inv}}_{y}:=\\{x\in[N]:(x,y)\in R\\}$ and

$\displaystyle r_{\max}:=\max\left\\{\max_{x\in[N]}\,\lvert
R_{x}\rvert,\max_{y\in[N]}\,\lvert R^{\mathrm{inv}}_{y}\rvert\right\\}.$

Unfortunately, the operators $E^{R,x}$ for different $x$ do not commute, so we
cannot simply use these to construct a measurement answering the existence
question. Instead, we will check whether a _random_ $x$ has this property. To
lift the worst-case bounds established in the previous section to the average
case, we further consider running the query algorithm with the _twirled_
permutation oracle for uniformly random $\sigma,\tau\in S_{N}$. Because the
permutation in the database is now twirled as compared to the action of the
oracle, we must also consider the twirled relation $R^{\sigma,\tau}$ that is
defined as follows in terms of $R$:

$\displaystyle(x,y)\in
R^{\sigma,\tau}:\\!\\!\iff(\sigma^{-1}(x),\tau^{-1}(y))\in R.$ (6.1)

Thus we are led to consider the following natural progress measure:

$\displaystyle\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2},$

where $\ket{\phi^{\sigma,\tau}}$ denotes the joint state of (a unitary
realization of) the algorithm and database obtained by running the algorithm
with the twirled permutation oracle $\mathsf{TSPO}^{\sigma,\tau}$. Remarkably,
this progress measure not only has an intuitive operational interpretation,
but it is also directly related to the upper bound furnished by the
fundamental lemma (cf. Lemma 5.3):

######  Lemma 6.1.

For any relation $R\subseteq[N]\times[N]$, it holds that

$\displaystyle N\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}=\mathop{\bf
E\/}_{\sigma,\tau\leftarrow S_{N}}\sum_{(x,y)\in
R}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
\tau^{-1}(\pi(\sigma(x)))=y\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\phi^{\sigma,\tau}}\right\rVert^{2}.$

###### Proof.

We calculate:

$\displaystyle\quad\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}\sum_{(x,y)\in R}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
\tau^{-1}(\pi(\sigma(x)))=y\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle=\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}\sum_{x=1}^{N}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
(\sigma(x),\pi(\sigma(x)))\in
R^{\sigma,\tau}\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{\sigma(x)}\rangle\langle+_{\sigma(x)}\rvert_{D_{\sigma(x)}}\right\rparen\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle=\mathop{\bf E\/}_{\sigma,\tau\leftarrow
S_{N}}\sum_{x=1}^{N}\sum_{\begin{subarray}{c}\pi\in S_{N}\text{ s.th.}\\\
(x,\pi(x))\in
R^{\sigma,\tau}\end{subarray}}\left\lVert\bra{\pi}_{D}\left\lparen
I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rparen\ket{\phi^{\sigma,\tau}}\right\rVert^{2}$
$\displaystyle=N\mathop{\bf E\/}_{\begin{subarray}{c}x\leftarrow[N],\\\
\sigma,\tau\leftarrow S_{N}\end{subarray}}\left\lVert
E^{R^{\sigma,\tau},x}_{D}\ket{\phi^{\sigma,\tau}}\right\rVert^{2}.\qed$

We can now summarize the plan for the remainder of this section:

  1. (i)

We bound the effect of a single query on any fixed location $x$ of the
database in Section 6.1.

  2. (ii)

We derive a bound on the success probability of the adversary in Section 6.2,
but in expectation over the random choice of the database location and the
choice of the twirling.

  3. (iii)

We bound the (weighted) average probability that a database register is no
longer in the uniform state, which is necessary to complete the proof, in
Section 6.3.

  4. (iv)

We combine (ii) and (iii) with the fundamental lemma to obtain our main
theorem in Section 6.4.

###  6.1 Bounding the Success Probability in the Worst Case

We start with a useful lemma that follows readily from Lemma 5.2.

######  Lemma 6.2.

Let
$Q^{\mathsf{SPO}}_{XYD}\in\\{O^{\mathsf{SPO}}_{XYD},O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\\}$,
and $x\in[N]$. Then:

  1. (i)

$\big{\lVert}E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\big{\lparen}I-\Pi^{R,x}_{D}\big{\rparen}\big{\rVert}\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}$.

  2. (ii)

$\big{\lVert}E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\ket{\phi}\big{\rVert}-\big{\lVert}E^{R,x}_{D}\ket{\phi}\big{\rVert}\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\big{\lVert}\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\big{\rVert}+\big{\lVert}E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\big{\rVert}$
for any pure state $\ket{\phi}_{AXYD}$.

  3. (iii)

$\big{\lVert}E^{R,x}_{D}Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rVert}\leq
2\sqrt{\frac{\lvert R_{x}\rvert}{x}}$ for all $z\in[N]$, where
$Q^{\mathsf{SPO},z}_{YD}:=\bra{z}_{X}Q^{\mathsf{SPO}}_{XYD}\ket{z}_{X}$.

###### Proof.

(i) Since $Q^{\mathsf{SPO}}_{XYD}$ is a unitary controlled on register $D$, it
commutes with computational basis projections, and hence with $\Pi^{R,x}_{D}$.
Therefore, and using unitary invariance, we obtain

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\big{\lparen}I-\Pi^{R,x}_{D}\big{\rparen}\right\rVert$
$\displaystyle=\left\lVert
E^{R,x}_{D}\big{\lparen}I-\Pi^{R,x}_{D}\big{\rparen}Q^{\mathsf{SPO}}_{XYD}\right\rVert$
$\displaystyle=\left\lVert\Pi^{R,x}_{D}\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\big{\lparen}I-\Pi^{R,x}_{D}\big{\rparen}\right\rVert$
$\displaystyle=\left\lVert\Pi^{R,x}_{D}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\lparen}I-\Pi^{R,x}_{D}\big{\rparen}\right\rVert$
$\displaystyle\leq\left\lVert\Pi^{R,x}_{D}\ket{+_{x}}_{D_{x}}\right\rVert\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}.$

The last inequality holds due to Lemma 5.2.

(ii) Since

$\displaystyle
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\ket{\phi}=E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}E^{R,x}_{D}\ket{\phi}+E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\left\lparen
I-E^{R,x}_{D}\right\rparen\ket{\phi},$

and $\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}E^{R,x}_{D}\ket{\phi}\rVert\leq\lVert
E^{R,x}_{D}\ket{\phi}\rVert$, we have, by the triangle inequality,

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\ket{\phi}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi}\right\rVert\leq\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\left\lparen
I-E^{R,x}_{D}\right\rparen\ket{\phi}\right\rVert.$

Since
$I-E^{R,x}_{D}=(I-\Pi^{R,x}_{D})(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\;+\;\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}$,
we can bound the right-hand side by

$\displaystyle\quad\left\lVert E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\left\lparen
I-E^{R,x}_{D}\right\rparen\ket{\phi}\right\rVert$
$\displaystyle\leq\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}(I-\Pi^{R,x}_{D})(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}\right\rVert+\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert$
$\displaystyle\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\right\rVert+\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert,$

using another triangle inequality and, in the last step, part (i).

(iii) We can proceed similarly as in part (i):

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert$
$\displaystyle=\left\lVert\Pi^{R,x}_{D}\left\lparen
I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rparen
Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert$
$\displaystyle\leq\left\lVert\Pi^{R,x}_{D}Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert+\left\lVert\Pi^{R,x}_{D}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert$
$\displaystyle=\left\lVert
Q^{\mathsf{SPO},z}_{YD}\Pi^{R,x}_{D}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert+\left\lVert\Pi^{R,x}_{D}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}Q^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\right\rVert$
$\displaystyle\leq 2\lVert\Pi^{R,x}_{D}\ket{+_{x}}_{D_{x}}\rVert\leq
2\sqrt{\frac{\lvert R_{x}\rvert}{x}}.\qed$

We now bound the effect of a single forward query on the probability
amplitude.

######  Lemma 6.3 (Forward query).

For any pure state $\ket{\phi}_{AXYD}$ such that
$\lVert\bra{\pi}_{D}\ket{\phi}_{AXYD}\rVert^{2}=\frac{1}{N!}$ for all $\pi\in
S_{N}$, and for any $x\in[N]$, we have

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\ket{\phi}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi}\right\rVert$ $\displaystyle\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\right\rVert+2\sqrt{\zeta_{\ket{\phi},x}}$

where $\ket{\phi_{x}}_{AYD}:=\bra{x}_{X}\ket{\phi}_{AXYD}$ and

$\displaystyle\zeta_{\ket{\phi},x}:=\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{\lvert
R_{x}\rvert}{x^{2}N}+\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$

###### Proof.

By Lemma 6.2 (ii), we have

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\ket{\phi}\right\rVert-\big{\lVert}E^{R,x}_{D}\ket{\phi}\big{\rVert}\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\big{\lVert}\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\big{\rVert}+\big{\lVert}E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\big{\rVert},$
(6.2)

To upper bound the right-hand side norm, we compute its square as follows:

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert^{2}=\sum_{z\in[N]}\left\lVert\bra{z}_{X}E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert^{2}=\sum_{z\in[N]}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2},$

where we defined
${O}^{\mathsf{SPO},z}_{YD}:=\bra{z}_{X}O^{\mathsf{SPO}}_{XYD}\ket{z}_{X}$. We
analyze the summands and distinguish three cases:

  1. (i)

For $z>x$, ${O}^{\mathsf{SPO},z}_{YD}$ acts trivially on $D_{x}$ by Lemma 4.4,
and hence commutes with $\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}$. As
$E^{R,x}_{D}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}=0$, we see that the
corresponding summands vanish.

  2. (ii)

For $z=x$, then we have the following bound from Lemma 6.2 (iii):

$\displaystyle\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},x}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{x}}\right\rVert^{2}\leq
4\frac{\lvert R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}.$

  3. (iii)

For $z<x$, the argument is more involved. We begin by computing the action of
${O}^{\mathsf{SPO},z}_{YD}$ on computational basis states. For $\pi\in S_{N}$,
let us write $\pi=\pi_{>x}\left(x\;t\right)\pi_{<x}$ as in Section 3.2, with
$t\in[x]$, and define $\pi_{x^{c}}:=\pi_{>x}\pi_{<x}$. We may identify
$\pi_{x^{c}}$ with the indices $t_{k}$ for $k\neq x$; accordingly we shall
write $\ket{\pi}_{D}=\ket{t}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$. Note that
if $\pi_{<x}(z)=t$ then $\pi(z)=\pi_{>x}(x)$, while otherwise
$\pi(z)=\pi_{x^{c}}(z)$. Thus, for every $\pi\in S_{N}$ and $y\in[N]$, we have

$\displaystyle{O}^{\mathsf{SPO},z}_{YD}\ket{y,\pi}_{YD}={O}^{\mathsf{SPO},z}_{YD}\ket{y,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}=\begin{cases}\ket{y\oplus\pi_{>x}(x),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{if
$\pi_{<x}(z)=t$},\\\
\ket{y\oplus\pi_{x^{c}}(z),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{otherwise.}\end{cases}$

It follows that

$\displaystyle{O}^{\mathsf{SPO},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\ket{y\oplus\pi_{x^{c}}(z)}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle+\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus\pi_{>x}(x)}_{Y}-\ket{y\oplus\pi_{x^{c}}(z)}_{Y}\Big{\rparen}\ket{\pi_{<x}(z)}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}},$

hence

$\displaystyle\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}{O}^{\mathsf{SPO},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus\pi_{>x}(x)}_{Y}-\ket{y\oplus\pi_{x^{c}}(z)}_{Y}\Big{\rparen}$
$\displaystyle\otimes\Big{\lparen}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{\sqrt{x}}\ket{+_{x}}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$

and finally

$\displaystyle\quad
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus\pi_{>x}(x)}_{Y}-\ket{y\oplus\pi_{x^{c}}(z)}_{Y}\Big{\rparen}\otimes\Big{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=M_{YD_{x^{c}}}^{(z)}\left\lparen\frac{1}{\sqrt{x}}\ket{y}_{Y}\otimes\Big{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}\right\rparen,$

where the operator $M_{YD_{x^{c}}}^{(z)}$ is defined by
$M_{YD_{x^{c}}}^{(z)}\ket{y}_{Y}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=\left\lparen\ket{y\oplus\pi_{>x}(x)}_{Y}-\ket{y\oplus\pi_{x^{c}}(z)}_{Y}\right\rparen\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
and has operator norm $\leq\sqrt{2}$. Thus:

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=M_{YD_{x^{c}}}^{(z)}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\ket{\pi_{x^{c}}}_{D_{x^{c}}}.$

We can now bound the desired norm:

$\displaystyle\quad\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle=\Big{\lVert}E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\sum_{\pi_{x^{c}}}\lvert\pi_{x^{c}}\rangle\langle\pi_{x^{c}}\rvert_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\Big{\lVert}\sum_{\pi_{x^{c}}}E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\Big{\lVert}M_{YD_{x^{c}}}^{(z)}\sum_{\pi_{x^{c}}}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{2}{x}\sum_{\pi_{x^{c}}}\Big{\lVert}\Big{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\ket{\pi_{<x}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{\pi_{x^{c}}}\bigg{\lparen}\bm{1}_{\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{1}{x^{2}}\Big{\lVert}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\bigg{\rparen}$
$\displaystyle=\frac{4}{x}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\big{\rVert}^{2}.$

Here the first inequality follows from the bound on the operator norm of
$M_{YD_{x^{c}}}^{(z)}$, and the fact that all $\pi_{x^{c}}$ are orthogonal,
the second inequality follows by Cauchy-Schwarz, and the last inequality
follows by the fact that $\ket{+_{x}}$ is a unit vector. It follows that

$\displaystyle\quad\sum_{z=1}^{x-1}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi}\big{\rVert}^{2}$
$\displaystyle=\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\frac{1}{N!},$

where we used that $\lVert\bra{\pi}_{D}\ket{\phi}\rVert^{2}=\frac{1}{N!}$ for
all $\pi\in S_{N}$ and hence
$\lVert\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi}\rVert^{2}=\frac{x}{N!}$. Since

$\displaystyle\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\frac{1}{N!}=\frac{1}{N!}\sum_{\pi\in
S_{N}:\pi(x)\in R_{x}}1=\Pr\bigl{(}\pi(x)\in R_{x}\mid\pi\leftarrow
S_{N}\bigr{)}\leq\frac{\lvert R_{x}\rvert}{N},$

we find that

$\displaystyle\sum_{z=1}^{x-1}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}.$

Altogether, we obtain the following bound for the right-hand side term in Eq.
6.2:

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert$
$\displaystyle\leq\sqrt{4\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}}$ $\displaystyle=2\sqrt{\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{\lvert
R_{x}\rvert}{x^{2}N}+\frac{1}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{x^{c}}(z)\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}}$

and the lemma follows. ∎

Next, we now bound the effect of an inverse query on the probability
amplitude.

######  Lemma 6.4 (Inverse query).

For any pure state $\ket{\phi}_{AXYD}$ such that
$\lVert\bra{\pi}_{D}\ket{\phi}_{AXYD}\rVert^{2}=\frac{1}{N!}$, and for any
$x\in[N]$, we have

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\ket{\phi}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi}\right\rVert$ $\displaystyle\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\right\rVert+4\sqrt{\zeta^{\mathrm{inv}}_{\ket{\phi},x}},$

where $\ket{\phi_{x}}_{AYD}:=\bra{x}_{X}\ket{\phi}_{AXYD}$ and

$\displaystyle\zeta^{\mathrm{inv}}_{\ket{\phi},x}:=\;$
$\displaystyle\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{\lvert
R_{x}\rvert}{x^{2}N}+\frac{1}{x}\sum_{z\in
R_{x}}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$

###### Proof.

By Lemma 6.2 (ii), we have

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\ket{\phi}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi}\right\rVert\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi}\right\rVert+\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert,$
(6.3)

and we need to bound the right-hand side term, which we can rewrite as

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert^{2}=\sum_{z\in[N]}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2},$

where
${O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}:=\bra{z}_{X}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\ket{z}_{X}$.
We analyze the the right-hand side summands and distinguish three cases:

  1. (i)

For $z=x$, we have the following bound from Lemma 6.2 (iii):

$\displaystyle\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{x}}\right\rVert^{2}\leq
4\frac{\lvert R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}.$

  2. (ii)

For $z<x$, we proceed similarly as in the corresponding case of Lemma 6.3. For
$\pi\in S_{N}$, let us again write $\pi=\pi_{>x}\left(x\;t\right)\pi_{<x}$ as
in Section 3.2, with $t\in[x]$, define $\pi_{x^{c}}:=\pi_{>x}\pi_{<x}$,
identify $\pi_{x^{c}}$ with the indices $t_{k}$ for $k\neq x$, and write
$\ket{\pi}_{D}=\ket{t}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$. Let

$\displaystyle S_{x,z}:=\big{\\{}\pi_{x^{c}}\;:\;\pi_{>x}^{-1}(z)\leq
x\big{\\}}=\big{\\{}\pi_{x^{c}}\;:\;\pi_{>x}^{-1}(z)<x\big{\\}}=\big{\\{}\pi_{x^{c}}\;:\;\pi_{>x}^{-1}(z)=z\big{\\}}=\big{\\{}\pi_{x^{c}}\;:\;t_{w}\neq
z\;\forall w>x\big{\\}}.$

If $\pi_{x^{c}}\not\in S_{x,z}$, then $\pi^{-1}(z)=z$ for any choice of $t$.
Hence ${O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}$ acts trivially on $D_{x}$ and
we have

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=E^{R,x}_{D}\ket{+_{x}}_{D_{x}}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=0.$
(6.4)

Now suppose that $\pi_{x^{c}}\in S_{x,z}$. Then,

$\displaystyle{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}=\ket{y\oplus\pi^{-1}(z),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}=\begin{cases}\ket{y\oplus
x,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{ if $t=z$, }\\\
\ket{y\oplus\pi_{<x}^{-1}(z),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{
otherwise.}\end{cases}$

It follows that

$\displaystyle{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\ket{y\oplus\pi_{<x}^{-1}(z)}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle+\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{<x}^{-1}(z)}_{Y}\Big{\rparen}\ket{z}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}},$

hence

$\displaystyle\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{<x}^{-1}(z)}_{Y}\Big{\rparen}$
$\displaystyle\otimes\Big{\lparen}\ket{z}_{D_{x}}-\frac{1}{\sqrt{x}}\ket{+_{x}}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$

and finally

$\displaystyle\quad
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{<x}^{-1}(z)}_{Y}\Big{\rparen}\otimes\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{z}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=M_{YD_{x^{c}}}^{(z)}\left\lparen\frac{1}{\sqrt{x}}\ket{y}_{Y}\otimes\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{z}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}\right\rparen,$

where the operator $M_{YD_{x^{c}}}^{(z)}$ is defined by
$M_{YD_{x^{c}}}^{(z)}\ket{y}_{Y}\ket{\pi_{x^{c}}}_{YD_{x^{c}}}=\left\lparen\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{<x}^{-1}(z)}_{Y}\right\rparen\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
and has operator norm $\leq\sqrt{2}$. Thus:

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=M_{YD_{x^{c}}}^{(z)}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{z}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$

Using the above and Eq. 6.4, we can now bound the desired norm:

$\displaystyle\quad\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle=\Big{\lVert}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\sum_{\pi_{x^{c}}}\lvert\pi_{x^{c}}\rangle\langle\pi_{x^{c}}\rvert_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\Big{\lVert}\sum_{\pi_{x^{c}}\in
S_{x,z}}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\Big{\lVert}M_{YD_{x^{c}}}^{(z)}\sum_{\pi_{x^{c}}\in
S_{x,z}}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{z}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{2}{x}\sum_{\pi_{x^{c}}\in
S_{x,z}}\Big{\lVert}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{z}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{\pi_{x^{c}}\in
S_{x,z}}\bigg{\lparen}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{1}{x^{2}}\Big{\lVert}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\bigg{\rparen}$
$\displaystyle=\frac{4}{x}\sum_{\pi_{x^{c}}\in S_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}\in
S_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{\pi_{x^{c}}\in S_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}\in
S_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$

following the same reasoning as the proof of Lemma 6.3. It follows that

$\displaystyle\quad\sum_{z=1}^{x-1}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}\in
S_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}\in
S_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}\in
S_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{3}}\sum_{\pi_{x^{c}}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}\in
S_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}$
$\displaystyle=\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\frac{\lvert
R_{x}\rvert}{N},$

where the last inequality follows from the same argument as in the proof of
Lemma 6.3 and is using the assumption that
$\lVert\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi}\rVert^{2}=\frac{x}{N!}$ for all
$\pi\in S_{N}$.

  3. (iii)

For $z>x$, we use the same notation as above, but instead of $S_{x,z}$ we
consider

$\displaystyle S^{\prime}_{x,z}$
$\displaystyle:=\big{\\{}\pi_{x^{c}}\;:\;\pi_{>x}^{-1}(z)<x\big{\\}},$
$\displaystyle S^{\prime\prime}_{x,z}$
$\displaystyle:=\big{\\{}\pi_{x^{c}}\;:\;\pi_{>x}^{-1}(z)=x\big{\\}}.$

If $\pi_{x^{c}}\not\in S^{\prime}_{x,z}\cup S^{\prime\prime}_{x,z}$, then we
see as above that $\pi^{-1}(z)$ does not depend on the choice of $t$ and hence

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=E^{R,x}_{D}\ket{+_{x}}_{D_{x}}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=0.$
(6.5)

Next, suppose that $\pi_{x^{c}}\in S^{\prime}_{x,z}$. Then,

$\displaystyle{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}=\begin{cases}\ket{y\oplus
x,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{ if $t=\pi_{>x}^{-1}(z)$, }\\\
\ket{y\oplus\pi_{x^{c}}^{-1}(z),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}&\text{
otherwise.}\end{cases}$

It follows that

$\displaystyle{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\ket{y\oplus\pi_{x^{c}}^{-1}(z)}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle+\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{x^{c}}^{-1}(z)}_{Y}\Big{\rparen}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}},$

hence

$\displaystyle\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{x^{c}}^{-1}(z)}_{Y}\Big{\rparen}$
$\displaystyle\otimes\Big{\lparen}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{\sqrt{x}}\ket{+_{x}}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$

and finally

$\displaystyle\quad
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\Big{\lparen}\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{x^{c}}^{-1}(z)}_{Y}\Big{\rparen}\otimes\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=M_{YD_{x^{c}}}^{(z)}\left\lparen\frac{1}{\sqrt{x}}\ket{y}_{Y}\otimes\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{x}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}\right\rparen,$

where the operator $M^{\prime}_{YD_{x^{c}},z}$ is defined by
$M^{\prime}_{YD_{x^{c}},z}\ket{y}_{Y}\ket{\pi_{x^{c}}}_{YD_{x^{c}}}=\left\lparen\ket{y\oplus
x}_{Y}-\ket{y\oplus\pi_{x^{c}}^{-1}(z)}_{Y}\right\rparen\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
and has operator norm $\leq\sqrt{2}$. Thus:

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=M^{\prime}_{YD_{x^{c}},z}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{x}\\!\\!\\!\\!\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\\!\\!\\!\\!\\!\\!\\!\\!\ket{t}_{D_{x}}\Big{\rparen}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}.$
(6.6)

Finally, suppose that $\pi_{x^{c}}\in S^{\prime\prime}_{x,z}$. Then,

$\displaystyle{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y,t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}}=\ket{y\oplus\pi_{<x}^{-1}(t),t,\pi_{x^{c}}}_{YD_{x}D_{x^{c}}},$

hence

$\displaystyle\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\sum_{t=1}^{x}\ket{y\oplus\pi_{<x}^{-1}(t)}_{Y}$
$\displaystyle\otimes\left\lparen\ket{t}_{D_{x}}-\frac{1}{\sqrt{x}}\ket{+_{x}}_{D_{x}}\right\rparen\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}},$

and finally

$\displaystyle\quad
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{y}_{Y}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=\frac{1}{\sqrt{x}}\sum_{t=1}^{x}\ket{y\oplus\pi_{<x}^{-1}(t)}_{Y}\otimes\left\lparen\bm{1}_{\pi_{>x}(t)\in
R_{x}}\ket{t}_{D_{x}}-\frac{1}{x}\sum_{t^{\prime}\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t^{\prime}}_{D_{x}}\right\rparen\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}$
$\displaystyle=M^{\prime\prime}_{YD}\left\lparen\frac{1}{\sqrt{x}}\ket{y}_{Y}\otimes\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}\right\rparen,$

with
$M^{\prime\prime}_{YD}\ket{y,t,\pi_{x^{c}}}:=(\ket{y\oplus\pi_{<x}^{-1}(t)}_{Y}-\frac{1}{x}\sum_{t^{\prime}=1}^{x}\ket{y\oplus
t^{\prime}}_{Y})\ket{t}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}$, an operator of
norm $\leq 2$, hence

$\displaystyle
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}=M^{\prime\prime}_{YD}\frac{1}{\sqrt{x}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\otimes\ket{\pi_{x^{c}}}_{D_{x^{c}}}.$

Together with Eqs. 6.5 and 6.6, we obtain

$\displaystyle\quad\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle=\Big{\lVert}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\sum_{\pi_{x^{c}}}\lvert\pi_{x^{c}}\rangle\langle\pi_{x^{c}}\rvert_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\Big{\lVert}\sum_{\pi_{x^{c}}\in S^{\prime}_{x,z}\cup
S^{\prime\prime}_{x,z}}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq 2\,\Big{\lVert}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+2\,\Big{\lVert}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\ket{+_{x}}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=2\,\Big{\lVert}M^{\prime}_{YD_{x^{c}},z}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\frac{1}{\sqrt{x}}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{x}\\!\\!\\!\\!\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\\!\\!\\!\\!\\!\\!\\!\\!\ket{t}_{D_{x}}\Big{\rparen}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+2\,\Big{\lVert}M^{\prime\prime}_{YD}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\frac{1}{\sqrt{x}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\ket{\pi_{x^{c}}}_{D_{x^{c}}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{4}{x}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\Big{\lVert}\Big{\lparen}\bm{1}_{z\in
R_{x}}\ket{\pi_{>x}^{-1}(z)}_{D_{x}}-\frac{1}{x}\\!\\!\\!\\!\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\\!\\!\\!\\!\\!\\!\\!\\!\ket{t}_{D_{x}}\Big{\rparen}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+\frac{8}{x}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\Big{\lVert}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\ket{t}_{D_{x}}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{8}{x}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{3}}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+\frac{8}{x}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{+_{x}}_{D_{x}}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{8}{x}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{3}}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+\frac{8}{x}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}.$

By summing the above estimate over all $z>x$, we obtain

$\displaystyle\quad\sum_{z=x+1}^{N}\left\lVert
E^{R,x}_{D}{O}^{\mathsf{SPO},\mathrm{inv},z}_{YD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi_{z}}\right\rVert^{2}$
$\displaystyle\leq\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{3}}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle+\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle\leq\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}\in
S^{\prime}_{x,z}}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}+\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}\in
S^{\prime\prime}_{x,z}}\sum_{t\in[x]\cap\pi_{>x}^{-1}(R_{x})}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}$
$\displaystyle=\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}$
$\displaystyle+\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}.$

The last estimate follows as in part (ii).

By combining the results of (i), (ii), and (iii), we obtain the following
bound on the right-hand side Eq. 6.3:

$\displaystyle\left\lVert
E^{R,x}_{D}O^{\mathsf{SPO},\mathrm{inv}}_{XYD}\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\ket{\phi}\right\rVert$
$\displaystyle\leq\sqrt{\begin{aligned} &4\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{4}{x}\sum_{z=1}^{x-1}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{4}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}\\\
&+\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}+\frac{8}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}\\\
&+\frac{8}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\end{aligned}}$
$\displaystyle\leq 4\sqrt{\begin{aligned} &\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{1}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}+\frac{1}{x}\sum_{z=1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\bm{1}_{z\in
R_{x}}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\\\
&+\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\end{aligned}}$
$\displaystyle\leq 4\sqrt{\begin{aligned} &\frac{\lvert
R_{x}\rvert}{x}\,\lVert\ket{\phi_{x}}\rVert^{2}+\frac{1}{x^{2}}\frac{\lvert
R_{x}\rvert}{N}+\frac{1}{x}\sum_{z\in
R_{x}}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)<x}\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\\\
&+\frac{1}{x}\sum_{z=x+1}^{N}\sum_{\pi_{x^{c}}:\pi_{>x}^{-1}(z)=x}\lvert[x]\cap\pi_{>x}^{-1}(R_{x})\rvert\,\Big{\lVert}\bra{\pi_{x^{c}}}_{D_{x^{c}}}\ket{\phi_{z}}\Big{\rVert}^{2}\end{aligned}}.$

Now the lemma follows. ∎

As a consequence of the preceding lemmas, we obtain a bound that holds for any
query algorithm that makes $q$ queries.

######  Proposition 6.5.

Let $\mathcal{A}$ be a unitary query algorithm on registers $AXY$, where $X$
and $Y$ are $N$-dimensional registers, that gets query access to two oracles
that each act on $XY$. Let $\ket{\phi}_{AXYD}$ be the joint state of algorithm
and oracle defined by running $\mathsf{Init}^{\mathsf{SPO}}_{D}$ and then
$\mathcal{A}^{\mathsf{SPO}_{D}}$. Suppose that $\mathcal{A}$ makes in total
$q$ queries to its oracles. Then for any $x\in[N]$,

$\displaystyle\left\lVert E^{R,x}_{D}\ket{\phi}\right\rVert$
$\displaystyle\leq\sum_{j=1}^{q}\left\lparen\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(j)}}\right\rVert+4\sqrt{\zeta^{(j)}_{x}}\right\rparen$
$\displaystyle\leq\sqrt{2q\sum_{j=1}^{q}\left\lparen\frac{\lvert
R_{x}\rvert}{x}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(j)}}\right\rVert^{2}+16\zeta^{(j)}_{x}\right\rparen},$

where $\ket{\phi^{(j)}}_{AXYD}$ denotes the state right before the $j$-th
query of $\mathcal{A}^{\mathsf{SPO}_{D}}$ and where we defined
$\zeta^{(j)}_{x}:=\zeta_{\ket{\phi^{(j)}},x}$ as in Lemma 6.3 if the $j$-th
query is a forward query and otherwise
$\zeta^{(j)}_{x}:=\zeta^{\mathrm{inv}}_{\ket{\phi^{(j)}},x}$, as in Lemma 6.4.

###### Proof.

We will prove the first inequality, since the second follows directly using
the Cauchy-Schwartz inequality. To this end, we first observe that
$\lVert\bra{\pi}_{D}\ket{\phi^{(j)}}_{AXYD}\rVert^{2}=\frac{1}{N!}$ for every
$j\in[q]$ and $\pi\in S_{N}$. This is because the database is initialized in a
uniform superposition of the basis states $\ket{\pi}_{D}$, the query unitaries
$O^{\mathsf{SPO}}_{XYD}$ and $O^{\mathsf{SPO},\mathrm{inv}}_{XYD}$ are
controlled on $D$ in this basis and hence commute with a basis measurement,
and all other unitaries applied by $\mathcal{A}$ only act on registers $AXY$.
Thus the states $\ket{\phi^{(j)}}_{AXYD}$ satisfy the requirements of Lemmas
6.3 and 6.4 and hence we see that, for
$Q^{\mathsf{SPO}}\in\\{O^{\mathsf{SPO}},O^{\mathsf{SPO},\mathrm{inv}}\\}$ and
any $x\in[N]$,

$\displaystyle\left\lVert
E^{R,x}_{D}Q^{\mathsf{SPO}}_{XYD}\ket{\phi^{(j)}}\right\rVert-\left\lVert
E^{R,x}_{D}\ket{\phi^{(j)}}\right\rVert$ $\displaystyle\leq\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(j)}}\right\rVert+4\sqrt{\zeta^{(j)}_{x}}$
(6.7)

We will now show the following inequality for every $k\in\\{0,1,\dots,q\\}$,
with $\ket{\phi^{(q+1)}}:=\ket{\phi}$:

$\displaystyle\left\lVert E^{R,x}_{D}\ket{\phi^{(k+1)}}\right\rVert$
$\displaystyle\leq\sum_{j=1}^{k}\left\lparen\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(j)}}\right\rVert+4\sqrt{\zeta^{(j)}_{x}}\right\rparen,$
(6.8)

This will conclude the proof, since for $k=q$ it is the desired inequality. We
use induction over $k$. For $k=0$, the inequality holds trivially, since all
database registers are initialized in a uniform superposition and hence
$(I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}})\ket{\phi}=0$ and
$E^{R,x}_{D}\ket{\phi}=0$. For the induction step, note that for any $k>0$ we
can write

$\displaystyle
E^{R,x}_{D}\ket{\phi^{(k+1)}}_{AXYD}=E^{R,x}_{D}U_{AXY}{Q}^{\mathsf{SPO}}_{XYD}\ket{\phi^{(k)}}_{AXYD}=U_{AXY}E^{R,x}_{D}{Q}^{\mathsf{SPO}}_{XYD}\ket{\phi^{(k)}}_{AXYD},$

for some unitary $U_{AXY}$, where
$Q^{\mathsf{SPO}}\in\\{O^{\mathsf{SPO}},O^{\mathsf{SPO},\mathrm{inv}}\\}$
depending on $\mathcal{A}$’s choice for the $k$-th query. Here we have used
that the operators $U_{AXY}$ and $E^{R,x}_{D}$ act on disjoint registers.
Using first the unitary invariance of the norm, then Eq. 6.7, and finally the
induction hypothesis, we get

$\displaystyle\left\lVert E^{R,x}_{D}\ket{\phi^{(k+1)}}\right\rVert$
$\displaystyle=\left\lVert
E^{R,x}_{D}{Q}^{\mathsf{SPO}}_{XYD}\ket{\phi^{(k)}}_{AXYD}\right\rVert$
$\displaystyle\leq\left\lVert
E^{R,x}_{D}\ket{\phi^{(k)}}\right\rVert+\sqrt{\frac{\lvert R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(k)}}\right\rVert+4\sqrt{\zeta^{(k)}_{\ket{\phi^{(k)}},x}}$
$\displaystyle\leq\sum_{j=1}^{k}\left\lparen\sqrt{\frac{\lvert
R_{x}\rvert}{x}}\
\left\lVert\big{\lparen}I-\lvert+_{x}\rangle\langle+_{x}\rvert_{D_{x}}\big{\rparen}\ket{\phi^{(j)}}\right\rVert+4\sqrt{\zeta^{(j)}_{x}}\right\rparen.$

This concludes the proof of Eq. 6.8 and hence proof of the corollary. ∎

###  6.2 Bounding the Success Probability in Expectation

As discussed at the beginning of the section we will now lift the worst-case
bounds established in the previous section to the average case by running the
query algorithm with the _twirled_ permutation oracle for uniformly random
$\sigma,\tau\in S_{N}$ and also averaging over the choice of $x\in[N]$,