bucket brigade, errors can get stuck. That is, if an error occurs on some node
deep in the tree, this does not necessarily affect any other nodes.

The only way for errors to affect the final result is if they propagate to the
root node somehow. At each node, the routing circuit only swaps from one of
its two child nodes, so the error will only propagate upward if it is on the
correct side. As there is only one path which will get routed all the way to
the top of the tree – the path representing the actual address in the query –
an error propagates to the root only if it occurs on this path. But only
$O(\log N)$ qubits are on this path.

Errors could propagate in other ways; for example, if the control qubit has an
error _and_ the routing qubits have errors, then this will erroneously create
a path that propagates further up. But for the error to keep propagating
upward, a very precise sequence of errors must occur to create a path for it,
and this is unlikely for even modestly low probability errors. Overall, if
qubit undergoes an error channel with probability $p$, the error of the final
readout is only $O(p\cdot\log^{2}(N))$ [58].

The bucket-brigade requires all nodes to be in the “wait” state at the start
of an access. However, errors in a previous access that change this state
could persist to later accesses, depending on the device’s Hamiltonian. If the
probability of a persistent error is $p$ for each node in each access, then
after $Q$ accesses the proportion of error-ridden nodes grows proportional to
$Q^{2}p$.

Generally, the per-component error rate $p$ must still be exponentially small
for applications like database QAA, but for other applications, like quantum
linear algebra (see Section IV.4), higher error rates could be manageable.

Moreover, we propose that a bucket-brigade QRAM system could be partially
passive. Following the observation that errors in the root nodes of are more
destructive, we can run full error-correction on the first $k$ layers of the
bucket-brigade tree. If $k$ is selected to be a constant, or at least $o(\log
N)$, then this circumvents the issues with active QRAM that we have
extensively highlighted. The remaining $\log(N)-k$ layers would be a
collection of smaller, passive QRAMs joined to the error-corrected root nodes.
This encounters the same problem of interfacing noisy components with quantum
data encoded into a logical state that we discuss in Section VII. This
proposal requires $2^{k}$ error-corrected nodes, and we expect that the
overall probability of error would scale something like $O(p(\log(N)-k)^{2})$.
This wouldn’t change the asymptotic error rate of bucket-brigade, but with the
same physical error rate, this method could allow larger memories to become
practical than a fully passive bucket-brigade architecture would allow.

Example. To show why the small bucket-brigade error rates are somewhat unique,
we describe here an alternative readout circuit that _does_ require $O(1/N)$
gate error, as shown in Figure 9. To explain this circuit, we add an extra
layer $L$ of qubits at the leaves of the routing tree (shown as boxes in
Figure 9). We then add a single extra qubit prepared in the
$\left|1\right\rangle$ state, and propagate it through the tree by applying
the routing circuits at each node. This routes the $\left|1\right\rangle$ to
the location indexed by the address regiter. From there, for every $i$ such
that $T[i]=1$, we apply a CNOT from the leaf at the $i$th address to a qubit
in $L$. This means this final layer of qubits is all zeros if $T[i]=0$, and
has precisely one qubit in the $\left|1\right\rangle$ state otherwise. Thus,
we can read out the result by computing the parity of this final layer.

Parity is an appealing operation in the surface code, since it can be done by
conjugating a multi-target CNOT (itself depth-1 in a surface code) by Hadamard
gates.

The drawback of this method is that if an error occurs anywhere on this final
layer of ancilla qubits, it will propagate immediately to the output. Thus,
the qubits and gates in $L$ would need to have error rates of $O(1/N)$.

$T$$\mathsf{0}$$\mathsf{1}$$\mathsf{1}$$\mathsf{0}$$\mathsf{0}$$\mathsf{1}$$\mathsf{0}$$\mathsf{0}$$\oplus$$\oplus$$\oplus$
(a)

$\oplus$$\oplus$$\oplus$$\oplus$$\oplus$$\oplus$$\oplus$$\oplus$Output (b)

Figure 9: Alternative, suboptimal bucket-brigade readout forcing the readout
gates to have error rates of $O(1/N)$. The blue nodes are those with
$\left|1\right\rangle$ during the memory access for a specific address (in
this case, $i=2$). Notice that the parity in the second step only needs to use
leaves for $i$ with $T[i]=1$, but we include all of them for clarity.

##  X Other Proposals

Here we summarize some other proposals which do not follow the bucket-brigade
approach, and detail the ways in which they fail to provide passive gate QRAM,
as they are currently described.

$T$Trapped atomLenspPolarizing beam splitterMirrorpLasersp Figure 10:
Schematic of quantum optical fanout QRAM, almost exactly as shown in [48].

###  X.1 Time-bins

Many applications and methods to store quantum states with photon echoes exist
(e.g. [102]), but [78] propose an additional addressing component to turn this
storage into QRAM. To summarize their method, there is a memory cavity with
$M\gg N$ atoms and a control cavity. To store data, the device would send
quantum states encoded as photons into the memory cavity, where they would
excite the memory atoms. The memory atoms can replay this input via a two-
pulse echo technique; sending a second pulse will prompt the atoms to re-emit
the photons that were sent in. Importantly, if photons are sent in one-at-a-
time, they will be re-emitted in a time-reversed order.

Thus, to read the memory, the device sends a pulse which prompts the memory
cavity to re-emit its stored state. With just the memory cavity, this would
re-emit all input states at classically determined times, giving us CRAQM but
not QRAQM. For quantum addressing they use a second _control_ cavity. The
control cavity contains an atom such that, when this atom is in its ground
state, the memory cavity cannot emit any photons. However, when the control
cavity’s atom is excited, it allows the transfer of photons out of the memory
cavity.

An address state $\sum_{i}\alpha_{i}\left|i\right\rangle$ must then be
translated so that each address $\left|i\right\rangle$ is entangled with a
photonic state $\left|\psi_{i}(t)\right\rangle$ which reaches the control
cavity at precisely the right time to allow the memory cavity’s photons to
pass through. In this way, other addresses, which will not be entangled with a
photon pulse at that time, will not allow any emission from the memory cavity.

The fundamental nature of the time-bin addressing means that this requires
$\Omega(N)$ time for each memory access. The purported feature of this method
is the minimal hardware requirements (though it still requires $\Omega(N)$
atoms in the memory cavity), but unary circuit QRAM already provides a near-
optimal circuit on the $\Omega(N)$ side of the time-hardware tradeoff of QRAM
circuits.

In [84], they use a second type of pulse to decohere a memory atom so that it
will only re-emit once an identical pulse is sent to it. Using different
frequencies of pulses to store different memory bits, this could reduce the
total time requirement, at the expense of needing higher precision in pulse
frequencies.

There is still an issue of how the time-bin photonic address state is created.
As an example of how this could be created, consider the unary circuit QRAM.
It classically iterates through addresses $j$, and for each address $j$, flips
the state of a control qubit if the address in superposition equals $j$.
Suppose that flipping the control qubit puts it into an excited state which
can be stimulated to emit a photon. If we do this sequentially, then at time
$t_{j}$, only the address state $\left|j\right\rangle$ will cause a photon to
be emitted, thus the presence of photons at that time is in superposition and
entangled with the state of the address. In this way, applying this
stimulation instead of a CNOT turns the unary circuit QRAM into a circuit that
translates an address superposition into a superposition of time-bin photons.

Unfortunately, this has solved the addressing problem by using another QRAM
circuit to create the address! While superpositions of photons at different
points in time _may_ be a native quantum state in some architecture, for other
architectures, creating such a state is essentially a quantum addressing
problem, which is the difficult problem of QRAM anyway. The decohering pulses
of [84] face a similar issue, where they must be addressed and sent in a
coherent superposition to create a QRAM device.

As a final note, many aspects of the scheme in [78] require $\Omega(N)$ active
interventions. For example, with the photon echo technique, stimualating the
memory cavity to emit its states requires a phase-flipping pulse on all $M$
atoms for each time bin, meaning $\Omega(N)$ pulses that each require
$\Omega(N)$ energy. As in other proposals with photon-atom interactions, the
control cavity requires a stimulating pulse for each interaction (thus,
another $\Omega(N)$ stimulating pulses).

$\scriptscriptstyle\left|0\right\rangle$$\scriptscriptstyle\left|1\right\rangle$$\scriptscriptstyle\left|0\right\rangle$Readout
modeReadout modeSpatial address modesTransfer modes

Figure 11: Phase gate fanout QRACM, from [48]. The address qubits route the
address modes (red), which excites the phase-control qubits (blue transmons).
The excited phase-control qubits are highlighted yellow. This will cause
exactly one cavity’s transfer mode to resonate (dark green), exciting the 2
memory qubits (bottom, blue) for that address. The memory qubits change the
phase of the readout modes (yellow) which can be detected. The arrangement of
the two types of memory qubits (shown as white and grey) represents the data:
in this case, the table is $\mathsf{01010001}$.

###  X.2 Quantum Optical Fanout

[48] describe an architecture using only $\log N$ trapped atoms, and instead
encode the QRAM access in $N$ spatial modes of light. The basic principle is
this: each bit of the address becomes one trapped atom, and then each beam
interacts with the atom, and if the atom is in $\left|1\right\rangle$, the
photon is polarized differently than if the atom is $\left|0\right\rangle$.
Then the photon beam is sent through a half-wave plate which spatially
separates different polarizations, thus doubling the number of photonic modes
and ensuring that an input beam is directed according to the state of the
atom.

Figure 10 duplicates Figure 4 from [48], with a crucial difference: we show
the schematic for an 8-bit address, rather than only 3. This immediately
highlights the problem: the number of spatial modes grows exponentially with
the number of address bits, but they must be focused back onto a single point.

