groups

# Unified architecture for a quantum lookup table

Shuchen Zhu  Microsoft Quantum, Redmond, Washington, 98052, USA  Department of
Computer Science, Georgetown University, Washington, DC 20057, USA  Aarthi
Sundaram  Microsoft Quantum, Redmond, Washington, 98052, USA  Guang Hao Low
Microsoft Quantum, Redmond, Washington, 98052, USA

###### Abstract

Quantum access to arbitrary classical data encoded in unitary black-box
oracles underlies interesting data-intensive quantum algorithms, such as
machine learning or electronic structure simulation. The feasibility of these
applications depends crucially on gate-efficient implementations of these
oracles, which are commonly some reversible versions of the boolean circuit
for a classical lookup table. We present a general parameterized architecture
for quantum circuits implementing a lookup table that encompasses all prior
work in realizing a continuum of optimal tradeoffs between qubits, non-
Clifford gates, and error resilience, up to logarithmic factors. Our
architecture assumes only local 2D connectivity, yet recovers results that
previously required all-to-all connectivity, particularly, with the
appropriate parameters, poly-logarithmic error scaling. We also identify novel
regimes, such as simultaneous sublinear scaling in all parameters. These
results enable tailoring implementations of the commonly used lookup table
primitive to any given quantum device with constrained resources.

##  I Introduction

Quantum computers promise dramatic speedups over classical computers for a
broad range of problems. Provable advantage in many cases such as in
Hamiltonian simulation [1, 2, 3, 4, 5, 6], quantum machine learning [7, 8, 9,
10, 11, 12], and quantum search are in the so-called query model. The quantum
gate costs of these quantum algorithms are typically dominated by queries made
to a particular unitary oracle, with each oracle query having a gate cost that
scales polynomially with the amount of classical data needed to encode the
problem instance. As quantum computers will execute orders-of-magnitude fewer
logical operations per second than classical computers [13, 14], the crossover
of runtime between classical and quantum advantage is highly sensitive to the
constant factors in synthesizing these oracles. Understanding the cost of
oracle synthesis, such as in simulating chemistry, for a given algorithm can
mean a crossover of days rather than years [15].

The dominant gate cost of quantum oracles in many cases reduces to some
instance of a quantum lookup table [16] – a generic framework that facilitates
access to unstructured classical data in superposition. In analogy to the
classical lookup table that returns data $x_{i}$ for specified address bits
$i\in[N]$, the quantum lookup table is some unitary quantum circuit
$O_{\vec{x}}$ that responds with a superposition of data

$\displaystyle
O_{\vec{x}}\sum_{i\in[N]}\alpha_{i}\ket{i}\ket{0}=\sum_{i\in[N]}\alpha_{i}\ket{i,x_{i}},$
(1)

when queried by an arbitrary superposition of address bits
$\sum_{i}\alpha_{i}\ket{i}\ket{0}$. In general, quantum circuits implementing
$O_{\vec{x}}$ can be efficiently found for any data $\vec{x}$.

It is understood that a decisive quantum advantage for interesting problems
will be achieved with logical qubits in the fault-tolerant regime. Hence, the
cost of quantum table-lookup should be understood in the context of fault-
tolerant quantum resources. Specifically, logical Clifford gates {H, S, CNot}
are cheap, such as due to a native implementation on underlying physical
qubits [17]. In contrast, logical non-Clifford gates
{$\textsc{T},\textsc{Toffoli}$} are remarkably expensive [18], following the
Eastin-Knill theorem for the nonexistence of a set of transversal gates
universal for quantum computing, and require sophisticated protocols to
realize, like magic-state distillation and code-switching.

There are myriad possible implementations of quantum table-lookup Eq. 1, which
realize distinct resource trade-offs. Early seminal work called QRAM [19]
found implementations [20] using $\Theta(N)$ T gates and qubits in
$\Theta(\mathrm{polylog}{N})$ depth. However, realizing this shallow depth (or
runtime) is impractical due to the bottleneck of T gate production.
Synthesizing a single T gate in each unit of depth has an overhead of 100s
qubits [18]. Moreover, interesting problems such as in chemistry have on the
order of $N\sim 10^{6}$ [21] terms. Overall, the extreme space requirements
make the full potential of QRAM implementations difficult to realize. This has
motivated spacetime tradeoffs on the other extreme end — QROM [4] uses
$\Theta(N)$ T gates, but now with the minimum of $\Theta(\log N)$ qubits in
$\Theta(N)$ depth. It is straightforward to interpolate between these extremes
[22], but a most surprising discovery is that interpolating a novel SELECT-
SWAP [23] architecture reduces the expensive T gate count to an optimal
$\Theta(\sqrt{N})$ with only a moderate number of $\Theta(\sqrt{N})$ qubits.
Even more recently, the bucket-brigade QRAM implementation was discovered to
be error-resilient with polylogarithmic error scaling [24] in an all-to-all
quantum gate model, compared to all other approaches with linear error
scaling. Error resilience indirectly reduces the cost of logical resources, as
lower errors allow cheaper, lower-distance error-correcting codes with faster
logical cycle times.

Architecture | Infidelity | Query-depth | Qubits | T-gates | Layout
---|---|---|---|---|---
QRAM [19, 24] | $O(\log^{2}N)$ | $O(\log N)$ | $O(N)$ | $O(N)$ | all-to-all
QROM [4] | $O(bN)$ | $O(N)$ | $O(\log{N}+b)$ | $O(N)$ | all-to-all
SELECT-SWAP [23] | $O(bN)$ | $O(\frac{N}{\lambda}+\log\lambda)$ | $O(\log{N}+b\lambda)$ | $O(\frac{N}{\lambda}+b\lambda)$ | all-to-all
general single-bit (Sec. III) | $\tilde{O}(\frac{\gamma N}{\lambda})$ | $O(\frac{N}{\lambda}\log{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}N})$ | $O(\log{\frac{N}{\lambda}}+\lambda)$ | $O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+\lambda)$ | local, planar
general multi-bit parallel (Sec. V) | $\tilde{O}(\frac{b\gamma N}{\lambda})$ | $O(\frac{N}{\lambda}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\log bN})$ | $O(\log{\frac{N}{\lambda}}+b\lambda)$ | $O(\frac{N}{\lambda}\log\frac{N}{\lambda}+\frac{bN}{\gamma}+b\lambda)$ | local, planar
general multi-bit sequential (Sec. V) | $\tilde{O}(\frac{b\gamma N}{\lambda}+b^{2})$ | $O(\frac{N}{\lambda}\log(bN)+b)$ | $O(\log{\frac{N}{\lambda}}+b\lambda)$ | $O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+b\lambda)$ | local, planar
single-bit (Sec. III) | $\tilde{O}(N^{3/4})$ | $O(\sqrt{N}\log N)$ | $O(\sqrt{N})$ | $O(N^{3/4})$ | local, planar
parallel multi-bit  (Sec. V) | $\tilde{O}(bN^{3/4})$ | $O(\sqrt{N}\log N)$ | $O(b\sqrt{N})$ | $O(bN^{3/4})$ | local, planar
sequential multi-bit  (Sec. V) | $\tilde{O}(bN^{3/4}+b^{2})$ | $O(\sqrt{N}\log(bN)+b)$ | $O(b\sqrt{N})$ | $O(N^{3/4}+b\sqrt{N})$ | local, planar
Table 1: Asymptotic scaling for qubit and T gate cost, query depth, and
single-query infidelity in terms of memory size $N$ and word size $b$. Trade-
offs are realized by setting tuning parameters $\lambda\in[1,N]$ and
$\gamma\in[1,\lambda]$ with both assuming values that are a power of 2. The
types of models studied in this work are in bold. The last four rows show
asymptotic results for the particular choice of $\lambda=\sqrt{N}$, and
$\gamma=N^{1/4}$.

Our key contribution is an architecture for table-lookup summarized in Table 1
that encompasses all previous methods and enables a new continuum of tradeoffs
in the three key parameters of qubits, T gates, and error. Crucially, our
architecture only requires a planar layout of nearest-neighbor quantum gates.
There are concerns that local connectivity in QRAM variants [25, 26] limit
their capabilities in end-to-end implementations [27, 28]. We similarly find
in Table 2, that the naive implementation of long-range gates in our
architecture severely limits error resilience. However, we introduce a more
sophisticated implementation based on entanglement distillation that
establishes the feasibility of long-range connectivity within a planar layout.
This allows us to recover, up to logarithmic factors, in Table 3 the scaling
found in prior work assuming all-to-all connectivity. In other words, our
refined method for long-range connectivity in our table-lookup architecture is
equivalent to allowing unrestricted access to long-range gates, at some small
(logarithmic) overhead.

Novel tradeoffs are enabled by our general architecture. These include, for
instance, simultaneous sublinear scaling of all parameters with $N$, in both
the case where $x_{i}$ is a single bit, and the more general setting of a
$b$-bit word.

######  Theorem I.1 (Informal version of Theorem III.1 and Corollary III.2 ).

There exists a single-word quantum lookup table that has sublinear scaling in
infidelity, T-gate count, and qubit count, with local connectivity.

######  Theorem I.2 (Informal version of Theorem V.1 and Theorem V.2).

For constant word size $b$, there exist multi-word quantum lookup tables that
have sublinear scaling in infidelity, T-gate count, and qubit count, with
local connectivity.

We also provide a fine-grained error analysis of our table-lookup
implementation. We parameterize overall circuit error in terms of each common
gate type present, e.g. Idling error, non-Clifford gate errors, etc.
summarized in Table 4. In contrast, prior art universally assumes a generic
$\epsilon$ error parameter for all gates, which we do, in Table 1 to ease
presentation, but elaborate on with details later. Our approach proves useful
for understanding dominant error sources, which future experimental
implementations can then focus on minimizing.

Our table-lookup architecture is assembled from common circuit primitives
reviewed in Section II, and the general framework is introduced in Section
III. We then elucidate in Section IV the importance of long-range connectivity
in table-lookup on a planar layout, and demonstrate that entanglement
distillation provides a scalable means for overcoming the geometric error
scaling of naive long-range implementations. These tools also enable our
general table-lookup architecture to be extended to multi-bit words in Section
V. Finally, we conclude and discuss future work in Section VI.

Table 2: The exponent of infidelity scaling is examined for $N=2^{n}$ with
zero long-range budget, while varying $d$ and $d^{\prime}$ subject to the
constraint $d+d^{\prime}\leq n$, where $\lambda=2^{n-d}$ and
$\gamma=2^{n-d-d^{\prime}}$. The color gradient corresponds to different
T-count scalings. The $O(\sqrt{N})$ infidelity region corresponds to the
regime associated with the basic planar case in Fig. 11.

Table 3: The exponent of infidelity scaling is examined for $N=2^{n}$ with an
effectively infinite long-range budget. The linear infidelity region links to
the all-to-all connectivity QRAM case explored in Ref. [4], while the zero
exponent region pertains to the look-up table as detailed in Ref. [23].

##  II Preliminaries

All the circuit designs in this work are assumed to access data addressed by
$n$ bits with a memory of size $N=2^{n}$. We demonstrate how to read a single
bit of data before discussing extensions for large word sizes. Here, we
consider four key characteristics of the quantum lookup table and describe how
they directly impact its efficiency: circuit depth, qubit count, T-gate count,
and infidelity.

The minimum time taken to query a memory location is proportional to circuit
depth. It is commonly claimed that quantum algorithms have an exponential
speedup over classical algorithms when circuit depth scales
polylogarithmically in memory size. However, this minimum time is only
achieved under exceptional circumstances requiring extremely large space. In
most cases, the overall spacetime volume is the correct metric for evaluating
cost, and not depth alone. Thus, we also consider qubit count as a key
characteristic.

