# The Space-Time Cost of Purifying Quantum Computations

Mark Zhandry
NTT Research

###### Abstract

General quantum computation consists of unitary operations and also
measurements. It is well known that intermediate quantum measurements can be
deferred to the end of the computation, resulting in an equivalent purely
unitary computation. While time efficient, this transformation blows up the
space to linear in the running time, which could be super-polynomial for low-
space algorithms. Fefferman and Remscrim (STOC’21) and Girish, Raz and Zhan
(ICALP’21) show different transformations which are space efficient, but blow
up the running time by a factor that is exponential in the space. This leaves
the case of algorithms with small-but-super-logarithmic space as incurring a
large blowup in either time or space complexity. We show that such a blowup is
likely inherent, demonstrating that any “black-box” transformation which
removes intermediate measurements must significantly blow up either space or
time.

##  1 Introduction

Measurements play a fundamental role in quantum computation. After all, it is
through measurements that useful classical information is extracted from the
hidden world of a quantum state. That said, formal treatments typically regard
a quantum computation as being _unitary_ , with any measurement only occurring
at the very end of the computation. For example, many algorithmic techniques
such as amplitude amplification [BH97, Gro97, BHMT02], numerous query
complexity lower bounds techniques [BBBV97, BBC+98, Amb00], and cryptographic
proofs involving rewinding [Wat09, Unr12, KSS+20, CMSZ22, LMS22], all assume
unitary algorithms whose states are pure. On the other hand, when designing
quantum algorithms it is often convenient to measure and/or discard quantum
states in the middle of a computation. Unitary computations may also be
desireable from a practical perspective, as implementing measurements can be
challenging, and may have energy-use implications (see Section 1.2 below).
Fortunately, assuming unitary computations can be justified by appealing to
the “Principle of Delayed Measurement,” which states that measurements in
general quantum computations can always be delayed until the end of the
computation with minimal time-complexity overhead. This is accomplished by,
instead of measuring the qubit, writing it into an external register that is
never touched again in the computation.

However, it has long been recognized that delaying measurements naively gives
a space complexity that is potentially as large as the time complexity, even
if the original computation used very little space. Thus, delaying
measurements potentially incurs a huge space-complexity overhead. Eliminating
measurements in a space-efficient way has therefore become a major
foundational question in quantum computation. This question may also be of
practical importance, as quantum storage will plausibly be a limiting resource
in future quantum computers.

Fefferman and Remscrim [FR21] and Girish, Raz and Zhan [GRZ21] give space-
optimal answers to this problem, showing that intermediate measurements can be
eliminated to yield a unitary computation with only a linear blowup in space
complexity. However, these results incur a potentially _exponential_ blowup in
time complexity: the new running time is ${\sf poly}(T,2^{S})$ where $T,S$ are
the original time and space complexities. This leaves the following important
open problem:

Can intermediate measurements be eliminated in a
simultaneously space- _and_ time-efficient manner?

Our work. Our main result is to show a _black-box barrier_ to achieving such a
result.

###  1.1 What is a Quantum Measurement, Anyway?

Before proceeding, we must mention the work of Girish and Raz [GR22], which
eliminates intermediate “measurements” from any space $S$, time $T$ quantum
algorithm, resulting in a space $O(S\log T)$, time $T\times{\sf poly}(S)$
algorithm without measurements. This seemingly resolves the central question
above positively. However, we note that their result only works for a very
particular notion of measurement.

Digging deeper, their model of computation allows for unitary gates, plus a
probabilistic measurement gate defined as mapping

$\alpha|0\rangle+\beta|1\rangle\mapsto\begin{cases}|0\rangle&\text{ with
probability }|\alpha|^{2}\\\ |1\rangle&\text{ with probability
}|\beta|^{2}\end{cases}\enspace.$

Crucially, the measurement gates in [GR22] do not output the classical
measurement result, and their model does not allow the resulting quantum
register to be discarded or reset to a fixed state.

Such a measurement gate as considered in [GR22] is _unital_ , meaning it maps
the totally mixed state to the totally mixed state of the same dimension.
Unitary operations are also unital, as is any combination of unital gates. As
such, their model of quantum computation with measurements only captures
unital computations.

Not all works treat measurements in this way, and many algorithms in the
literature are not described using such unital measurements. In fact,
measurements are most often depicted as producing a _classical_ output,
sometimes consuming the quantum state (such as with the POVM formalism) and
sometimes leaving behind a “collapsed” quantum register (such as with the
projective measurement formalism). A key distinguishing feature of classical
information is that it can be erased, something which is forbidden with unital
gates. One can also consider “reset” gates which reset a qubit to $|0\rangle$,
or even “discard” gates, which simply discards a register. A depiction of some
different kinds of measurement gates is given in Figure 1.

Figure 1:  Different kinds of measurement gates. Here, $|\psi\rangle$ is the
state being measured, $b$ is the probabilistic measurement outcome, and
$|\phi\rangle$ is the state that $|\psi\rangle$ collapses to when the
measurement outcome is $b$.

We note that the rightmost four types of measurement gates in Figure 1 — that
is, consuming the quantum state but outputing the classical measurement
result, outputting both the measurement result and the collapsed state,
resetting a qubit to $|0\rangle$, or simply discarding the state — are all
easily seen to be equivalent under appropriate assumptions111Assuming the
ability to (1) arbitrarily discard classical values, (2) have quantum gates
depend on previously obtained classical values, and (3) initialize new
registers.. In fact, unitary operations plus any one of these gates can be
used to implement any quantum channel, a consequence of Stinespring Dilation
[Sti55]. Moreover, all four appear frequently at least implicitly throughout
the literature in the descriptions of quantum algorithms. On the other hand,
the left-most type of gate — the one considered in [GR22] — which outputs the
collapsed state but no classical output, is unital, meaning it alone is not
enough to lift unitary operations to general channels. Thus, we see that
[GR22] only applies to a version of measurement that is potentially quite
limited.

More generally, one can consider a quantum computation involving general non-
unitary channel gates, of which measurements are only a specific example. The
goal is then to “purify” the computation, turning it into a computation
involving only unitary gates. [GR22] will fail on general channels. We note
that, in contrast to [GR22], [FR21] applies to quantum algorithms comprising
arbitrary (potentially non-unital) channels, at the cost of a potentially
exponential blowup in time complexity222[GRZ21], on the other hand, only
claims to apply to unital channels..

######  Remark 1.

We stress that [GR22] only claim their results work for their notion of
measurement gates. They also mention that with qubit reset gates, it is
trivial to simulate an intermediate measurement. But then the resulting
circuit would have qubit reset gates. Qubit reset could reasonably itself be
considered a “measurement” in a broader sense, since it is non-unitary and is
equivalent to various other versions of measurements. To try to avoid any
confusion, we will use the term “general quantum computation” to refer to
computations involving this more general view of measurement.

###  1.2 Relationship to Classical Reversible Computation

The task of eliminating intermediate measurements has an analog in classical
computation: namely, turning general (irreversible) classical computation into
reversible computation. One motivation for reversible computing is Landauer’s
principle [Lan61], which states that any irreversible logic operation requires
a certain minimum energy consumption, therefore imposing a limit on how much
efficiency can be improved. Meanwhile, no such energy consumption is inherent
to reversible operations, meaning in principle reversible computation could
have zero energy cost. In the quantum setting, measurements make a quantum
algorithm irreversible and Landauer’s principle would likewise impose a
minimal energy consumption. Meanwhile, unitary algorithms are reversible and
therefore “immune” to Landauer’s principle.

Analogous to the quantum setting, in the classical setting one can make a
general computation reversible trivially by blowing up the space to be linear
in the running time. An old classical question was whether anything better is
doable.

Bennett [Ben89] resolved this classical question, showing that space $S$ and
time $T$ general computation can be made reversible with space
$S^{\prime}=O(S\log T)$ and time $T^{\prime}={\sf poly}(T)$, thus preserving
time and space efficiency. One may therefore be tempted to apply similar
techniques to obtain an analogous result for eliminating quantum measurements.
We now explain, however, that this strategy fails.

Bennett’s result works roughly as follows. We first start with the trivial
conversion, which makes an irreversible computation reversible by simply
storing the complete program trace containing all prior states of the
algorithm. To reverse a step of the computation, one simply un-computes the
last state in the trace by re-computing it from the penultimate state. This of
course blows up the space from $S$ to $S\times T$. What Bennett does is
cleverly store only a few carefully selected prior states at a time, and show
that this is sufficient to reversibly simulate the original computation, with
only a modest blow-up in time complexity.

One may be tempted to adapt this technique in order to make a quantum
computation with measurements reversible in low space and time, thereby
removing intermediate measurements. We observe, however, that Bennett’s result
relies on a crucial feature of classical information that is no longer true
quantumly: that the classical intermediate states of the algorithm can be
copied — one copy going into the program trace, and another copy to continue
the computation. In contrast, the intermediate quantum states of a general
quantum algorithm will not be copy-able by the no-cloning theorem. Of course,
instead of copying, we could try to produce two copies of the state by running
the algorithm a second time from the beginning. This will potentially fail for
non-unitary algorithms, however, as intermediate measurements may have made
the intermediate states unpredictable. But even worse, running the algorithm a
second time will involve its own intermediate measurements that will need to
be eliminated. So it is not clear if copying the state by running the
algorithm from scratch a second time resulted in any progress. No-cloning thus
seems to invalidate this approach to eliminating quantum measurements.

###  1.3 Our Results

#### Formalizing Black Box Impossibilities.

Our goal is to show that there is no procedure to eliminate general quantum
measurements without blowing up either space or time. However, we observe that
an unconditional result is out of reach given the current state of complexity
theory. Indeed, if ${\sf BQL}={\sf BQP}$ (quantum log-space equals quantum
polynomial-time), then for any ${\sf BQP}$ computation, we can trivially
eliminate measurements using delayed measurements, thereby blowing up the
space, but then “compress” the space using the equivalence to ${\sf BQL}$.

We therefore provide a notion of “black-box” compilers for quantum circuits.
Such black-box compilers capture natural techniques such as all the quantum
compilers mentioned above [FR21, GRZ21, GR22] and the Principle of Delayed
Measurement. The classical version of our notion also captures [Ben89], and
therefore our notion of quantum black-box compiler captures natural attempts
to adapt [Ben89] to the quantum setting. We note that our notion of black-box
is somewhat different than notions studied in cryptography [IR89]. Indeed, all
the compilers mentioned above inherently operate on the computation at the
circuit level, meaning the compilers get to “see” the circuit representation.
In contrast, black-box techniques in cryptography treat the inputs as a
monolithic computation, and the techniques are explicitly forbidden from
seeing the circuit representation. Our key insight is that natural circuit
compilers like those discussed above do make use of the circuit
representation, but are essentially agnostic to the gates used in the original
computation, giving equally good space- and time-bounds regardless of the gate
set used. We therefore define black-box compilers, roughly, as those that work
equally well for _any_ set of gates.

#### Our Main Theorem.

We can now state our main theorem:

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

For any black-box compiler mapping space $S$, time $T$ general quantum
computation to space $S^{\prime}$, time $T^{\prime}$ unitary computation,
either $S^{\prime}=\Omega(T)$ or $T^{\prime}=2^{\Omega(S)}$.

We note that the Principle of Delayed Measurement and [FR21] demonstrate that
Theorem 1.1 is essentially tight333Assuming the typical parameter setting
where $T\leq 2^{O(S)}$.. We prove our theorem by exhibiting, for any $S,T$, a
set of unitary gates and a space $S$, time $T$ general quantum computation
(with measurements) relative to these gates, such that any unitary simulation
using these gates requires space $S^{\prime}=\Omega(T)$ or time
$T^{\prime}=2^{\Omega(S)}$. Theorem 1.1 also demonstrates that [GR22] cannot
be generalized to handle arbitrary measurement gates.

#### New Space Lower Bound Technique.

In order to prove Theorem 1.1, we need a lower-bound technique that works on
unitary computation, but crucially fails to lower bound general quantum
computation containing measurements. After all, Theorem 1.1 requires the
existence of a low-space general quantum algorithm with measurements for the
task. Prior quantum space lower bounds (e.g. [KvdW07, NABT15, CGLQ20, HM23])
typically work similarly well for both general quantum algorithms and those
that make no measurements. Indeed, this would be considered a _feature_ in the
usual setting of space lower bounds as it makes them more general. But for us,
it means we need a fundamentally new lower-bound technique.

Our lower bound technique works by simulating a quantum gate using a stateful
simulator. The simulator will start out having some space. Then we show that
for any algorithm solving some task, the size of the simulator’s state must
decrease by a certain amount. As the joint state of the simulator and any
algorithm that does not make measurements is pure, we argue that the total
joint state size must not decrease from its original value. But since the
simulator’s state decreased in size, this means the algorithm’s state size
increased. Observe that this technique does not apply to algorithms which may
make measurements, as such measurements result in a joint operation that is
non-unitary and can decrease in size.

##  2 Technical Overview

#### Our Construction.

We now give an overview of our results and techniques. Motivated by the
challenges of adapting [Ben89] to remove quantum measurements, our idea is to
design a computation where intermediate states are unclonable. In our case,
the intermediate states are predictable. But only part of the intermediate
state, call it $|\psi\rangle$, is useful, and the other part, say
$|\phi\rangle$, is a useless byproduct of the computation of $|\psi\rangle$.
If measurements are allowed — or more precisely, the ability to reset
registers — then $|\phi\rangle$ can always be reset before proceeding. But if
we demand a unitary version of the computation, the only way to eliminate
$|\phi\rangle$ appears to be to un-compute it. But in principle, the only way
to uncompute $|\phi\rangle$ is to actually undo the joint computation of
$|\psi\rangle$ and $|\phi\rangle$. Remember that $|\psi\rangle$ is unclonable;
this means uncomputing $|\psi\rangle$ actually just returned to a previous
point in the computation, and we have not actually made any progress. If one
tries to compute $|\psi\rangle$ a second time from scratch, this will work,
but now there are two $|\phi\rangle$ states that need to be un-computed. There
seems to be no unitary way of computing $|\psi\rangle$ without also having
$|\phi\rangle$ be present. By having many intermediate steps produce useless
side states $|\phi_{1}\rangle,|\phi_{2}\rangle,\cdots$ that all must be
present to make progress, we force any unitary version of the computation to
be large. Meanwhile, with measurements we can simply reset all the
$|\phi_{i}\rangle$ as they are computed to re-use their space, keeping the
overall space small. This is depicted in Figure 2.

Figure 2:  Our task that can be computed in low time and space with
measurements, but requires large space or time without.

The final step of the computation will be to output $|\psi_{t}\rangle$ for
some $t$, or potentially some other value that requires first computing
$|\psi_{t}\rangle$. We observe that an algorithm that can make general quantum
measurements can easily compute $|\psi_{t}\rangle$ in low space by iteratively
computing $|\psi_{i}\rangle|\phi_{i}\rangle$ and discarding
$|\phi_{i}\rangle$.

#### Formalizing Black Box Compilers.

As discussed earlier, it is consistent with current knowledge (even if
considered unlikely) that ${\sf BQL}={\sf BQP}$, in which case one can
eliminate measurements in a space- and time-efficient manner by first blowing
up the space using delayed measurements, and then generically reducing the
space back. However, such a mechanism would be non-black-box, in the sense
that it would have to inherently use the circuit representation of the unitary
${\mathbf{O}}$, the computation that jointly computes
$|\psi\rangle,|\phi\rangle$.

We therefore imagine a class of black-box compilers, which work regardless of
${\mathbf{O}}$. That is, any such compiler takes as input a circuit $C$
involving ${\mathbf{O}}$ gates and measurements, and produces a new unitary
circuit $C^{\prime}$ using ${\mathbf{O}}$ (and potentially other ordinary
unitary gates) but no measurement gates. $C^{\prime}$ must have
(approximately) the same functionality as $C$. The compiler must work for
_any_ unitary ${\mathbf{O}}$, though we allow the compiler to have complete
knowledge of ${\mathbf{O}}$ and potentially have the choice of circuit
$C^{\prime}$ depend on ${\mathbf{O}}$. The aforementioned compilers for
eliminating measurements such as delayed measurements, [FR21, GRZ21, GR22], or
any strategy similar to [Ben89] are all black box in this sense. We explain in
slightly more detail how our notion of black-box captures these works in
Section 4.