If the photons are not aimed precisely, then after interacting with the atom
they will drift into another spatial mode. This causes an error. The precision
required for this aiming is $O(1/N)$ for $N$ bits of memory. This seems to be
the only physical mechanism for errors to propagate from one sequence of
spatial modes to another, suggesting that the overall error scaling has
similar robustness to bucket-brigade QRAM, but the aiming argument above means
that each component requires a precision scaling as $O(1/N)$ or it will have
an error. Intuitively, it doesn’t matter whether errors propagate across
“paths” of access, if all paths have an error.

Trying to guide the photons with a waveguide does not fix the problem,
regardless of the miniaturization we achieve. Taking the perspective of the
atom, the sources and receptors of the photons and must occupy non-overlapping
sections of all radial paths out of the atom. If either source or receptor has
a smaller cross-sectional area, then we can move it closer, but it occupies
the same “arc-area” from the atom’s perspective. This means the precision of
the beam must be the same – $O(1/N)$ – no matter the absolute area of the
photonic components.

Thus, in the exact formulation given, errors in this QRAM must scale
infeasibly. We can wonder whether a different technology, inspired by this
approach, could succeed. A core function of this approach is that the $i$th
address bit interacts with $2^{i}$ spatial modes in one “operation”. This is
the crux: finding a mechanism to enact such a large number of interactions
passively, with error scaling much less than $2^{i}$, seems difficult if not
impossible.

###  X.3 Phase Gate Fanout

[48] describe another quantum fanout system, shown in Figure 11. This system
translates each address qubit into a photon in one of two spatial modes (based
on $\left|0\right\rangle$ or $\left|1\right\rangle$ in the address qubit,
shown as red horizontal beams in Figure 11). Each of these $2\lg N$ spatial
address modes couples to $N$ phase-control qubits (the upper blue transmons in
Figure 11), so that the phase-control qubits change state when there is a
photon in this spatial address mode.

Each phase-control qubit also couples to a another optical mode, which we’ll
call a transfer mode (the vertical green beams in Figure 11), such that there
are $N$ transfer modes, each coupled to $\lg N$ phase-control qubits. The
coupling is such that if the phase-control qubit is in its
$\left|1\right\rangle$ state, it adds a phase to the transfer mode. This two-
mode coupling is similar to the recently experimentally-realized photon
transistor in [107].

The net effect of all this is that if the address is $\left|j\right\rangle$,
then the $i$th transfer mode gains a phase of $e^{ij\varphi_{0}}$ for some
constant $\varphi_{0}$.

For readout, we have another collection of $N$ memory qubits (the bottom two
rows of transmons in Figure 11), each coupled to a different transfer mode, so
that the $j$th memory qubit interacts with the transfer mode only when the
transfer mode has a phase of $e^{ij\varphi_{0}}$. Thus, the memory qubit
changes state depending on whether the transfer mode is in resonance. For the
final readout, we use another optical readout mode (the yellow beams in Figure
11), which interacts with all memory qubits, and picks up a phase for each one
that is active. This means we will actually need $2N$ memory qubits and 2
readout modes, so that _which_ readout mode gains a phase will encode the
binary result of the memory lookup.

There are a number of practical issues with this scheme.

The foremost issue is the narrowness of the resonance of the memory qubits.
[48] note that there will need to be $N$ different resonant phases, and
analyze the width of a Fabry-Perot cavity’s resonance and conclude that if the
transmissitivity of the beamsplitters in the cavity is $O(1/N)$, the width of
resonant phases is also $O(1/N)$. However, this does not address the need to
fabricate each cavity, where the resonant phase must be constructed with
$O(1/N)$ precision as well. For a Fabry-Perot cavity, this would mean $O(1/N)$
precision in the physical distance between the mirrors.

Second, each address mode must interact with $N$ qubits. Modelled with a
Jaynes-Cummings Hamiltonian, every excited qubit means a reduced photon number
in the address mode. If not all qubits are excited, we will end up with some
superposition where only a small portion of the total amplitude corresponds to
states where the _right_ qubits are exicted to properly perform the memory
access. Thus, we need all qubits to be excited, meaning the photon number of
each address mode must be $\Omega(N)$.

In addition to forcing us to use $\Omega(N\log N)$ energy per QRAM access, we
must also provide this energy to the address modes in such a way that, for
each address qubit, we do not learn _which_ of the two address modes took this
energy. If we learned this, it effectively measures the address qubit. The
quantum router of [27] might suffice.

This QRAM may not even be passive, in fact. To excite the memory qubits, we do
not want to activate a new pulse – which requires $\Omega(N)$ interventions
and $\Omega(N)$ energy – but rather we want the memory qubits to reside in an
optical cavity that maintains some electric field. Consider a back-of-the-
envelope analysis of the losses of the optical cavities. If each cavity has
quality factor $Q$ and resonant frequency $f$, the fraction of energy lost per
unit time is proportional to $Nf/Q$, since there are $N$ cavities. Modern
“ultra-high” quality factors are on the order of $10^{9}$ [73], about the same
scale as the frequency (in hertz) of microwaves. Thus, to maintain the QRAM
for more than a few seconds requires either enormous optical cavities (to
increase the resonant frequency) or spectacular improvements in optical cavity
quality factors. In either case, if these improvements do not keep pace with
the increase in the number of memory bits, the _total_ energy loss quickly
becomes enormous.

Finally, each readout mode interacts with $N$ qubits. If our error model
permits some probability $\epsilon$ of adding the wrong phase from each memory
qubit (e.g., the probability from measuring after interacting with that memory
qubit), then we need $\epsilon$ to be at most $O(1/N)$, or the memory readout
will fail.

Unlike [48], the arrangment of phase-control qubits in Figure 11 means that
for each address, only one cavity has all $n$ phase-control qubits excited.
Potentially one could engineer each phase-control qubit to contribute $1/n$ of
the necessary phase to bring the transfer mode into resonance. If so, the
precision of the resonator might only need to be $O(1/\log N)$. However, given
the readout method, any leakage from the resonators will contribute directly
to readout error (if leakage excites the incorrect memory qubit, the readout
detects this). Hence, the transfer modes may still need $O(1/N)$ precision.

###  X.4 Derangement Codes

[54] proposes error correction based on code switching, which we summarize and
slightly tweak here.

We start by imagining a no-op state $\left|\text{nop}\right\rangle$, such that
not only is $\left|\text{nop}\right\rangle$ invariant under $U_{QRAM}$, the
internal quantum state of the QRAM nodes are also invariant when we input
$\left|\text{nop}\right\rangle$. As an example for bucket-brigade QRAM, we
could use an ancilla flag qubit which controls the production of the input
photons from the address qubits. If this flag is set to $0$, no input photons
are generated and nothing enters the QRAM device.

Then we consider the circuit shown in Figure 12. This has $m$ devices to
access the same table $T$. It generates a superposition of $m$ different
states, indexing which QRAM device to shuffle our real query into (the query
is
$\left|\phi\right\rangle=\sum_{i}\alpha_{i}\left|i\right\rangle\left|0\right\rangle$),
while sending $\left|\text{nop}\right\rangle$ states to all the other devices.
We then apply all the QRACM devices, un-shuffle the state, and measure the
shuffle controls in the Hadamard basis.

$\left|\mathsf{nop}\right\rangle\left|0\right\rangle$$\times$$\dots$$\dots$$\left|\mathsf{nop}\right\rangle\left|0\right\rangle$$\times$$\sum\limits_{i=0}^{N-1}\alpha_{i}\left|i\right\rangle\left|0\right\rangle$$\times$$\phantom{{}^{\otimes
m}}\left|0\right\rangle^{\otimes\lg
m}$$H$$U_{QRACM}(T)$$U_{QRACM}(T)$$\dots$$U_{QRACM}(T)$$\times$$\times$$\times$$\dots$$H$$\left|\mathsf{nop}\right\rangle\left|0\right\rangle$$\left|\mathsf{nop}\right\rangle\left|0\right\rangle$$\dots$$\sum\limits_{i=0}^{N-1}\alpha_{i}\left|i\right\rangle\left|T_{i}\right\rangle$
Figure 12: QRACM with heralded error mitigation, adapted from [54]. Shaded
regions and thicker wires indicate error corrected qubits and operations, and
red rectangles on the border indicate decoding and re-encoding. The controlled
swaps indicate that, based on the $\lg m$ control qubits, the last register is
swapped to one of the intermediate registers. The states shown at the top are
the states if no errors occur, in which case the measurement result is all
$0$.

Measuring all zeros in the shuffle controls means the states that went out
came back to the registers they started in, enforcing a “sameness” among the
queries between different QRAM devices. If the errors are independent, then
this suppresses errors, since it’s unlikely for the same error to occur in all
QRAM devices at the same time.

[54] proposes compressing this to use only one QRAM device by sequentially
controlling swaps, so that only one of $m$ applications of the QRAM applies to
the real query state. Since this error correction method only works for
uncorrelated errors, it fails for bucket-brigade QRAM. Specifically, if an
error occurs at some point in the routing nodes, that error will persist
between queries (unless the routing nodes are reset, which creates an
$\Omega(N)$ cost as discussed previously). Thus, on average half of all errors
will be identical between queries, rendering the error suppression
ineffective.

Expanding their idea to a wide, parallel repetition increases hardware
overhead by a factor of $m$, but we imagine $m\ll N$, otherwise the error
suppression scheme – which requires $\Omega(m\log N)$ gates for the shuffles
alone – will start to approach the cost of a circuit QRAM access.