The qubits in a lookup table design are either used to maintain memory and
router status or to act as control or ancilla bits The current generation of
quantum devices is relatively small, often having a few dozen to a few hundred
qubits [29, 30]. Considering such constraints in near-to-intermediate term
devices, a quantum lookup table design with sublinear qubit scaling becomes
highly desirable.

T-gates, essential for implementing routers in the presence of superposition
queries, are non-Clifford gates that remain difficult to physically implement
without substantial resources in most qubit modalities [31, 32]. Hence, in
practical circuit design, the T-gate count needs to be minimized and roughly
approximate the overall spacetime volume of the circuit.

The infidelity is the probability of failing a single query and it scales as a
function of memory size multiplied by a generic gate error $\varepsilon$. Thus
for a constant target query error, lower infidelity provides more gate error
tolerance and flexibility for accommodating larger memories.

In classical memory, a combination of logical gates sends the bus signal to
the specific memory location determined by the input address bit and relays
the data stored in that memory location to the output register. Similarly,
quantum routers (Fig. 1) help to navigate the qubit to a memory location
determined by the address, after which the corresponding classical data is
loaded onto the bus qubit, and subsequently, the bus qubit is navigated to the
output register. The circuit design of the quantum router plays a pivotal role
in determining the properties of a quantum lookup table. We review some of
these router designs and prior architectures each of which assumes all-to-all
connectivity.

$\ket{a}$RouterIncident qubit$\ket{b}$Left outputRight output Figure 1: A
high-level description of a quantum router, the router status is set to
$\ket{a}$. Incident qubit $\ket{b}$ will be routed to the left (right) when
the router state is set to $\ket{0}$ ($\ket{1}$).

###  II.1 Fan-out architecture

The fan-out architecture [33], an initial proposal for the QRAM, can be
visualized as a binary tree of depth $\log N$, where the $N$ memory locations
are situated at the tree’s leaves (Fig. 2). Every non-leaf node in this tree
functions as a router, which guides the bus signal to its left or right child.
The status of the routers on the $\ell$-th level is determined by the
$\ell$-th address bit, which is maximally entangled with the router qubits.
Once the memory contents $x_{j}$ are written into the bus, such as using a
classically-controlled X gate, the bus qubit is routed back out via the same
path, and all router qubits are restored to their original disentangled state.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{1}$$\ket{1}$$\ket{0}$$\ket{0}$$\ket{1}$$\ket{0}$

Figure 2: High-level routing scheme for the fan-out architecture. The address
bits $\ket{010}$ are entangled with their corresponding routers at each level.
In the end the stored classical data at memory location $x_{2}$ is queried.

A significant drawback of this architecture is its high linear infidelity. If
a single router gets corrupted, it will flip the status of all other routers
on that same level, thereby misdirecting the query to an incorrect memory
path. Consequently, for error resilience, it is suboptimal to have all the
routers simultaneously entangled with the address bits.

###  II.2 Bucket-brigade architecture

The bucket-brigade architecture [16] is an improved QRAM proposal over the
fan-out architecture with three phases for querying memory: setting router
status, qubit route-in, and qubit route-out. It uses CSWAP (Fig. 3) routers to
direct signals.

$\mathbf{R}_{j}$ (a)

$t_{j}$$in_{j}$$R_{j}$$L_{j}$$in_{j}$$L_{j}$$t_{j}$$in_{j}$$R_{j}$$t_{j}$ (b)

Figure 3: (a) A single CSWAP router that takes input qubit and sends it to one
of its child nodes based on its state. (b) It takes four qubits to maintain a
CSWAP router. The $in_{j}$ register takes in input and directs the input qubit
to either the left or right register depending on the state of $t_{j}$.

The circuit description for a CSWAP router $\mathbf{R}_{j}$ is illustrated in
Fig. 3(b) following [24]. The router is composed of four qubits ($t_{0}$,
$in_{0}$, $L_{0}$, and $R_{0}$) and is referred to as a CSWAP router as it
uses Controlled-SWAPs to route information.

The status of a router at depth $\ell$ of the bucket-brigade model is set
according to the $\ell$th address bit. For our toy model, $\mathbf{R}_{j}$’s
status is set by storing the address qubit $a_{\ell}$ in the status register
$t_{j}$. Once a router’s status is set, it is said to be active and part of a
query path. During qubit route-in, the bus qubit enters the router by being
swapped into the $in_{j}$ register. It is then swapped to the desired memory
location connected to either $R_{j}$ or $L_{j}$ depending on the status in
$t_{j}$. In Fig. 3(b), the circuit for qubit route-out is not explicitly
depicted, as it is the qubit-route in a circuit in reverse.

When a memory address is queried, the control qubits activate a path through
the routers to the target memory cell (shown highlighted in blue in Fig. 4).
Only the routers along this path are activated, significantly reducing the
number of active routers at any time. This is in contrast to the fan-out
architecture where all routers are activated simultaneously. As a result, only
$\log N$ routers in the binary tree are strongly entangled with the address
bits, and all other routers are weakly entangled. Similarly, the bus qubit
storing $x_{j}$ is routed back out via the same path and is weakly entangled
with all other routers off the path.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$\ket{w}$$\ket{0}$$\ket{w}$$\ket{w}$$\ket{1}$$\ket{w}$$\ket{0}$$\ket{010}$

Figure 4: High-level routing scheme for the bucket-brigade architecture. The
address bits $\ket{010}$ are sent in from the root level router to set all the
routers in the corresponding query path to the correct state. The routers not
in the query path remain inactive.

A pivotal study by Hann et al. [24] demonstrated a circuit design for the
bucket-brigade model with $O(\log^{2}N)$ infidelity that is resilient to
generic gate errors, assuming all-to-all connectivity. They observed that the
error in some query paths remains contained and does not spread to every other
branch of the bucket-brigade model thereby ensuring that some of the query
paths remain free of fault. The key idea here is that CSWAP routers have a
certain ability to contain error. Assuming that all CSWAP routers along a
given path suffer no errors, one can prove that arbitrary errors on any other
router off the path do not affect the state of the bus qubit containing the
queried data. Hence, by linearity, the overall error for this model is limited
only by the error of all CSWAP routers and circuit elements along any one
query path.

###  II.3 SELECT-SWAP architecture

The SELECT-SWAP architecture [23] uses a combination of linear and CNOT
routers (described below) to route addresses and the fan-out architecture to
route out the bus qubit.

The linear routers $\mathcal{R}_{0}$ and $\mathcal{R}_{1}$ in Fig. 5 act like
a SELECT circuit that sets the state of register $q$ to $\ket{1}$ if and only
if the state on the routers equals the state of the address qubits. This is
achieved with the use of multi-control CNOT gates and a detailed
implementation can be found in Ref. [4, Section 3A]. The router is named
linear as its qubits can be set in a line within a planar layout.

$\ket{0}$$\ket{0}$$q$ (a)

$t_{0}$$t_{1}$$q_{0}=\ket{0}$$\ket{1}$ (b)

$t_{0}$$t_{1}$$q_{3}=\ket{0}$$\ket{0}$ (c)

Figure 5: (a) The linear routers $\mathcal{R}_{0}$ and $\mathcal{R}_{1}$ are
configured based on the value of address bits which are set to $\ket{00}$. (b)
In round 0, a specific set of multi-control CNOT gates is applied to ensure
that the control qubit $q_{0}$ is set to $\ket{1}$. (c) The circuit outputs
$q_{i}=\ket{0}$ for all $i\neq\ket{00}$.

The CNOT router in Fig. 6 can be used for diffusing the input signals from a
parent to all child nodes. Notice that implementing a CNOT router does not
require any T gates.

+input (a)

$\ket{0}$ (b)

Figure 6: (a) A single CNOT router for route-in that takes input qubit and
sends it to all its child nodes. (b) Circuit for the CNOT router during route-
in.

The high-level routing scheme for memory with $16$ locations is shown in Fig.
7 where the address bits are partitioned into two sets, each controlling the
linear and fan-out routers respectively. The linear and CNOT routers activate
one out of four sets of memory locations using the first set of address bits.
The second set of address bits then activates the fan-out routers to route out
the qubits stored at the designated memory location to an output register.

$\mathcal{R}_{0}$$\mathcal{R}_{1}$$q_{i}$+++$x_{4i}$$x_{4i+1}$$x_{4i+2}$$x_{4i+3}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$
Figure 7: High-level routing scheme for the SELECT-SWAP architecture for
$N=16$.

Although the SELECT-SWAP architecture targets T count reduction, it cannot
achieve better than linear infidelity for generic error resilience. This
limitation arises because every route in the tree must be correct to produce
the desired output.

###  II.4 Fine-grained error types

A common scenario while analyzing various table lookup designs is to assume a
single error parameter that represents the error contribution of any
operation. However, this obscures the fact that every operation could
contribute differently to the errors in the overall circuit. Separating the
contributions from various errors allows for more in-depth circuit profiling
that helps in identifying which operations hamper the overall performance of a
model or circuit design and how one can best harness its full potential. The
errors that we will consider throughout this work are summarized in Table 4.

###  II.5 Circuit optimization

We note that all the high-level circuits we have presented usually admit
straightforward circuit optimizations. We outline a few examples in this
section.

The CNOT router in Fig. 6(a) is depicted is sending a single input to two
outputs. However, it can be clearly optimized to have one fewer qubit by
instead having the input as one of the outputs.

Similarly, the CSWAP router Fig. 3(a) is depicted as performing a controlled
swap to move the qubit $in_{j}$ to either the left or right. However, this can
also also be optimized by removing one output qubit and one controlled-swap
gate by having the $in_{j}$ input be the same as the $L_{j}$ output. Then, the
qubit will be swapped to $R_{j}$ if and only if $t_{j}$ is $1$ without
affecting the functionality of the router.

Error type | Symbol
---|---
Idling | $\varepsilon_{I}$
Qubit | $\varepsilon_{Q}$
Long range | $\varepsilon_{L}$
SWAP gate | $\varepsilon_{s}$
CSWAP gate | $\varepsilon_{cs}$
CNOT gate | $\varepsilon_{c}$
CCNOT gate | $\varepsilon_{cc}$
Table 4: Error types considered in the fine-tuned analysis throughout this
work.

##  III General table lookup framework

In this section, we present our general error-resilient quantum table lookup
architecture that can simultaneously have sub-linear scaling in qubit count, T
count, and infidelity for a specific choice of parameters. We begin by
describing our framework’s structure followed by delineating its working and
correctness.

$\mathcal{R}$$\mathcal{R}$$\ket{q_{i}}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$++++++++$q_{0}^{\prime}\oplus
x_{\lambda i}$$q_{1}^{\prime}\oplus x_{\lambda
i+1}$$q_{\lambda-2}^{\prime}\oplus x_{\lambda
i+\lambda-2}$$q_{\lambda-1}^{\prime}\oplus x_{\lambda
i+\lambda-1}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$\mathbf{R}$$d$$d^{\prime}$$n-d-d^{\prime}$$n-d$

Figure 8: High-level routing scheme for a generic noise resilient data lookup
framework.