By treating ${\mathbf{O}}$ as a black box, we have now turned a potentially
intractable problem involving at a minimum quantum complexity lower-bounds
into an oracle problem, which may be tractable.

######  Remark 2.

Note that one can use the space-efficient version of the Solovay-Kitaev
Theorem ([vMW12] Theorem 7) to replace any constant-sized set of unitary gates
with any other constant-sized set of unitary gates in a space- and time-
efficient manner. However, this transformation is only efficient when fixing
the gate sets and then considering the complexities asymptotically; the
constants in the asymptotics will depend on the gate sets in question. In
particular, if we let $n$ be the number of qubits ${\mathbf{O}}$ acts on,
applying [vMW12] to replace ${\mathbf{O}}$ with gates from a fixed universal
gate set will blow up the running time to $2^{\Omega(n)}$. This is “constant”
if ${\mathbf{O}}$ and $n$ are fixed, but is exponential if we allow $n$ to
vary. In our case, we set $n=S$, the space of $C$, in which case applying
[vMW12] gives a running time of at least $2^{\Omega(S)}$.

Our notion of a black-box compiler requires the space and time complexities
$S^{\prime},T^{\prime}$ of $C^{\prime}$ to be fixed functions
$S^{\prime}=S^{\prime}(S,T),T^{\prime}=T^{\prime}(S,T)$ of the space and time
complexities $S,T$ of $C$. The functions $S^{\prime},T^{\prime}$ have to be
the same, regardless of the gate set used by $C$ or how $C$ is constructed. We
stress, however, that our notion allows $C^{\prime}$ to depend arbitrarily on
$C$ and its gate set, with the only restriction being on the space and time
complexities. Restricting the space and time complexities in this way seems
inherent: if $S^{\prime},T^{\prime}$ as functions of $S,T$ were allowed to
depend on the gate set, then we can apply the space-efficient Solovay-Kitaev
Theorem to move to a fixed universal gate set. Then, if ${\sf BQL}={\sf BQP}$,
we can eliminate intermediate measurements in low space and time as explained
above.

#### Proving Large Unitary Space.

We now turn to proving that any unitary computation which computes
$|\psi_{t}\rangle$ efficiently must have large space, specifically we prove
that $\Omega(t\times S)$ unitary space is necessary, where $S$ is the space of
the non-unitary computation in Figure 2 and is also proportional to the size
of $|\phi_{t}\rangle$. Note that our modeling has the size of the non-unitary
circuit be $T:=t\times S$, as resetting $\Theta(S)$ qubits in our model
requires $\Theta(S)$ gates. Our $\Omega(t\times S)$ unitary space lower bound
then implies that any efficient _unitary_ computation of $|\psi_{t}\rangle$
requires space $\Omega(T)$, matching what one gets via delayed measurements.

More specifically, our goal is to show, roughly, that the only way to compute
$|\psi_{t}\rangle$ efficiently with unitaries requires computing and storing
each of $|\phi_{1}\rangle,\cdots,|\phi_{t}\rangle$. The challenge is, of
course, that the algorithm can apply arbitrary unitaries to the
$|\phi_{i}\rangle$, including applications of ${\mathbf{O}}$. So we cannot
hope to say that each of the $|\phi_{i}\rangle$ are explicitly stored in
memory, as they may be hidden behind a more complex computation.

Another challenge, as mentioned previously, is that existing quantum space
lower bounds make no distinction between unitary and non-unitary algorithms.
Since we have a low-space non-unitary computation, any attempt to use existing
techniques would necessarily fail at giving meaningful unitary lower bounds.

#### Simulating ${\mathbf{O}}$ Statefully.

We show how to simulate the oracle ${\mathbf{O}}$. Our simulator will only use
several copies of each of $|\phi_{1}\rangle,\cdots,|\phi_{t}\rangle$ and
$|\psi_{1}\rangle,\cdots,|\psi_{t}\rangle$. Essentially, whenever the gate
must output $|\psi_{i}\rangle|\phi_{i}\rangle$, instead of constructing the
state our simulator will simply swap in one of its copies, thereby reducing
the number of copies the simulator has. Likewise, whenever the gate takes as
input $|\psi_{i}\rangle$ and must eliminate it by uncomputing it, the
simulator instead moves $|\psi_{i}\rangle$ from the algorithm’s registers to
the simulator’s list of copies.

Importantly, as any supposed algorithm makes progress towards computing
$|\psi_{t}\rangle$, we show that if the states are Haar random, then the
number of copies of the various $|\phi_{i}\rangle$ the simulator has must
_decrease_. But if the algorithm is unitary, the overall joint state size can
never decrease, since the initial copies of the various $|\phi_{i}\rangle$
cannot be destroyed by unitary computation. Therefore, if the simulator’s
storage decreases, the algorithm’s storage must increase. Observe that this
space bound does _not_ apply to algorithms with measurements, which can easily
destroy copies of $|\phi_{i}\rangle$ by measuring/resetting them. This means
the joint system of the non-unitary algorithm and simulator could decrease in
space. Indeed, this is what happens in our low-space measurement-based
algorithm.

######  Remark 3.

Our arguments above only apply to algorithms with running time at most
$2^{O(S)}$; this is inherent as our black-box notion captures the low-space
algorithm of [FR21], which runs in time $2^{\Omega(S)}$. The restriction to
running time $2^{O(S)}$ appears in two places. First, the claim that the
number of copies of a state cannot be unitarily changed only holds for a
bounded number of copies, since beyond $2^{O(S)}$ copies it is possible to
perform tomography on the state. Our simulator must have a number of copies
that is at least the number of queries made to ${\mathbf{O}}$, so our
arguments only apply if the number of queries is bounded. The second place
where we assume a bounded running time is that our simulation introduces a
small error of order $2^{-O(S)}$ for each query to ${\mathbf{O}}$, and after
$2^{O(S)}$ queries the error becomes $O(1)$, meaning the simulation failed.

##  3 Preliminaries

#### Quantum Computation.

A quantum system is associated with a finite-dimensional complex Hilbert space
${\mathcal{H}}$. A (pure) state over a quantum system is a unit column vector
$|\psi\rangle$ with $\||\psi\rangle\|=1$. The Hermitian transpose of
$|\psi\rangle$ is denoted $\langle\psi|$. A probability distribution over pure
states is a mixed state, and is characterized by its density matrix
$\rho=\sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$ where $p_{i}$ is the
probability of $|\psi_{i}\rangle$. Note that ${\sf Tr}(\rho)=1$. When the
distribution over $i$ is clear, we can also write
$\rho=\mathop{\mathbb{E}}_{i}[|\psi_{i}\rangle\langle\psi_{i}|]$.

Given a complex matrix ${\mathbf{U}}$, let ${\mathbf{U}}^{\dagger}$ be the
Hermitian transpose. A unitary operation is a complex square matrix
${\mathbf{U}}$ such that ${\mathbf{U}}{\mathbf{U}}^{\dagger}={\mathbf{I}}$.
Unitary evolution of a quantum system is described by a unitary ${\mathbf{U}}$
that transforms $|\psi\rangle$ into ${\mathbf{U}}|\psi\rangle$.

General _non-unitary_ evolution of a quantum system is described by a
completely-positive trace-preserving (CPTP) map $M$ from system
${\mathcal{H}}_{\sf in}$ to ${\mathcal{H}}_{\sf out}$. Such maps are in
particular linear on density matrices, and trace preserving: ${\sf
Tr}(M(\rho))={\sf Tr}(\rho)=1$. Given a joint system
${\mathcal{A}}\otimes{\mathcal{B}}$, a special CPTP map is the partial trace
${\sf Tr}_{\mathcal{B}}$ which maps ${\mathcal{A}}\otimes{\mathcal{B}}$ to
${\mathcal{A}}$, with the property that ${\sf
Tr}_{\mathcal{B}}(\rho_{\mathcal{A}}\otimes\rho_{\mathcal{B}})=\rho_{\mathcal{A}}$
for any mixed states $\rho_{\mathcal{A}},\rho_{\mathcal{B}}$ over
${\mathcal{A}},{\mathcal{B}}$ respectively. By linearity, ${\sf
Tr}_{\mathcal{B}}$ can be extended to all mixed state inputs. If we apply
${\sf Tr}_{\mathcal{B}}$ to a quantum state, we will say that ${\mathcal{B}}$
has been traced out.

Given any unitary operation ${\mathbf{U}}$ on ${\mathcal{A}}$, we can extend
it to a unitary operation ${\mathbf{U}}\otimes{\mathbf{I}}$ on
${\mathcal{A}}\otimes{\mathcal{B}}$ by acting as the identity on
${\mathcal{B}}$. Likewise, a CPTP map $M$ from ${\mathcal{A}}$ to
${\mathcal{A}}^{\prime}$ can be extended to a CPTP map from
${\mathcal{A}}\otimes{\mathcal{B}}$ to
${\mathcal{A}}^{\prime}\otimes{\mathcal{B}}$ by acting as the identity on
${\mathcal{B}}$. In both cases, we will abuse terminology and say that
${\mathbf{U}}$ or $M$ is acting on ${\mathcal{A}}\otimes{\mathcal{B}}$.

#### Distance.

The _trace distance_ between two mixed quantum states $\rho,\rho^{\prime}$
over the same system ${\mathcal{H}}$ is given by
$TD(\rho,\rho^{\prime})=\frac{1}{2}{\sf
Tr}(\sqrt{(\rho-\rho^{\prime})\cdot(\rho-\rho^{\prime})})$. The trace distance
is equivalent to the optimal distinguishing probability between the two
states. The distance between two distributions $D,D^{\prime}$, denoted
$\Delta(D,D^{\prime})$, is given by $\frac{1}{2}\sum_{x}|\Pr[x\leftarrow
D]-\Pr[x\leftarrow D^{\prime}]|$.

#### Quantum circuits.

A _qubit_ is the special case where ${\mathcal{H}}$ has dimension 2, often
denoted ${\mathcal{H}}_{2}$. We will typically consider Hilbert spaces that
are the product of many qubits: ${\mathcal{H}}={\mathcal{H}}_{2}^{\otimes n}$.

We now describe our non-uniform model of computation using quantum circuits,
following [AKN98]. Let ${\mathcal{G}}$ be a fixed, finite set of operations.
We will assume each operation in ${\mathcal{G}}$ is length preserving, meaning
it makes $k$ qubits to $k$ qubits for some $k$ (different operations in
${\mathcal{G}}$ may have different $k$). We will call the elements of
${\mathcal{G}}$ _gates_. We will always assume ${\mathcal{G}}$ is closed under
Hermitian transpose. A unitary circuit is composed of a sequence of
applications of unitary gates, and a general quantum circuit is composed of a
sequence of applications of general quantum gates. The qubits are then
partitioned into three sets: ${\mathcal{H}}_{\sf in}$, which contains the
input state, ${\mathcal{H}}_{\sf out}$, which will contain the output state,
and ${\mathcal{H}}_{\sf work}$, which will contain private work space. The
classical input $x$ is loaded into the register ${\mathcal{H}}_{\sf in}$,
denoted as $|x\rangle$, and then ${\mathcal{H}}_{\sf out}$ and
${\mathcal{H}}_{\sf work}$ are initialized to fixed states, which will both be
denoted $|0\rangle$. At the end of the computation, ${\mathcal{H}}_{\sf in}$
and ${\mathcal{H}}_{\sf work}$ are traced out and ${\mathcal{H}}_{\sf out}$ is
measured to get the final output.

For a quantum circuit $C$ and a classical input $x$, we will let $C(x)$ denote
the distribution of outputs obtained by computing $C|x\rangle$ and then
measuring ${\mathcal{H}}_{\sf out}$.

In general, we will consider the gate set as being a property of a quantum
circuit $C$, which we will denote as ${\mathcal{G}}(C)$. We note that we allow
$C$ to not use all the gates in the gate set, meaning ${\mathcal{G}}(C)$ may
include gates not used in $C$.

#### Complexity Metrics.

The _time complexity_ of a quantum circuit is the number of gates in the
circuit. The _space complexity_ is the sum of the number of qubits in
${\mathcal{H}}_{\sf in},{\mathcal{H}}_{\sf out},{\mathcal{H}}_{\sf work}$.

######  Remark 4.

The above space metric is not well-suited to the regime of space sub-linear in
the input size. But this can be easily handled in a number of ways, such as by
having ${\mathcal{H}}_{\sf in}$ only being used as control qubits, and not
counting it in the space. These details will not be important for us.

######  Remark 5.

It is also possible to consider uniform quantum computational models [Wat04,
vMW12, Ta-13]. However, as we discuss in Section 4, working in a non-uniform
model makes our result stronger, as we are interested in lower-bounds.

#### Oracle-assisted Circuits.

An oracle-assisted circuit is one that may make queries to a unitary
${\mathbf{U}}$. For oracle-assisted circuits, the time complexity is the total
of the number of gates and number of oracle calls to ${\mathbf{U}}$. The space
complexity is still the number of qubits in ${\mathcal{H}}_{\sf
in},{\mathcal{H}}_{\sf out},{\mathcal{H}}_{\sf work}$. These time and space
complexities do _not_ include the time and space used internally by
${\mathbf{U}}$.

#### Universality.

A _universal unitary gate set_ is a finite set of unitary gates
${\mathcal{G}}$, such that any unitary operation can be approximately
arbitrarily closely by circuits over ${\mathcal{G}}$. A _universal general
gate set_ is a finite set of general gates ${\mathcal{G}}$, such that any CPTP
map can be approximated arbitrarily closely by circuits over ${\mathcal{G}}$.
A _universal measurement set_ is a set of gates ${\mathcal{M}}$, such that for
any universal unitary gate set ${\mathcal{G}}$,
${\mathcal{G}}\cup{\mathcal{M}}$ is a universal general gate set. An example
of a universal measurement set is ${\mathcal{M}}=\\{{\sf Trash},{\sf
Init}\\}$, where ${\sf Trash}$ traces out a qubit (outputting nothing) and
${\sf Init}$ initializes a new qubit to a fixed state typically denoted as
$|0\rangle$. Note that any universal general gate set is also a universal
measurement set. A _proper_ universal general gate set has the form
${\mathcal{G}}\cup{\mathcal{M}}$ where ${\mathcal{G}}$ is a universal unitary
gate set and ${\mathcal{M}}$ is a universal measurement set.

Note that the unital measurement gate from [GR22] is _not_ universal, since
when combined with unitary gates it only gives unital circuits.

#### Symmetric Subspaces

For a Hilbert space ${\mathcal{H}}$ and positive integer $\ell$, let ${{\sf
Sym}}^{\ell}{\mathcal{H}}$ be the symmetric subspace of $\ell$ copies of
${\mathcal{H}}$, which is the space of all states that are invariant under
permuting the $\ell$ copies of ${\mathcal{H}}$. The symmetric subspace has
dimension ${\sf Dim}\left({{\sf Sym}}^{\ell}{\mathcal{H}}\right)=\binom{{\sf
Dim}({\mathcal{H}})+\ell-1}{\ell}$. We will somewhat abuse notation, and also
let ${{\sf Sym}}^{\ell}$ denote the projection of the space
${\mathcal{H}}^{\otimes\ell}$ onto the symmetric subspace ${{\sf
Sym}}^{\ell}{\mathcal{H}}$.

#### Haar Random States.

We will avoid specifying the formal definition of Haar random states, but will
make use of a few key facts. First is that the density matrix of $\ell$ copies
of a Haar random state over system ${\mathcal{H}}$ is identical to that of the
totally mixed state over ${{\sf Sym}}^{\ell}{\mathcal{H}}$. Second is a no-
cloning statement, which says that the optimal probability of constructing
$|\psi\rangle^{\otimes(\ell+1)}$ from $|\psi\rangle^{\otimes\ell}$ is at most
the ratio of the dimensions of the symmetric subspaces ${{\sf
Sym}}^{\ell}{\mathcal{H}}$ and ${{\sf Sym}}^{\ell+1}{\mathcal{H}}$, which
works out to be $\ell/({\sf Dim}({\mathcal{H}})+\ell)$ [Wer98].