The overall effect of this is a “heralded” QRAM access, where if we measure
all zeros in the control qubits, we know that the infidelity has been
suppressed to $1/m$ of the physical error rate (see [54, Chapter 4] for
proof), _but_ the probability $p$ of measuring all-zero is approximately equal
to the original physical infidelity. This means that for an algorithm to have
a reasonable probability of success, it must be limited to $O(\frac{1}{1-p})$
QRAM queries. Recalling the applications from Section III, this forbids
database QAA.

Finally, the code switching process raises some issues. Imagine Figure 12 in
the surface code. We can attempt to limit the time when a qubit is outside of
the surface code to the smallest possible, but even a brief period without
error correction could spell disaster for a resource-intensive algorithm.

##  XI Discussion

Large scale, high quality QRAM which is cheap to use is unlikely. It would
require passively-corrected quantum memory and highly complex, high-fidelity
ballistic computation. We argued in Section VI and Section VII that these are
much stronger assumptions about quantum computing hardware than general large-
scale, fault-tolerant quantum computing. Even if those assumptions come true,
QRAM may still be difficult: building a ballistic computation is complicated
(Theorem VI.1) and it may not interact well with the rest of a fault-tolerant
quantum computation (Theorem VII.1). Indeed, we could find no proposed gate-
QRAM technology that was not implicitly active or required unreasonably low
error rates (Section IX,Section X).

All of that said, we cannot _prove_ that cheap QRAM will not be possible.
However, many powerful computing devices (say, a polynomial time SAT-solver)
are not provably impossible, but we do not assume they will be built. Our
claim is that cheap QRAM should be considered infeasible until shown
otherwise, instead of the reverse. While classical RAM appears to set a
precedent for such devices, we argued in Section VIII that this is an
inappropriate comparison: QRAM is more difficult relative to other quantum
computations, than classical RAM is difficult relative to classical
computation.

Despite these critiques, QRAM will likely be a crucial tool for quantum
algorithms. In a circuit model, QRAM has a linear gate cost (regardless of
depth), but optimized circuits allow it to help with quantum chemistry and
some cryptographic attacks (Section V). We encourage readers to consider
circuit QRAM for their algorithms, and use one of the optimized circuits we
referenced.

We leave here a summary of some open questions we raised in this work:

  1. 1.

With the favourable error scaling of bucket-brigade QRACM, can it be more
effective than other methods in a surface code, especially for cryptographic
attacks?

  2. 2.

If we correct only some of the nodes in a bucket-brigade QRAM, can this
suppress enough noise for practical purposes?

  3. 3.

Can Theorem V.2 and Theorem VII.1 extend to account for measurement feedback,
and can the latter extend to data-specific distillation processes?

  4. 4.

How should we model the errors and the costs of construction and use of large-
scale Hamiltonians for ballistic computations?

  5. 5.

Are there codes for which QRAM is transversal, or can otherwise be applied
directly to logical states?

  6. 6.

Can we fix the scaling issues of the transmon-based bucket-brigade memory of
[27]?

  7. 7.

How much noise can fault-tolerant quantum linear algebra tolerate in the QRAM
access, and could bucket-brigade QRAM reach that level?

ACKNOWLEDGEMENTS

We thank John Schanck for many fruitful discussions and providing many of
these arguments; Simon C. Benjamin, Balínt Koczor, Sam McArdle, Shouvanik
Chakrabarti, Dylan Herman, Yue Sun, Patrick Rebentrost and an anonymous
reviewer for helpful comments; and Romy Minko, Ryan Mann, Oliver Brown, and
Christian Majenz for valiant attempts to generalize Theorem D.2. S.J. was
funded by the University of Oxford Clarendon fund and A.G.R. was funded by a
JPMorgan Chase Global Technology Applied Research PhD Fellowship.

DISCLAIMER

This research was funded in part by JPMorgan Chase & Co. Any views or opinions
expressed herein are solely those of the authors listed, and may differ from
the views and opinions expressed by JPMorgan Chase & Co. or its affiliates.
This material is not a product of the Research Department of J.P. Morgan
Securities LLC. This material should not be construed as an individual
recommendation for any particular client and is not intended as a
recommendation of particular securities, financial instruments or strategies
for a particular client. This material does not constitute a solicitation or
offer in any jurisdiction.