The high-level scheme of our design to query a memory of size $N=2^{n}$ with
partition size $\lambda\leq N$ and CNOT tree size $\gamma\leq\lambda$ can be
visualized as the tree-like structure shown in Fig. 8. The top of our design
contains $d\leq n$ linear routers $\mathcal{R}_{0},\ldots,\mathcal{R}_{d-1}$
where $d=\log_{2}\left(\frac{N}{\lambda}\right)$. This is followed by a tree
of depth $d^{\prime}$ made up of CSWAP routers
$\mathbf{R}_{0},\ldots,\mathbf{R}_{2^{d^{\prime}+1}-1}$ where
$d^{\prime}=\log_{2}\left(\frac{\lambda}{\gamma}\right)$. Each of the
$2^{d^{\prime}}$ leaves of this tree has a corresponding CNOT tree with
$\gamma$ leaves attached to it. Essentially, the linear routers are used to
partition the $N$ memory locations into sets of size $\lambda$ and the CSWAP
routers further partition these into sets of size $\gamma$. Each leaf of the
CNOT tree is connected to a memory location. The bottom of the design contains
a tree of depth $n-d$ made up of CSWAP routers
$\mathbf{R}_{0},\ldots,\mathbf{R}_{2^{n-d+1}-1}$ to read the queried data from
the appropriate location. The parts of the tree that correspond to the query
path for $x_{0}$ are highlighted in blue in Fig. 8.

Data lookup in our framework can be broken into three stages and without loss
of generality, we describe the process to query address
$\ket{a}=\ket{a_{0}\ldots a_{n-1}}=\ket{0\ldots 0}$:

#### Stage I (address setting).

The status of the linear routers is set using the first $d$ address bits such
that $\ket{\mathcal{R}_{z}}=\ket{a_{z}}$. Next, the status of the $d^{\prime}$
CSWAP routers in the query path are set sequentially using the address bits
$\ket{a_{d}\dots a_{d+d^{\prime}-1}}$. Note that only the CSWAP routers along
the query path are set, as opposed to every router in the CSWAP tree.

#### Stage II (querying memory).

Let $[m]$ denote the set $\\{0,\ldots,m-1\\}$ for a number $m$. The objective
in this stage is to compute intermediate values
$q^{\prime}_{0},q^{\prime}_{1},\ldots,q^{\prime}_{\lambda-1}$ through
$N/\lambda$ repetitions. For $i\in\left[\frac{N}{\lambda}\right]$, the control
qubit $q_{i}$ is set to $\ket{1}$ if and only if $\ket{i}=\ket{a_{0}\ldots
a_{d-1}}$. In our example, only $q_{0}$ is set to $\ket{1}$ and $q_{i}$ is set
to $\ket{0}$ for $i\neq 0$. The control $q_{i}$ is routed along the query path
determined by the status of the CSWAP routers set in Stage I to a leaf of the
depth $d^{\prime}$ tree. Then, $q_{i}$’s value is diffused to the $\gamma$
leaves of the activated CNOT tree attached to this leaf. In our example,
$q_{i}$ will be routed and diffused to the leftmost CNOT tree. Note that in
the $i$th repetition, the leaves of this CNOT tree are associated with the
memory locations $\\{{\lambda\cdot i+j}\mid j\in[\lambda]\\}$. Finally,
$q_{i}$’s value acts as a control indicating whether data from memory is
loaded into the corresponding $q^{\prime}_{j}$ qubit registers. For instance,
when $\ket{a_{d}\dots a_{d+d^{\prime}-1}}=\ket{0\ldots 0}$, qubit registers
$\\{q^{\prime}_{j}\\}$ are updated with the data $\\{x_{\lambda\cdot i+j}\\}$
for $j\in[\gamma]$. By contrast, the qubit registers $q^{\prime}_{j}$ for
$j\in\\{\gamma,\gamma+1,\ldots,{\lambda-1}\\}$ remain unchanged. Specifically,
the values in the $q^{\prime}_{j}$ registers satisfy:

$\displaystyle q^{\prime}_{j}=\bigoplus_{i=0}^{N/\lambda}q_{i}x_{\lambda\cdot
i+j}$ (2)

where $\oplus$ denotes addition modulo 2. For our example, after $N/\lambda$
repetitions, only $q_{0}=1$ and only the leftmost CNOT tree is activated.
Hence, we find that $q^{\prime}_{j}=x_{j}$ for $j\in[\gamma]$ and
$q^{\prime}_{j}=\ket{0}$ otherwise. We remark that between each repetition,
the qubits in the CNOT trees can be trivially reset to $\ket{0}$.
Additionally, $q_{i}$ is routed back to the top of the CSWAP tree and all
qubits except for the router status qubits are reset trivially to $\ket{0}$.

#### Stage III (retrieving data).

Data is retrieved similar to how the bus qubit is routed out of the noise-
resilient bucket brigade architecture in Ref. [24]. We use the address bits
$\ket{a_{d}\ldots a_{n-1}}$ to set the status of the $n-d$ CSWAP routers at
the bottom of our design. As in Stage I, it is only the routers in the query
path whose status is set. The leaves of this CSWAP tree point to the
$q^{\prime}$ registers and only the data in $q^{\prime}_{\ell}$ for
$\ell=a_{d}\ldots a_{n-1}$ is retrieved. In our example, this leads to
$q^{\prime}_{0}$ being retrieved at the end of the data lookup process.

The detailed procedure for data lookup is shown in Algorithm 1. Our objective
is to examine the optimal balance between $d$ and $d^{\prime}$ that results in
the most favorable infidelity, T count, and qubit count scaling. Our fine-
grained analysis uses the error types from Table 4.

Algorithm 1 Pseudocode for quantum data lookup on memory of size $N$,
partition size $\lambda$, and CNOT tree size $\gamma$

Setup: classical database data of size $N$ with $n=\log_{2}N$, memory
partition $\lambda\leq N$ with $d=\log_{2}\left(\frac{N}{\lambda}\right)$ and
CNOT tree size $\gamma\leq\lambda$ with
$d^{\prime}=\log_{2}\left(\frac{\lambda}{\gamma}\right)$.

Input: state $\ket{a}$ where $a=a_{0}\ldots a_{n-1}$ is an address of length
$n$.

Output: state $\ket{a}\ket{\texttt{data}[a]}$ where data$[a]$ refers to the
data at address $a$.

1:Stage I:

2:Initialize all qubits of the quantum lookup table to $0$.

3:for $k$ in $0\ldots d-1$ do

4: Set $a_{k}$ as the status of the linear router $\mathcal{R}_{k}$.

5: Set the status of the CSWAP routers based on address bits $a_{d}\dots
a_{d+d^{\prime}-1}$

6:Stage II:

7:for $i$ in $0\ldots 2^{d}-1$ do

8: if $i=a_{0}\ldots a_{d-1}$ then

9: Set $q_{i}\leftarrow\ket{1}$

10: else

11: Set $q_{i}\leftarrow\ket{0}$

12: Route $q_{i}$ along the query path determined by the CSWAP routers to a
leaf attached to a CNOT tree.

13: Propagate $q_{i}$’s signal to the $\gamma$ leaves
$c_{0},\dots,c_{\gamma-1}$ of the CNOT tree.

14: for $j$ in $0\ldots\lambda-1$ do

15: Apply unitary $U_{\lambda\cdot i+j}$ where $U_{\lambda\cdot i+j}=$
CNOT$\ket{c_{j}}\ket{q^{\prime}_{j}}$ if data$[\lambda\cdot i+j]=1$ and
$\mathbf{I}$ otherwise.

16: Reset all qubits $c_{j}$ and those in the CNOT tree to $0$.

17: Route $q_{i}$ back up the CSWAP routers to its original location.

18: Reset all the qubits of the CSWAP routers except the router status qubits
and $q_{i}$ to $0$.

19:Stage III:

20:Set the status of $\log_{2}(\lambda)$ CSWAP routers based on address bits
$a_{d}\ldots a_{n-1}$.

21:Route $q^{\prime}_{\ell}$ along the query path determined by the CSWAP
routers to the output register where $\ell=a_{d}\ldots a_{n-1}$.

######  Theorem III.1.

Consider the quantum data lookup structure with the high-level scheme in Fig.
8 with $N$ memory locations. Let $n=\log N$, $\lambda=2^{n-d}$ be the
partition size and $\gamma=2^{n-d-d^{\prime}}$ be the size of a CNOT tree with
$d^{\prime}\leq d\leq n$. The infidelity of this circuit is

$\displaystyle\begin{split}&O\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\varepsilon_{L}\left(\frac{\gamma
N}{\lambda}+\frac{N}{\lambda}\log\frac{\lambda}{\gamma}\right)}+\varepsilon_{s}\log\frac{\lambda^{2}}{\gamma}\right.\\\
&\left.+\varepsilon_{I}\left(\frac{N}{\lambda}\log
N\left(\log\frac{N}{\gamma}+\gamma+\log\frac{\lambda}{\gamma}\right)+\operatorname{polylog}\lambda\right)\right.\\\
&\left.+\varepsilon_{c}\frac{\gamma
N}{\lambda}+\varepsilon_{cc}\frac{N}{\lambda}\log\frac{N}{\lambda}\right.\\\
&\left.+\varepsilon_{cs}\left(\frac{N}{\lambda}\log\frac{\lambda}{\gamma}+\log^{2}\frac{\lambda}{\gamma}+\log^{2}\lambda\right)\right).\end{split}$
(3)

Moreover, the T count for this design is
$O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+\lambda)$, and its
qubit count is $O(\log\frac{N}{\lambda}+\lambda)$.

We will restate and prove this theorem in Section IV.3 after explaining how to
lay out the scheme in Fig. 8 on a planar grid with nearest neighbor
connectivity. Here, we use the above theorem to find an instance that has sub-
linear scaling for infidelity, qubit, and T-counts.

######  Corollary III.2.

For $N$ memory locations, there exists a quantum data lookup scheme that has
$\tilde{O}(N^{\frac{3}{4}})$ infidelity, $O(N^{\frac{3}{4}})$ T count, and
$O(\sqrt{N})$ qubit count.

###### Proof.

For the high-level scheme depicted in Fig. 8, setting $\lambda=\sqrt{N}$ and
$\gamma=N^{1/4}$ and applying Theorem III.1, gives the result. ∎

We claim that it is necessary to have CSWAP routers at the top of our design
in Stages I and II to achieve sublinear infidelity scaling. Assume by way of
contradiction that the CSWAP routers are replaced with CNOT routers. First,
note that CNOT routers are not robust to Pauli $Z$ errors as shown in Fig. 9.
Although the Pauli $Z$ error propagates only to the parent node in the CNOT
router, it can result in a phase kickback that can alter the address state
presented during a query. Specifically for our example, this happens when
$i=a_{0}\ldots a_{d-1}$ in Stage II, and there are an odd number of Z errors
along the query path in the framework. A comparable scenario is also presented
in Ref. [25, Section V], where the read-out CNOT tree demonstrates resilience
to only Pauli Z errors.

qubit q[3]; setstyle very thick, blue q[2]; setstyle very thick, red q[1];
[fill=red!20] x q[1]; cnot q[1] — q[0]; cnot q[2] — q[0]; setstyle very thick,
blue q[2]; setstyle very thick, red q[1]; cnot q[1] — q[0]; cnot q[2] — q[0];
[fill=red!20] x q[1];

(a)

qubit q[3]; setstyle very thick, blue q[2]; setstyle very thick, red q[1];
[fill=red!20] z q[1]; cnot q[1] — q[0]; cnot q[2] — q[0]; setstyle very thick,
blue q[2]; setstyle very thick, red q[1]; setstyle very thick, red q[0]; cnot
q[1] — q[0]; cnot q[2] — q[0]; [fill=red!20] z q[0]; [fill=red!20] z q[1];

(b)

Figure 9: (a) Pauli $X$ error does not propagate from the bad branch (red) to
the good branch (blue) in the CNOT router. (b) Pauli $Z$ error does propagate
into the parent register from a child branch in the CNOT router.

Second, to prevent a phase kickback, we need to assume that the entire CNOT
tree with $\lambda$ leaves is part of the query branch and remains Pauli $Z$
error-free. In this case, the idling error will be dominated by Stage II’s
contribution of
$O\left(2^{d}\varepsilon_{I}\left(d+2^{n-d}\right)\right)=O(2^{n})$ leading to
a linear infidelity scaling. By contrast, the CSWAP router is robust against
error propagation (see Section IV for details). Hence, we consider our
framework with a non-zero number of CSWAP routers at the top of our design to
be a more resource-efficient approach.