#### Reflections and Projections.

For a state $|\psi\rangle$, let
$P_{|\psi\rangle}:=1-2|\psi\rangle\langle\psi|$ be the reflection about
$|\psi\rangle$. We observe that $P_{|\psi\rangle}$ can be used to implement
the map satisfying $|\psi\rangle|b\rangle\mapsto|\psi\rangle|b\oplus 1\rangle$
and identity on all states orthogonal to $|\psi\rangle|b\rangle$. Indeed, we
can apply the Hadamard transform to $|b\rangle$, obtaining
$\frac{1}{\sqrt{2}}|0\rangle+(-1)^{b}\frac{1}{\sqrt{2}}|1\rangle$. Then
controlled on the bit in this register, we apply $P_{|\psi\rangle}$. In the
case where the state is $|\psi\rangle$, then $|0\rangle$ maps to $|0\rangle$
while $|1\rangle$ maps to $-|1\rangle$. This maps the overall qubit state to
$\frac{1}{\sqrt{2}}|0\rangle+(-1)^{b+1}\frac{1}{\sqrt{2}}|1\rangle$; applying
Hadamard one more time give $|b\oplus 1\rangle$. On the other hand, if the
state is $|\tau\rangle$ orthogonal to $|\psi\rangle$, then $P_{|\psi\rangle}$
acts as the identity.

Using the latter formulation, we can also implement the projective measurement
$|\psi\rangle\langle\psi|$ by simply initializing the qubit to 0, applying the
transformation above, and then measuring the qubit. If we get a 1, we know the
state is $|\psi\rangle$, while a zero tells us that the state is orthogonal to
$|\psi\rangle$. We will abuse notation, and let $P_{|\psi\rangle}$ whichever
version (reflection, $|\psi\rangle|b\rangle\mapsto|\psi\rangle|b\oplus
1\rangle$, or projection) is most convenient.

#### Queries to Classical Functions.

Given a classical function $O:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, we can
have an algorithm make queries to $O$. Do do so, we turn $O$ into a unitary
${\mathbf{O}}$ that acts on ${\mathcal{H}}_{2}^{\otimes
m}\otimes{\mathcal{H}}_{2}^{\otimes n}$ as ${\mathbf{O}}|x,y\rangle=|x,y\oplus
O(x)\rangle$. Then any query to $O$ simply applies the unitary ${\mathbf{O}}$.

#### Some Useful Lemmas.

Consider the state $|\phi_{t}\rangle=\sum\alpha_{x,y}|x,y\rangle$ of a quantum
query algorithm when it makes its $t$-th quantum query. Define
$q_{x}(|\phi_{t}\rangle)$ to be the magnitude squared of $x$ in the
superposition of query $t$, that is
$q_{x}(|\phi_{t}\rangle)=\sum_{y}|\alpha_{x,y}|^{2}$. Call this the query
magnitude of $x$. Let $q_{x}=\sum_{t}q_{x}(|\phi_{t}\rangle)$ be the total
query magnitude of $x$. For a set $S$, let $q_{S}=\sum_{x\in S}q_{x}$ be the
total query magnitude of $S$.

######  Lemma 3.1 ([BBBV97] Theorem 3.1).

Suppose $\||\phi\rangle-|\psi\rangle\|\leq\epsilon$. Then performing any
measurement measurement on $|\phi\rangle$ and $|\psi\rangle$ yields
distributions with statistical distance at most $4\epsilon$.

######  Lemma 3.2 ([BBBV97] Theorem 3.3).

Let ${\mathcal{A}}$ be a quantum query algorithm making $T$ queries to an
oracle $O$. Let $\epsilon>0$ and let $S$ be a set such that
$q_{S}\leq\epsilon$. Let $O^{\prime}$ be another oracle that is identical to
$O$ on all points not in $S$. Let $|\phi\rangle,|\psi\rangle$ be the final
state of ${\mathcal{A}}$ when given $O,O^{\prime}$, respectively. Then
$\||\phi\rangle-|\psi\rangle\|\leq\sqrt{T\epsilon}$

##  4 Quantum Circuit Compilers and Black Box Purifiers

Here, we give our notion of black box impossibility for circuit compilers. A
_property_ of a quantum circuit is a function ${\mathcal{P}}(C)\in\\{0,1\\}$.
We say that $C$ has property ${\mathcal{P}}$ if ${\mathcal{P}}(C)=1$.
Equivalently, a property is a subset of all possible quantum circuits. Example
properties include:

  * •

The “all circuits” property $P_{\mathbb{1}}$ defined as $P_{\mathbb{1}}(C)=1$
for all $C$.

  * •

The unitary property ${\mathcal{P}}_{\sf Unitary}$, where ${\mathcal{P}}_{\sf
Unitary}(C)=1$ if and only if $C$ only makes use of unitary gates444Note that
$C$ may compute a unitary operation even if it contains non-unitary gates. In
such a case we would say that ${\mathcal{P}}_{\sf Unitary}(C)=0$ despite $C$
being a unitary operation..

  * •

The size property ${\mathcal{P}}_{{\sf Size}(S)}$ property, where
${\mathcal{P}}_{{\sf Size}(S)}(C)=1$ if and only if $C$ has size at most $S$.
Likewise we can define the time property ${\mathcal{P}}_{{\sf Time}(T)}$.

  * •

Fix a proper universal general gate set ${\mathcal{G}}_{0}$555Recall that
being proper means that ${\mathcal{G}}_{0}$ can be divided into a universal
unitary gate set and a universal measurement set.. The “normal form” property
${\mathcal{P}}_{\sf Normal}$ (with respect to ${\mathcal{G}}_{0}$) is the
property that (1) ${\mathcal{G}}_{0}\subseteq{\mathcal{G}}(C)$, and (2) that
${\mathcal{G}}(C)\setminus{\mathcal{G}}_{0}$ contains only unitary gates. In
other words, a normal form circuit is a circuit whose non-unitary gates must
come from ${\mathcal{G}}_{0}$, but the unitary gates could be arbitrary.

  * •

Any combination of the above properties, such as being unitary and time $T$,
which would be denoted ${\mathcal{P}}_{\sf Unitary}\cap{\mathcal{P}}_{{\sf
Time}(T)}$.

######  Definition 4.1.

Let ${\mathcal{P}},{\mathcal{Q}}$ be two properties of quantum circuits. A
${\mathcal{P}}\Rightarrow{\mathcal{Q}}$ compiler is a function ${\mathcal{C}}$
from circuits to circuits such that:

  * •

Same gate sets: For any quantum circuit $C$,
${\mathcal{G}}({\mathcal{C}}(C))={\mathcal{G}}(C)$ 666Recall that
$C,{\mathcal{C}}(C)$ do not need to use all gates in their gate set..

  * •

Close functionalities: For any $C$ and any classical string $x$,
$\Delta(\;C(x)\;,\;{\mathcal{C}}(C)(x)\;)\leq 1/3$.

  * •

Property transforming: For any $C$, if ${\mathcal{P}}(C)=1$, then
${\mathcal{Q}}({\mathcal{C}}(C))=1$.

The choice of the constant $1/3$ is arbitrary, and typically only affects an
overall constant factor in the complexity of ${\mathcal{C}}(C)$, which would
be absorbed into Big-Oh notation. Note that any compiler, by definition, maps
normal-form circuits to normal-form circuits, since the input and output
circuits have the same gate set.

######  Remark 6.

Typically, one would want a circuit transformation to approximately preserve
the action of $C$ on any _quantum_ input. However, as we are interested in
low-bounds here, only asking for approximately preservation on classical
inputs will make our results stronger.

#### Purifiers.

With our notion of compilers in hand, we are now ready to give our notion of a
purifier. A purifier transforms any quantum circuit with measurement gates (or
more generally non-unitary gates) into a circuit with only unitary gates. A
_black-box_ purifier, in some sense, successfully removes non-unitary gates,
no matter what gate set the original circuit used. More precisely:

######  Definition 4.2.

Fix a universal general gate set ${\mathcal{G}}_{0}$. A _black-box purifier_
is a ${\mathcal{P}}_{\sf Normal}\Rightarrow{\mathcal{P}}_{\sf Unitary}$
compiler. We can also consider purifiers that maintain bounds on the time
and/or space:

  * •

For a function $S^{\prime}:\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}$, a _black-
box $S^{\prime}$-space purifier_ is a ${\mathcal{P}}_{\sf
Normal}\cap{\mathcal{P}}_{{\sf Space}(S)}\Rightarrow{\mathcal{P}}_{\sf
Unitary}\cap{\mathcal{P}}_{{\sf Space}(S^{\prime}(S))}$ compiler, for any
$S>0$.

  * •

For a function $T^{\prime}:\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}$, a _black-
box $T^{\prime}$-time purifier_ is a ${\mathcal{P}}_{\sf
Normal}\cap{\mathcal{P}}_{{\sf Time}(T)}\Rightarrow{\mathcal{P}}_{\sf
Unitary}\cap{\mathcal{P}}_{{\sf Time}(T^{\prime}(T))}$ compiler, for any
$T>0$.

  * •

For functions
$S^{\prime},T^{\prime}:(\mathbb{Z}^{+})^{2}\rightarrow\mathbb{Z}^{+}$, a
_black-box $(S^{\prime},T^{\prime})$-space-time purifier_ is a
${\mathcal{P}}_{\sf Normal}\cap{\mathcal{P}}_{{\sf
Space}(S)}\cap{\mathcal{P}}_{{\sf Time}(T)}\Rightarrow{\mathcal{P}}_{\sf
Unitary}\cap{\mathcal{P}}_{{\sf
Space}(S^{\prime}(S,T))}\cap{\mathcal{P}}_{{\sf Time}(T^{\prime}(S,T))}$
compiler.

In other words, a black box purifier maps any quantum circuit that is in
normal form into one that is unitary (and also in normal form, since compilers
preserve gate sets). A black box purifier, in other words, removes the non-
unitary gates, and must do so using the unitary part of the original gate set,
_regardless_ of the choice of unitaries. We note, however, that our definition
allows the purifier to depend arbitrarily on the gate set and circuit inputs.
The only requirement is that it must work no matter the choice of unitaries in
the original gate set. An $S^{\prime}$ space, $T^{\prime}$ time or
$(S^{\prime},T^{\prime})$ space-time purifier must do this while outputting
circuits with space $S^{\prime}$ and/or time $T^{\prime}$.

#### Purifies from the literature.

We now explain our notion of black box purifier captures existing approaches
for removing intermediate measurements from quantum computation:

  * •

[GR22]: This work takes the original quantum circuit $C$, and generates a new
quantum circuit $C^{\prime}$ as follows: it takes every measurement gate, and
replaces it essentially with a random phase gate. The randomness for the phase
gate is then derived by a suitable explicit pseudorandom generator (PRG). As a
consequence, the “unitary part” of $C$ is entirely un-touched, and we only
need to add the PRG computation which can be expressed in any universal gate
set. As long as the gate set of $C$ is proper, this PRG computation can be
expressed in terms of the unitary gates from the gate set. Thus, their result
is black-box.

  * •

[FR21, GRZ21]: These works follow an approach where the computation is broken
into a sequence of arbitrary channels $\Phi_{1},\cdots\Phi_{T}$ 777In [FR21],
the channels are truly arbitrary. In [GRZ21], the channels are restricted to
being unital. This restriction does not affect the discussion here.. These
channels are then expressed as matrices representing the transformations on
the underlying Hilbert spaces, and then multiplied using a low-space
multiplication algorithm to get the final result. Arbitrary channels can
implement any arbitrary gate set, and the algorithm for low-space matrix
multiplication can be implemented in any universal gate set. Thus we see that
their results are also black-box. Note here that these results appear to be
“non-black-box” in the sense that they make explicit use of the matrix
representation of the gates. However, they are still “black-box” in our sense,
as we allow the circuit $C^{\prime}$ to depend arbitrarily on $C$ and it’s
gates, as long as the transformation is possible _for any_ starting $C$ with
arbitrary gates.

  * •

[Ben89]: this work is not a black-box purifier in our sense simply because it
is a transformation on _classical_ circuits, and the goal is not to remove
measurements but to make the circuit reversible. However, we can define an
analogous notion of classical _reversible-izers_ that takes any classical
circuit $C$ comprising both reversible and irreversible gates, and outputs a
new circuit $C^{\prime}$ comprising only of reversible gates. A reversible-
izer would then be black-box as long as is worked for any set of starting
gates. [Ben89] would then be a black-box reversible-izer. Because of the
similarities of purifying and reversible-izing, we would therefore expect any
attempt to adapt [Ben89] in order to purify quantum computations would result
in a black-box purifier as well.

######  Remark 7.

[FR21, GRZ21, GR22] work in the uniform setting where the quantum circuits are
generated uniformly by a classical Turing machine, and additional space and
time constraints are placed on the Turing machine. Our notion of a purifier is
more lax, as it does not place any resource constraints on how the circuits
are generated. In our lower bound in Sections 5, 6, the starting low-space
algorithm that contains measurements is easily seen to be uniformly generated.
Since our lower bound will apply even to compilers producing non-uniform
quantum circuits, the laxness of our purifier notion makes our results even
stronger.

##  5 A separation between pure and general quantum computation

Before proving our main theorem, we first prove a slightly weaker theorem
separating pure and general computation that captures the main technical
challenges in our main theorem.

In short, here we show that we can construct a gate relative to which there is
a bit $b$ that can be computed by a low space-time algorithm with
measurements, but no low space-time _unitary_ algorithm can compute $b$. Here,
it is crucial that the algorithms are independent of the choice of gate. If
the algorithm is allowed to depend on the choice of gate, then the algorithm
can simply have $b$ hardcoded and output that $b$. As such, our result in this
section does not result in a separation for circuits that are allowed to
depend on the choice of gate. Note that our notion of a compiler is allowed to
depend on the gates being used, so the result from this section is
insufficient. We extend this result to gate-dependent algorithms, and
therefore rule out time- and space-efficient black box purifiers, in Section
6.

Consider $n,t\in\mathbb{Z}^{+}$. Assume for simplicity that $t+1=2^{m}$ for an
integer $m$. Let $\Psi=\\{|\psi_{i}\rangle,|\phi_{i}\rangle\\}_{i\in[t]}$ be a
list of $2t$ pure quantum states over ${\mathcal{H}}_{2}^{\otimes n}$ that are
orthogonal to $|0\rangle$; denote this space as ${\mathcal{H}}_{2}^{\otimes
n}\setminus\\{|0\rangle\\}$. We will think of these states as each being Haar
random over ${\mathcal{H}}_{2}^{\otimes n}\setminus\\{|0\rangle\\}$. Let
$o\in\\{0,1\\}$ be a bit, which we will think of as being a uniform random
bit. Define the following unitary function ${\mathbf{O}}_{\Psi,{\sf out}}$
that acts on ${\mathcal{H}}_{2}^{\otimes(m+n+n)}$:

$\begin{array}[]{lllllll}{\mathbf{O}}_{\Psi,{\sf
out}}|0\rangle&|0^{n}\rangle&|0^{n}\rangle&=|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle\\\
\vspace{5pt}{\mathbf{O}}_{\Psi,{\sf
out}}|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle&=|0\rangle&|0^{n}\rangle&|0^{n}\rangle\\\
{\mathbf{O}}_{\Psi,{\sf
out}}|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&=|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&\text{
for }i\in[1,t-1]\\\ \vspace{5pt}{\mathbf{O}}_{\Psi,{\sf
out}}|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&=|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&\text{
for }i\in[1,t-1]\\\ {\mathbf{O}}_{\Psi,{\sf
out}}|t\rangle&|\psi_{t}\rangle&|z\rangle&=|t\rangle&|\psi_{t}\rangle&|z\oplus{\sf
out}0^{n-1}\rangle&\text{ for }z\in\\{0,1\\}^{n}\end{array}$