## References

  * Aar [15] Scott Aaronson.  Read the fine print.  Nature Physics, 11(4):291–293, April 2015.
  * AGJO+ [15] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan.  On the robustness of bucket brigade quantum RAM.  New Journal of Physics, 17(12):123010, December 2015.
  * AGPS [20] Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, and John M. Schanck.  Estimating quantum speedups for lattice sieves.  In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, pages 583–613, Cham, 2020. Springer International Publishing.
  * AMD [22] AMD.  AMD instinct™ MI250X accelerator, 2022.
  * AS [22] Martin R. Albrecht and Yixin Shen.  Quantum augmented dual attack.  Cryptology ePrint Archive, Paper 2022/656, 2022.  https://eprint.iacr.org/2022/656.
  * BBG+ [13] Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather.  Efficient distributed quantum computing.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2153):20120686, May 2013.
  * BBHL [20] Gustavo Banegas, Daniel J. Bernstein, Iggy Van Hoof, and Tanja Lange.  Concrete quantum cryptanalysis of binary elliptic curves.  IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 451–472, December 2020.
  * BCSS [23] Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen.  Finding many collisions via reusable quantum walks: Application to lattice sieving.  In Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V, page 221–251, Berlin, Heidelberg, 2023. Springer-Verlag.
  * Ber [01] D. J. Bernstein.  Circuits for integer factorization: a proposal, 2001.  https://cr.yp.to/papers.html#nfscircuit.
  * Ber [09] D. J. Bernstein.  Cost analysis of hash collisions: Will quantum computers make sharcs obsolete?  Workshop Record of SHARCS’09: Special-purpose Hardware for Attacking Cryptographic Systems, 2009.
  * BGB+ [18] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven.  Encoding electronic spectra in quantum circuits with linear t complexity.  Phys. Rev. X, 8:041015, Oct 2018.
  * BGM+ [19] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush.  Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization.  Quantum, 3:208, December 2019.
  * BHMT [02] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * BHPP [15] Mihir K Bhaskar, Stuart Hadfield, Anargyros Papageorgiou, and Iasonas Petras.  Quantum algorithms and circuits for scientific computing.  arXiv preprint arXiv:1511.08253, 2015.
  * BHT [97] Gilles Brassard, Peter Høyer, and Alain Tapp.  Quantum cryptanalysis of hash and claw-free functions.  ACM SIGACT News, 28(2):14–19, June 1997.
  * BJLM [13] Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer.  Quantum algorithms for the subset-sum problem.  In Philippe Gaborit, editor, Post-Quantum Cryptography, pages 16–33, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * BJWS [19] Akrem Benatia, Weixing Ji, Yizhuo Wang, and Feng Shi.  Sparse matrix partitioning for optimizing SpMV on CPU-GPU heterogeneous platforms.  The International Journal of High Performance Computing Applications, 34(1):66–80, November 2019.
  * BL [13] Daniel J. Bernstein and Tanja Lange.  Non-uniform cracks in the concrete: The power of free precomputation.  In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology \- ASIACRYPT 2013, pages 321–340, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * BLP+ [16] Benjamin J. Brown, Daniel Loss, Jiannis K. Pachos, Chris N. Self, and James R. Wootton.  Quantum memories at finite temperature.  Reviews of Modern Physics, 88(4), November 2016.
  * [20] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven.  Focus beyond quadratic speedups for error-corrected quantum advantage.  PRX Quantum, 2(1):010103, 2021.
  * [21] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven.  Focus beyond quadratic speedups for error-corrected quantum advantage.  PRX Quantum, 2:010103, Mar 2021.
  * BMR+ [20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Curran Associates, Inc., 2020.
  * BP [95] G. Bilardi and F.P. Preparata.  Horizons of parallel computation.  Journal of Parallel and Distributed Computing, 27(2):172–182, 1995\.
  * BS [20] Xavier Bonnetain and André Schrottenloher.  Quantum security analysis of CSIDH.  In Advances in Cryptology – EUROCRYPT 2020, pages 493–522. Springer International Publishing, 2020.
  * BT [23] Ainesh Bakshi and Ewin Tang.  An improved classical singular value transformation for quantum machine learning.  arXiv preprint arXiv:2303.01492, 2023.
  * BWP+ [17] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * Cad [15] Arnau Sala Cadellans.  A transmon based quantum switch for a quantum random access memory.  Master’s thesis, Leiden University Faculty of Science, Leiden, Netherlands, 2015.
  * CCH+ [22] Nadiia Chepurko, Kenneth Clarkson, Lior Horesh, Honghao Lin, and David Woodruff.  Quantum-inspired algorithms from randomized numerical linear algebra.  In International Conference on Machine Learning, pages 3879–3900. PMLR, 2022.
  * CDEH+ [21] Kevin C. Chen, Wenhan Dai, Carlos Errando-Herranz, Seth Lloyd, and Dirk Englund.  Heralded quantum random access memory in a scalable photonic integrated circuit platform.  In Conference on Lasers and Electro-Optics. Optica Publishing Group, 2021.
  * CDS+ [22] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng.  Quantum resources required to block-encode a matrix of classical data, 2022.
  * CGH+ [17] Yu Cai, Saugata Ghose, Erich F. Haratsch, Yixin Luo, and Onur Mutlu.  Error characterization, mitigation, and recovery in flash-memory-based solid-state drives.  Proceedings of the IEEE, 105(9):1666–1704, 2017.
  * CGL+ [22] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  Journal of the ACM, 69(5):1–72, 2022.
  * CH [10] Aaron Carroll and Gernot Heiser.  An analysis of power consumption in a smartphone.  In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference, USENIXATC’10, page 21, USA, 2010. USENIX Association.
  * CHI+ [18] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig.  Quantum machine learning: a classical perspective.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, January 2018.
  * Cho [22] Charles Q. Choi.  The beating heart of the world’s first exascale supercomputer, 2022\.
  * CL [21] André Chailloux and Johanna Loyer.  Lattice sieving via quantum random walks.  In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, pages 63–91, Cham, 2021. Springer International Publishing.
  * CSCDJRH [21] Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques, and Francisco Rodríguez-Henríquez.  The SQALE of CSIDH: sublinear vélu quantum-resistant isogeny action with low exponents.  Journal of Cryptographic Engineering, August 2021.
  * CT [18] Tore Vincent Carstens and Dirk Oliver Theis.  Note on (active-)qram-style data access as a quantum circuit, 2018.
  * DLBZ [22] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer.  Llm. int8 (): 8-bit matrix multiplication for transformers at scale.  arXiv preprint arXiv:2208.07339, 2022.
  * EG [02] Laurent El Ghaoui.  Inversion error, condition number, and approximate inverses of uncertain matrices.  Linear algebra and its applications, 343:171–193, 2002.
  * FAHA [22] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh.  Gptq: Accurate post-training quantization for generative pre-trained transformers.  arXiv preprint arXiv:2210.17323, 2022.
  * Fey [85] Richard P. Feynman.  Quantum mechanical computers.  Optics News, 11(2):11–20, Feb 1985.
  * GE [21] Craig Gidney and Martin Ekerå.  How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.  Quantum, 5:433, April 2021.
  * GGKK [03] Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar.  Introduction to Parallel Computing.  Addison Wesley, 2003.
  * Gid [19] Craig Gidney.  Windowed quantum arithmetic.  arXiv:1905.07682, 2019.
  * Gid [22] Craig Gidney.  Quantum dictionaries without qram.  arXiv:2204.13835, 2022.
  * Gio [17] R. Gioiosa.  Resilience for extreme scale computing.  In Rugged Embedded Systems, pages 123–148. Elsevier, 2017.
  * [48] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Architectures for a quantum random access memory.  Phys. Rev. A, 78:052310, Nov 2008.
  * [49] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Quantum random access memory.  Phys. Rev. Lett., 100:160501, Apr 2008.
  * GLT [18] András Gilyén, Seth Lloyd, and Ewin Tang.  Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension.  arXiv preprint arXiv:1811.04909, 2018.
  * God [68] John T. Godfrey.  Binary digital computer, U.S. Patent 3390471A, Jul. 1968.
  * Goo [22] Google.  Cloud TPU documentation: System architecture, 2022.  https://cloud.google.com/tpu/docs/system-architecture-tpu-vm.
  * GSLW [19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019.
  * Han [21] Connor T. Hann.  Practicality of Quantum Random Access Memory.  PhD thesis, Yale Graduate School of Arts and Sciences Dissertations, 2021\.
  * Hei [21] Max Heiser.  Improved quantum hypercone locality sensitive filtering in lattice sieving.  Cryptology ePrint Archive, Paper 2021/1295, 2021.  https://eprint.iacr.org/2021/1295.
  * HHL [09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Phys. Rev. Lett., 103:150502, Oct 2009.
  * HJN+ [20] Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken.  Improved quantum circuits for elliptic curve discrete logarithms.  In Post-Quantum Cryptography, pages 425–444. Springer International Publishing, 2020.
  * HLGJ [21] Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang.  Resilience of quantum random access memory to generic noise.  PRX Quantum, 2(2), April 2021.
  * HSH+ [09] J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten.  Lest we remember: Cold-boot attacks on encryption keys.  Commun. ACM, 52(5):91–98, may 2009.
  * HXZ+ [12] Fang-Yu Hong, Yang Xiang, Zhi-Yan Zhu, Li-zhen Jiang, and Liang-neng Wu.  Robust quantum random access memory.  Phys. Rev. A, 86:010306, Jul 2012.
  * JPC+ [19] N. Jiang, Y.-F. Pu, W. Chang, C. Li, S. Zhang, and L.-M. Duan.  Experimental realization of 105-qubit random access quantum memory.  npj Quantum Information, 5(1), April 2019.
  * JS [19] Samuel Jaques and John M. Schanck.  Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE.  In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part I, volume 11692 of Lecture Notes in Computer Science, pages 32–61. Springer, 2019.
  * Kir [18] Elena Kirshanova.  Improved quantum information set decoding.  In Tanja Lange and Rainer Steinwandt, editors, Post-Quantum Cryptography, pages 507–527, Cham, 2018. Springer International Publishing.
  * KMM+ [19] Dhiraj Kalamkar, Dheevatsa Mudigere, Naveen Mellempudi, Dipankar Das, Kunal Banerjee, Sasikanth Avancha, Dharma Teja Vooturi, Nataraj Jammalamadaka, Jianyu Huang, Hector Yuen, et al.  A study of bfloat16 for deep learning training.  arXiv preprint arXiv:1905.12322, 2019.
  * KP [16] Iordanis Kerenidis and Anupam Prakash.  Quantum recommendation systems.  arXiv preprint arXiv:1603.08675, 2016.
  * KSV [02] A. Yu. Kitaev, A. Shen, and M. N. Vyalyi.  Classical and Quantum Computation.  American Mathematical Society, USA, 2002.
  * KT [17] Ghazal Kachigar and Jean-Pierre Tillich.  Quantum information set decoding algorithms, 2017.
  * Kup [13] G. Kuperberg.  Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem.  In TQC 2013, LIPIcs 22, pages 20–34, 2013.
  * KV [17] Ravindran Kannan and Santosh Vempala.  Randomized algorithms in numerical linear algebra.  Acta Numerica, 26:95–135, 2017.
  * Laa [17] Thijs Laarhoven.  Sieving for closest lattice vectors (with preprocessing).  In Roberto Avanzi and Howard Heys, editors, Selected Areas in Cryptography – SAC 2016, pages 523–542, Cham, 2017. Springer International Publishing.
  * LC [19] Guang Hao Low and Isaac L Chuang.  Hamiltonian simulation by qubitization.  Quantum, 3:163, 2019.
  * Lin [22] Lin Lin.  Lecture notes on quantum algorithms for scientific computation.  arXiv preprint arXiv:2201.08309, 2022.
  * LJGGK [16] C. Lecaplain, C. Javerzac-Galy, M. L. Gorodetsky, and T. J. Kippenberg.  Mid-infrared ultra-high-q resonators based on fluoride crystalline materials.  Nature Communications, 7(1), November 2016.
  * LKS [18] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer.  Trading t-gates for dirty qubits in state preparation and unitary synthesis, 2018.
  * LLL+ [23] Junyu Liu, Minzhao Liu, Jin-Peng Liu, Ziyu Ye, Yuri Alexeev, Jens Eisert, and Liang Jiang.  Towards provably efficient quantum algorithms for large-scale machine-learning models.  arXiv preprint arXiv:2303.03428, 2023.
  * LMvdP [15] Thijs Laarhoven, Michele Mosca, and Joop van de Pol.  Finding shortest lattice vectors faster using quantum search.  Designs, Codes and Cryptography, 77(2-3):375–400, April 2015.
  * MGM [20] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca.  Fault-tolerant resource estimation of quantum random-access memories.  IEEE Transactions on Quantum Engineering, 1:1–13, 2020.
  * MM [16] E. S. Moiseev and S. A. Moiseev.  Time-bin quantum RAM.  Journal of Modern Optics, 63(20):2081–2092, May 2016.
  * Moh [10] Vidyabhushan Mohan.  Modelling the physical characteristics of NAND flash memory.  PhD thesis, School of Engineering and Applied Science, University of Virginia, 2010.
  * Moo [22] Dustin Moody.  Status report on the third round of the NIST post-quantum cryptography standardization process.  Technical report, National Institute of Standards and Technology, 2022\.
  * MP [21] Michele Mosca and Marco Piani.  Quantum threat timeline report 2020.  Technical report, Global Risk Institute, 2021.
  * MRTC [21] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang.  Grand unification of quantum algorithms.  PRX Quantum, 2(4):040203, 2021.
  * NZB+ [22] Murphy Yuezhen Niu, Alexander Zlokapa, Michael Broughton, Sergio Boixo, Masoud Mohseni, Vadim Smelyanskyi, and Hartmut Neven.  Entangling quantum generative adversarial networks.  Phys. Rev. Lett., 128:220505, Jun 2022.
  * OKD+ [22] James O’Sullivan, Oscar W. Kennedy, Kamanasish Debnath, Joseph Alexander, Christoph W. Zollitsch, Mantas Šimėnas, Akel Hashim, Christopher N. Thomas, Stafford Withington, Irfan Siddiqi, Klaus Mølmer, and John J. L. Morton.  Random-access quantum memory using chirped pulse phase encoding.  Phys. Rev. X, 12:041014, Nov 2022.
  * PAA+ [21] Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar, Alexander Buts, Shouvanik Chakrabarti, Dylan Herman, Shaohan Hu, Andrew Jena, Pierre Minssen, Pradeep Niroula, et al.  Quantum machine learning for finance iccad special session paper.  In 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pages 1–9. IEEE, 2021.
  * PBK+ [22] Jung Jun Park, Kyunghyun Baek, M. S. Kim, Hyunchul Nha, Jaewan Kim, and Jeongho Bang.  $t$-depth-optimized quantum search with quantum data-access machine, 2022\.
  * PCG [23] Koustubh Phalak, Avimita Chatterjee, and Swaroop Ghosh.  Quantum random access memory for dummies, 2023.
  * Pei [20] Chris Peikert.  He gives c-sieves on the CSIDH.  In Advances in Cryptology – EUROCRYPT 2020, pages 463–492. Springer International Publishing, 2020.
  * PLG [22] Koustubh Phalak, Junde Li, and Swaroop Ghosh.  Approximate quantum random access memory architectures, 2022.
  * POB [20] Alexandru Paler, Oumarou Oumarou, and Robert Basmadjian.  Parallelizing the queries in a bucket-brigade quantum random access memory.  Phys. Rev. A, 102:032608, Sep 2020.
  * PPR [19] Daniel K. Park, Francesco Petruccione, and June-Koo Kevin Rhee.  Circuit-based quantum random access memory for classical data.  Scientific Reports, 9(1), March 2019.
  * PY [15] Fernando Pastawski and Beni Yoshida.  Fault-tolerant logical gates in quantum error-correcting codes.  Phys. Rev. A, 91:012305, Jan 2015.
  * RK [22] Arthur G Rattew and Bálint Koczor.  Preparing arbitrary continuous functions in quantum registers with logarithmic complexity.  arXiv preprint arXiv:2205.00519, 2022.
  * RML [14] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  Physical review letters, 113(13):130503, 2014.
  * RS [08] Oded Regev and Liron Schiff.  Impossibility of a quantum speed-up with a faulty oracle.  In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, pages 773–781, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * SB [18] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * Sch [21] John M. Schanck, Jun 2021.
  * SCS+ [22] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S. Sara Mahdavi, Rapha Gontijo Lopes, Tim Salimans, Jonathan Ho, David J Fleet, and Mohammad Norouzi.  Photorealistic text-to-image diffusion models with deep language understanding, 2022.
  * SPW [11] Bianca Schroeder, Eduardo Pinheiro, and Wolf-Dietrich Weber.  Dram errors in the wild: A large-scale field study.  Commun. ACM, 54(2):100–107, feb 2011.
  * Ste [16] Damien Steiger.  Racing in parallel: Quantum versus classical, 2016.
  * STY+ [23] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang.  Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 1–1, 2023.
  * TAC+ [10] W. Tittel, M. Afzelius, T. Chaneliére, R.L. Cone, S. Kröll, S.A. Moiseev, and M. Sellars.  Photon-echo quantum memory in solid state systems.  Laser & Photonics Reviews, 4(2):244–267, 2010.
  * Tan [07] Seiichiro Tani.  An improved claw finding algorithm using quantum walk.  In Mathematical Foundations of Computer Science 2007, pages 536–547. Springer Berlin Heidelberg, 2007.
  * Tan [19] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 217–228, 2019.
  * Tez [04] Tezzaron Semiconductor, January 2004.
  * VBE [96] Vlatko Vedral, Adriano Barenco, and Artur Ekert.  Quantum networks for elementary arithmetic operations.  Physical Review A, 54(1):147, 1996.
  * WBL+ [22] Zhiling Wang, Zenghui Bao, Yan Li, Yukai Wu, Weizhou Cai, Weiting Wang, Xiyue Han, Jiahui Wang, Yipu Song, Luyan Sun, Hongyi Zhang, and Luming Duan.  An ultra-high gain single-photon transistor in the microwave regime.  Nature Communications, 13(1), October 2022.
  * YMH+ [15] X. X. Yuan, J.-J. Ma, P.-Y. Hou, X.-Y. Chang, C. Zu, and L.-M. Duan.  Experimental demonstration of a quantum router.  Scientific Reports, 5(1), July 2015.
  * YZ [22] Pei Yuan and Shengyu Zhang.  Optimal qram and improved unitary synthesis by quantum circuits with any number of ancillary qubits, 2022.
  * ZDM+ [19] Darko Zivanovic, Pouya Esmaili Dokht, Sergi Moré, Javier Bartolome, Paul M. Carpenter, Petar Radojković, and Eduard Ayguadé.  Dram errors in the field: A statistical approach.  In Proceedings of the International Symposium on Memory Systems, MEMSYS ’19, page 69–84, New York, NY, USA, 2019. Association for Computing Machinery.
  * [111] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan.  Quantum state preparation with optimal circuit depth: Implementations and applications.  Phys. Rev. Lett., 129:230504, Nov 2022.
  * [112] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan.  Quantum state preparation with optimal circuit depth: Implementations and applications.  Physical Review Letters, 129(23):230504, 2022.

##  Appendix A Linear Algebra Proofs

######  Lemma A.1 (Optimality of Quantum Eigenvalue Transform).

Any quantum algorithm implementing a degree-$k$ polynomial of a matrix $H$
(with the polynomial defined on the eigenvalues) requires $\Omega(k)$ queries
to $O_{H}$, in general.

###### Proof.

We prove this lower-bound by a reduction to unstructured search, in the QSVT
framework (as per [53]), from which the bound immediately follows. We note
that the result of [53] almost immediately implies this bound, but we present
the following derivation in a format to enhance the clarity of our discussion.
First we formally define a block-encoding. As per [53], an $n+a$-qubit unitary
matrix $U_{A}$ is called an $(\alpha,a,\epsilon)$-block encoding of the
$n$-qubit matrix $A$ if $\left\lVert A-\alpha(\left\langle 0\right|^{\otimes
a}\otimes I_{n})U_{A}(\left|0\right\rangle^{\otimes a}\otimes
I_{n})\right\rVert_{2}\leq\epsilon$.

Given an unstructured search function $f(x)=0$ for all $x\neq m$, and $f(m)=1$
(with m being unique), specified by an $O_{f}$, oracle defined as
$O_{f}\left|x\right\rangle=(-1)^{f(x)\oplus 1}\left|x\right\rangle$ (where we
negate the sign for ease of analysis), we can construct a $(1,9,0)$-block-
encoding $U_{A}$ of $A:=\frac{1}{\sqrt{N}}|m\rangle\langle+^{n}|$, where
$\left|+^{n}\right\rangle=H^{\otimes n}\left|0\right\rangle$. We give a very
inefficient block encoding (in terms of the number of ancillas) for ease of
exposition. First, we construct a $(1,4,0)$-block-encoding of $H^{\otimes
n}|0\rangle\langle 0|H^{\otimes n}$. This can first be done by constructing a
$(1,2,0)$-block-encoding of $|0\rangle\langle
0|=\frac{1}{2}(I_{n}+(2|0\rangle\langle 0|-I_{n}))$ (which can be done by
applying the standard sum of block encoding lemma [53]) of an $n$ qubit
identity matrix with the standard $2|0\rangle\langle 0|-I_{n}$ unitary from
Grover search. We can then use the product of block encodings lemma with
$H^{\otimes n}$, $|0\rangle\langle 0|$, and $H^{\otimes n}$ again to get a
$(1,4,0)$-block encoding of $|+^{n}\rangle\langle+^{n}|$. We can then use the
product of block encoding with $I_{1}\otimes O_{f}$ and
$|+^{n}\rangle\langle+^{n}|$ to get a $(1,5,0)$-block encoding of
$O_{f}|+^{n}\rangle\langle+^{n}|$. We can then use the sum of block encodings
with $|+^{n}\rangle\langle+^{n}|$ and $O_{f}|+^{n}\rangle\langle+^{n}|$ to get
a $(1,9,0)$-block-encoding of
$\frac{1}{2}((O_{f}+I)|+^{n}\rangle\langle+^{n}|)=\frac{1}{\sqrt{N}}|m\rangle\langle+^{n}|$,
as desired.

We can apply the polynomial approximation of the sign function as per [53] to
our block encoding unitary $U_{A}$, giving a constant probability of success
of measuring the marked state. They give the degree of this (odd degree)
polynomial as $k=O(\log(1/\epsilon)/\delta)$, where $\epsilon$ is an upper-
bound on the maximum deviation of the polynomial approximation to the sign
function in the $x\in[-2,2]\backslash(-\delta,\delta)$. If we set
$\delta=\frac{1}{\sqrt{N}}$, then the sign function maps our non-zero singular
value to $1$, while leaving the zero-valued singular values unchanged. As a
result, we can measure the ancilla register in the $\left|0\right\rangle$
state with $\propto 1-\epsilon$ probability, learning the result of the
unstructured search problem. If it were possible to implement this degree
$\tilde{O}(1/\delta)$ degree-polynomial with fewer than $\Omega(1/\delta)$
queries to $U_{A}$, we could solve unstructured search in general with fewer
than $\Omega(\sqrt{N})$ queries to the unstructured search oracle, violating
well-known lower-bounds for unstructured search. As a consequence, any general
algorithm implementing a SVT of a degree-$k$ polynomial of some matrix $H$
must use at least $\Omega(k)$ queries to that matrix.

A polynomial implementing the sign function applied to the eigenvalues of a
block encoding of $\tilde{A}:=\begin{pmatrix}0&A\\\
A^{\dagger}&0\end{pmatrix}$ would also solve unstructured search in the same
way (noting that the non-zero eigenvalues of $\tilde{A}$ correspond to
$\pm\frac{1}{\sqrt{N}}$ and have associated eigenvectors
$\frac{1}{\sqrt{2}}(\left|0\right\rangle_{1}\left|m\right\rangle\pm\left|1\right\rangle_{1}\left|+^{n}\right\rangle)$.
Thus, applying $\text{Sign}(\tilde{A})$ leaves the $0$ eigenvalues unchanged,
and maps the $\pm\frac{1}{\sqrt{N}}$ eigenvalues to $\pm 1$ (within $\epsilon$
distance). Consequently,
$\text{Sign}(\tilde{A})\approx\begin{pmatrix}0&|m\rangle\langle+^{n}|\\\
|+^{n}\rangle\langle m|&0\end{pmatrix}$. Applying $\text{Sign}(\tilde{A})$ to
an initial state $\left|1\right\rangle\left|+^{n}\right\rangle$ then gives the
solution to the unstructured search problem, and so the same bound holds for
Problem 1. ∎

######  Lemma A.2.

Given $P$ classical processors sharing a common memory of access time $O(1)$,
a $d$-sparse matrix $A\in\mathbb{C}^{N\times N}$ and a vector
$\bm{v}\in\mathbb{C}^{N}$, we can compute $A\bm{v}$ with $\tilde{O}(Nd/P)$
time complexity.

###### Proof.

This is a standard result; see [44]. Assume we represent $A$ as $N$ lists of
elements $(j,A_{ij})$, where $A_{ij}$ are the non-zero components in row $i$,
and $\bm{v}$ as an $N$-element array. With fewer than $N$ processors, each
processor will iterate through a row of $A$. For an entry $(j,A_{ij})$, it
will look up the $j$th element of $\bm{v}$, multiply it by $A_{ij}$ and add
that to a running total. This produces one element of $A\bm{v}$. Each element
can be computed independently, so this parallelizes perfectly. With more than
$N$ processors, rows will have multiple processors. The processors for row $i$
can divide the entries of $A$ in that row and compute sub-totals. To compute
the full sum, they add their sub-totals together in a tree structure; this
tree has depth $O(\log(P/N))$. ∎

Following the techniques of [9], we use sorting to build matrix
multiplication.

######  Lemma A.3.

Given $P$ parallel processors forming a sorting network that can sort in time
$\mathsf{S}$, multiplying an $N$-dimensional vector $\bm{v}$ by a $d$-sparse
$N\times N$ matrix $A$ takes time $O(\mathsf{S}+Nd/P+\lg(d))$.

###### Proof.

First the processors create $d$ copies of $\bm{v}$. Each processor will store
a block of $A$ or $\bm{v}$ in local memory, so by treating $A$ as a block
matrix, we suppose each processor has one entry $A_{ij}$ of $A$ or
$\bm{v}_{j}$ of $\bm{v}$. We assume there is an efficiently-computable
function $f_{j}$ for each column $j$, which injectively maps indices $k$ from
$1$ to $d$ to the non-zero elements of that column. Each processor creates a
tuple $(k,j,0,A_{f_{j}(k)j})$ for components of $A$, and $(k,j,\bm{v}_{j})$
for components of $\bm{v}$ (each copy of $\bm{v}$ has a distinct value of
$k$). They will then sort this data by the second component, then the first.
Because each column of $A$ contains at most $d$ non-zero entries, this ensures
each processor with a tuple $(k,j,0,A_{f_{j}(k)j})$ is adjacent to a tuple
$(k,j,\bm{v}_{j})$, so these two processors can compute
$A_{f_{j}(k)j}\bm{v}_{j}$ and store the result in the tuple for $A$. The
processors can then discard the tuples for $\bm{v}$, and change the first
component from $k$ to $f_{j}(k)$. Then they re-sort so that the rows of $A$
are physically close (e.g., in a square of length $\sqrt{d}$ in 2 dimensions).
They then add the entries of $A_{ij}\bm{v}_{j}$ for each row. Cascading these
together will take at least $\lg(d)$ sequential additions, but it will be
asymptotically less than the sorts of the full matrix and vector. This
produces the $i^{th}$ element of $A\bm{v}$. Another sort can send these to
whatever memory location represents the output. ∎

######  Lemma A.4 (Dense Matrix-Vector Multiplication with Local Memory).

A set of $O(N^{2}\log(N))$ processors arranged in a $3D$ grid and with nearly
local connectivity, leading to a total wire-length of $\tilde{O}(N^{2})$, can
implement a matrix-vector multiplication with an $N\times N$ matrix $A$ and an
$N$-dimensional vector $\bm{v}$ with $O(\log(N))$ complexity.

###### Proof.

Consider a grid of $N\times N$ processors, each with local memory, and no
connections to their nearest neighbors. Assume that each element in $A$ is
assigned to a corresponding processor in the grid, i.e. the processor in the
$i^{th}$ row and $j^{th}$ column stores element $A_{ij}$. If our initial
vector $\bm{v}$ is stored in a set of $N$ data cells, using a stack of
$\log(N)$ local processors, of dimension $2\times N,4\times N,...,N\times N$
we can recursively spread the elements in the vector to construct an $N\times
N$ matrix $V$ such that $V_{ij}=\bm{v}_{j}$. The first layer in this stack has
2 wires per layer, each of length $N/2$, for a total wire-length of
$O(N^{2})$. The final layer in this stack, the one that connects element
$V_{ij}$ to element $A_{ij}$ in the main $N\times N$ grid, has $O(N^{2})$
wires, each of length $O(1)$ for a total wire length of $O(N^{2})$. The middle
layers in the stack similarly have a total wire length of $O(N^{2})$ (summing
progressively more shorter wires). Thus, the main $N\times N$ processor grid
can store $A_{ij}\bm{v}_{j}$ with a total of $O(N^{2}\log N)$ ancillary local
processors with a total wire length of $O(N^{2}\log N)$. We can then repeat
this process of spreading out the elements of $\bm{v}$ in reverse, adding
another stack of $\log N$ processors of size $N\times N,N\times
N/2,...,N\times 2,N\times 1$. We then add elements in adjacent cells, sending
them to the cell in the layer above, building up the sum of products of the
appropriate matrix and vector element. This produces the output vector
$A\bm{v}$, where the $i^{th}$ row stores $\sum_{j=1}^{N}A_{ij}\bm{v}_{j}$,
with a total wire-length of $O(N^{2}\log N)$, and with a total of $O(N^{2}\log
N)$ processors. ∎

##  Appendix B Proof of Lemma V.1

We start by defining the set of circuits $\mathcal{C}(W,D,G,g,k)$ to be all
circuits on $W$ qubits, of circuit depth $D$, using $G$ gates from a set of
size $g$ with fanin at most $k$. Here we assume all gates have depth 1 and we
count circuits based on the arrangement of gates, not by function. Define a
“circuit” as a function that takes as input a pair of (qubit,time step) and
returns as output the particular gate applied to that qubit at that time step.

If two circuits have a different effect on quantum states, they must use
different gates, and thus will be distinct circuits by this definition. This
definition overcounts circuits, since equivalent circuits are counted twice,
but we want to upper bound the number of circuits so this is fine.

######  Proposition B.1.

Under this notation,
$|\mathcal{C}(W,D,G,g,k)|\leq|\mathcal{C}(W,D,\min\\{kG,DW\\},Wg,1)|$.

###### Proof.

Let $U$ be an $\ell$-qubit gate in the gate set of $\mathcal{C}(W,D,g,k)$. We
can define $\ell$ distinct single-qubit gates $U_{1},\dots,U_{\ell}$ from $U$,
expanding the total number of gates from $g$ to $gk$, and and then further
define $W/\ell$ multiples of each of these single qubit gates, i.e.,
$U_{1}^{(1)},\dots,U_{\ell}^{(1)},\dots,U_{1}^{(m)},\dots,U_{\ell}^{(m)}$
where $m=\left\lfloor W/\ell\right\rfloor$. This gives at most $W$ single-
qubit gates from $U$, so the total number of single-qubit gates defined in
this way is at most $Wg$.

We now define an injective function from $\mathcal{C}(W,D,G,g,k)$ to
$\mathcal{C}(W,D,\min\\{kG,DW\\},Wg,1)$. For each circuit, at each timestep we
take all $\ell$-qubit gates $U^{(1)},\dots U^{(m)}$ (we know there are fewer
tham $m=\left\lfloor W/\ell\right\rfloor$ gates of fanin $\ell$ in one
timestep, because there aren’t enough qubits for more!) and decompose each
into $U_{1}^{(i)},\dots,U_{\ell}^{(i)}$, such that the qubit mapped to the
$j$th input of the $i$th gate is given gate $U_{j}^{(i)}$. This increases the
total number of gates by at most a factor of $k$, and cannot increase the
number of gates above $DW$.

For example, a CNOT would split into two gates, a “target” gate and a
“control” gate, and if these are reversed, the circuit is different (by our
counting).

To show injectivity, suppose two circuits $C_{1}$ and $C_{2}$ in
$\mathcal{C}(W,D,G,g,k)$ map to the same circuit in
$\mathcal{C}(W,D,kG,gW,1)$. Let $U$ be any gate in $C_{1}$; suppose it applies
to $\ell$ qubits $q_{1},\dots,q_{\ell}$ in time step $t$. This means there is
some $i$ such that the image circuit has $U_{1}^{(i)},\dots,U_{\ell}^{(i)}$
applied to $q_{1},\dots,q_{\ell}$ in time step $t$. By construction of our
function, this means there must be some gate in $C_{2}$ of the same type as
$G$ which is also applied to those same qubits, in the same order, in time
step $t$. Repeating for all gates shows that $C_{1}=C_{2}$. ∎

######  Proposition B.2.

In the same notation, $|\mathcal{C}(W,D,G,g,1)|\leq\binom{DW}{G}g^{G}$.

###### Proof.

We can straightforwardly count: There are $DW$ possible “slots” for each gate,
depending on which qubit and which time step. We choose $G$ slots, and for
each one, we select one of the $g$ gates. ∎

######  Lemma B.3.

$|\mathcal{C}(W,D,G,g,k)|\leq\binom{DW}{\min\\{kG,DW\\}}(Wg)^{G}$.

###### Proof.

We combine Proposition B.1 and Proposition B.2 to obtain the result. ∎

##  Appendix C Proof of Hamiltonian Complexity

Our model for a ballistic computation is a Hamiltonian on $W$ qubits, where we
choose $n$ $k$-local terms $H_{1},\dots,H_{n}$ out of a set of $N$ possible
terms, scaling each to an an energy $a_{i}$ between $-E$ and $E$, then
evolving for a time $t$. The Hamiltonian will be

$H=\sum_{i=1}^{n}a_{i}H_{i}.$ (15)

Since $e^{itH/\hbar}=e^{i(tE)(H/E)/\hbar}$, for convenience we scale the
energy to $1$ and scale up the time $t$. Note this also captures the case of
evolving the same Hamiltonian for less time, e.g., evolving for time $t_{0}<t$
is the same as scaling all energy coefficients by $\frac{t_{0}}{t}$ and
evolving to time $t$.

Before the main theorem, we need a lemma about matrix exponentials:

######  Lemma C.1.

Suppose $H_{1}$ and $H_{2}$ are two Hamiltonians of norm at most $1$ such that
$\|H_{1}-H_{2}\|_{2}\leq\epsilon$. If

$\|e^{itH_{1}/\hbar}-e^{itH_{2}/\hbar}\|_{2}\geq\delta$ (16)

then

$\epsilon\geq\frac{\hbar\ln(\delta
e^{-t/\hbar}+1)}{t}\geq\frac{\hbar}{t}\delta e^{-t/\hbar}(1-\delta
e^{-t/\hbar}).$ (17)

We will introduce an unusual but helpful notation: for any natural numbers
$n,j$ with $j\leq n$, and two matrices $A$ and $B$,

$\binom{n:A}{j:B}:=\sum_{\vec{x}\in\\{0,1\\}^{n}:\|\vec{x}\|_{1}=j}B^{x_{1}}A^{1-x_{1}}\cdots
B^{x_{n}}A^{1-x_{n}}$ (18)

In other words, we add up all arrangements of $A$ and $B$ that contain $j$
terms of $B$ and $n-j$ terms of $A$. This is useful because

$(A+B)^{n}=\sum_{j=0}^{n}\binom{n:A}{j:B}.$ (19)

###### Proof.

Suppose that $H_{1}-H_{2}=\epsilon H_{12}$, where $H_{12}$ has singular values
at most $1$. We can then argue that

$\displaystyle e^{itH_{1}/\hbar}=$ $\displaystyle e^{itH_{2}/\hbar+it\epsilon
H_{12}/\hbar}$ (20) $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\frac{i^{n}t^{n}}{\hbar^{n}n!}(H_{2}+\epsilon
H_{12})^{n}$ (21) $\displaystyle=$
$\displaystyle\underbrace{\sum_{n=0}^{\infty}\frac{i^{n}t^{n}}{\hbar^{n}n!}H_{2}^{n}}_{=e^{itH_{2}/\hbar}}+\sum_{n=0}^{\infty}\frac{i^{n}t^{n}}{\hbar^{n}n!}\sum_{j=1}^{n}\epsilon^{j}\binom{n:H_{2}}{j:H_{12}}$
(22)

Since $\|H_{1}\|\leq 1$ and $\|H_{2}\|\leq 1$, we can bound

$\left\|\binom{n:H_{1}}{j:H_{12}}\right\|\leq\sum_{\vec{a}\in\\{0,1\\}^{n},\|\vec{a}\|_{1}=j}1=\binom{n}{j}.$
(23)

so we can bound

$\displaystyle\delta\leq\|e^{itH_{1}/\hbar}-e^{itH_{2}/\hbar}\|\leq$
$\displaystyle\sum_{n=0}^{\infty}\frac{t^{n}}{\hbar^{n}n!}\sum_{j=1}^{n}\epsilon^{j}\binom{n}{j}$
(24) $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\frac{t^{n}}{\hbar^{n}n!}\left((1+\epsilon)^{n}-1\right)$
(25) $\displaystyle=$ $\displaystyle e^{t/\hbar}(e^{t\epsilon/\hbar}-1).$ (26)

Rearranging gives the result. ∎

######  Theorem C.2.

Let $\mathcal{G}$ be a set of mutually orthogonal circuits (i.e., for any
$U_{1},U_{2}\in\mathcal{G}$, there is some input state such that
$\left\langle\psi\right|U_{2}^{\dagger}U_{1}\left|\psi\right\rangle=0$). Let
$\mathcal{H}$ be a set of Hamiltonians constructed in the manner specified
above, such that for all $U\in\mathcal{G}$, there is $H\in\mathcal{H}$ such
that $U=e^{itH/\hbar}$. Then

$\log(|\mathcal{G}|)\in O(ntE+n\log W).$ (28)

###### Proof.

Let $\vec{a}=(a_{1},\dots,a_{n})$ be the vector of the coefficients of each
term. First we note that the singular values of $a_{1}H_{1}+\dots+a_{n}H_{n}$
are bounded by $\epsilon$ if $\|\vec{a}\|_{1}<\epsilon$. If we choose the same
$n$ Hamiltonians and two coefficient vectors $\vec{a}_{A}$ and $\vec{a}_{B}$
such that $\|\vec{a}_{A}-\vec{a}_{B}\|_{1}\leq\epsilon$, then the induced
Hamiltonians $H_{A}$ and $H_{B}$ satisfy $\|H_{A}-H_{B}\|\leq\epsilon$.

We then consider how many possible Hamiltonians we might be able to produce
that are all mutually at distance at least $2\epsilon$. Our goal here is an
upper bound. Optimistically, assume that if we choose two different sets of
Hamiltonian terms $\\{H_{1},\dots,H_{n}\\}$, we automatically achieve the
required distance. Then each choice (there are $\binom{N}{n}$ choices)
partitions the space $[-1,1]^{n}\subseteq\mathbb{R}^{n}$ into $\ell_{1}$-balls
of radius $\epsilon$. The volume of the space is $2^{n}$ and the volume of
each ball is $\frac{2^{n}}{n!}\epsilon^{n}$, so this gives us at most

$\binom{N}{n}\frac{n!}{\epsilon^{n}}$ (29)

such matrices.

If we want to capture all the gates in the set $\mathcal{G}$ with a
Hamiltonian, we thus need

$\binom{N}{n}\frac{n!}{\epsilon^{n}}\geq|\mathcal{G}|$ (30)

for some $\epsilon$. Rearranging gives

$\epsilon\leq\left(\binom{N}{n}\frac{n!}{|\mathcal{G}|}\right)^{1/n}$ (31)

However, if $\epsilon$ is small enough that
$e^{t\hbar}(e^{t\hbar\epsilon}-1)\leq 1$, then by Lemma C.1 the unitaries
induced by the Hamiltonians are too close to represent the mutually orthogonal
gates in $\mathcal{G}$, which are at distance $1$. To put this another way, we
need

$\displaystyle\epsilon>$
$\displaystyle\frac{\hbar\ln(e^{-t/\hbar}+1)}{t}\geq\frac{\hbar
e^{-t/\hbar}}{2t}.$ (32)

Combining these inequalities gives

$\frac{e^{-t/\hbar}}{2t\hbar}\leq\left(\binom{N}{n}\frac{n!}{|\mathcal{G}|}\right)^{1/n}$
(33)

With some work, Stirling’s inequality gives

$\displaystyle\frac{N!}{(N-n)!}\leq$ $\displaystyle N^{n}e^{n}$ (34)

Combining that with Equation 31 gives

$\frac{\hbar e^{-t/\hbar}}{2t}<Ne|\mathcal{G}|^{-1/n}$ (35)

or

$\ln|\mathcal{G}|<n\ln N+\frac{nt}{\hbar}+n\ln(2te)-n\ln(\hbar)$ (36)

Here we bound $N$ in terms of the width $W$. If there are more than $4^{k}$
possible $k$-local Hamiltonian terms on the same $k$ qubits, then the final
Hamiltonian term can be written as a linear combination of at most $4^{k}$
terms, so we can assume the “extra” terms are not used. Adding up over all
arities,

$N\leq
4\mathsf{W}+4^{2}\binom{\mathsf{W}}{2}+\dots+4^{k}\binom{\mathsf{W}}{k}\in
O(\mathsf{W}^{k}).$ (37)

Thus, $n\ln N=O(nk\log W)$, so the full bound is $O(nt+n\log W)$. ∎

Our QRACM result follows:

######  Corollary C.3.

Using a family of Hamiltonians with $n$ terms of energy $E$ for time $t$ to
create a QRACM access to tables of size $N$ must satisfy

$ntE+n\log W\in\Omega(N).$ (38)

###### Proof.

We use the set of possible QRACM access gates as $\mathcal{G}$. There are
$2^{N}$ possible QRACM access gates, and they are mutually orthogonal, so the
result follows immediately. ∎

##  Appendix D Proof of No Distillation

There are two components of the proof: First, we argue that with only $d$
inputs in the QRACM, we can always find some indices which are
“underrepresented”, i.e., very little of the amplitude of the input state is
concentrated on those indices. This is more general than necessary: we only
need $\ell=1$ to prove our main theorem.

######  Lemma D.1.

Let $\rho_{1},\dots,\rho_{d}$ be any collection of states, each in
$B(\mathcal{H}_{i}\otimes\mathcal{H}_{QRACM})$, i.e., part of the state is in
the input space for a QRACM gate. Then there exists some set of $\ell$ indices
such that for any two tables $T$ and $T^{\prime}$ differing only in those
$\ell$ indices, if we define

$\delta_{i}:=\left\|\mathcal{U}_{QRACM}(T)(\rho_{i})-\mathcal{U}_{QRACM}(T^{\prime})(\rho_{i})\right\|_{1}$
(39)

(with an implicit identity channel on $\mathcal{H}_{i}$) then

$\sum_{i=1}^{d}\delta_{i}\leq\frac{2\ell\sqrt{d}}{N}.$ (40)

###### Proof.

Because we care about the application of a perfect QRACM gate, we will purify
each of these states, so we consider some purification of $\rho_{i}$:

$\left|\psi_{i}\right\rangle=\sum_{j=0}^{n}\sum_{b\in\\{0,1\\}}\alpha_{jb}\left|\psi_{ijb}\right\rangle\left|j\right\rangle\left|b\right\rangle$
(41)

where we have expressed the input space to the QRACM gate in the computational
basis. Here $\left|\psi_{ijb}\right\rangle$ is in
$\mathcal{H}_{i}\otimes\mathcal{H}_{p}$, where $\mathcal{H}_{p}$ is the space
necessary to purify $\rho_{i}$. We see that
$U_{QRACM}(T)=\sum_{j,b}\left|\left.j\right\rangle\kern-1.99997pt\left\langle
j\right.\right|\otimes\left|\left.b\oplus
T[j]\right\rangle\kern-1.99997pt\left\langle b\right.\right|$, so that

$\displaystyle U_{QRACM}$ $\displaystyle(T^{\prime})^{\dagger}U_{QRACM}(T)$
$\displaystyle=\sum_{j:T^{\prime}[j]=T[j]}\left|\left.j\right\rangle\kern-1.99997pt\left\langle
j\right.\right|\otimes I_{2}+\sum_{j:T^{\prime}[j]\neq
T[j]}\left|\left.j\right\rangle\kern-1.99997pt\left\langle
j\right.\right|\otimes X$ (42)

where $X$ is the Pauli $X$. This implies that

$\displaystyle\left\langle\psi_{i}\right|$ $\displaystyle
U_{QRACM}(T^{\prime})^{\dagger}U_{QRACM}(T)\left|\psi_{i}\right\rangle$ (43)
$\displaystyle=$
$\displaystyle\sum_{j:T[j]=T^{\prime}[j],b\in\\{0,1\\}}|\alpha_{ijb}|^{2}+$
(44) $\displaystyle\sum_{j:T[j]\neq
T^{\prime}[j]}\overline{\alpha_{ij0}}\alpha_{ij1}\left\langle\left.\psi_{ij0}\right|\psi_{ij1}\right\rangle+\overline{\alpha_{ij1}}\alpha_{ij0}\left\langle\left.\psi_{ij1}\right|\psi_{ij0}\right\rangle$
(45) $\displaystyle\geq$ $\displaystyle 1-\left(\sum_{j:T[j]\neq
T^{\prime}[j]}|\alpha_{j0}|^{2}+|\alpha_{j1}|^{2}+\overline{\alpha_{ij0}}\alpha_{ij1}+\overline{\alpha_{ij1}}\alpha_{ij0}\right)$
(46) $\displaystyle\geq$ $\displaystyle 1-2\sum_{j:T[j]\neq
T^{\prime}[j]}|\alpha_{ij0}|^{2}+|\alpha_{ij1}|^{2}$ (47)

Since $U_{QRACM}(T^{\prime})$ commutes with tracing out the purifying space,
and partial trace can only decrease trace distance, we have that the trace
distance between the states after applying QRACM to the two different tables
is at most

$\delta_{i}:=\sqrt{2\sum_{j:T[j]\neq
T^{\prime}[j]}|\alpha_{ij0}|^{2}+|\alpha_{ij1}|^{2}}$ (48)

We then let

$m_{j}:=\sum_{i=1}^{d}|\alpha_{ij0}|^{2}+|\alpha_{ij1}|^{2}$ (49)

We know that $\sum_{j=0}^{N}m_{j}=1$. Thus, for any $\ell$, there exist a set
$\mathcal{J}$ of $d$ indices such that

$\sum_{j\in\mathcal{J}}m_{j}\leq\frac{\ell}{N}.$ (50)

If we set $T$ and $T^{\prime}$ to differ only on $\mathcal{J}$, we see that
$\sum_{i=1}^{d}\delta_{i}^{2}\leq\frac{2\ell}{N}$, from which we see that

$\sum_{i=1}^{d}\delta_{i}\leq\frac{2\ell\sqrt{d}}{N}.$ (51)

∎

We now argue by saying that since so little of the input state is concentrated
on certain indices, we can replace any table $T$ with a different table that
differs on those indices, and this will be indistinguishable to the QRACM
distillation-and-teleportation process. Since the process needs to handle all
logical inputs, it must fail on that index.

######  Theorem D.2.

Suppose there is a QRACM state distillation-and-teleportation process,
accessing tables of size $N=2^{n}$ and making at most $d$ calls to the
physical QRACM. Then the minimal fidelity for this process is at most

$\frac{3}{4}+2\frac{\sqrt{d}}{N}.$ (52)

###### Proof.

Let $T$ be any table, and label the states input into the QRAM device during
the distillation process as $\rho_{1}(T),\dots,\rho_{d}(T)$. Let $\mathcal{J}$
be the set of $\ell$ indices implied by Lemma D.1 for these states, and let
$T^{\prime}$ be a table that differs from $T$ in those $\ell$ indices. We will
show by induction that

$\|\rho_{i}(T^{\prime})-\rho_{i}(T)|_{1}\leq\sum_{j=1}^{i}\delta_{j}$ (53)

with $\delta_{i}$ as in Lemma D.1. This holds for $i=0$ since both take
$\left|\left.0\right\rangle\kern-1.99997pt\left\langle 0\right.\right|$ as the
starting state.

For induction, recall from the definition of the distillation process that

$\rho_{i+1}(T)=\Phi_{i+1}\circ(I\otimes\mathcal{Q}(T))\rho_{i}(T)$ (54)

(similarly for $T^{\prime}$). Since the channel $\Phi_{i+1}$ can only reduce
the trace distance between then by the data processing inequality, we obtain:

$\displaystyle\|\rho_{i+1}(T^{\prime})-$ $\displaystyle\rho_{i+1}(T)\|_{1}$
(55) $\displaystyle\leq$
$\displaystyle\|(I\otimes\mathcal{Q}(T^{\prime}))\rho_{i}(T^{\prime})-(I\otimes\mathcal{Q})(T)\rho_{i}(T)\|_{1}$
(56) $\displaystyle\leq$
$\displaystyle\|((I\otimes\mathcal{Q}(T)-(I\otimes\mathcal{Q}(T^{\prime}))\rho_{i}(T)\|_{1}$
(57)
$\displaystyle+\|(I\otimes\mathcal{Q}(T^{\prime}))(\rho_{i}(T^{\prime})-\rho_{i}(T))\|_{1}$
(58) $\displaystyle\leq$ $\displaystyle\delta_{i+1}+\sum_{j=1}^{i}\delta_{j}$
(59)

using Lemma D.1.

We finally note that $\rho_{d}(T)=\rho_{distill}(T)$, the state input into the
final teleportation process. This means the distance between
$\rho_{distill}(T)$ and $\rho_{distill}(T^{\prime})$ is at most
$\frac{2\ell\sqrt{d}}{N}$ by Lemma D.1. Again by the data processing
inequality, the final teleportation process cannot increase the distance.
Denoting the full process as $\tilde{\mathcal{U}}_{QRACM}(T)$, we see that for
any logical input $\rho_{L}$, we obtain

$\|(\tilde{\mathcal{U}}_{QRACM}(T)-\tilde{\mathcal{U}}_{QRACM}(T^{\prime}))\rho_{L}\|_{1}\leq\frac{2\ell\sqrt{d}}{N}$
(60)

However, let $\rho_{L}=\left|\left.j\right\rangle\kern-1.99997pt\left\langle
j\right.\right|\otimes\left|\left.0\right\rangle\kern-1.99997pt\left\langle
0\right.\right|$ for some $j$ with $T[j]\neq T^{\prime}[j]$. Then we have for
the _ideal_ QRACM access,

$\|(\mathcal{U}_{QRACM}(T)-\mathcal{U}_{QRACM}(T^{\prime}))(\rho_{L})\|_{1}=1$
(61)

But by the triangle inequality,

$\displaystyle 1=$
$\displaystyle\|(\mathcal{U}_{QRACM}(T)-\mathcal{U}_{QRACM}(T^{\prime}))(\rho_{L})\|_{1}$
(62) $\displaystyle\leq$
$\displaystyle\|(\mathcal{U}_{QRACM}(T)-\tilde{\mathcal{U}}_{QRACM}(T))\rho_{L}\|_{1}$
(63)
$\displaystyle+\|(\mathcal{U}_{QRACM}(T^{\prime})-\tilde{\mathcal{U}}_{QRACM}(T^{\prime}))\rho_{L}\|_{1}$
(64)
$\displaystyle+\|(\tilde{\mathcal{U}}_{QRACM}(T)-\tilde{\mathcal{U}}_{QRACM}(T^{\prime}))\rho_{L}\|_{1}$
(65) $\displaystyle 1-\frac{2\ell\sqrt{d}}{N}\leq$
$\displaystyle\|(\mathcal{U}_{QRACM}(T)-\tilde{\mathcal{U}}_{QRACM}(T))\rho_{L}\|_{1}$
(66)
$\displaystyle+\|(\mathcal{U}_{QRACM}(T^{\prime})-\tilde{\mathcal{U}}_{QRACM}(T^{\prime}))\rho_{L}\|_{1}$
(67)

meaning (WLOG) that the distance between the realized QRACM channel and the
ideal QRACM channel, for state $\rho_{L}$ on access to table $T$, is at least
$\frac{1}{2}-\frac{\ell\sqrt{d}}{N}$. Using known relations between trace
distance and fidelity and setting $\ell=1$ gives the result. ∎