Uncomputing the table lookup circuit is crucial to ensure that there are no
residual garbage states entangled with the address and output registers once a
query has been performed. For our design, uncomputing can be done as follows.
First, run the circuit for Stage III in reverse to route the output bit back
into its corresponding $q^{\prime}$ register, then run the Stage II circuits
again to set all $q^{\prime}$ registers to $0$. Finally, run the Stage I
circuit in reverse to reset the status of all the routers. This will
effectively double the infidelity scaling.

A potential way to reduce the T count for our framework without worsening its
query infidelity is by modifying the design for Stage III. Specifically, in
Fig. 8, we retain the CSWAP tree from the bottom of the figure up to a depth
$d^{\prime}$. Each of the $2^{d^{\prime}}$ leaves of this tree has a
corresponding tree of fan-out routers with $\gamma$ leaves attached to it.
Each of the $\gamma$ leaves is connected to a corresponding $q^{\prime}_{j}$
register. Essentially, this creates $\lambda/\gamma$ different fan-out router
substructures each of whose routers is set independently of the other. Let
$\ell=a_{d}\ldots a_{n}-1$. Then, this will impose the condition that the
$\gamma$-sized sub-structure of the fan-out routers containing
$q^{\prime}_{\ell}$ should be error-free for noise resiliency. Since a similar
condition is satisfied by the CNOT trees in Stage II, this does not affect the
asymptotic scaling for the infidelity. However, the T count reduces as the
fan-out routers do not use T gates. A more detailed analysis of this
improvement is left for future work.

##  IV Planar layouts for quantum data lookup frameworks

In this section, we discuss how our general quantum data lookup framework can
be designed on a planar layout with only local connectivity. We first build
some intuition for the underlying principles to achieve this by modifying the
bucket-brigade design of [24] for a planar layout. This is illustrated in
Section IV.1. An initial analysis of query infidelity for this design, shows
that it scales sub-linearly in memory size for the planar layout. In Section
IV.2 we use entanglement distillation to perform long-range operations and
recover the log scaling for query infidelity in the planar layout. We put
these ideas together to present the planar layout for our general framework in
Section IV.3.

###  IV.1 Planar layout for the bucket-brigade model

We provide a circuit design for the bucket-brigade QRAM model, assuming the
qubits are laid out on a 2D planar lattice and multi-qubit gates act only on
adjacent qubits. We first demonstrate a toy model with two memory locations,
where the routing scheme is depicted as a binary tree in Fig. 3(a). To reach
the desired memory allocation, a single CSWAP router $\mathbf{R}_{0}$ is
employed to direct the incoming address qubit into the designated memory
location, from where the stored data $x_{i}$ is retrieved and then routed out
using the same path.

$t_{0}$$L_{0}$$in_{0}$$R_{0}$$a_{0}$inputbus (a)

(b)

Figure 10: (a) A planar layout of qubits for the toy model with nearest-
neighbor connectivity. (b) Joining two T-shaped routers to form a single
H-tree segment.

The CSWAP router’s four qubits can be arranged in a T-shaped configuration as
shown in Fig. 10(a) where the qubits are located at the intersections of the
grid. This configuration ensures that each router qubit is adjacent to any
other router qubit with at most one local SWAP. The three-qubit CSWAP gate can
be decomposed into a sequence of Clifford and T gates that operate on at most
two qubits [23].

For the larger memory size of $N=16$, the high-level bucket-brigade routing
scheme is shown in Fig. 11(a), where both the route-in and route-out phases
follow the same path in the tree. The corresponding planar layout is shown in
Fig. 11(b) where the blue lines show the structure of a CSWAP router, the red
lines show connections between different levels of the routing scheme, and the
input, address, and bus qubits are positioned in the center of the diagram.

The routers are placed on the grid following the H-tree fractal pattern [34]
starting from the root at the center and leaves at the boundaries of the grid.
The left and right registers of the leaf-level routers send an incoming qubit
to the respective memory locations. A pair of T-shaped routers each laid out
according to Fig. 10(a) can be joined together to form a single H-tree segment
as shown in Fig. 10(b). Note that such a planar layout scheme can be naturally
extended to higher dimensions such as a cubic grid for 3D. However, we focus
only on the planar grid throughout this work.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$\mathbf{R}_{7}$$\mathbf{R}_{8}$$\mathbf{R}_{9}$$\mathbf{R}_{10}$$\mathbf{R}_{11}$$\mathbf{R}_{12}$$\mathbf{R}_{13}$$\mathbf{R}_{14}$$\mathbf{R}_{3}$$\mathbf{R}_{4}$$\mathbf{R}_{5}$$\mathbf{R}_{6}$$\mathbf{R}_{1}$$\mathbf{R}_{2}$$\mathbf{R}_{0}$
(a)

inputbus$a_{0}$$a_{1}$$a_{2}$$a_{2}$$t_{0}$$in_{0}$$R_{0}$$L_{0}$$t_{1}$$in_{1}$$L_{1}$$R_{1}$$t_{2}$$in_{2}$$L_{2}$$R_{2}$$t_{3}$$in_{3}$$L_{3}$$R_{3}$$t_{4}$$in_{4}$$L_{4}$$R_{4}$$t_{5}$$in_{5}$$L_{5}$$R_{5}$$t_{6}$$in_{6}$$L_{6}$$R_{6}$$t_{7}$$in_{7}$$L_{7}$$R_{7}$$t_{8}$$in_{8}$$L_{8}$$R_{8}$$t_{9}$$in_{9}$$L_{9}$$R_{9}$$t_{10}$$in_{10}$$L_{10}$$R_{10}$$t_{11}$$in_{11}$$L_{11}$$R_{11}$$t_{12}$$in_{12}$$L_{12}$$R_{12}$$t_{13}$$in_{13}$$L_{13}$$R_{13}$$t_{14}$$in_{14}$$L_{14}$$R_{14}$
(b)

Figure 11: (a) High-level routing scheme for the bucket-brigade architecture
with $16$ memory locations. (b) Qubit layout arrangement of the bucket-brigade
model with $16$ memory locations.

The recursive expansion of the fractal layout yields an optimal layout that
occupies an area of size $O(N)$. For this layout scheme the T count, and qubit
count scale as $O(N)$ since the layout uses $O(N)$ CSWAP routers and there are
$O(N)$ points in the rectangular grid where each point corresponds to a qubit.
Unlike in the all-to-all connectivity case, the error accumulation in the
planar layout occurs due to the long-range gates that need to be performed
such as those along the red lines in Fig. 11(b). Naively, if we assume that
the probability of gate error is $\varepsilon_{max}$ and a long-range SWAP is
performed using a successive series of SWAP gates, the overall infidelity
scales as $O(N\varepsilon_{max})$ as both the circuit depth and number of
gates for each query scales as $O(\sqrt{N})$. However, by performing a more
fine-grained error analysis, we show how the infidelity can scale sub-linearly
in $N$.

The foundation for calculating the infidelity scaling lies in the crucial
property of error containment exhibited by the bucket-brigade QRAM. Consider
the tree branches in Fig. 11(a). They can be categorized either as good or bad
based on the presence or absence of errors in them. In Ref. [24, Appendix D],
it was shown that the errors do not spread from a bad branch to a good branch,
and assuming that the query path is a good branch, this implies that errors in
other parts of the QRAM do not significantly affect the query. Importantly,
this holds regardless of the layout scheme as long as CSWAP routers are used
to enact the high-level routing scheme in Fig. 11(a). Hence, we can use the
error containment property for our planar layout too.

To improve the overall infidelity of our layout scheme, we modify the circuit
and employ constant depth circuits for long-range operations between non-
adjacent qubits. One way to implement a long-range SWAP between two qubits
separated by a line of $m$ qubits(e.g., a single red line in Fig. 11(b)), is
to use a strongly entangled length-$m$ GHZ state as a resource. The long-range
gate is then performed involving the qubits near the endpoint as shown in Ref.
[35]. A length-$m$ GHZ state is

$\displaystyle\ket{\text{GHZ}_{m}}=\frac{\ket{0}^{\bigotimes
m}+\ket{1}^{\bigotimes m}}{\sqrt{2}}.$ (4)

The error contribution for using GHZ states in this case is stated below.

######  Lemma IV.1.

For a given GHZ state of length $m$, the probability that any long-range
operation using this state has an error is $O(m\varepsilon_{Q})$ where
$\varepsilon_{Q}$ is the probability of a single qubit having an error.

###### Proof.

For the GHZ state to be correct, all its underlying qubits have to be correct.
Using triangular inequality yields the desired error probability for the GHZ
state. ∎

Lemma IV.1 shows that despite the constant depth needed for the long-range
operation, its error rate increases linearly with the length of the GHZ state.
However, GHZ states of arbitrary length can be created using a constant-depth
circuit [17]. Consequently, all the GHZ states utilized for the long-range
SWAPs can be generated in place without incurring a substantial overhead. In
fact, with this modification, the circuit depth for the planar layout reduces
from $O(\sqrt{N})$ to $O(\log N)$, thereby leading to a sub-linear infidelity
scaling of $O(\sqrt{N})$.

###  IV.2 Recovering log scaling in infidelity

As using GHZ states still gives a polynomial dependence on $N$ in the
infidelity analysis, we instead consider performing a long-range SWAP on
remote qubits using a Bell state $\Bigl{(}$i.e.,
$\ket{\Phi^{+}}=\frac{\ket{00}+\ket{11}}{\sqrt{2}}\Bigr{)}$ between them as a
resource. To obtain a high-quality Bell state, we use noisy Bell states, a
quantum error correcting code, and an entanglement distillation protocol as
shown in [36, Section II.D].

######  Lemma IV.2.

Given an $[[\hat{n},\hat{k},\hat{d}]]$ quantum error correcting code and
$\hat{n}$ noisy Bell pairs with initial error $\varepsilon_{i}$, there exists
a distillation protocol that creates $\hat{k}$ Bell pairs with error
$\varepsilon_{f}<\varepsilon_{i}$ where
$\varepsilon_{f}=O(\varepsilon_{I}^{d})$. Moreover, when
$\varepsilon_{i}=O(m\cdot\varepsilon_{G})$ and $\varepsilon_{f}<1$ is a small
constant, $d=O(\log m)$.

To perform a long-range SWAP, consider the Bell pair being created on adjacent
qubits near the source qubit with one half of it being teleported to be
adjacent to the target qubit using the length-$m$ GHZ state where
$m=O(\sqrt{N})$ as per our layout. Then, from Lemma IV.1 these noisy Bell
pairs could have an error $\varepsilon_{i}\leq
O(\sqrt{N}\cdot\varepsilon_{Q})$ and it is possible to distill a Bell pair
with constant error using say, the surface code, with distance $O(\log N)$.
For this choice of code, the protocol to distill would have depth $O(d)=O(\log
N)$ and the number of noisy Bell pairs used would be
$\hat{n}=O(d^{2})=O(\log^{2}N)$. Combining the two methods gives the
following.

######  Corollary IV.3.

Given two qubits separated by $m$ qubits on a planar grid with local
connectivity, qubit error $\varepsilon_{Q}$ and the error on a distilled Bell
pair $\varepsilon_{f}$, the error on performing a long-range operation between
the two qubits is given by

$\displaystyle\varepsilon_{L}:=\min(m\cdot\varepsilon_{Q},\,\varepsilon_{f}).$
(5)