Meanwhile, ${\mathbf{O}}_{\Psi,{\sf out}}$ preserves all states orthogonal to
the states above. The goal will be, given oracle access to
${\mathbf{O}}_{\Psi,{\sf out}}$, to compute ${\sf out}$.

An alternative view of the transformation is as:

$\displaystyle{\mathbf{O}}_{\Psi,{\sf out}}=|0\rangle\langle 0|\otimes$
$\displaystyle\Big{[}\;{\mathbf{I}}-\Big{(}\;|0^{n}\rangle|0^{n}\rangle-|\psi_{1}\rangle|\phi_{1}\rangle\;\Big{)}\Big{(}\;\langle
0^{n}|\langle 0^{n}|-\langle\psi_{1}|\langle\phi_{1}|\;\Big{)}\;\Big{]}$
$\displaystyle+\sum_{i=1}^{t-1}|i\rangle\langle i|\otimes$
$\displaystyle\Big{[}\;{\mathbf{I}}-\Big{(}\;|\psi_{i}\rangle|0^{n}\rangle-|\psi_{i+1}\rangle|\phi_{i+1}\rangle\;\Big{)}\Big{(}\;\langle\psi_{i}|\langle
0^{n}|-\langle\psi_{i+1}|\langle\phi_{i+1}|\;\Big{)}\;\Big{]}$
$\displaystyle+|t\rangle\langle t|\otimes$
$\displaystyle\Big{[}\;\Big{(}{\mathbf{I}}-|\psi_{t}\rangle\langle\psi_{t}|\Big{)}\otimes{\mathbf{I}}+|\psi_{t}\rangle\langle\psi_{t}|\otimes\;\Big{(}\sum_{z}|z\oplus{\sf
out}0^{n-1}\rangle\langle z|\;\Big{)}\;\Big{]}$

#### A Low-Space-Time Circuit with Measurements.

######  Lemma 5.1.

There exists a general quantum circuit $C$ with space $O(n+m)=O(n+\log t)$ and
time $O(nt)$ that computes ${\sf out}$ probability 1.

###### Proof.

Our general quantum circuit does the following:

  * •

Initialize registers $|0\rangle|0^{n}\rangle|0^{n}\rangle$.

  * •

Apply an ${\mathbf{O}}$ gate, to obtain
$|0\rangle|\psi_{1}\rangle|\phi_{1}\rangle$

  * •

Repeat the following loop for $i=1,\dots,t$, where the state at the beginning
of the loop is $|i-1\rangle|\psi_{i}\rangle|\phi_{i}\rangle$:

    * –

Reset the state $|\phi_{i}\rangle$ to $|0^{n}\rangle$

    * –

Add 1 (mod $t+1$) to the first register, which contains $i-1$. At this point,
the state is $|i\rangle|\psi_{i}\rangle|0^{n}\rangle$

    * –

Make a query to ${\mathbf{O}}$. If $i<t$, the resulting state is now
$|i\rangle|\psi_{i+1}\rangle|\phi_{i+1}\rangle$. If $i=t$, the state is now
$|t\rangle|\psi_{t}\rangle|{\sf out}0^{n-1}\rangle$.

  * •

Discard $|t\rangle,|\psi_{t}\rangle$, and $|0^{n-1}\rangle$, leaving $|{\sf
out}\rangle$. Measure and output ${\sf out}$.

Above, resetting $|\phi_{i}\rangle$ to $|0^{n}\rangle$ can be accomplished
with $n$ qubit reset gates. As mentioned in Section 1, qubit reset gates are
space- and time-equivalent to many typical notions of measurement gates,
assuming the ability to use the classical results of measurement to control
later gates. However, we cannot reset $|\phi_{i}\rangle$ with a unital
measurement: such a unital measurement will result in $|z\rangle$ for a random
$z$, but then there is no way to overwrite $|z\rangle$ with $|0^{n}\rangle$.
Please see Figure 3 for a depiction of our algorithm.

Figure 3:  Our task that can be computed in low space and time with
measurements, but requires large space or large time without.

The space of the algorithm above is $2n+m=O(n+\log(t))$, plus any extra space
needed to discard and initialize new registers, which is constant. Thus, the
overall space is $O(n+\log(t))$. For time, there are $t+1$ applications of the
${\mathbf{O}}$ gate, plus in each of the $t$ iterations we have $n$ qubits are
discarded and re-initialized, taking time $O(n)$ per iteration. This gives an
overall number of gates equal to $O(nt)$.∎

#### No Low-Space-Time Circuit without Measurements.

######  Lemma 5.2.

There exists a distribution over $\Psi,{\sf out}$ and constants
$c^{\prime},d^{\prime}$ such that, for any unitary circuit over any gate set
which makes at most $2^{d^{\prime}n}$ queries to ${\mathbf{O}}_{\Psi,{\sf
out}}$ and runs in space $S\leq c^{\prime}nt$, the probability of outputting
${\sf out}$ is less than $7/12$.

The constant $7/12$ above is arbitrary, as long as it is strictly between
$1/2$ and $2/3$ (the latter being the arbitrary constant in the definition of
a black box purifier). Above, note that the time $T$ of the circuit is at
least the number of queries to ${\mathbf{O}}_{\Psi,{\sf out}}$. As a
consequence, there is no time $T\leq 2^{d^{\prime}n}$ and space $S\leq
c^{\prime}nt$ circuit that can guess ${\sf out}$ with probability at least
$7/12$. This holds independent of the gate set that the algorithm uses, as
long as the gates do not depend of the choice of $\Psi,{\sf out}$. This
independence from the gate set will be important for our ultimate result in
Section 6. There, we will construct from any low space-time purifier a circuit
which contradicts Lemma 5.2. Our circuit, however, will have to make some
computations that are potentially very expensive, but fortunately are
independent of $\Psi,{\sf out}$. In order for these extra computations to
still contradict Lemma 5.2, we state the lemma as only counting queries to
${\mathbf{O}}_{\Psi,{\sf out}}$ but being otherwise independent of the actual
time-complexity of the circuit.

The rest of this section will be devoted to proving Lemma 5.2.

#### Roadmap.

We will assume an algorithm ${\mathcal{A}}$ running in time much less than
$2^{O(n)}$ with probability of outputting ${\sf out}$ being at least $7/12$.
We will show that such an algorithm must have space $\Omega(nt)$. First, we
will show that any unitary algorithm that outputs ${\sf out}$ with significant
probability must actually be able to produce $|\psi_{t}\rangle$. This follows
from standard quantum query techniques. Then, we will design a simulator which
approximately simulates $\Psi$ using only several copies of the
$|\psi_{i}\rangle,|\phi_{i}\rangle$ instead of the full descriptions of these
states. This simulation uses ideas from [JLS18], and will cause some error
which will be small assuming the unitary algorithm’s running time is small. As
the unitary algorithm is run, some of these copies will be provided to the
algorithm, decreasing the storage of the simulator. We show essentially that
the simulator must have given at least one copy of $|\phi_{i}\rangle$ for each
$i$ to the algorithm in order for the algorithm to have obtained
$|\psi_{t}\rangle$. This implies an upper bound on the space of the simulator
at the end of the computation. Finally, we observe that the total joint
storage of the simulator and the unitary algorithm cannot drop below the
initial simulator storage. This then implies a lower bound on the space of the
unitary algorithm.

###  5.1 From Computing ${\sf out}$ to computing $|\psi_{t}\rangle$

######  Lemma 5.3.

Fix any $\Psi$. Let ${\mathcal{A}}$ be a unitary algorithm making queries to
${\mathbf{O}}_{\Psi,{\sf out}}$ running in time $T$ and space $S$, such that
$\Pr_{o\leftarrow\\{0,1\\}}[{\mathcal{A}}^{{\mathbf{O}}_{\Psi,{\sf
out}}}()=o]\geq 7/12$. Then there is a another unitary algorithm
${\mathcal{A}}_{1}$ running in time $\leq T$ and space $\leq S$ that attempts
to output $|\psi_{t}\rangle$ with the following guarantee. If $\rho$ is the
final state of ${\mathcal{A}}_{1}$ when making queries to
${\mathbf{O}}_{\Psi,{\sf out}}$ for a random ${\sf out}$, then
$\langle\psi_{t}|\rho|\psi_{t}\rangle\geq(48T)^{-2}$.

###### Proof.

Since ${\mathcal{A}}$ runs in time at most $T$, it makes at most $T$ queries
to ${\mathbf{O}}$. We zoom in on the basis states of the queries to
${\mathbf{O}}$ where the first register is $|t\rangle$. Pick any basis for
${\mathcal{H}}_{2}^{\otimes n}$ which contains $|\psi_{t}\rangle$ as the first
element, and look at the queries to ${\mathbf{O}}$ in that basis. Then we see
that ${\mathbf{O}}$, when restricted to the first register being $|t\rangle$,
is implementing a quantum query to a classical function, namely the function
that maps $0$ (corresponding to the first basis element being
$|\psi_{t}\rangle$) to ${\sf out}$, and everything else to 0. Let the total
query weight on the basis element $|\psi_{t}\rangle$ be $\epsilon$. We now
switch from ${\mathbf{O}}_{\Psi,{\sf out}}$ to ${\mathbf{O}}_{\Psi,0}$, which
contains no information about ${\sf out}$. This means ${\mathcal{A}}$ when
querying ${\mathbf{O}}_{\Psi,0}$ outputs ${\sf out}$ with probability $1/2$.
By Lemma 3.2, this change moves the output state of ${\mathcal{A}}$ by at most
$\sqrt{T\epsilon}$. Then applying Lemma 3.1 shows that the output distribution
is affected by at most $4\sqrt{T\epsilon}$. In other words, $|p-1/2|\leq
4\sqrt{T\epsilon}$. By our assumption that $p\geq 7/12$, we have that
$\epsilon\geq(48^{2}T)^{-1}$.

This means there is some query $j\in[T]$ such that the query weight on
$|\psi_{t}\rangle$ is at least $\epsilon/T\geq(48T)^{-2}$. We therefore define
${\mathcal{A}}_{1}$ as the algorithm which runs ${\mathcal{A}}$ until query
$j$, and outputs the middle register of the query. See Figure 4.

Figure 4:  Converting from an algorithm ${\mathcal{A}}$ (top) which computes
${\sf out}$ to an algorithm ${\mathcal{A}}_{1}$ (bottom) which computes
$|\psi_{t}\rangle$.

By the analysis above, if $\rho$ is the output state of ${\mathcal{A}}_{1}$,
then $\langle\psi_{t}|\rho|\psi_{t}\rangle\geq(48T)^{-2}$. Observe that the
number of queries ${\mathcal{A}}_{1}$ makes and the space of
${\mathcal{A}}_{1}$ are at most the query count and space for ${\mathcal{A}}$.
If ${\mathcal{A}}$ is unitary, then so is ${\mathcal{A}}_{1}$.∎

From now on, we will assume an algorithm ${\mathcal{A}}$ which outputs
$|\psi_{t}\rangle$.

###  5.2 Simulating ${\mathbf{O}}_{\Psi,{\sf out}}$: Counting

We now gradually build up a simulator which simulates ${\mathbf{O}}_{\Psi,{\sf
out}}$ to the algorithm. Our ultimate simulator will only use several copies
of each of the $|\psi_{i}\rangle$ and $|\phi_{i}\rangle$.

As a first step, we show that we can simulate ${\mathbf{O}}_{\Psi,{\sf out}}$
as specified above, but we can record in some ancilla registers the net number
of copies of each of the $|\psi_{i}\rangle,|\phi_{i}\rangle$ that have given
out/consumed888By “net”, we mean the difference between the number given out
minus the number consumed..

Let ${\mathcal{H}}_{\infty}$ be the infinite-dimensional Hilbert space spanned
by $\\{|x\rangle\\}_{x\in\mathbb{Z}}$. Note that we use an infinite
dimensional space for simplicity, and we can make the space finite-dimensional
by instead using the Hilbert space spanned by $\\{-U,-U+1,\cdots,U-1,U\\}$ for
some $U\geq T$.

For $i=1,\dots,t$ let ${\mathcal{C}}_{i}$ be a copy of
${\mathcal{H}}_{\infty}$ and likewise for $i=1,\dots,t-1$ let
${\mathcal{D}}_{i}$ be a copy of ${\mathcal{H}}_{\infty}$. Each of the
${\mathcal{C}}_{i},{\mathcal{D}}_{i}$ will be initialized to $|0\rangle$. Let
${\mathcal{C}}$ be the joint system of all
${\mathcal{C}}_{i},{\mathcal{D}}_{i}$. We will write the basis states of
${\mathcal{C}}$ as $|{\mathbf{c}}\rangle$ where
${\mathbf{c}}\in\mathbb{Z}^{2t-1}$.

Let ${\sf Incr}_{{\mathcal{C}}_{i}}$ and ${\sf Decr}_{{\mathcal{C}}_{i}}$ be
the operation on ${\mathcal{C}}$ which applies the map
$|j\rangle\mapsto|j+1\rangle$ and $|j\rangle\mapsto|j-1\rangle$, respectively,
to register ${\mathcal{C}}_{i}$. Likewise define ${\sf
Incr}_{{\mathcal{D}}_{i}}$ and ${\sf Decr}_{{\mathcal{D}}_{i}}$.

Now define the following unitary ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ that
acts on ${\mathcal{H}}_{2}^{\otimes(m+n+n)}\otimes{\mathcal{C}}$:

$\begin{array}[]{lllllllll}{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|{\mathbf{c}}\rangle&=|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle&{\sf
Incr}_{{\mathcal{C}}_{1}}{\sf Incr}_{{\mathcal{D}}_{1}}|{\mathbf{c}}\rangle\\\
\vspace{5pt}{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle&|{\mathbf{c}}\rangle&=|0\rangle&|0^{n}\rangle&|0^{n}\rangle&{\sf
Decr}_{{\mathcal{C}}_{1}}{\sf Decr}_{{\mathcal{D}}_{1}}|{\mathbf{c}}\rangle\\\
{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&|{\mathbf{c}}\rangle&=|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&{\sf
Decr}_{{\mathcal{C}}_{i}}{\sf Incr}_{{\mathcal{C}}_{i+1}}{\sf
Incr}_{{\mathcal{D}}_{i+1}}|{\mathbf{c}}\rangle&\text{ for }i\in[1,t-1]\\\
\vspace{5pt}{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&|{\mathbf{c}}\rangle&=|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&{\sf
Incr}_{{\mathcal{C}}_{i}}{\sf Decr}_{{\mathcal{C}}_{i+1}}{\sf
Decr}_{{\mathcal{D}}_{i+1}}|{\mathbf{c}}\rangle&\text{ for }i\in[1,t-1]\\\
{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}|t\rangle&|\psi_{t}\rangle&|z\rangle&|{\mathbf{c}}\rangle&=|t\rangle&|\psi_{t}\rangle&|z\oplus{\sf
out}0^{n-1}\rangle&|{\mathbf{c}}\rangle&\text{ for
}z\in\\{0,1\\}^{n}\end{array}$

In other words, any time ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ outputs a
$|\psi_{i}\rangle$, it increments the corresponding ${\mathcal{C}}_{i}$
register; and analogously increments ${\mathcal{D}}_{i}$ whenever it outputs a
$|\phi_{i}\rangle$. On the other hand, any time ${\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}$ must absorb a $|\psi_{i}\rangle$ or $|\phi_{i}\rangle$, it decrements
the analogous register.

Above, we will think of ${\mathcal{C}}$ as being in the private state of a
simulator, inaccessible to the algorithm. We now demonstrate that
${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ is actually indistinguishable from
${\mathbf{O}}_{\Psi,{\sf out}}$, for certain distributions over $\Psi$. Note
that while ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ and ${\mathbf{O}}_{\Psi,{\sf
out}}$ may look like they act identically on
${\mathcal{H}}_{2}^{\otimes(m+n+n)}$, the fact that
${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ is modifying external registers based on
the contents of ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ means that the
operations are, in fact, not identical on
${\mathcal{H}}_{2}^{\otimes(m+n+n)}$. Essentially, by adding/subtracting from
${\mathcal{C}}$, ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ may split different
branches of the computation, eliminating interference that may be present with
${\mathbf{O}}_{\Psi,{\sf out}}$. In particular, if $\Psi$ is fixed and known
to the algorithm, it is not hard to design an algorithm which can successfully
distinguish between ${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ and
${\mathbf{O}}_{\Psi,{\sf out}}$. We show, however, that if $\Psi$ is chosen
from a “sufficiently random” collection of states, then such distinguishing is
not possible.

######  Definition 5.4.

We say a distribution ${\mathcal{D}}$ over states in
${\mathcal{H}}_{2}^{\otimes n}$ is _phase invariant_ if ${\mathcal{D}}$ is
identical to a distribution of the following form:

  * •

Sample a state $|\psi^{\prime}\rangle$ from some distribution
${\mathcal{D}}^{\prime}$.

  * •

Choose for each $x\in\\{0,1\\}^{n}$ a uniform real number
$\tau_{x}\in(-\pi,\pi]$

  * •

Apply to $|\psi^{\prime}\rangle$ the operation which maps $|x\rangle\mapsto
e^{i\tau_{x}}|x\rangle$ for each $x$.

  * •

Output the resulting state $|\psi\rangle$.

We say ${\mathcal{D}}$ is $M$-phase invariant if $\tau_{x}$ is instead uniform
on the multiples of $2\pi/M$ in $(-\pi,\pi]$.

We note that any phase invariant distribution is also $M$-phase invariant,
since we can absorb the “extra” randomness of $\tau_{x}$ into the distribution
of $|\psi^{\prime}\rangle$. We also observe that Haar random states are phase
invariant.

######  Lemma 5.5.

Let ${\mathcal{A}}$ be a time $T$ algorithm. Then for any $M\geq 2T+1$ and any
$M$-phase invariant distribution ${\mathcal{D}}$, if
$\Psi\leftarrow{\mathcal{D}}^{2t-1}$ (meaning the $|\psi_{i}\rangle$ and
$|\phi_{i}\rangle$ are sampled from ${\mathcal{D}}$), then

$\mathop{\mathbb{E}}_{\Psi}\left[{\mathcal{A}}^{{\mathbf{O}}_{\Psi,{\sf
out}}}()\right]=\mathop{\mathbb{E}}_{\Psi}\left[{\mathcal{A}}^{{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}}()\right]$

###### Proof.

Let ${\mathcal{A}},M,{\mathcal{D}}$ be as in the statement of Lemma 5.5. Let
$\mathbb{Z}_{M}$ be the set of of integers mod $M$, which we will associate
with the interval $[-\lfloor(M-1)/2\rfloor,\cdots,\lceil(M-1)/2\rceil]$.

Consider sampling each $|\psi_{i}\rangle$ and $|\phi_{i}\rangle$ from
${\mathcal{D}}$. Let $|\psi_{i}^{\prime}\rangle,|\phi_{i}^{\prime}\rangle$ be
the samples from ${\mathcal{D}}^{\prime}$ used to sample
$|\psi_{i}\rangle,|\phi_{i}\rangle$ according to the definition of $M$-phase
invariance. For each state $|\psi_{i}\rangle$, let
$F_{i}:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{M}$ be the function mapping $x$ to
$\tau_{x}*(M/2\pi)$ where the $\tau_{x}$ are the random values used to
construct $|\psi_{i}\rangle$. Likewise define
$G_{i}:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{M}$ as the functions mapping $x$ to
$\tau_{x}*(M/2\pi)$ for each of the $|\phi_{i}\rangle$. Then the $F_{i},G_{i}$
are uniform random functions.

Now fix each $|\psi_{i}^{\prime}\rangle,|\phi_{i}^{\prime}\rangle$. We will
show that $\Pr[{\mathcal{A}}^{{\mathbf{O}}_{\Psi,{\sf
out}}}()=z]=\Pr[{\mathcal{A}}^{{\mathbf{O}}^{(1)}_{\Psi,{\sf out}}}()=z]$
holds even when fixing these states. Now the only randomness is over the
choice of $F_{i},G_{i}$ and any randomness of ${\mathcal{A}}$.

For a function $F:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{M}$, let ${{\sf
Ph}}_{F}$ be the unitary that maps $|x\rangle\mapsto e^{i2\pi
F(x)/M}|x\rangle$. Then $|\psi_{i}\rangle={{\sf
Ph}}_{F_{i}}|\psi_{i}^{\prime}\rangle$ and $|\phi_{i}\rangle={{\sf
Ph}}_{G_{i}}|\phi_{i}^{\prime}\rangle$

We will use a variant of the query recording technique of [Zha19]. Instead of
sampling random $F_{i},G_{i}$, we will purify them, initializing uniform
superpositions $\frac{1}{M^{2^{n}/2}}\sum_{F_{i}}|F_{i}\rangle$ and
$\frac{1}{M^{2^{n}/2}}\sum_{G_{i}}|G_{i}\rangle$. Let ${\mathcal{F}}$ be the
register containing all the $F_{i},G_{i}$. Now we can think of
${\mathbf{O}}_{\Psi,{\sf out}}$ as a larger unitary ${\mathbf{O}}_{\sf out}$
acting on ${\mathcal{H}}_{2}^{\otimes(m+n+n)}\otimes{\mathcal{F}}$, and
${\mathbf{O}}^{(1)}_{\Psi,{\sf out}}$ as a larger unitary
${\mathbf{O}}^{(1)}_{\sf out}$ acting on
${\mathcal{H}}_{2}^{\otimes(m+n+n)}\otimes{\mathcal{F}}\otimes{\mathcal{C}}$.
${\mathbf{O}}_{{\sf out}}$ has the following behavior:

$\begin{array}[]{llllllll}{\mathbf{O}}_{{\sf
out}}|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle&=|0\rangle&{{\sf
Ph}}_{F_{1}}|\psi_{1}^{\prime}\rangle&{{\sf
Ph}}_{G_{1}}|\phi_{1}^{\prime}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle\\\
\vspace{5pt}{\mathbf{O}}_{{\sf out}}|0\rangle&{{\sf
Ph}}_{F_{1}}|\psi_{1}^{\prime}\rangle&{{\sf
Ph}}_{G_{1}}|\phi_{1}^{\prime}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle&=|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle\\\
{\mathbf{O}}_{{\sf out}}|i\rangle&{{\sf
Ph}}_{F_{i}}|\psi_{i}^{\prime}\rangle&|0^{n}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle&=|i\rangle&{{\sf
Ph}}_{F_{i+1}}|\psi_{i+1}^{\prime}\rangle&{{\sf
Ph}}_{G_{i+1}}|\phi_{i+1}^{\prime}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle\\\
\vspace{5pt}{\mathbf{O}}_{{\sf out}}|i\rangle&{{\sf
Ph}}_{F_{i+1}}|\psi_{i+1}^{\prime}\rangle&{{\sf
Ph}}_{G_{i+1}}|\phi_{i+1}^{\prime}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle&=|i\rangle&{{\sf
Ph}}_{F_{i}}|\psi_{i}^{\prime}\rangle&|0^{n}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle\\\
{\mathbf{O}}_{{\sf out}}|t\rangle&{{\sf
Ph}}_{F_{t}}|\psi_{t}^{\prime}\rangle&|z\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle&=|t\rangle&{{\sf
Ph}}_{F_{T}}|\psi_{t}^{\prime}\rangle&|z\oplus{\sf
out}0^{n-1}\rangle&|\\{F_{i}\\}_{i},\\{G_{i}\\}_{i}\\}\rangle\end{array}$

Meanwhile, ${\mathbf{O}}^{(1)}_{\sf out}$ has the same behavior, except that
it also acts on ${\mathcal{C}}$ using the ${\sf Incr},{\sf Decr}$ operations.

Now we switch to viewing the ${\mathcal{F}}$ register in the Fourier basis. To
do so, we use the following:

######  Lemma 5.6.

Consider an algorithm making queries in one of two worlds. In the first,
${\mathcal{F}}$ is initialized to the uniform superposition over tuples of
random functions, and the algorithm makes queries to ${\mathbf{O}}_{\sf out}$
(resp. ${\mathbf{O}}^{(1)}_{\sf out}$). In the other world, ${\mathcal{F}}$ is
initialized to a list of all-zero functions $|(0^{2^{n}})^{2t-1}\rangle$, and
the algorithm makes queries to ${{\sf
QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}_{\sf out}\cdot{{\sf
QFT}}_{\mathcal{F}}$ (resp. ${{\sf
QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}^{(1)}_{\sf out}\cdot{{\sf
QFT}}_{\mathcal{F}}$). Then the output distributions in the two worlds are
equal.

###### Proof.

We prove the ${\mathbf{O}}_{\sf out}$ case, the other being essentially
identical. We insert ${{\sf QFT}}\cdot{{\sf QFT}}^{\dagger}={\mathbf{I}}$
applied to ${\mathcal{F}}$ between each query to ${\mathbf{O}}_{\sf out}$. We
likewise observe that the initial state of ${\mathcal{F}}$, the uniform
superposition over all tuples of functions, is just ${{\sf QFT}}$ applied to
$|(0^{2^{n}})^{2t-1}\rangle$. We can also apply a final ${{\sf
QFT}}^{\dagger}$ to ${\mathcal{F}}$ at the very end of the computation, which
does not affect the algorithm’s registers. Now we observe that each ${{\sf
QFT}},{{\sf QFT}}^{\dagger}$ we injected commutes with the algorithm’s gates
other than ${\mathbf{O}}_{\sf out}$, so we can take one half of each ${{\sf
QFT}}\cdot{{\sf QFT}}^{\dagger}$ and push it to being next to the previous
query to ${\mathbf{O}}_{\sf out}$ and push the other half to being next to the
subsequent query. The result is each query to ${\mathbf{O}}_{\sf out}$ is
sandwiched between two ${{\sf QFT}}$ gates. In other words, the algorithm is
now making queries to ${{\sf QFT}}^{\dagger}\cdot{\mathbf{O}}_{\sf
out}\cdot{{\sf QFT}}$, and the initial state of ${\mathcal{F}}$ is
$|(0^{2^{n}})^{2t-1}\rangle$. These changes are all perfectly
indistinguishable to the algorithm. This completes the proof of Lemma 5.6.∎

We now observe that ${{\sf QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}_{\sf
out}\cdot{{\sf QFT}}_{\mathcal{F}}$ (resp. ${{\sf
QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}^{(1)}_{\sf out}\cdot{{\sf
QFT}}_{\mathcal{F}}$) have particularly nice forms. We start by observing that
if we define ${{\sf Ph}}|y\rangle=e^{i2\pi y/M}|y\rangle$, then

${{\sf QFT}}^{\dagger}\cdot{{\sf Ph}}\cdot{{\sf
QFT}}|z\rangle=\frac{1}{M}\sum_{z^{\prime},y}e^{-i2\pi yz^{\prime}/M}e^{i2\pi
y/M}e^{i2\pi yz/M}|z^{\prime}\rangle=\frac{1}{M}\sum_{z^{\prime},y}e^{i2\pi
y(z+1-z^{\prime})/M}|z^{\prime}\rangle=|z+1\rangle$

where above we used that $\sum_{y}e^{i2\pi yw/M}$ equals $M$ if $w=0$ and
equals 0 otherwise.

Using this identity, we will interpret ${\mathcal{F}}$ as a collection $V$ of
$2t-1$ tables, each table having length $2^{n}$ and containing entries from
$\mathbb{Z}_{M}$. For a string $x$, let ${\sf Incr}_{{\mathcal{F}}_{i}(x)}$ be
the operation that adds 1 (mod $M$) to the entry of register ${\mathcal{F}}$
corresponding to the $i$th function $F_{i}$ on input $x$. Likewise define
${\sf Decr}_{{\mathcal{F}}_{i}(x)},{\sf Incr}_{{\mathcal{G}}_{i}(x)},{\sf
Decr}_{{\mathcal{G}}_{i}(x)}$. Let
$|\psi_{i}^{\prime}\rangle=\sum_{x}\alpha^{(i)}_{x}|x\rangle$ and
$|\phi_{i}^{\prime}\rangle=\sum_{x}\beta^{(i)}_{x}|x\rangle$. Then
${\mathbf{P}}_{\sf out}:={{\sf
QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}_{\sf out}\cdot{{\sf
QFT}}_{\mathcal{F}}$ is just

$\begin{array}[]{llllllll}{\mathbf{P}}_{{\sf
out}}|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|V\rangle&=|0\rangle&\sum\limits_{x,y}\alpha^{(1)}_{x}\beta^{(1)}_{y}|x\rangle&|y\rangle&{\sf
Incr}_{{\mathcal{F}}_{1}(x)}{\sf Incr}_{{\mathcal{G}}_{1}(y)}|V\rangle\\\
\vspace{5pt}{\mathbf{P}}_{{\sf
out}}|0\rangle&\sum\limits_{x,y}\alpha^{(1)}_{x}\beta^{(1)}_{y}|x\rangle&|y\rangle&{\sf
Incr}_{{\mathcal{F}}_{1}(x)}{\sf
Incr}_{{\mathcal{G}}_{1}(y)}|V\rangle&=|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|V\rangle\\\
{\mathbf{P}}_{{\sf
out}}|i\rangle&\sum\limits_{x}\alpha^{(i)}_{x}|x\rangle&|0^{n}\rangle&{\sf
Incr}_{{\mathcal{F}}_{i}(x)}|V\rangle&=|i\rangle&\sum\limits_{x^{\prime},y^{\prime}}\alpha^{(i+1)}_{x^{\prime}}\beta^{(i+1)}_{x^{\prime}}|x^{\prime}\rangle&|y^{\prime}\rangle&{\sf
Incr}_{{\mathcal{F}}_{i+1}(x^{\prime})}{\sf
Incr}_{{\mathcal{G}}_{i+1}(y^{\prime})}|V\rangle\\\
\vspace{5pt}{\mathbf{P}}_{{\sf
out}}|i\rangle&\sum\limits_{x^{\prime},y^{\prime}}\alpha^{(i+1)}_{x^{\prime}}\beta^{(i+1)}_{x^{\prime}}|x^{\prime}\rangle&|y^{\prime}\rangle&{\sf
Incr}_{{\mathcal{F}}_{i+1}(x^{\prime})}{\sf
Incr}_{{\mathcal{G}}_{i+1}(y^{\prime})}|V\rangle&=|i\rangle&\sum\limits_{x}\alpha^{(i)}_{x}|x\rangle&|0^{n}\rangle&{\sf
Incr}_{{\mathcal{F}}_{i}(x)}|V\rangle\\\ {\mathbf{P}}_{{\sf
out}}|t\rangle&\sum\limits_{x}\alpha^{(t)}_{x}|x\rangle&|z\rangle&{\sf
Incr}_{{\mathcal{F}}_{t}(x)}|V\rangle&=|t\rangle&\sum\limits_{x}\alpha^{(i)}_{x}|x\rangle&|z\oplus{\sf
out}0^{n-1}\rangle&{\sf Incr}_{{\mathcal{F}}_{t}(x)}|V\rangle\end{array}$

Likewise we can define ${\mathbf{P}}^{(1)}_{\sf out}:={{\sf
QFT}}_{\mathcal{F}}^{\dagger}\cdot{\mathbf{O}}^{(1)}_{\sf out}\cdot{{\sf
QFT}}_{\mathcal{F}}$, and obtain equations for the definition of
${\mathbf{P}}^{(1)}_{\sf out}$, which look exactly like those for
${\mathbf{P}}^{(1)}_{\sf out}$, except that they include additionally the
operations ${\sf Incr},{\sf Decr}$ on the register ${\mathcal{C}}$.

######  Claim 5.7.

Each register ${\mathcal{C}}_{i}$ in ${\mathcal{C}}$ contains exactly the sum
of the entries of ${\mathcal{F}}_{i}$ (when interpreted as integers in the
interval $[-\lfloor(M-1)/2\rfloor,\cdots,\lceil(M-1)/2\rceil]$), and likewise
${\mathcal{D}}_{i}$ contains exactly the sum of the entries of
${\mathcal{G}}_{i}$.

###### Proof.

This is true initially since all the registers are zero. Then the property is
preserved $\bmod M$ since, any time ${\sf Incr}_{{\mathcal{F}}_{i}(x)}$ is
applied, then so is ${\sf Incr}_{{\mathcal{C}}_{i}}$, and likewise for ${\sf
Incr}_{{\mathcal{G}}_{i}(x)}$ and ${\sf Incr}_{{\mathcal{D}}_{i}}$. Since the
number of queries is less than $M/2$ and each query only increases or
decreases the value of any register by 1, the entries in
${\mathcal{F}}_{i},{\mathcal{G}}_{i}$ always remain in the interval
$[-\lfloor(M-1)/2\rfloor,\cdots,\lceil(M-1)/2\rceil]$ and never need to be
reduced $\bmod M$. Therefore, equality holds over the integers.∎

Since the register ${\mathcal{C}}$ can be computed from ${\mathcal{F}}$, which
is local to the oracle simulation and not seen by the algorithm, we can
imagine computing ${\mathcal{C}}$ from ${\mathcal{F}}$ immediately before each
query, and then uncomputing ${\mathcal{C}}$ from ${\mathcal{F}}$ immediately
after each query, and this change will not affect the algorithm in any way.
The result is that we move from applying ${\mathbf{P}}_{\sf out}$ to
${\mathbf{P}}_{\sf out}^{(1)}$ without any affect on the algorithm. This shows
that ${\mathbf{P}}_{\sf out}$ to ${\mathbf{P}}_{\sf out}^{(1)}$, and hence
${\mathbf{O}}_{\sf out}$ to ${\mathbf{O}}_{\sf out}^{(1)}$, are perfectly
indistinguishable. This completes the proof of Lemma 5.5. ∎

We next observe the following feature of ${\mathbf{O}}_{\Psi,{\sf out}}$:

######  Lemma 5.8.

At all times, for $i=1,\dots,t-1$, the support of ${\mathcal{C}}$ is on states
where the count in register ${\mathcal{D}}_{i+1}$ is equal to the count in
register ${\mathcal{D}}_{i}$ minus the count in register ${\mathcal{C}}_{i}$.

In other words, the net number of $|\phi_{i}\rangle$ given out is equal to the
difference in the net numbers of $|\psi_{i}\rangle$ and $|\psi_{i+1}\rangle$
given out.

###### Proof.

Initially all counts are 0 so the lemma is trivially true. In any query where
the first register is 0, the difference between ${\mathcal{C}}_{1}$ and
${\mathcal{D}}_{1}$ is preserved (since both are increased or decreased or
preserved together) and all other counts are kept the same. Thus, the
relations between the counts are preserved. For any query where the first
register is $i\in[1,t-1]$, the count in ${\mathcal{C}}_{i}$ may be decreased,
therefore increasing the difference between ${\mathcal{D}}_{i}$ and
${\mathcal{C}}_{i}$, but in this case ${\mathcal{D}}_{i+1}$ is increased; no
other registers are effected. Thus the relations between the counts are
preserved. For any query where the first register is $t$, the counts, and
therefore the relations between them, are preserved. ∎

###  5.3 Simulating ${\mathbf{O}}_{\Psi,{\sf out}}$: State Swap

Fix a list of states $\Psi$. Now we replace the register
$|{\mathbf{c}}\rangle$ with the following. Let
${\mathcal{H}}={\mathcal{H}}_{2}^{n}\setminus\\{|0\rangle\\}$, the space of an
$n$-qubit system with the state $|0\rangle$ removed. Recall that ${{\sf
Sym}}^{\ell}{\mathcal{H}}$ is the symmetric subspace of
${\mathcal{H}}^{\ell}$. Let ${{\sf
Sym}}^{*}{\mathcal{H}}=\cup_{\ell=1}^{\infty}{{\sf Sym}}^{\ell}{\mathcal{H}}$.

For $i=1,\dots,t$, let ${\mathcal{S}}_{i}$ be a copy of ${{\sf
Sym}}^{*}{\mathcal{H}}$; for $i=1,\dots,t-1$, let ${\mathcal{T}}_{i}$ be
another copy of ${{\sf Sym}}^{*}{\mathcal{H}}$. Let ${\mathcal{S}}$ be the
joint system of all ${\mathcal{S}}_{i},{\mathcal{T}}_{i}$. Each
${\mathcal{S}}_{i}$ is initialized with $\ell$ copies of $|\psi_{i}\rangle$,
and each ${\mathcal{T}}_{i}$ is initialized with $\ell$ copies of
$|\phi_{i}\rangle$. Here, $\ell\geq T$ is a parameter to be chosen later;
think of $\ell$ as polynomial in $T$.

Let ${\sf Incr}_{{\mathcal{S}}_{i}}$ increase the number of copies of
$|\psi_{i}\rangle$ in ${\mathcal{S}}_{i}$ by 1 (mod $N$ for some $N>T+\ell$),
and likewise define ${\sf Decr}_{{\mathcal{S}}_{i}},{\sf
Incr}_{{\mathcal{T}}_{i}},{\sf Decr}_{{\mathcal{T}}_{i}}$. Note that because
each ${\mathcal{S}}_{i},{\mathcal{T}}_{i}$ contains many copies of an
identical state, the state of the system is always in a symmetric subspace.

Now define the following unitary ${\mathbf{O}}^{(2)}_{\Psi,{\sf out},\ell}$
that acts on ${\mathcal{H}}_{2}^{\otimes(m+n+n)}\otimes{\mathcal{S}}$:

$\begin{array}[]{lllllllll}{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}|0\rangle&|0^{n}\rangle&|0^{n}\rangle&|\omega\rangle&=|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle&{\sf
Decr}_{{\mathcal{S}}_{1}}{\sf Decr}_{{\mathcal{T}}_{1}}|\omega\rangle\\\
\vspace{5pt}{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}|0\rangle&|\psi_{1}\rangle&|\phi_{1}\rangle&|\omega\rangle&=|0\rangle&|0^{n}\rangle&|0^{n}\rangle&{\sf
Incr}_{{\mathcal{S}}_{1}}{\sf Incr}_{{\mathcal{T}}_{1}}|\omega\rangle\\\
{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&|\omega\rangle&=|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&{\sf
Incr}_{{\mathcal{C}}_{i}}{\sf Decr}_{{\mathcal{S}}_{i+1}}{\sf
Decr}_{{\mathcal{T}}_{i+1}}|\omega\rangle&\text{ for }i\in[1,t-1]\\\
\vspace{5pt}{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}|i\rangle&|\psi_{i+1}\rangle&|\phi_{i+1}\rangle&|\omega\rangle&=|i\rangle&|\psi_{i}\rangle&|0^{n}\rangle&{\sf
Decr}_{{\mathcal{C}}_{i}}{\sf Incr}_{{\mathcal{S}}_{i+1}}{\sf
Incr}_{{\mathcal{T}}_{i+1}}|\omega\rangle&\text{ for }i\in[1,t-1]\\\
{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}|t\rangle&|\psi_{t}\rangle&|z\rangle&|\omega\rangle&=|t\rangle&|\psi_{t}\rangle&|z\oplus{\sf
out}0^{n-1}\rangle&|\omega\rangle&\text{ for }z\in\\{0,1\\}^{n}\end{array}$

Observe that, as long as the number of queries is at most $\ell$, then
${\mathbf{O}}^{(2)}_{\Psi,{\sf out},\ell}$ can be easily simulated from just
the initial state of ${\mathcal{S}}$ containing $\ell$ copies of each of the
$|\psi_{i}\rangle,|\phi_{i}\rangle$, as well as oracle access to the
reflections $P_{|\psi_{i}\rangle}$ and $P_{|\phi_{i}\rangle}$ where
$P_{|\psi\rangle}:=1-2|\psi\rangle\langle\psi|$. Indeed, we need two queries
to each $P_{|\psi_{i}\rangle}$ and $P_{|\phi_{i}\rangle}$ in order to decide
if the input register is in one of the states
$|\psi_{i}\rangle,|\phi_{i}\rangle$, and then uncompute the decision at the
end of simulating the query. Moreover, whenever we need to remove an
$|\psi_{i}\rangle$ or $|\phi_{i}\rangle$ from $|\omega\rangle$, we also need
to output an $|\psi_{i}\rangle$ or $|\phi_{i}\rangle$, respectively. So
instead of deleting, say, one of the copies of $|\psi_{i}\rangle$ from
$|\omega\rangle$, we just put it into the response register given back to the
algorithm. Likewise, when we need to increase the number of
$|\psi_{i}\rangle$, we also are given one of the $|\psi_{i}\rangle$ as input.
Since the input $|\psi_{i}\rangle$ needs to be deleted to execute the gate, we
can instead just swap the $|\psi_{i}\rangle$ given as input into
$|\omega\rangle$, simultaneously deleting the input copy and increasing the
number of copies in $|\omega\rangle$, as desired. The only issue is if the
number of copies drops below 0 or increases to $N$ or larger, in which case
the number of copies gets reduced mod $N$. But since we started with $\ell$
copies which is at least the number of queries, then we can never run out of
copies. Likewise, the number of copies can never increase by more than $T$,
for a total of $\ell+T<N$. Thus, we never need to reduce the number of copies
$\bmod N$. See Figure 5.

Figure 5:  How our simulator maps the query input (top) to the query output
(bottom) by simply moving registers around.

We also have the following:

######  Lemma 5.9.

Let ${\mathcal{A}}$ be a time $T\leq\ell$ algorithm. Then for any $\Psi$, any
${\sf out}$, we have the following equality of density matrices:

${\mathcal{A}}^{{\mathbf{O}}^{(1)}_{\Psi,{\sf
out}}}()={\mathcal{A}}^{{\mathbf{O}}^{(2)}_{\Psi,{\sf out},\ell}}()$

###### Proof.

We can compute $|\omega\rangle$ from $|{\mathbf{c}}\rangle$ (assuming
knowledge of the $|\psi_{i}\rangle,|\phi_{i}\rangle$), and vice versa, as
follows. The count in ${\mathcal{C}}_{i}$ is just $\ell$ minus the number of
copies of $|\psi_{i}\rangle$ in ${\mathcal{S}}_{i}$. Likewise the count in
${\mathcal{D}}_{i}$ is just $\ell$ minus the number of copies of
$|\phi_{i}\rangle$ in ${\mathcal{T}}_{i}$. Therefore, since $|\omega\rangle$
can be computed from $|{\mathbf{c}}\rangle$ just by computing on registers of
the simulator, the algorithm cannot distinguish whether $|\omega\rangle$ or
$|{\mathbf{c}}\rangle$ is stored by the simulator. The only issue is if the
number of copies of some state in $|\omega\rangle$ gets reduced mod $N$, but
this cannot happen by our choice of $\ell\geq T$ and $N\geq T+\ell$. ∎

Let $c_{i}$ be $\ell$ minus the number of copies of $|\phi_{i}\rangle$ and
$d_{i}$ be $\ell$ minus the number of copies of $|\psi_{i}\rangle$ in
$|\omega\rangle$. By mapping the constraints on ${\mathbf{c}}$ from Lemma 5.8
to $|\omega\rangle$, we also have:

######  Corollary 5.10.

At any point when running ${\mathcal{A}}^{{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}}()$, the support of the simulator’s state is only on terms
satisfying, $d_{i+1}=d_{i}-c_{i}$.

###  5.4 Simulating ${\mathbf{O}}_{\Psi,{\sf out}}$: Approximating
$|\psi\rangle\langle\psi|$

Above in Section 5.3, we show how to _almost_ simulate
${\mathbf{O}}_{\Psi,{\sf out}}$ just using copies of $|\psi_{i}\rangle$ and
$|\phi_{i}\rangle$. The only part where we need actual knowledge of
$|\psi_{i}\rangle,|\phi_{i}\rangle$ is to implement the reflections
$P_{|\psi_{i}\rangle},P_{|\phi_{i}\rangle}$. Here, we use techniques from
[JLS18] to simulate queries to the reflection, just using our copies of
$|\psi_{i}\rangle$.

Let ${\mathcal{A}}^{P_{|\psi\rangle}}$ be an algorithm making $Q$ queries to
$P_{|\psi\rangle}$. [JLS18] simulate the queries to $P_{|\psi\rangle}$ as
follows. Initialize a register ${{\sf Sym}}^{\ell}{\mathcal{H}}$ to contain
$\ell$ copies of $|\psi\rangle$. Now, instead of responding to each query with
$P_{|\psi\rangle}$, respond to each query with ${{\sf Sym}}^{\ell+1}$, the
reflection about the symmetric subspace of $\ell+1$ copies of ${\mathcal{H}}$,
where $\ell$ copies come from the simulator’s register ${{\sf
Sym}}^{\ell}{\mathcal{H}}$, and the remaining register is the query.

Let $\rho_{0}$ be the final state of the algorithm
${\mathcal{A}}^{P_{|\psi\rangle}}$ when making queries to the actual
reflection, together with $\ell$ copies of $|\psi\rangle$. Let $\rho_{1}$ be
the final state of ${\mathcal{A}}$ when the queries are simulated, together
with the final state of ${{\sf Sym}}^{\ell}{\mathcal{H}}$ (which is symmetric
but may no longer be identical copies of $|\psi\rangle$ since the simulation
will have perturbed them).

######  Lemma 5.11 ([JLS18], Theorem 4).

$TD\left[\rho_{0},\rho_{1}\right]\leq\frac{2Q}{\sqrt{\ell+1}}$

In our case, we have to be a bit careful applying Lemma 5.11, since we do not
have a fixed number of copies of $|\psi\rangle$, and the states in
${\mathcal{S}}_{i},{\mathcal{T}}_{i}$ can be in superposition of having
differing numbers of copies. Instead, we will need the following refinement.
Initialize a register ${{\sf Sym}}^{*}{\mathcal{H}}$ to contain $\ell$ copies
of $|\psi\rangle$. Now, respond to each query with the reflection ${{\sf
Sym}}^{*+1}$: for states in ${{\sf Sym}}^{*}{\mathcal{H}}$ contained in ${{\sf
Sym}}^{\ell^{\prime}}{\mathcal{H}}$, ${{\sf Sym}}^{*+1}$ will reflect about
the symmetric subspace of the joint system of ${{\sf
Sym}}^{\ell^{\prime}}{\mathcal{H}}$ and the query register. Between queries,
${\mathcal{A}}$ is now allowed to add or remove copies of $|\psi\rangle$ from
${{\sf Sym}}^{*}{\mathcal{H}}$. Let $T$ be an upper bound on the number of
copies that can be removed. Let $\rho_{0}$ be the final joint state
${\mathcal{A}}$ and ${{\sf Sym}}^{*}{\mathcal{H}}$ when ${\mathcal{A}}$’s
queries are answered by $P_{|\psi\rangle}$, and let $\rho_{0}$ be the final
joint state when the queries are answered by ${{\sf Sym}}^{*+1}$.

######  Corollary 5.12.

If the number of removed copies is at most $T$,
$TD\left[\rho_{0},\rho_{1}\right]\leq\frac{2Q}{\sqrt{\ell-T+1}}$

###### Proof.

This follows from a simple hybrid argument. Let $H_{0}$ be the case where
${\mathcal{A}}$’s queries are answered with $P_{|\psi\rangle}$, and $H_{i}$ be
the case where the first $Q-i$ queries are answered with $P_{|\psi\rangle}$,
and the remaining queries are answered with ${{\sf Sym}}^{*+1}$. It suffices
to prove that the trace distance between $H_{i}$ and $H_{i+1}$ is at most
$2/\sqrt{\ell-T+1}$, and the triangle inequality implies the lemma.

Toward that end, observe that $H_{i},H_{i+1}$ are identical except for the
$i$th query from the end. Up until this point, ${{\sf Sym}}^{*}{\mathcal{H}}$
has not been used to answer queries, though it may have had some copies of
$|\psi\rangle$ added or removed. Therefore, the state of ${{\sf
Sym}}^{*}{\mathcal{H}}$ is a superposition over
$|\psi\rangle^{\otimes\ell^{\prime}}$ for several different $\ell^{\prime}$.
Since ${\mathcal{A}}$ is only allowed to remove up to $T$ of the copies, we
know that the support of this state has $\ell^{\prime}\geq\ell-T$. It is
therefore a straightforward application of Lemma 5.11 that the trace distance
between $H_{i},H_{i+1}$ is at most $\frac{2}{\sqrt{\ell-T+1}}$, as desired. ∎

We now apply Lemma 5.11 to for each $|\psi_{i}\rangle,|\phi_{i}\rangle$. We
set $Q=2T$ and use that our simulation ${\mathbf{O}}^{(2)}$ makes $2T$ queries
to each projection oracle (2 for each of ${\mathcal{A}}$’s $T$ queries) and
removes at most $T$ copies of each $|\psi_{i}\rangle,|\phi_{i}\rangle$. We
therefore obtain a simulator ${\mathbf{O}}^{(3)}_{\Psi,{\sf out},\ell}$ which
is given $\ell$ copies of each of the $|\psi_{i}\rangle,|\phi_{i}\rangle$, and
attempts to simulate ${\mathbf{O}}^{(2)}_{\Psi,{\sf out},\ell}$. We
immediately have:

######  Lemma 5.13.

Let ${\mathcal{A}}$ be a time $T$ algorithm. Then for any $\ell>T$, any
$\Psi$, any ${\sf out}$, and output $z$,

$TD\left[{\mathcal{A}}^{{\mathbf{O}}^{(2)}_{\Psi,{\sf
out},\ell}}(),{\mathcal{A}}^{{\mathbf{O}}^{(3)}_{\Psi,{\sf
out},\ell}}()\right]\leq\frac{8tT}{\sqrt{\ell-T+1}}$

where the states on both sides include the register provided to
${\mathbf{O}}^{(2)},{\mathbf{O}}^{(3)}$ which initially contains the $\ell$
copies of each of the $|\psi_{i}\rangle,|\phi_{i}\rangle$.

Now measure the number of ${\mathcal{H}}_{2}^{n}$ registers in each of
${\mathcal{S}}_{i}$ and ${\mathcal{T}}_{i}$, obtaining values $\ell-c_{i}$ and
$\ell-d_{i}$ for integers $c_{i},d_{i}$. By Corollary 5.10, we have:

######  Corollary 5.14.

With probability 1, $d_{i+1}=d_{i}-c_{i}$.

######  Lemma 5.15.

Except with probability at most
$\frac{8tT}{\sqrt{\ell-T+1}}+\frac{2t\times\ell}{2^{n}-1+\ell}$, $c_{i}\geq 0$
and $d_{i}\geq 0$ for all $i$.

###### Proof.

If any $c_{i}$ (resp. $d_{i}$) are less than zero, it means the number of
“copies” of $|\psi_{i}\rangle$ of the simulator exceeds the original number
provided originally. If these were actually perfect copies, then this would
violate the unclonability of Haar random states. Indeed, it is known [Wer98]
that for a Haar random state over dimension $D$, the probability of mapping
$r$ copies to $r+1$ is bounded by $\ell/(D+\ell)$. In our case, $D=2^{n}-1$
(since the states are Haar random in ${\mathcal{H}}$, which is
${\mathcal{H}}_{2}^{\otimes n}$ excluding $|0\rangle$). Then we can union
bound over all $2t-1\leq 2t$ states $|\psi_{i}\rangle,|\phi_{i}\rangle$, to
get the probability of any $c_{i}$ or $d_{i}$ being less than 0 being at most
$2t\times\ell/(2^{n}-1+\ell)$.

Now, the copies provided to the simulator have potentially been perturbed as
the simulator runs. However, Lemma 5.13 implies that they can only have been
perturbed by $\frac{8tT}{\sqrt{\ell-T+1}}$, meaning the states are still close
to the respective $|\psi_{i}\rangle,|\phi_{i}\rangle$. Putting these together
completes the proof of the lemma.∎

###  5.5 Putting it All Together

When ${\mathcal{A}}$ terminates, apply the operation $P_{|\psi_{t}\rangle}$ to
the output. If it accepts, then add the resulting state to
${\mathcal{S}}_{t}$. By piecing together the above results, we therefore have
an algorithm which, with probability at least

$W:=\frac{1}{(48T)^{2}}-\frac{8tT}{\sqrt{\ell-T+1}}-\frac{2t\times\ell}{2^{n}-1+\ell}$

results in $c_{t}\geq 1$, and for $i\in[1,t-1]$, $c_{i},d_{i}\geq 0$ and
$d_{i+1}=d_{i}-c_{i}$. If we assume $T\geq\max(n,t)$ and let
$\ell=\Omega(T^{6})=\Omega(t^{2}T^{4})$, and if we assume $T^{6}\ll 2^{n}$, we
can lower bound $W$ as $\Omega(T^{-2})$.

But observe that in this case, we must have all $d_{i}\geq 1$. In this case,
the system has collapsed to a space of lower dimension. Specifically, as each
of the registers ${\mathcal{F}}_{i},{\mathcal{G}}_{i}$ are in the symmetric
spaces ${{\sf Sym}}^{\ell-c_{i}}{\mathcal{H}},{{\sf Sym}}^{\ell-
d_{i}}{\mathcal{H}}$, their dimension is $\binom{(2^{n}-1)+(\ell-
c_{i})-1}{\ell-c_{i}},\binom{(2^{n}-1)+(\ell-d_{i})-1}{\ell-d_{i}}$,
respectively. Thus, if we let $S$ be the algorithm’s space, and using that the
$d_{i}\geq 1$ and the $c_{i}\geq 0$, the total dimension of the joint system
of the simulator’s state and algorithm’s state is at most

$D_{\sf
Final}:=\binom{(2^{n}-1)+\ell-1}{\ell}^{t}\times\binom{(2^{n}-1)+(\ell-1)-1}{\ell-1}^{t-1}\times
2^{S}$

On the other hand, these spaces all started in the symmetric subspace ${{\sf
Sym}}^{\ell}{\mathcal{H}}$, which has dimension
$\binom{(2^{n}-1)+\ell-1}{\ell}$. Specifically, since the $|\psi_{i}\rangle$
and $|\phi_{i}\rangle$ are Haar random, the initial mixed state is equivalent
to the totally mixed state in this symmetric subspace. The algorithm’s state
starts out deterministically in the state $|0\rangle$. Thus, the initial state
joint state of the algorithm and simulator is a totally mixed state in a space
of dimension

$D_{\sf Initial}:=\binom{(2^{n}-1)+\ell-1}{\ell}^{2t-1}\times 1$

######  Lemma 5.16.

Let $\rho$ be a totally mixed state in a subspace of dimension $D_{\sf
Initial}$. Let $U$ be a unitary. Let $S_{\sf Final}$ be any subspace of
dimension $D_{\sf Final}$, which we will also associate with the projection
onto that space. Then ${\sf Tr}[S_{\sf Final}U\rho U^{\dagger}S_{\sf
Final}]\leq D_{\sf Final}/D_{\sf Initial}$. In other words, the probability
that a totally mixed state in dimension $D_{\sf Initial}$ can be mapped to a
space of dimension $D_{\sf Final}$ using unitary computations is at most
$D_{\sf Final}/D_{\sf Initial}$.

###### Proof.

Since $\rho$ is a totally mixed state in a subspace of dimension $D_{\sf
Initial}$, it has $D_{\sf Initial}$ positive eigenvalues, all equal to
$1/D_{\sf Inital}$. On the other hand, the state $S_{\sf Final}U\rho
U^{\dagger}S_{\sf Final}$ has rank at most $D_{\sf Final}$, and therefore the
number of non-negative eigenvalues is at most $D_{\sf Final}$. Moreover, if
$\lambda$ is the maximal eigenvalue of $S_{\sf Final}U\rho U^{\dagger}S_{\sf
Final}$ and $|\tau\rangle$ the associated maximal eigenvector, then

$\lambda=\langle\tau|S_{\sf Final}U\rho U^{\dagger}S_{\sf
Final}|\tau\rangle=\langle\tau^{\prime}|\rho|\tau^{\prime}\rangle\leq(1/D_{\sf
Inital})\langle\tau^{\prime}|\tau^{\prime}\rangle\leq 1/D_{\sf Inital}$

where $|\tau^{\prime}\rangle=U^{\dagger}S_{\sf Final}|\tau\rangle$, which has
norm at most 1 since it is the projection of a norm-1 vector. In other words,
the maximal eigenvalue $\lambda$ is at most the maximal eigenvalue of $\rho$.
Since the number of non-negative eigevalues is at most $D_{\sf Final}$, the
trace, which equals the sum of all eigenvalues, is at most $D_{\sf
Final}/D_{\sf Inital}$, as desired. ∎

Applying Lemma 5.16, we therefore have:

$\Omega(T^{-2})\leq D_{\sf Final}/D_{\sf
Initial}=\left(\frac{\ell}{(2^{n}-1)+\ell}\right)^{t-1}\times 2^{S}$

Rearranging and taking logarithms gives

$S\geq\Omega(\;tn-t\log\ell-\log T\;)$

Using our assumption that $T^{6}\ll 2^{n}$ (equivalently, $T\ll 2^{n/6}$) and
setting $\ell\geq\Omega(T^{6})$, we have that $S\geq\Omega(tn)$. This
completes the proof of Lemma 5.2.

##  6 Our Main Theorem

We now prove our main theorem.

######  Theorem 6.1.

Fix a proper universal measurement set. Then there are constants $c,d$ such
that there is no black box $(S^{\prime}=cT,T^{\prime}=2^{dS})$-space-time
purifier.

In other words, either $S^{\prime}\geq\Omega(T)$ or $T^{\prime}\geq
2^{\Omega(S)}$. The rest of this section will be devoted to proving Theorem
6.1.

#### Roadmap.

We break into three cases: the first is when $T$ is small, specifically $T<S$.
In this case, we can trivially bound $S^{\prime}$. The second case is when $T$
is large, specifically $T\geq 2^{\Omega(S)}$. In this case, we can bound
$T^{\prime}$ easily (regardless of $S^{\prime}$) using known query complexity
lower-bounds. In both these “easy” cases, we actually do not even care that
the compiler is removing measurements, as the bounds hold for _any_ circuit
that approximates the starting circuit. In the final and most interesting case
when $S\leq T\leq 2^{O(S)}$. Here is where we finally use the fact that the
compiler is actually removing measurements, and invoke our oracle from Section
5. This requires some care, since our model allows the compiled program to
effectively have non-uniform advice about the oracle, which our analysis in
Section 5 did not handle. We then use known techniques to get a lower-bound
even in the case of advice, thus completing the theorem.

###  6.1 The case $T<S$

Let ${\mathcal{G}}_{0}$ be the proper universal gate set. Let ${\mathbf{U}}$
be an arbitrary permutation matrix acting on $S$ qubits. Consider the gate set
${\mathcal{G}}_{0}\cup\\{{\mathbf{U}}\\}$. Consider the space-$S$, time-$T$
for $T=1<S$ circuit $C$ which simply queries ${\mathbf{U}}$ on its input. Now
consider any other circuit $C^{\prime}$ which approximates $C$, meaning it
computes the permutation ${\mathbf{U}}$. Since $C^{\prime}$ must act on input
and output of $S$ qubits, $C^{\prime}$ must have space $S^{\prime}\geq S$.
Thus no compiler (in particular, no purifier) can map space $S$ to space
$S^{\prime}<S$. In particular, if $T<S$, then any compiler/purifier must have
$S^{\prime}>T$.

###  6.2 The case $T\geq 2^{\Omega(S)}$

Let ${\mathcal{G}}_{0}$ be the proper universal gate set. Let
$H:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ be a permutation, and consider the
gate set ${\mathcal{G}}_{0}\cup\\{{\mathbf{H}}\\}$, where ${\mathbf{H}}$ is
the unitary representation of $H$, which acts on $2n$ qubits. We first recall
the foundational Grover’s algorithm, re-expressed in our language.

######  Lemma 6.2 ([Gro96]).

There is a quantum circuit $C$ running in space $S=2n$ and time
$O(2^{n/2})=2^{O(S)}$ over ${\mathcal{G}}_{0}\cup\\{{\mathbf{H}}\\}$, such
that for any $x$, $\Pr[C(x)=H^{-1}(x)]\geq 1-O(2^{-n})$.

On the other hand, we know by the optimality of Grover search [BBBV97], that
_any_ circuit must make $\Omega(2^{n/2})$ queries to ${\mathbf{H}}$, and must
therefore run in at least as much time. However, we note that our notion of
compiler allows the compiled circuit to depend on the gate set, and in
particular the function $H$. But a priori it may be possible for a circuit
that depends on $H$ to beat the basic $2^{n/2}$ bound. Fortunately, this is
the domain of pre-processing attacks, and is well-understood. We recall the
following theorem of Nayebi et al. [NABT15], again rephrased in our language:

######  Theorem 6.3 ([NABT15]).

There is a polylogarithmic function ${\sf polylog}$ such that the following is
true. If $H$ is a random permutation, then for any circuit $C^{\prime}$ that
may depend on $H$, if $C^{\prime}$ has at most $Q$ ${\mathbf{H}}$ gates and
total size $T^{\prime}$ such that $Q^{2}T^{\prime}{\sf
polylog}(T^{\prime})\leq 2^{n}$, then $\Pr[C^{\prime}(x)=H^{-1}(x)]<2/3$.

Note that [NABT15] considers quantum advice, as opposed to circuits that
depend on $H$. But these are equivalent by thinking of the circuit of size
$T^{\prime}$ itself as the advice, which takes $T^{\prime}\log T^{\prime}$
bits to write down.

Since $Q\leq T^{\prime}$, we therefore have that for $C^{\prime}$ to
approximate $C$, it must be that $T^{\prime}\geq\Omega(2^{n/3}/{\sf
poly}(n))\geq 2^{\Omega(n)}=2^{\Omega(S)}$. Thus, for any $S$ and any $T\geq
2^{\Omega(S)}$, we can choose $n$ to be a sufficiently small constant multiple
of $S$ so that Grover’s algorithm runs in time $\leq T$ and space $\leq S$.
Meanwhile, any compiler (whether or not it is a purifier) must have
$T^{\prime}\geq 2^{\Omega(S)}$.

###  6.3 The case $S\leq T\leq 2^{O(S)}$

Let $t=\Theta(T/S)$ and $n=\Theta(S)$ and $m=\lceil\log t+1\rceil$. We
construct a unitary ${\mathbf{U}}$ as follows. Choose a random function
$F:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. For each $x\in\\{0,1\\}^{n}$, sample
$\Psi_{x}$ as the description of $2t-1$ Haar random states. Then
${\mathbf{U}}$ is the oracle acting on ${\mathcal{H}}_{2}^{\otimes(n+m+n+n)}$
defined as:

${\mathbf{U}}=\sum_{x\in\\{0,1\\}^{n}}|x\rangle\langle
x|\otimes{\mathbf{O}}_{\Psi_{x},F(x)}$

Our gate set will be ${\mathcal{G}}_{0}\cup\\{{\mathbf{U}}\\}$, where
${\mathcal{G}}_{0}$ is the fixed proper universal general gate set.

Observe that we can use ${\mathbf{U}}$ and the algorithm from Lemma 5.1 to
evaluate the function $F(x)$ with perfect probability, in time $O(nt)=T$ and
space $O(n+\log(t))=O(n)=S$, using measurements. It remains to prove that no
_unitary_ algorithm running in space $o(T)$ and time $2^{o(S)}$ with gate set
${\mathcal{G}}_{0}\cup\\{{\mathbf{U}}\\}$ can even approximately compute
$F(x)$. To do so, we use the lower bound from Lemma 5.2. That result showed a
lower bound for low space-time algorithms to compute the bits $F(x)$ for any
$x$. However, the lower bound in Lemma 5.2 only applies to circuits that are
specified independently from the choice of unitary ${\mathbf{U}}$. Here, we
show that even if the choice of circuit depends on ${\mathbf{U}}$, then it
still remains hard to compute $F(x)$ on most $x$. The idea is to view the
circuit description as non-uniform advice about ${\mathbf{U}}$. This advice
could have some of the $F(x)$ hardcoded. However, because the circuit needs to
be small, the advice is therefore small, and by the incompressibility of
random strings, most of $F(x)$ cannot be hardcoded. The challenge here is that
there may be a clever algorithm which takes the advice string and also makes
queries to ${\mathbf{U}}$, and is able to use the advice to reduce the space-
time requirements for computing $F(x)$, even if $F(x)$ is not directly
hardcoded in the advice. Here, we show that this is not possible.

Note that the situation is similar to the “salting defeats pre-processing”
setting of [CGLQ20]. There, the authors consider a general cryptographic game
relative to a random classical oracle, and show that if a game is hard
relative to algorithms that are independent of the random oracle, then it is
also hard relative to algorithms with advice, provided the game is “salted,”
meaning a random salt of sufficient length is appended to the random oracle
queries. In our setting, the original un-salted game is to compute $o$ given
${\mathbf{O}}_{\Psi,o}$, and the salted game is to compute $F(x)$ for a random
$x$, given ${\mathbf{U}}$. Unfortunately, it is unclear how to apply their
result to our setting, since our oracle ${\mathbf{O}}$ is a structured quantum
oracle and not a random classical oracle. We also care about the space
complexity of the game, which is not considered in [CGLQ20].

Instead, we will borrow a technique from [YZ22], which can also be seen as a
“salting defeats pre-processing” result, except it is far more flexible. On
the other hand, the quantitative bounds are weaker, though they are sufficient
for our purposes.

#### A Technical Lemma.

Here we give a simple lemma which states that, given joint leakage on many iid
random variables sampled from a distribution ${\mathcal{D}}$, the marginal
distribution of most of the variables will still be distributed approximately
as ${\mathcal{D}}$.

######  Lemma 6.4.

Let ${\mathcal{D}}$ be a distribution and $X_{1},\dots,X_{g},Y$ be iid random
variables sampled from ${\mathcal{D}}$. Let $L$ be a function with co-domain
of size $2^{r}$. Then

$\Delta(\;(i,X_{i},F(X_{1},\dots,X_{g}))\;,\;(i,Y,L(X_{1},\dots,X_{g}))\;)\leq\sqrt{r/2g}$

Above, $i$ is uniform in $[g]$.

###### Proof.

Let $I(X;Y)$ denote the mutual information between random variables $X$ and
$Y$. Then

$r\geq
I(\;L(X_{1},\dots,X_{g})\;;\;X_{1},\dots,X_{t}\;)\geq\sum_{i=1}^{g}I(\;L(X_{1},\dots,X_{g})\;;\;X_{i}\;)$

where the second inequality is due to the independence of the $X_{i}$. Let
$\delta_{i}$ be the statistical distance between
$(L(X_{1},\dots,X_{g}),X_{i})$ and $(L(X_{1},\dots,X_{g}),Y)$. Let $\delta$ be
the statistical distance between $(i,X_{i},L(X_{1},\dots,X_{g}))$ and
$(i,Y,L(X_{1},\dots,X_{g}))$; our goal is to bound $\delta$.
$I(\;L(X_{1},\dots,X_{g})\;X_{i}\;)$ is just the KL divergence between
$(L(X_{1},\dots,X_{g}),X_{i})$ and $(L(X_{1},\dots,X_{g}),Y)$. By Pinsker’s
inequality, we therefore have that
$\delta_{i}\leq\sqrt{I(\;L(X_{1},\dots,X_{t})\;X_{i}\;)/2}$. This implies

$r\geq 2\sum_{i=1}^{g}\delta_{i}^{2}$

On the other hand, $\delta=(\sum_{i}\delta_{i})/g$. Jensen’s inequality then
gives that

$\delta\leq\sqrt{\sum_{i}\delta_{i}^{2}/g}\leq\sqrt{r/2g}\qed$

#### Our Reduction.

We are now ready to give our reduction.

######  Lemma 6.5.

Consider a function ${\mathcal{C}}(F,\\{\Psi_{x}\\}_{x})$ which outputs a
circuit ${\mathcal{A}}$ of size $r$, where ${\mathcal{A}}$ makes queries to
${\mathbf{U}}$ and runs in space $S$ and time $T$. Let $T\leq 2^{n/4}$.
Suppose that with probability $p$ over the choice of $F$ and
$\\{\Psi_{x}\\}_{x}$, ${\mathcal{A}}$ is able to compute $F(x)$ with
probability $2/3$ for all $x$. Then there is a unitary circuit ${\mathcal{B}}$
which gets no input and makes queries to ${\mathbf{O}}_{\Psi^{*},o^{*}}$ for a
random choice of $\Psi^{*},o^{*}$, and is able to output $o^{*}$ with
probability at least $7/12$ for sufficiently large $n$. ${\mathcal{B}}$ makes
at most $O(T)$ queries to ${\mathbf{O}}_{\Psi^{*},o^{*}}$ and for an
appropriate gate set (which is independent of ${\mathbf{O}}_{\Psi^{*},o^{*}}$)
has space $O(S)$.

###### Proof.

To construct ${\mathcal{B}}$, do the following. First choose a random subset
$V\subseteq\\{0,1\\}^{n}$ of size $g$, for a parameter $g$ to be chosen later.
Also choose a random $x^{*}\in\\{0,1\\}^{n}\setminus V$. Then choose
$F,\\{\Psi_{x}\\}_{x}$, and let
${\mathcal{A}}={\mathcal{C}}(F,\\{\Psi_{x}\\}_{x})$. Now, for each $x\in V$,
sample $o_{x}^{\prime}\leftarrow\\{0,1\\}$ and a fresh random
$\Psi_{x}^{\prime}$. We define a unitary ${\mathbf{V}}$ as

${\mathbf{V}}=\sum_{x\in\\{0,1\\}^{n}\setminus V}|x\rangle\langle
x|\otimes{\mathbf{O}}_{\Psi_{x},F(x)}+\sum_{x\in V}|x\rangle\langle
x|\otimes{\mathbf{O}}_{\Psi_{x}^{\prime},o_{x}^{\prime}}$

${\mathcal{B}}$ will run ${\mathcal{A}}$ on input $x^{*}$, but answer
${\mathcal{A}}$’s queries with the unitary ${\mathbf{U}}^{\prime}$ defined as:

${\mathbf{U}}^{\prime}=\sum_{x\in\\{0,1\\}^{n}\setminus(V\cup\\{x^{*}\\})}|x\rangle\langle
x|\otimes{\mathbf{O}}_{\Psi_{x},F(x)}+\sum_{x\in V}|x\rangle\langle
x|\otimes{\mathbf{O}}_{\Psi_{x}^{\prime},o_{x}^{\prime}}+|x^{*}\rangle\langle
x^{*}|\otimes{\mathbf{O}}_{\Psi^{*},o^{*}}$

${\mathcal{B}}$ can simulate ${\mathbf{U}}^{\prime}$ with minimal time and
space overhead by making a single query each to ${\mathbf{V}}$ and
${\mathbf{O}}_{\Psi^{*},o^{*}}$. Thus, by including ${\mathbf{V}}$ in the gate
set for ${\mathcal{B}}$, the time and space complexity are linear in that of
${\mathcal{A}}$.

We lower bound ${\mathcal{B}}$’s success probability in a few steps.

######  Claim 6.6.

Fix ${\mathbf{U}},{\mathbf{A}},x^{*}$. Then
$|\Pr[{\mathcal{A}}^{\mathbf{U}}(x^{*})=F(x^{*})]-\Pr[{\mathcal{A}}^{\mathbf{V}}(x^{*})=F(x^{*})]|\leq
4T\sqrt{g/(2^{n}-1)}$, where the probability is taken over the randomness of
${\mathbf{A}}$ and the choice of ${\mathbf{V}}$.

###### Proof.

${\mathbf{U}}$ and ${\mathbf{V}}$ differ only on inputs $x\in V$, which is
chosen randomly. Consider running ${\mathcal{A}}^{\mathbf{U}}(x^{*})$. Since
the view of ${\mathcal{A}}$ is independent of $V$ (except that $x^{*}\notin
V$), the expected query weight of points in $V$ is at most
$\epsilon=gT/(2^{n}-1)$, with equality obtained only if the query weight on
$x^{*}$ is 0. Lemmas 3.1 and 3.2 then imply the difference in output
probabilities is at most $4\sqrt{T\epsilon}$, proving the claim. ∎

######  Claim 6.7.

Let $r$ be the description size of ${\mathcal{A}}$. Then
$|\Pr[{\mathcal{A}}^{\mathbf{V}}(x^{*})=F(x^{*})]-\Pr[{\mathcal{A}}^{{\mathbf{U}}^{\prime}}(x^{*})=F(x^{*})]|\leq\sqrt{r/2g}$,
where the probability is taken over the choice of
${\mathbf{U}},$V$,{\mathbf{V}},{\mathbf{A}},x^{*}$ and the randomness from
running ${\mathbf{A}}$.

###### Proof.

We apply Lemma 6.4, where $X_{1},\dots,X_{g+1}$ are the variables
$(\Psi_{x},F(x))$ for $x\in V\cup\\{x^{*}\\}$, and $L$ is the function
obtained from ${\mathcal{C}}$ by fixing $(\Psi_{x},F(x))$ for $x\notin
V\cup\\{x^{*}\\}$. Since $x^{*}$ is uniform in $V\cup\\{x^{*}\\}$ and all the
$(\Psi_{x},F(x))$ for $x\in V$ have been replaced with fresh random samples,
Lemma 6.4 shows that $(\Psi_{x^{*}},F(x^{*}))$ and a fresh uniform
$(\Psi^{*},o^{*})$ have statistical distance $\sqrt{r/2g}$, thus bounding the
change in success probability. ∎

Now we set $g=\sqrt{(2^{n}-1)r/32T^{2}}$, we have that

$\Pr[{\mathcal{B}}^{{\mathbf{O}}_{\Psi^{*},o^{*}}}()=o^{*}]=\Pr[{\mathcal{A}}^{{\mathbf{U}}^{\prime}}(x^{*})=F(x^{*})]\geq\frac{2}{3}-\sqrt[4]{\frac{32T^{2}r}{2^{n}-1}}$

Since $r$ is the description size of a circuit of size $T$, we have that
$r=T\times{\sf polylog}(T)$. Therefore, since $T\leq 2^{n/4}$, for
sufficiently large $n$ we have that $\sqrt[4]{\frac{32T^{2}r}{2^{n}-1}}\leq
1/12$. Thus $\Pr[{\mathcal{B}}^{{\mathbf{O}}_{\Psi^{*},o^{*}}}()=o^{*}]\geq
7/12$.∎

Combining Lemma 6.5 with Lemma 5.2 (which rules out such a ${\mathcal{B}}$)
finishes the case $S\leq T\leq 2^{O(S)}$. This finishes the proof of Theorem
6.1.∎

## References

  * [AKN98] Dorit Aharonov, Alexei Kitaev, and Noam Nisan.  Quantum circuits with mixed states.  In 30th ACM STOC, pages 20–30. ACM Press, May 1998.
  * [Amb00] Andris Ambainis.  Quantum lower bounds by quantum arguments.  In 32nd ACM STOC, pages 636–643. ACM Press, May 2000.
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM J. Comput., 26(5):1510–1523, Oct 1997.
  * [BBC+98] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  In 39th FOCS, pages 352–361. IEEE Computer Society Press, November 1998.
  * [Ben89] Charles H. Bennett.  Time/space trade-offs for reversible computation.  SIAM J. Comput., 18(4):766–776, aug 1989.
  * [BH97] G. Brassard and P. Hoyer.  An exact quantum polynomial-time algorithm for simon's problem.  In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems. IEEE Comput. Soc, 1997.
  * [BHMT02] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation, 2002.
  * [CGLQ20] Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian.  Tight quantum time-space tradeoffs for function inversion.  In 61st FOCS, pages 673–684. IEEE Computer Society Press, November 2020.
  * [CMSZ22] Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry.  Post-quantum succinct arguments: Breaking the quantum rewinding barrier.  In 62nd FOCS, pages 49–58. IEEE Computer Society Press, February 2022.
  * [FR21] Bill Fefferman and Zachary Remscrim.  Eliminating intermediate measurements in space-bounded quantum computation.  In Samir Khuller and Virginia Vassilevska Williams, editors, 53rd ACM STOC, pages 1343–1356. ACM Press, June 2021.
  * [GR22] Uma Girish and Ran Raz.  Eliminating intermediate measurements using pseudorandom generators.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 76:1–76:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In 28th ACM STOC, pages 212–219. ACM Press, May 1996.
  * [Gro97] Lov K. Grover.  Quantum computers can search rapidly by using almost any transformation.  Physical Review Letters, 80:4329–4332, 1997.
  * [GRZ21] Uma Girish, Ran Raz, and Wei Zhan.  Quantum logspace algorithm for powering matrices with bounded norm.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, ICALP 2021, volume 198 of LIPIcs, pages 73:1–73:20. Schloss Dagstuhl, July 2021.
  * [HM23] Yassine Hamoudi and Frédéric Magniez.  Quantum time-space tradeoff for finding multiple collision pairs.  ACM Trans. Comput. Theory, apr 2023.
  * [IR89] Russell Impagliazzo and Steven Rudich.  Limits on the provable consequences of one-way permutations.  In 21st ACM STOC, pages 44–61. ACM Press, May 1989.
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song.  Pseudorandom quantum states.  In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Heidelberg, August 2018.
  * [KSS+20] Veronika Kuchta, Amin Sakzad, Damien Stehlé, Ron Steinfeld, and Shifeng Sun.  Measure-rewind-measure: Tighter quantum random oracle model proofs for one-way to hiding and CCA security.  In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 703–728. Springer, Heidelberg, May 2020.
  * [KvdW07] Hartmut Klauck, Robert Špalek, and Ronald de Wolf.  Quantum and classical strong direct product theorems and optimal time-space tradeoffs.  SIAM Journal on Computing, 36(5):1472–1493, 2007.
  * [Lan61] R. Landauer.  Irreversibility and heat generation in the computing process.  IBM Journal of Research and Development, 5(3):183–191, 1961.
  * [LMS22] Alex Lombardi, Fermi Ma, and Nicholas Spooner.  Post-quantum zero knowledge, revisited or: How to do quantum rewinding undetectably.  In 63rd FOCS, pages 851–859. IEEE Computer Society Press, October / November 2022.
  * [NABT15] Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan.  Quantum lower bound for inverting a permutation with advice.  Quantum Info. Comput., 15(11–12):901–913, sep 2015.
  * [Sti55] W. Forrest Stinespring.  Positive functions on c*-algebras.  Proceedings of the American Mathematical Society, Apr 1955.
  * [Ta-13] Amnon Ta-Shma.  Inverting well conditioned matrices in quantum logspace.  In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 881–890. ACM Press, June 2013.
  * [Unr12] Dominique Unruh.  Quantum proofs of knowledge.  In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 135–152. Springer, Heidelberg, April 2012.
  * [vMW12] Dieter van Melkebeek and Thomas Watson.  Time-space efficient simulations of quantum computations.  Theory of Computing, 8(1):1–51, 2012.
  * [Wat04] John Watrous.  On the complexity of simulating space-bounded quantum computations.  Comput. Complex., 12(1/2):48–84, jul 2004.
  * [Wat09] John Watrous.  Zero-knowledge against quantum attacks.  SIAM Journal on Computing, 39(1):25–58, 2009.
  * [Wer98] R. F. Werner.  Optimal cloning of pure states.  Phys. Rev. A, 58:1827–1832, Sep 1998.
  * [YZ22] Takashi Yamakawa and Mark Zhandry.  Verifiable quantum advantage without structure.  In 63rd FOCS, pages 69–74. IEEE Computer Society Press, October / November 2022.
  * [Zha19] Mark Zhandry.  How to record quantum queries, and applications to quantum indifferentiability.  In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 239–268. Springer, Heidelberg, August 2019.