We acknowledge that, by using entanglement distillation, the overall circuit
depth may increase by a polylogarithmic factor in the worst case, which is
acceptable. However, there might be strategies to mitigate this depth
increase. Therefore, for the purposes of our analysis, we proceed under the
assumption that long-range Bell states are readily available.

Accounting for the overheads due to entanglement distillation, for the planar
layout, we claim that the circuit depth $D$ scales as
$O(\operatorname{polylog}N)$. Understanding the activation sequence of routers
in a query branch is beneficial in performing fine-grained error analysis. For
instance, in the setting router status phase, we try to route as many address
qubits as possible in parallel. This means that it is not necessary to wait
for the address qubit $\ket{a_{\ell}}$ to reach the router at level $\ell$
before sending the address qubits $\ket{a_{\ell+1}}$ to be routed by
$\mathbf{R}_{0}$. Specifically, this reveals that not all qubits need to
maintain their state throughout the entire query depth $T$. Suppose we are
given a fixed query branch of depth four, with the routers
$\mathbf{R}_{0},\mathbf{R}_{1},\mathbf{R}_{2},\mathbf{R}_{3}$ counting from
root to leaf. The activation sequence for each router and associated gates is
depicted in Fig. 12, where the time $\tau_{i}$ increases by an
$O(\operatorname{polylog}N)$ additive factor and hence the total query time
$\sum_{i}\tau_{i}=O(\operatorname{polylog}(N))$.

$\mathbf{R}_{3}$$\mathbf{R}_{2}$$\mathbf{R}_{1}$$\mathbf{R}_{0}$$\tau_{0}$$\tau_{1}$$\tau_{2}$$\tau_{3}$

Figure 12: The activation sequence of routers in a given query branch of depth
four, where each column represents a single time step. $\tau_{i}$ is the total
time to set the status bit for router $\mathbf{R}_{i}$. The green and blue
dots indicate the router at the associated time step that is in use. The
rectangle represents a local SWAP operation over the qubits associated with
the router, the circle represents a local CSWAP operation, and the dashed
rectangle represents a long-range SWAP between qubits associated with parent
and child routers. The green and blue colors refer to routers at even and odd
depths respectively of the tree as per the routing scheme in Fig. 11(a).

The error terms for our fine-grained analysis are taken from Table 4.

######  Theorem IV.4.

For $N$ memory locations, the improved fine-grained infidelity of the bucket-
brigade QRAM with planar layout (Fig. 11(b)) scales as

$\displaystyle O\left(\log^{2}N\varepsilon_{L}+\log
N\varepsilon_{s}+\log^{2}N\varepsilon_{cs}+\operatorname{polylog}N\varepsilon_{I}\right).$
(6)

###### Proof.

For a fixed query branch, we first consider the error contribution from the
long-range operation. Let $T=\log N$ be the tree depth of the routing scheme
as shown in Fig. 11(a). By Corollary IV.3, the contribution of long-range
error to the probability of a successful query is

$\displaystyle P_{L}$ $\displaystyle=\prod_{\ell=1}^{\log
N}(1-\varepsilon_{L})^{3(T-\ell)}=(1-\varepsilon_{L})^{\Omega(T^{2})},$ (7)

where $3(T-\ell)$ is the number of times a long-range CNOT is applied to
execute $T-\ell$ long-range SWAP operations. This pattern is also evident in
Fig. 12, where a long-range operation between $\mathbf{R}_{1}$ and
$\mathbf{R}_{2}$ occurs $T$ times, but occurs only $T-1$ times between
$\mathbf{R}_{2}$ and $\mathbf{R}_{3}$.

Next, consider the error contribution from the local SWAP operation over
qubits associated with individual routers. It can be observed from Fig. 12
that it takes two local swap operations for the address setting of each
router. Hence the contribution of local SWAP error to the probability of a
successful query is

$\displaystyle P_{s}$
$\displaystyle=(1-\varepsilon_{s})^{2T}=(1-\varepsilon_{s})^{\Omega(T)}.$ (8)

The error contribution of the local CSWAP operation can be found similarly,
and its probability contribution toward success is

$\displaystyle P_{cs}$ $\displaystyle=\prod_{\ell=1}^{\log
N}(1-\varepsilon_{cs})^{2\ell}=(1-\varepsilon_{cs})^{\Omega(T^{2})}.$ (9)

Last, we consider the idling error of the status qubit $t_{\ell}$ for each
router $\mathbf{R}_{\ell}$ as it must maintain its value immediately after its
associated router’s address is set. By contrast, the other qubits in the
router can be reset and remain irrelevant until their next usage. The idling
time for each $\mathbf{R}_{\ell}$’s status qubit $t_{\ell}$ is the total
active time of the router minus the number of CSWAP operations over the qubits
of $\mathbf{R}_{\ell}$. Then, by Fig. 12 and Corollary IV.3, the total idling
time for $\mathbf{R}_{\ell}$ is
$O(T-\ell+\operatorname{polylog}(\frac{\sqrt{N}}{2^{\lceil\ell/2\rceil}}))$.
Therefore, the idling qubit error contribution toward total query success
probability is

$\displaystyle P_{I}$
$\displaystyle=(1-\varepsilon_{I})^{\Omega(\operatorname{polylog}N)}.$ (10)

Since the total success probability is $P=P_{L}\cdot P_{s}\cdot P_{cs}\cdot
P_{I}$, combining Corollary IV.3 with a similar analysis as in reference [24,
Appendix D], we obtain the desired infidelity. ∎

###  IV.3 Planar layout for the general framework

The CSWAP routers form only one part of our general data lookup framework but
the techniques from Section IV.1 can be reused here. For ease of description,
consider a memory of size $N=16$, partition size $\lambda=4$, and CNOT tree
size $\gamma=2$ for our design as shown in Fig. 13.

$\mathcal{R}_{0}$$\mathcal{R}_{1}$$\ket{q_{i}}$$\mathbf{R}_{0}$++$\ket{q^{\prime}_{0}}\leftarrow\ket{q^{\prime}_{0}\oplus
x_{4i}}$$\ket{q^{\prime}_{1}}\leftarrow\ket{q^{\prime}_{1}\oplus
x_{4i+1}}$$\ket{q^{\prime}_{2}}\leftarrow\ket{q^{\prime}_{2}\oplus
x_{4i+2}}$$\ket{q^{\prime}_{3}}\leftarrow\ket{q^{\prime}_{3}\oplus
x_{4i+3}}$$\mathbf{R}^{\prime}_{1}$$\mathbf{R}^{\prime}_{2}$$\mathbf{R}^{\prime}_{0}$Stage
IStage IIStage III Figure 13: High-level routing scheme for a general noise
resilient data lookup framework with sub-linear scaling in qubit count, T
count and infidelity having memory size $N=16$, partition size $\lambda=4$,
CNOT tree size $\gamma=2$ and, $i\in\\{0,1,2,3\\}$. For an address
$\ket{a_{0}a_{1}a_{2}a_{3}}$, the routers are set to
$\ket{\mathcal{R}_{0}}=\ket{a_{0}}$, $\ket{\mathcal{R}_{1}}=\ket{a_{1}}$,
$\ket{\mathbf{R}_{0}}=\ket{\mathbf{R}^{\prime}_{0}}=\ket{a_{2}}$, and
$\ket{\mathbf{R}^{\prime}_{1}}=\ket{a_{3}}$. The colored line highlights the
query branch for $x_{0}$. The number of repetitions in Stage II is
$N/\lambda=4$.

The planar layout for 16 memory locations is given in Figs. 14(a) and 14(b)
where the former depicts the layout during Stages I and II while the latter
holds for Stage III. Some of the routers are labeled in the figures with their
components surrounded by dashed boxes. As the name suggests, the linear
routers are at the top of the design. The middle of the layouts contains the
CSWAP routers $\mathbf{R}_{0}$ and $\mathbf{R}^{\prime}_{0}$ respectively. In
Fig. 14(a), the routers at the sides in the bottom of the figure correspond to
the CNOT trees. By contrast, note that in Fig. 14(b), the same qubits can be
reused for the CSWAP routers $\mathbf{R}^{\prime}_{1}$ and
$\mathbf{R}^{\prime}_{2}$. In comparison to Fig. 11(b), clearly these layouts
use far fewer qubits.

$a_{0}$$\tilde{in}_{0}$$a_{1}$$\tilde{in}_{1}$$q_{i}$inputbus$a_{2}$$a_{3}$$t_{0}$$in_{0}$$R_{0}$$L_{0}$$in_{1}$$q^{\prime}_{0}$$q^{\prime}_{1}$$in_{2}$$q^{\prime}_{2}$$q^{\prime}_{3}$$\mathcal{R}_{0}$$\mathbf{R}_{0}$$\bigoplus$
(a)

$a_{0}$$\tilde{in}_{0}$$a_{1}$$\tilde{in}_{1}$$q_{i}$inputbus$a_{2}$$a_{3}$$t^{\prime}_{0}$$in^{\prime}_{0}$$R^{\prime}_{0}$$L^{\prime}_{0}$$t^{\prime}_{1}$$in^{\prime}_{1}$$q^{\prime}_{0}$$q^{\prime}_{1}$$t^{\prime}_{2}$$in^{\prime}_{2}$$q^{\prime}_{3}$$q^{\prime}_{4}$$\mathbf{R}^{\prime}_{0}$$\mathbf{R}^{\prime}_{1}$
(b)

Figure 14: (a) Qubit layout for the memory querying stage (II) of the unified
quantum lookup architecture framework described in Fig. 8, Section III. (b)
Qubit layout for the memory querying stage (III) of the unified quantum lookup
architecture framework described in Fig. 8, Section III.

Now, we can analyze the T count, qubit count, and query infidelity for our
framework for the planar layouts described here.

######  Theorem (Restatement of Theorem III.1).

Consider the quantum data lookup structure with the high-level scheme in Fig.
8 with $N$ memory locations. Let $n=\log N$, $\lambda=2^{n-d}$ be the
partition size and $\gamma=2^{n-d-d^{\prime}}$ be the size of a CNOT tree with
$d^{\prime}\leq d\leq n$. The infidelity of this circuit is

$\displaystyle\begin{split}&O\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\varepsilon_{L}\left(\frac{\gamma
N}{\lambda}+\frac{N}{\lambda}\log\frac{\lambda}{\gamma}\right)}+\varepsilon_{s}\log\frac{\lambda^{2}}{\gamma}\right.\\\
&\left.+\varepsilon_{I}\left(\frac{N}{\lambda}\log
N\left(\log\frac{N}{\gamma}+\gamma+\log\frac{\lambda}{\gamma}\right)+\operatorname{polylog}\lambda\right)\right.\\\
&\left.+\varepsilon_{c}\frac{\gamma
N}{\lambda}+\varepsilon_{cc}\frac{N}{\lambda}\log\frac{N}{\lambda}\right.\\\
&\left.+\varepsilon_{cs}\left(\frac{N}{\lambda}\log\frac{\lambda}{\gamma}+\log^{2}\frac{\lambda}{\gamma}+\log^{2}\lambda\right)\right).\end{split}$
(11)

Moreover, the T count for this design is
$O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+\lambda)$, and its
qubit count is $O(\log\frac{N}{\lambda}+\lambda)$.

###### Proof.

First, consider Stage I where the linear routers do not contribute to the
infidelity as their status is directly set by the address qubits. The CSWAP
tree functions like a depth-$d^{\prime}$ noise-resilient bucket-brigade QRAM.
For the planar layout, the infidelity for the bucket-brigade QRAM is computed
in Theorem IV.4. Using this, the depth-$d^{\prime}$ CSWAP tree has infidelity
$O(\operatorname{poly}(d^{\prime})\varepsilon_{I}+d^{\prime}{\varepsilon_{L}}+d^{\prime}\varepsilon_{s}+d^{\prime
2}\varepsilon_{cs})$ in Stage I.

For the $\frac{N}{\lambda}=2^{d}$ repetitions performed in Stage II, the
infidelity comes both from gate errors when operations are performed as well
as idling error on qubits that don’t have gates on them. The $O(d)$ Toffoli
gates used to implement the linear routers as per [4] each contribute
$\varepsilon_{cc}$ to the infidelity. The error containment property of the
CSWAP routers discussed in Section IV.2 implies that their contribution is
only $d^{\prime}\varepsilon_{L}$ for the long-range operations performed. For
the CNOT tree with $\gamma$ leaves, its contribution amounts to
$\varepsilon_{L}+\varepsilon_{c}$ for each node in the tree. Then, the overall
gate error infidelity is

$\displaystyle
O\left(2^{d}\left(\varepsilon_{cc}\,d+\varepsilon_{cs}\,d^{\prime}+{\varepsilon_{L}}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}d^{\prime}}+2^{n-d-d^{\prime}}\right)+\varepsilon_{c}\,2^{n-d-d^{\prime}}\right)\right).$
(12)

The infidelity from the idling error is

$\displaystyle
O\left(2^{d}\left(\varepsilon_{I}n\left(d+d^{\prime}+2^{n-d-d^{\prime}}\right)\right)\right),$
(13)

where the terms correspond to the qubits that are not reset between
repetitions. These are the router status qubits for the linear routers and
CSWAP routers along the query path, as well as the $\gamma$ intermediate
registers $q^{\prime}_{i}$ at the leaves of the activated CNOT tree.

Lastly, Stage III acts like a depth-$(n-d)$ bucket-brigade QRAM and applying
Theorem IV.4 again, we obtain its infidelity as
$O(\operatorname{poly}(n-d)\varepsilon_{I}+(n-d){\varepsilon_{L}}+(n-d)\varepsilon_{s}+(n-d)^{2}\varepsilon_{cs})$.
Combining the infidelity from all stages, and replacing $d,d^{\prime}$ and $n$
by $N,\lambda$, and $\gamma$ yields Eq. 11.

The overall T count for the design is

$\displaystyle O\left(2^{d}(2^{d^{\prime}}+d)+2^{n-d}\right),$ (14)

where the first term corresponds to the $2^{d}$ repetitions of Stage II each
of which uses the depth-$d^{\prime}$ CSWAP tree, and the last term comes from
the depth-$(n-d)$ CSWAP tree in Stage III. Note that stage I has T count
$O(2^{d^{\prime}})$ and it is always asymptotically smaller than the Stage II
T count. Replacing $d,d^{\prime}$ and $n$ yields a T count of
$O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+\lambda)$.

The overall qubit count for the design is

$\displaystyle O(d+2^{n-d}),$ (15)

where the first term comes from the linear routers. The depth-$d^{\prime}$
CSWAP tree and the $\gamma$ sized CNOT trees in total contain $O(2^{n-d})$
qubits. In Stage III, the qubits used for the CNOT trees are reused for the
CSWAP routers accounted for in Stage II. Replacing $n$ and $d$ with $N$ and
$\lambda$ yields an overall $O(\log\frac{N}{\lambda}+\lambda)$ qubit count. ∎

##  V Large word size

While all previous circuits considered reading a single bit of information
from memory, in most real-world scenarios, one would want to retrieve multiple
bits of classical information. In this section, we discuss two ways our
general framework can be modified to handle the readout of multiple bits of
information – (i) in parallel; and (ii) in sequence – while still maintaining
a sub-linear scaling for memory size $N$. While the former has lower query
infidelity, the latter has a lower T count. Determining where there exists a
single multi-bit readout scheme that simultaneously minimizes T-count and
infidelity or whether the need for two schemes remains a fundamental
limitation of our framework is left for future work.

Throughout this section, we assume that the _word size_ , i..e, number of bits
to be read out from each memory location is $b$ and for ease of description,
the designs will be described assuming $N=16,\lambda=4$ and $\gamma=2$.

###  V.1 Parallel multi-bit readout

To read $b$-bit words with parallel readout, we make $b$ copies of parts of
our general framework from Fig. 13. Specifically, we create $b$ copies of the
framework involving the register with $\ket{q_{i}}$, the CSWAP routers
$\mathbf{R}_{0}$, $\mathbf{R}^{\prime}_{0}$, $\mathbf{R}^{\prime}_{1}$ and
$\mathbf{R}^{\prime}_{2}$ and the CNOT trees. Note that the three stages for
data lookup proceed as described in Section III except that the $i$th copy
will be used to access the $i$th bit of data, and at the end of Stage III all
the $b$-bits will have been simultaneously retrieved. For $b=2$, this
modification is depicted in Fig. 15 where $\ket{q_{i}}$ is copied to the
registers with $\ket{q^{0}_{i}}$ and $\ket{q^{1}_{i}}$. A very high-level view
of this schematic for $b=6$ is given in Fig. 16 where each square labeled by
${q^{j}_{i}}$ contains the $j$th copy of the single-bit readout framework. The
asymptotic scaling for infidelity, qubit, and T counts for parallel multi-bit
readout is given below.

$\mathcal{R}_{0}$$\mathcal{R}_{1}$$q_{i}$$q_{i}^{(0)}$$q_{i}^{(1)}$${\mathbf{R}_{0}}^{(0)}$++${q^{\prime}_{0}}^{(0)}$${q^{\prime}_{1}}^{(0)}$${q^{\prime}_{2}}^{(0)}$${q^{\prime}_{3}}^{(0)}$${\mathbf{R}^{\prime}_{1}}^{(0)}$${\mathbf{R}^{\prime}_{2}}^{(0)}$${\mathbf{R}^{\prime}_{0}}^{(0)}$${\mathbf{R}_{0}}^{(1)}$++${q^{\prime}_{0}}^{(1)}$${q^{\prime}_{1}}^{(1)}$${q^{\prime}_{2}}^{(1)}$${q^{\prime}_{3}}^{(1)}$${\mathbf{R}^{\prime}_{1}}^{(1)}$${\mathbf{R}^{\prime}_{2}}^{(1)}$${\mathbf{R}^{\prime}_{0}}^{(1)}$

Figure 15: A high-level scheme for parallel readout of word size $b=2$, an
extension to the scheme in Fig. 8.
$q_{i}$${q_{i}}^{(0)}$${q_{i}}^{(1)}$${q_{i}}^{(2)}$${q_{i}}^{(3)}$${q_{i}}^{(4)}$${q_{i}}^{(5)}$
Figure 16: A planar layout of our general quantum data lookup framework for
parallel multi-bit readout with a word size of $b=6$. Each square, labeled by
$q^{j}_{i}$, encompasses the planar layout for each copy of the single-bit
readout framework as depicted in Fig. 15. The red line indicates the path used
for long-range operations responsible for diffusing the signal $q_{i}$ to all
the $q^{j}_{i}$ instances.

######  Theorem V.1.

Consider the quantum data lookup structure with the high-level scheme in Fig.
15 with $N$ memory locations. Let $b=2^{d^{\prime\prime}}$ be the word size,
$n=\log N$, $\lambda=2^{n-d}$ be the partition size and
$\gamma=2^{n-d-d^{\prime}}$ be the size of a CNOT tree with $d^{\prime}\leq
d\leq n$. Also, let $\mathbf{I}$ be the infidelity of the single-bit readout
framework from Theorem III.1. Then, the infidelity of this circuit is
$O(b\mathbf{I}).$ Moreover, the T count is
$O(\log\frac{N}{\lambda}\frac{N}{\lambda}+b\frac{N}{\gamma}+b\lambda)$, and
qubit count is $O(\log\frac{N}{\lambda}+b\lambda)$.

###### Proof.

The multi-bit parallel readout scheme amounts to containing a single copy of
the linear routers followed by $b$ copies of the remainder of the single-bit
readout framework. While the former uses $O(d)$ qubits, the latter uses
$O(b2^{n-d})$ qubits. Additionally, as depicted in Fig. 16, each of
$\ket{q_{i}^{j}}$ registers can be laid out such that they are separated by
$O(2^{\frac{n-d}{2}})$ qubits in the planar grid. Hence, the overall qubit
count is
$O(d+b2^{n-d}+b2^{\frac{n-d}{2}})=O(d+b2^{n-d})=O(\log\frac{N}{\lambda}+b\lambda)$.

Similarly, the T count for this design is
$O(2^{d}(d+b2^{d^{\prime}})+b2^{n-d})=O(\log\frac{N}{\lambda}\frac{N}{\lambda}+b\frac{N}{\gamma}+b\lambda)$.

To analyze the infidelity for this design, let $\mathbf{I}_{s}$ represent the
infidelity at stage $s$ as described in Theorem III.1. In Stage I, the
infidelity is
$O(b\mathbf{I}_{\text{I}}+\epsilon_{L}b2^{\frac{n-d}{2}}d^{\prime})$, where
the second term emerges from the fact that the $d^{\prime}$ address bits used
to set the CSWAP routers have to be copied $b$ times using long-range
operations and routed through each corresponding copy of the single-bit
readout framework as depicted in Fig. 15. Moving to Stage II, the infidelity
is $O(b\mathbf{I}_{\text{II}}+2^{d}(\epsilon_{L}b2^{\frac{n-d}{2}}))$, where
the second term is for the $2^{d}$ times when $\ket{q_{i}}$ is transmitted to
all the $\ket{q_{i}^{j}}$ registers. For Stage III, the infidelity is
$O(b\mathbf{I}_{\text{III}})$ as each of the $b$ bits is retrieved from the
corresponding copy of the readout framework when the procedure is finished.
Aggregating the infidelities across these stages, observing that the extra
terms only amount to an additional $(b\mathbf{I}_{\text{I}})$ factor and
following Eq. 11, we conclude that the total infidelity for parallel $b$-bit
readout is $O(b\mathbf{I})$. ∎

###  V.2 Sequential multi-bit readout

To read $b$-bit words in sequence, we extend the single-bit framework in Fig.
13 by assuming that each memory location points to a $b$-qubit register
instead of a single qubit one and repeating the readout procedure (i.e., Stage
III from Section III) for each bit of data. For $b=2$, this modification is
presented in Fig. 17 where the CNOT tree now has depth
$\log\frac{\lambda}{\gamma}+\log b$ and each leaf of the CNOT tree is
connected to one of the $b$ bits of data. This allows the signal for a memory
location to be accessed to be shared amongst the $b$ qubits. To achieve a
compact design, the planar H-tree design is used to lay out the $b$ qubits of
each memory location. A high-level view of this schematic is given in Fig. 18.
To retrieve the $k$th bit of data, $\ket{q^{\prime(k)}_{j}}$ is swapped into
the ${q^{\prime}_{j}}$ location at iteration $k$ after which Stage III is
applied to retrieve the data from the ${q^{\prime}_{j}}$ register. The
asymptotic scaling for infidelity, T count and qubit count for this design is
given below.

$\mathcal{R}_{0}$$\mathcal{R}_{1}$$q_{i}$$\mathbf{R}_{0}$++++++$q^{\prime(0)}_{4i}$$q^{\prime(1)}_{4i}$$q^{\prime(0)}_{4i+1}$$q^{\prime(1)}_{4i+1}$$q^{\prime(0)}_{4i+2}$$q^{\prime(1)}_{4i+2}$$q^{\prime(0)}_{4i+3}$$q^{\prime(1)}_{4i+3}$$\mathbf{R}^{\prime}_{1}$$\mathbf{R}^{\prime}_{2}$$\mathbf{R}^{\prime}_{0}$$q^{\prime}_{4i}$$q^{\prime}_{4i+1}$$q^{\prime}_{4i+2}$$q^{\prime}_{4i+3}$

Figure 17: A high-level scheme for sequential readout of word size $b=2$, an
extension to the scheme in Fig. 8.
$q_{i}$$q^{\prime}_{4i}$$q^{\prime}_{4i+1}$$q^{\prime}_{4i+2}$$q^{\prime}_{4i+3}$$q^{\prime(0)}_{4i}$$q^{\prime(1)}_{4i}$$q^{\prime(2)}_{4i}$$q^{\prime(3)}_{4i}$$q^{\prime(0)}_{4i+1}$$q^{\prime(1)}_{4i+1}$$q^{\prime(2)}_{4i+1}$$q^{\prime(3)}_{4i+1}$$q^{\prime(0)}_{4i+2}$$q^{\prime(1)}_{4i+2}$$q^{\prime(2)}_{4i+2}$$q^{\prime(3)}_{4i+2}$$q^{\prime(0)}_{4i+3}$$q^{\prime(1)}_{4i+3}$$q^{\prime(2)}_{4i+3}$$q^{\prime(3)}_{4i+3}$
Figure 18: A planar layout of the multi-bit register for each memory location
in the quantum data lookup framework with sequential readout having a word
size of $b=4$.

######  Theorem V.2.

Consider the QRAM with the high-level scheme in Fig. 17 with $N$ memory
locations. Let $b=2^{d^{\prime\prime}}$ be the word size, $n=\log N$. Let
$b=2^{d^{\prime\prime}}$ be the word size, $n=\log N$, $\lambda=2^{n-d}$ be
the partition size and $\gamma=2^{n-d-d^{\prime}}$ be the size of a CNOT tree
with $d^{\prime}\leq d\leq n$. Also, let $\mathbf{I}$ be the infidelity of the
single-bit readout framework in Theorem III.1. Then, the infidelity of this
circuit is $\tilde{O}(b\mathbf{I}+b^{2}\varepsilon_{I}).$ Moreover, the T
count is
$O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+b\lambda)$, and
qubit count is $O(\log\frac{N}{\lambda}+b\lambda)$.

###### Proof.

Before reading out the $b$ memory bits, the analysis follows the same as in
Theorem III.1 which yields $O(b\mathbf{I})$ infidelity. There is an additional
qubit idling error to be considered. It takes
$O(2^{d^{\prime\prime}}+n-d+d^{\prime\prime})$ time to transfer $b$ memory
bits out sequentially. The idling qubits are the memory qubits and the CSWAP
router status bits, hence the total idling error is
$O(\varepsilon_{I}(2^{d^{\prime\prime}}+d^{\prime})(2^{d^{\prime\prime}}+n-d+d^{\prime\prime})=\tilde{O}(b^{2}\varepsilon_{I})$.

The number of CSWAP routers and linear routers is unchanged for Stages I and
II but the CSWAP routers are used $b$ times in Stage III. Hence, the T count
is $O(\frac{N}{\gamma}+\frac{N}{\lambda}\log\frac{N}{\lambda}+b\lambda)$ where
each term matches the count for each Stage respectively. The qubit count is
$O(d+2^{n-d+d^{\prime\prime}})=O(\log\frac{N}{\lambda}+b\lambda)$ as the size
of the H-tree design for Stages II and III are scaled by $b$ due to the deeper
CNOT trees. ∎

##  VI Conclusion

In this work, we construct a general quantum data lookup framework and
describe how it can be arranged on a planar grid with local connectivity.
Further, we demonstrate that for specific choices of parameters, this
framework can be made to be simultaneously noise-resilient as well as
resource-efficient i.e., having a sub-linear dependency on memory size for
qubit count, T count, and query infidelity. The versatility of our framework
in highlighted as it provides the blueprint for describing a family of
circuits for quantum data lookup with various space, time, and noise
resiliency trade-offs.

As the community moves beyond NISQ architectures to designing error-corrected
implementations of quantum hardware [37, 38, 39, 40, 41] there is an urgent
need to design highly resource-optimal components for quantum applications.
For instance, initially, T gates would be considered an expensive resource so
the focus would be on minimizing the T count. However, future improvements in
large-scale quantum hardware and quantum error correction could dramatically
reduce the cost of T gates, which would shift the focus to minimizing the
query infidelity. Having sub-linear infidelity scaling in this setting would
imply that smaller distance error correcting codes can be used to minimize
overall errors and lead a to reduced qubit count. In this way, we expect the
space-time trade-offs that result from this work to be repeatedly harnessed
for the realization of end-to-end implementations of quantum algorithms using
the evolving state-of-the-art hardware of its time [42].

The circuit designs presented in this work consider limited local connectivity
with qubits laid out in a planar grid. To the best of our knowledge, there has
been no prior comprehensive investigation into a resilient quantum lookup
table framework for real-world applications that takes into account both
resource limitations and local connectivity. However, we believe that our
general framework would be noise resilient and can be more resource-efficient
than prior work irrespective of the constraints imposed by connectivity. For
instance, assuming only nearest neighbor connectivity is among the more
restrictive regimes and having some long-range connectivity for free improves
query infidelity as we show in Appendix A. A thorough analysis of how our
framework would perform for other qubit topologies is left for future work.

Our fine-grained analysis of noise resiliency can be put to use in practice by
replacing those error terms with the noise models or behavior exhibited by the
hardware of choice. Explicitly separating the different sources of error can
aid in understanding how hardware behavior contributes to the overall query
infidelity. This, in turn, can help identify any bottlenecks or design
improvements that may be needed to improve hardware capabilities and implement
quantum data lookup successfully.

Our framework recovers previous proposals for quantum data lookup for
different choices of parameters. For example, with $\lambda=N$ and $\gamma=1$,
we recover the noise-resilient bucket brigade QRAM design; with
$\lambda=\sqrt{N}$ and $\gamma=1$, we recover a variant of the SELECT-SWAP
design; and with $\lambda=1$ and $\gamma=1$ we recover the QROM design. Hence,
we feel justified in considering our design to be a unifying framework. On the
other hand, we acknowledge that one parameter regime that is not covered by
our framework is the indicator function design from [23] that has $\sqrt{N}$
T-count and logarithmic query depth. We conjecture that this design has linear
infidelity scaling but studying whether it can be made noise resilient while
still maintaining the same T-count is left for future work.

While we presented a straightforward method to reset the qubits used for table
lookup, it will result in a doubling of the T count and query infidelity.
Another approach would be to use measurement-based uncomputation as discussed
in [21, Appendix C]. This will lead to an increase in classical processing to
deal with the mid-circuit measurement outcomes but not add too much overhead
in terms of unitary operations. The further study needed to determine whether
this will maintain the sub-linear scaling in infidelity is left as an open
question.

There exists an implicit assumption that the planar layout and local
connectivity versions of both our framework and the bucket-brigade QRAM
require the use of error correction to drive gate errors below some critical
threshold. Without this, the designs can fail to be error-resilient. The
bottleneck here is the difficulty in implementing the entanglement
distillation that is used for long-range operations. For distillation to be
effective, it is necessary that the initial error of noisy Bell pairs –
determined solely by gate errors – be below some threshold. We leave as an
open question whether this threshold can be raised by more sophisticated
techniques such as using quantum repeaters negating the need for error
correction.

###### Acknowledgements.

S.Z. conducted the research during his internship at Microsoft. Additionally,
SZ is supported by the National Science Foundation CAREER award (grant
CCF-1845125), and part of the editing work was performed while SZ was visiting
the Institute for Pure and Applied Mathematics (IPAM), which is supported by
the National Science Foundation (Grant No. DMS-1925919).

## References

  * Berry and Childs [2012] D. W. Berry and A. M. Childs, Black-box Hamiltonian simulation and unitary implementation, Quantum Information & Computation 12, 29 (2012).
  * Berry  _et al._ [2015a] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Simulating Hamiltonian dynamics with a truncated Taylor series, Phys. Rev. Lett. 114, 090502 (2015a).
  * Berry  _et al._ [2015b] D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, in  _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_ (2015) pp. 792–809.
  * Babbush  _et al._ [2018] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  * Bauer  _et al._ [2020] B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Quantum algorithms for quantum chemistry and quantum materials science, Chemical Reviews 120, 12685 (2020).
  * Lloyd  _et al._ [2013] S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning, (2013), arXiv:1307.0411 .
  * Wittek [2014] P. Wittek,  _Quantum machine learning: what quantum computing means to data mining_ (Academic Press, 2014).
  * Adcock  _et al._ [2015] J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic, Advances in quantum machine learning, (2015), arXiv:1512.02900 [quant-ph] .
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).
  * Ciliberto  _et al._ [2018] C. Ciliberto, M. Herbster, A. D. Ialongo, M. Pontil, A. Rocchetto, S. Severini, and L. Wossnig, Quantum machine learning: a classical perspective, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018).
  * Huang  _et al._ [2022] H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, Provably efficient machine learning for quantum many-body problems, Science 377, eabk3333 (2022).
  * Babbush  _et al._ [2021] R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, Focus beyond quadratic speedups for error-corrected quantum advantage, PRX Quantum 2, 010103 (2021).
  * Hoefler  _et al._ [2023] T. Hoefler, T. Häner, and M. Troyer, Disentangling hype from practicality: On realistically achieving quantum advantage, Commun. ACM 66, 82–87 (2023).
  * von Burg  _et al._ [2021] V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler, and M. Troyer, Quantum computing enhanced computational catalysis, Phys. Rev. Res. 3, 033055 (2021).
  * Giovannetti  _et al._ [2008a] V. Giovannetti, S. Lloyd, and L. Maccone, Architectures for a quantum random access memory, Phys. Rev. A 78, 052310 (2008a).
  * Litinski [2019] D. Litinski, A game of surface codes: large-scale quantum computing with lattice surgery, Quantum 3, 128 (2019).
  * Beverland  _et al._ [2022a] M. E. Beverland, P. Murali, M. Troyer, K. M. Svore, T. Hoefler, V. Kliuchnikov, G. H. Low, M. Soeken, A. Sundaram, and A. Vaschillo, Assessing requirements to scale to practical quantum advantage, (2022a), arXiv:2211.07629 [quant-ph] .
  * Giovannetti  _et al._ [2008b] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Phys. Rev. Lett. 100, 160501 (2008b).
  * Arunachalam  _et al._ [2015] S. Arunachalam, V. Gheorghiu, T. Jochym-O’Connor, M. Mosca, and P. V. Srinivasan, On the robustness of bucket brigade quantum ram, New Journal of Physics 17, 123010 (2015).
  * Berry  _et al._ [2019] D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization, Quantum 3, 208 (2019).
  * Matteo  _et al._ [2020] O. D. Matteo, V. Gheorghiu, and M. Mosca, Fault-tolerant resource estimation of quantum random-access memories, IEEE Transactions on Quantum Engineering 1, 1 (2020).
  * Low  _et al._ [2024] G. H. Low, V. Kliuchnikov, and L. Schaeffer, Trading T gates for dirty qubits in state preparation and unitary synthesis, Quantum 8, 1375 (2024).
  * Hann  _et al._ [2021] C. T. Hann, G. Lee, S. Girvin, and L. Jiang, Resilience of quantum random access memory to generic noise, PRX Quantum 2, 020311 (2021).
  * Xu  _et al._ [2023] S. Xu, C. T. Hann, B. Foxman, S. M. Girvin, and Y. Ding, Systems architecture for quantum random access memory, (2023), arXiv:2306.03242 [quant-ph] .
  * Allcock  _et al._ [2023] J. Allcock, J. Bao, J. F. Doriguello, A. Luongo, and M. Santha, Constant-depth circuits for uniformly controlled gates and boolean functions with application to quantum memory circuits, (2023), arXiv:2308.08539 [quant-ph] .
  * Jaques and Rattew [2023] S. Jaques and A. G. Rattew, QRAM: A survey and critique, (2023), arXiv:2305.10310 [quant-ph] .
  * Dalzell  _et al._ [2023] A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gilyén, C. T. Hann, M. J. Kastoryano, E. T. Khabiboulline, A. Kubica, G. Salton, S. Wang, and F. G. S. L. Brandão, Quantum algorithms: A survey of applications and end-to-end complexities, (2023), arXiv:2310.03011 [quant-ph] .
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Pino  _et al._ [2021] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, _et al._ , Demonstration of the trapped-ion quantum ccd computer architecture, Nature 592, 209 (2021).
  * Campbell  _et al._ [2017] E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017).
  * Bravyi and Gosset [2016] S. Bravyi and D. Gosset, Improved classical simulation of quantum circuits dominated by Clifford gates, Phys. Rev. Lett. 116, 250501 (2016).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2010).
  * Mandelbrot and Mandelbrot [1982] B. B. Mandelbrot and B. B. Mandelbrot,  _The fractal geometry of nature_, Vol. 1 (WH freeman New York, 1982).
  * Beverland  _et al._ [2022b] M. Beverland, V. Kliuchnikov, and E. Schoute, Surface code compilation via edge-disjoint paths, PRX Quantum 3, 020342 (2022b).
  * Wilde  _et al._ [2010] M. M. Wilde, H. Krovi, and T. A. Brun, Convolutional entanglement distillation, in  _2010 IEEE International Symposium on Information Theory_ (IEEE, 2010) pp. 2657–2661.
  * Ryan-Anderson  _et al._ [2021] C. Ryan-Anderson, J. G. Bohnet, K. Lee, D. Gresh, A. Hankin, J. P. Gaebler, D. Francois, A. Chernoguzov, D. Lucchetti, N. C. Brown, T. M. Gatterman, S. K. Halit, K. Gilmore, J. A. Gerber, B. Neyenhuis, D. Hayes, and R. P. Stutz, Realization of real-time fault-tolerant quantum error correction, Phys. Rev. X 11, 041058 (2021).
  * Acharya  _et al._ [2023] R. Acharya, I. Aleiner, R. M. Allen, T. I. Andersen, M. Ansmann, F. Arute, K. Arya, A. Asfaw, J. Atalaya, R. Babbush, and et al., Suppressing quantum errors by scaling a surface code logical qubit, Nature 614, 676–681 (2023).
  * Erhard  _et al._ [2021] A. Erhard, H. Poulsen Nautrup, M. Meth, L. Postler, R. Stricker, M. Stadler, V. Negnevitsky, M. Ringbauer, P. Schindler, H. J. Briegel, _et al._ , Entangling logical qubits with lattice surgery, Nature 589, 220 (2021).
  * Postler  _et al._ [2022] L. Postler, S. Heu$\beta$en, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, _et al._ , Demonstration of fault-tolerant universal quantum gate operations, Nature 605, 675 (2022).
  * Bluvstein  _et al._ [2024] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, _et al._ , Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024).
  * Litinski and Nickerson [2022] D. Litinski and N. Nickerson, Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections, (2022), arXiv:2211.15465 [quant-ph] .

##  Appendix A Limited long-range connections

In this section, we consider variations in qubit architectures that allow for
limited long-range connectivity. Examples include superconducting qubits with
long-range connections for LDPC codes or those where qubits can be coupled
with photons that can be used to create high-quality Bell states. We study how
the assumption of allowing only a few gates to be able to act long-range
without overhead impacts infidelity. Unlike in the main text, we assume that
there are only two ways in which to perform long-range interactions: (i) using
a limited number of almost perfect Bell pairs that can be used to perfectly
perform long-range operations; and (ii) creating noisy GHZ states linked
between source and target qubits as described in Section III.

###  A.1 Bucket-brigade model

First, consider the planar bucket-brigade model from Section IV.1. We allow
the first $k$ level of CSWAP routers the ability to perform long-range
operations without any errors and produce a modified version of Theorem IV.4.

######  Corollary A.1.

Let the first $k$ level routers in the bucket-brigade QRAM of Fig. 11(a) have
the ability to perform long-range operations without any overhead. For $N$
memory locations, the improved fine-grained infidelity of the basic planar
layout (Fig. 11(b)) scales as

$\displaystyle O\left(2^{-\frac{k}{2}}\log N\sqrt{N}\varepsilon_{Q}+\log
N\varepsilon_{s}+\log^{2}N\varepsilon_{cs}+\log^{2}N\varepsilon_{I}\right).$
(16)

###### Proof.

The result largely follows from the proof of Theorem IV.4 along with two
modifications. First, adjust the initial value of $\ell$ in Eq. 7 from $1$ to
$k$ as all levels up to $k$ will not contribute to query infidelity.
Additionally, as the remaining long-range operations only use GHZ states as a
resource, its contribution to infidelity is $m\cdot\varepsilon_{Q}$ for GHZ
states of length $m$ from Lemma IV.1. As $m<\sqrt{N}$, we can upper bound this
contribution as $O(\sqrt{N}\varepsilon_{Q})$. Since no magic state
distillation is applied, the total idling time for each CSWAP router
$R_{\ell}$ is $O(T-\ell)$, which leads to an overall $\log^{2}N$ error
contribution from the idling error. This gives the desired result. ∎

When $k$ equals $\log{N}$, the planar layout achieves the expected
$O(\log^{2}N)$ infidelity scaling from [24].

###  A.2 General framework

We study the effect of allowing the first $k$ level of CSWAP + CNOT routers in
Stages I and II of the general framework from Section III the ability to
perform long-range operations without any error and produce a modified version
of version of Theorem III.1.

######  Corollary A.2.

Consider the quantum data lookup structure with the high-level scheme in Fig.
8 with $N$ memory locations. Let $n=\log N$, $\lambda=2^{n-d}$ be the
partitions size, and $\gamma=2^{n-d-d^{\prime}}$ be the size of a CNOT tree
with $d^{\prime}\leq d\leq n$. Let the first $k$-levels of the CSWAP + CNOT
routers in Stages I and II have the ability to perform long-distance SWAP
gates without any overhead. Let $\mathcal{E}$ denote the sum of all but
$\varepsilon_{L}$ error in Theorem III.1, then the infidelity of the circuit
is

$\displaystyle\tilde{O}\left(\varepsilon_{Q}\left(2^{-\frac{k}{2}}\sqrt{\lambda}+2^{-\frac{k}{2}}\frac{N}{\sqrt{\lambda}}+\frac{\gamma
N}{\lambda}\right)+\mathcal{E}\right),$ (17)

for $k\leq d^{\prime}$, and

$\displaystyle\tilde{O}\left(\varepsilon_{Q}\left(2^{-k}N+2^{-\frac{k}{2}}\sqrt{\lambda}\right)+\mathcal{E}\right),$
(18)

for $d^{\prime}<k\leq n-d$.

###### Proof.

For $k\leq d^{\prime}$, in stage I the GHZ error induced from qubit error is
$d^{\prime}2^{\frac{n-d-k}{2}}\varepsilon_{Q}$, and in Stage II the GHZ error
is $2^{d}(2^{\frac{n-d-k}{2}}+2^{n-d-d^{\prime}})\varepsilon_{Q}$. The
remaining error analysis follows from Theorem III.1, and combining these
yields the desired GHZ error.

For $k>d^{\prime}$, in stage I there is no GHZ error, in stage II the GHZ
error comes from the CNOT tree, which becomes $2^{d}\cdot
2^{n-d-d^{\prime}-(k-d^{\prime})}\varepsilon_{Q}$. The remaining error
analysis follows from Theorem III.1, and combining these yields the desired
GHZ error. ∎

Corollary A.2 illustrates the challenging nature of achieving optimal scaling
in various aspects by balancing the parameters $\lambda$ and $\gamma$ with a
budget of performing $O(2^{k})$ long-range operations without overhead. It
becomes apparent that striking the perfect balance is a formidable task as it
adds parameter that needs to be optimized.

However, for some limited flexibility in choices for
$d=\log\left(\frac{N}{\lambda}\right)$,
$d^{\prime}=\log\left(\frac{\lambda}{\gamma}\right)$, and the long-range
budget $2^{k}$, we try to provide some additional insights. For instance,
within the realm of $\tilde{O}(N^{3/4})$ T count, we tabulate how the exponent
determining how infidelity scales for increasing values of
$k\in\\{0,d^{\prime}/4,d^{\prime}/2,3d^{\prime}/4,d\\}$ in Tables 5, 7, 6, 8
and 9 respectively. Specifically for the green regions in these tables, we
find that:

  1. 1.

When $d^{\prime}$ is relatively small, specifically when $d^{\prime}\leq n/4$,
the presence of long-range connectivity does not decrease infidelity. This is
because the primary source of error originates from the CNOT tree section of
the circuit.

  2. 2.

Any further decrease in infidelity becomes unattainable when $k$ exceeds
$d^{\prime}/2$. This is because, when $k>d^{\prime}/2$, the predominant factor
contributing to the error is the idling error by Eq. 17.

  3. 3.

The greater the value of $d^{\prime}$ that can be accommodated, the more
favorable the infidelity scaling becomes. This is because larger values of
$d^{\prime}$ serve to diminish both the long-range errors as well as the
idling error for the CNOT tree.

  4. 4.

Increasing the value of $d$ leads to a more favorable qubit count, as the
qubit count scales as $O(2^{n-d})$. However, this sets up a trade-off between
selecting a larger value of $d$ for improved qubit count or a larger value of
$d^{\prime}$ for reduced infidelity within the $O(N^{3/4})$ T-count regime.

Extending the analysis naturally allows the initial $k$ levels in the route-in
procedure to perform long-range operations without overhead, while permitting
the final $k^{\prime}$ levels in the route-out procedure to do the same. In a
practical context, this can be likened to having a long-range budget of
$2^{d+k}$ for the route-in and a long-range budget of $2^{k^{\prime}}$ for the
route-out process. The objective is to strike a balance between the values of
$k$ and $k^{\prime}$ to attain the most favorable scaling of infidelity.

We can briefly argue that it is not useful to separately consider $k$ vs.
$k^{\prime}$ in the regime that yields sublinear infidelity and T count. This
is because the long-range error from route-out only dominates that of route-in
when $k>2d$, at which point a non-zero $k^{\prime}$ is required to suppress
the long-range error from the route-out procedure. However, we observed that
$k$ is only meaningful for $k\leq\frac{d^{\prime}}{2}$, and it only improves
the infidelity for cases where $d\leq\frac{d^{\prime}}{2}$, which contradicts
the condition where $k>2d$.

Table 5: The exponent of infidelity scaling is examined for $N=2^{n}$ with
zero long-range budget, while varying $d$ and $d^{\prime}$ subject to the
constraint $d+d^{\prime}\leq n$, where $\lambda=2^{n-d}$ and
$\gamma=2^{n-d-d^{\prime}}$.

Table 6: The exponent of infidelity scaling is examined for $N=2^{n}$ with
$k=d^{\prime}/4$, while varying $d$ and $d^{\prime}$ subject to the constraint
$d+d^{\prime}\leq n$.

Table 7: The exponent of infidelity scaling is examined for $N=2^{n}$ with
$k=d^{\prime}/2$, while varying $d$ and $d^{\prime}$ subject to the constraint
$d+d^{\prime}\leq n$.

Table 8: The exponent of infidelity scaling is examined for $N=2^{n}$ with
$k=3d^{\prime}/4$, while varying $d$ and $d^{\prime}$ subject to the
constraint $d+d^{\prime}\leq n$.

Table 9: The exponent of infidelity scaling is examined for $N=2^{n}$ with
$k=d^{\prime}$ long-range budget.