# Error-Robust Quantum Signal Processing using Rydberg Atoms

Sina Zeytinoğlu  Department of Physics, Harvard University, Cambridge,
Massachusetts 02138, USA<EMAIL_ADDRESS>Sho Sugiura  Physics
and Informatics Laboratory, NTT Research, Inc., Sunnyvale, California, 94085,
USA  Laboratory for Nuclear Science, Massachusetts Institute of Technology,
Cambridge, 02139, MA, USA

###### Abstract

Rydberg atom arrays have recently emerged as one of the most promising
platforms for quantum simulation and quantum information processing. However,
as is the case for other experimental platforms, the longer-term success of
the Rydberg atom arrays in implementing quantum algorithms depends crucially
on their robustness to gate-induced errors. Here we show that, for an
idealized biased error model based on Rydberg atom dynamics, the
implementation of QSP protocols can be made error-robust, in the sense that
the asymptotic scaling of the gate-induced error probability is slower than
that of gate complexity. Moreover, using experimental parameters reported in
the literature, we show that QSP iterates made out of up to a hundred gates
can be implemented with constant error probability. To showcase our approach,
we provide a concrete blueprint to implement QSP-based near-optimal
Hamiltonian simulation on the Rydberg atom platform. Our protocol
substantially improves both the scaling and the overhead of gate-induced
errors in comparison to those protocols that implement a fourth-order product-
formula.

††preprint: APS/123-QED

##  I Introduction

Neutral atoms have become a leading experimental platform for accomplishing
useful quantum information processing tasks [1, 2, 3, 4, 5, 6, 7, 8, 9], as
well as emulating a variety of non-trivial Hamiltonian dynamics [10] and
correlated states [11, 12, 13, 14, 15]. In this success, the rich physics of
neutral atoms has played an essential role. On the one hand, the tightly-
confined hyperfine states of the atoms interact very weakly with the
environment [16], making these states ideal for storing quantum information
[17, 18, 19, 20]. On the other hand, the extended Rydberg states enable strong
interactions between the atoms [21], allowing fast and high-fidelity multi-
qubit gates to be realized [1, 3, 22]. Moreover, the advances in trapping and
manipulating alkali-earth atoms resulted in drastic improvements in the error
characteristics of the one- and two-qubit gates on the neutral atom platform
[23, 24, 25], making it an important contender to other leading platforms
based on trapped ions [26, 27] and circuit Quantum Electrodynamics [28, 29]. A
distinctive advantage of neutral atoms compared to the other platforms is that
they can be trapped close to one another, resulting in a scalable and
dynamically reconfigurable [16, 30] architecture. Similarly, the rich internal
structure of neutral atoms results in a uniquely versatile setup where both
the unitary and dissipative dynamics of the system can be tailored for the
specific quantum information task at hand [31, 32, 33, 25, 34].

Yet, as is the case with all current experimental platforms for realizing
quantum computation, Rydberg atoms cannot be controlled without inducing
significant unwanted dynamics. Consequently, the protocols implemented for
processing quantum information involve errors and the resulting computation is
unreliable [35, 36, 37]. While fault-tolerant error-corrected quantum
computation is in principle possible [38, 39, 40], the resources necessary for
reaching the error-correction threshold with the error rates achieved in
current experiments is daunting [41], despite promising developments [34]. A
direct way to reduce this resource cost is to increase the robustness of the
system against errors [41]. In particular, it is desirable to realize error-
robust implementations, where the error probability associated with the
implementation scales slower than the gate complexity of the corresponding
circuit. Whether the rich physics of the Rydberg atoms can be leveraged to
realize error-robust implementations is crucial for the success of the
platform.

Here we design error-robust implementations of a wide range of quantum
algorithms on the Rydberg atom platform. We achieve such generality by
considering implementations of different instantiations of Quantum Signal
Processing (QSP) [42, 43], a framework which unifies Hamiltonian simulation,
unstructured search as well as phase-estimation [44]. In particular, we
demonstrate that, assuming an idealized error model based on the physics of
Rydberg atoms, the central oracle for the QSP framework, called the block-
encoding unitary [45], can be implemented with constant error probability with
respect to the gate complexity of the corresponding circuit. Moreover, we show
that in the parameter regime that is routinely reported in the literature [12,
46], it is possible to realize a hundred-fold reduction of the error
probability.

Our approach consists of two steps. First, we determine the characteristics of
an error model which can reduce the error probability for a particular
compilation of the block-encoded unitary, given by the Linear Combinations of
Unitaries (LCU) [47]. Second, we design Rydberg atom gates that realize the
desired biased error model. Two main observations help us drastically reduce
the error probability associated with the Rydberg atom implementation of LCU,
which consists of a state preparation unitary and its inverse, in addition to
a sequence of controlled unitaries. First, we observe that the error
probability associated with the sequence of controlled unitary operations is
reduced drastically if each controlled unitary induces errors only when the
control condition is satisfied. Motivated by this observation, we then discuss
biased-error controlled unitaries that can be implemented on the Rydberg atom
platform. Consequently, given an ideal implementation of such biased-error
controlled unitaries, the error probability associated with the LCU protocol
scales only with that of the state preparation step. Motivated by this second
observation, we determine a special class of states that can be prepared
efficiently using the long-range dipolar interactions between the Rydberg
states. In particular, we design a Rydberg blockade gate that prepares any
state in the span of computational basis states with one non-zero element in
constant time and with constant error probability. We refer to these states as
One-Hot amplitude Encoding (OHE) states, and also design schemes for error-
robust generation of a more general class of states called $k$-Hot Encoding
($k$HE) states, which are in the span of computational basis states with $k$
non-zero elements. Importantly, the sparse encoding realized by the $k$HE
states can be utilized to achieve a scalable architecture. Specifically, when
we are interested in general linear combinations of $k$-local Pauli
operations, the $k$HE states allow us to use an ancillary register whose size
is proportional to that the register used for processing quantum information.
To the best of our knowledge, our results provide the first discussion of
error-robust implementations.

The paper is organized as follows. We provide a summary of the main results
and insights in Section II. In Section III, we introduce QSP based on a block-
encoding unitary [45] implemented with LCU [47]. We also show that the
structure of the LCU protocol can be leveraged to drastically reduce the
effects of errors with low error state preparation and an biased-error
controlled unitaries. In Section IV, we design Rydberg atom gates that have
the desired biased error characteristics. We then provide concrete error-
robust implementations of QSP protocols on the Rydberg atom platform in
Section V and show that the error-robustness is scalable in Section VI. We
showcase our approach in Section VII by error bounds for the implementation of
a QSP-based near-optimal Hamiltonian simulation algorithm and provide a
comparison to the numerically optimized fourth-order product formula [48]. We
conclude with a discussion of our results in Section VIII.

##  II Main Results and ideas

We consider error-robust implementations that arise from the interplay between
gate-induced error mechanisms and circuits compiling QSP protocols at multiple
layers of abstraction. At the highest level, we determine the characteristics
of an idealized error model sufficient for error-robust implementations of QSP
protocols. Then, we go down to the hardware level and design Rydberg atom
gates which, in a suitable parameter regime, exhibit the characteristics of
such an idealized error model. At the system level, we show that the error-
robust implementation is scalable, considering the finite range of
interactions between the Rydberg atoms. Finally, we highlight the potential of
our approach by calculating the error probability for an implementation of
QSP-based Hamiltonian simulation. In this section, we provide an informal
discussion of the main insights and results pertaining to each level.

###  II.1 The conditions for the error-robust implementation of LCU-based QSP

A great variety of quantum protocols are described as functional transforms
$f(A)$ of high-dimensional linear operators $A$. The well-known examples
include Hamiltonian simulation, where $f(H)=e^{-iHt}$ [49] and HHL algorithm
for solving linear equations, where $f(A)=A^{+}$ with $+$ denoting the Moore-
Penrose pseudo-inverse [50] 111see Ref. [43, 44] for further examples. The
naive expectation is that the compilation of such algorithms is simple when
$f(\cdot)$ and the input $A$ have simple classical descriptions.

Quantum Signal Processing (QSP) is an iterative compilation method that
formally fulfills this naive expectation when $f(\cdot)$ is approximated by a
low-order polynomial, and $A$ is sparse or approximated by a linear
combination of a small number of Pauli strings 222 In contrast, compiling
time-dependent Hamiltonian simulation is difficult because then multiple
functional transformations $f_{t}(\cdot)$ and their inputs $A_{t}$ need to be
explicitly specified. . Each iteration step of the QSP protocol has two
components, called the block-encoding walk operator $W_{A}$ [45], which
encodes the linear operator $A$ (i.e., there exists a projector $\Pi$ such
that $\Pi W_{A}\Pi=A$), and the processing unitary [42] which encodes a single
rotation angle $\phi_{i}$. For a QSP protocol that terminates after $l$
iterations, the list of angles $\\{\phi_{i}\\}$ determines the $l^{\rm
th}$-order polynomial approximation of the functional transform $f(\cdot)$.

The QSP protocols can be simplified drastically when the controlled version of
$W_{A}$ (C$W_{A}$) is available. Then, the processing unitary is a single-
qubit rotation of the control qubit. This is an important simplification from
the perspective of error-robust implementation since the single-qubit rotation
only contributes a constant to the error probability per iteration.
Consequently, the scaling of the error probability associated with each
iteration step of the QSP protocol is the same as the scaling of errors for
C$W_{A}$. In other words, whether we can achieve an error-robust
implementation of the QSP protocol hinges on an error-robust implementation of
C$W_{A}$.

We find that the Linear Combination of Unitaries (LCU) method is an especially
well-suited compilation method for an error-robust implementation of $W_{A}$.
In this method, $A$ is decomposed as a linear combination of $N$ unitary Pauli
strings $\\{P_{i}\\}$, with the associated coefficients $\\{\alpha_{i}\\}$. In
the LCU protocol, the data consisting of $\\{\alpha_{i}\\}$ and $\\{P_{i}\\}$
are encoded by two separate unitaries $V$ and $\bar{U}$, respectively. The
state preparation unitary $V$ acts on an ancillary register of size $n_{a}$
($V\left|0\right\rangle^{\otimes
n_{a}}=\sum_{i}\alpha_{i}\left|x_{i}\right\rangle$), and amplitude-encodes
coefficients $\\{\alpha_{i}\\}$. On the other hand, $\bar{U}$ takes the
different components $\\{\left|x_{i}\right\rangle\\}$ of the ancillary state
as control conditions for applying $\\{P_{i}\\}$ to the system register.
Formally, $\bar{U}$ can be expanded as
$\bar{U}\equiv\prod_{i}^{N}C_{x_{i}}P_{i}$.

We show that the following two conditions are sufficient for an error-robust
implementation of $W_{A}\equiv(2\Pi-\mathbf{I})V^{\dagger}\bar{U}V$ and its
controlled version:

  * Condition 1: For controlled unitaries, error probability is negligible when the control condition is not satisfied

  * Condition 2: Controlled version of One-Hot Encoding state-preparation takes constant time/error.

Here, we define a $k$-Hot Encoding state as any superposition of bitstrings
with $k$ entries in the excited state (e.g., $\left|1\right\rangle$).

We show that Condition 1 is sufficient for achieving a dramatically error-
robust implementation of $\bar{U}$. On the other hand, through Condition 2, we
can design an ancillary register that facilitates the error-robust
implementation of $W_{A}$. We also show that the controlled version of $W_{A}$
can be implemented without changing the scaling of error probability.
Designing a Rydberg atom implementation of C$W_{A}$ which satisfies these two
conditions is the goal of our paper.

###  II.2 Designing biased-error Rydberg atom gates

In order to satisfy Condition 1, we design single-qubit-controlled unitary
gates which induce errors only when the control condition is satisfied. Such a
single-qubit-controlled unitary was proposed in Ref. [53]. The gate uses the
Rydberg-blockade effect in combination with Electromagnetically Induced
Transparency (EIT) [54, 55], and leverages the rich internal structure of the
Rydberg atoms. While the gate was proposed more than a decade ago, to our best
knowledge, our work is the first to emphasize its biased error characteristics
and use it to achieve error-robust implementations of quantum algorithms.

We demonstrate that the single-qubit controlled gate introduced in Ref. [53]
drastically reduces the probability of errors in both the control and target
registers when the control condition is not satisfied (i.e., when the state
$\left|\psi\right\rangle_{c}$ of the control atom has vanishing overlap with
the control condition, say $\left|0\right\rangle_{c}$,). Similar to other
multi-qubit gates that involve the Rydberg-blockade mechanism [3, 22], the
EIT-based gate protocol starts by exciting the control atom to the Rydberg
state if it satisfies the control condition. During this step, the control
atom in state $\left|1\right\rangle_{c}$ evolves trivially and does not
acquire any gate-induced errors. As a result, the error probability due to the
control atom is negligible when the control condition is not satisfied.

On the other hand, EIT mechanism ensures that the error probability due to the
dynamics of the target atoms can be drastically reduced when the control
condition is not satisfied. In particular, when the control atom is not
excited to the Rydberg state, the EIT mechanism ensures that the laser field
that couples the hyperfine states to shorter-lived excited states is not
absorbed (hence the name “transparency”). Consequently, when the control
condition is not satisfied, the evolution of the target atoms is nearly
trivial. In contrast, when the control condition is satisfied, the Rydberg
excitation of the control atom disturbs the EIT mechanism, and the target
qubit goes under a non-trivial and error-inducing evolution. As a result, EIT
effect enables the Rydberg blockade gates satisfy Condition 1.

There are two comments in order. First, in reality, the error can never be
perfectly biased with respect to the control condition. The ratio of the error
probabilities conditioned on the two control conditions is determined by the
ratio of two laser intensities in the EIT configuration (Fig. 2 b).
Specifically, in order to reduce the error probability by a factor of $N$, we
need to increase the intensity of a laser in by $O(N)$. In other words, the
robustness to errors comes at the expense of increased classical resource
requirements. Such a trade-off is also present for other controlled unitaries
[3, 22, 46]. However, the EIT-based gate has two characteristics that are
advantageous: (i) the EIT-based gate provides a quadratic advantage in laser
intensity compared to conventional gate implementations, where an $N$-fold
suppression of errors require an $O(N^{2})$ fold increase of the laser
intensity, (ii) the EIT-based gate is advantageous even when the laser drive
amplitude is much larger than the dipolar interaction strength. Second,
implementing a unitary that satisfies Condition 1 for general multi-qubit
control conditions is not possible by selectively driving atoms as described
above. Intuitively, given a multi-atom ancillary register, the local
interactions between the laser field and the atoms cannot be configured such
that only a single initial state goes through a nontrivial evolution. We
address this issue by utilizing a tensor product of $k$ One-Hot Encoding
address states. Whether the resulting $k$-Hot encoding state satisfies a
$k$-bit control condition can be checked using $k$ single-qubit controlled
Pauli operations. This step induces a trivial evolution on all but $k$ control
qubits. As a result, a controlled-Pauli operation conditioned on such a
$k-$Hot Encoding address state satisfies Condition 1. The non-negligible error
probability when the control condition is satisfied is only $O(k)$.

Finally, we use the previously reported values of the Rabi frequencies and
decay rates to calculate the error probability expected for 100 single-qubit
controlled unitaries conditioned on a One-Hot Encoding state to be less than 5
percent. As a result, the combination of our techniques with error-correction
promises a significant advance in the realization of fault-tolerant quantum
computation [34].

###  II.3 Designing error-robust ancillary control register

We satisfy Conditions 2 for the error-robust implementation of $W_{A}$ using a
novel multi-qubit Rydberg blockage gate, referred to as the One-Hot amplitude-
encoding gate $V_{\rm OHE}$.

We show that a tensor product of $k$ One-Hot Encoding address states can be
prepared using $O(kn_{\rm site})$ EIT-based single-qubit controlled $V_{\rm
OHE}$ (denoted C$V_{\rm OHE}$) gates, with a total error probability of
$O(k)$. Moreover, the reflection unitary required for the walk operator
$W_{A}$ can be implemented in an error-robust way by simply changing the
phases of some of the drive lasers implementing $V_{k{\rm OHE}}$. Lastly, the
tensor product of $k$ One-Hot Encoding states allows us to encode $N$
amplitudes in a small ancillary register of size $O(kN^{1/k})$. The size of
the ancillary register does not satisfy the theoretical lower bound
$\Omega(\log{N})$. However, for a system register of $n_{\rm site}$ atoms, as
many as $O(n_{\rm site}^{k})$ control conditions can be stored in an ancillary
register of size $O(kn_{\rm site})$.

The implementation of C$V_{\rm OHE}$ gates fully utilize the rich physics of
the Rydberg atoms, including the long-range dipolar interactions, availability
of even and odd parity Rydberg states, as well as EIT. Our results thus
highlight the importance of concrete physical processes for realizing error-
robust implementations. On the other hand, the scaling results above assume
that the range of dipolar interactions is larger than the geometric size of
the system and that one laser amplitude in the EIT configuration can be
increased as $O(\sqrt{N})$. To codify the rules for calculating the error
probability under these assumptions, we define the Error Bounded Gate Count
(EBGC). Our main result is that when EBGC is valid and $N=O(n_{\rm
site}^{k})$, the LCU-based walk operator can be implemented with constant
error and $O(kn_{\rm site})$ ancillae.

###  II.4 Scalable implementation and Hamiltonian simulation

The designs discussed so far assumed that the interaction range of the dipolar
interactions between the Rydberg atoms is infinite. However, in reality, the
dipolar interactions are effective only up to a fixed length scale, the so-
called Rydberg blockade radius. When the finite range of the Rydberg blockade
effect is taken into account, the scaling of the error probability with
increasing system size depends on the number of subsystems $n_{\rm sub}$ whose
geometric size is smaller than the Rydberg blockade volume. We show that as
long as the EBGC is valid, it is possible to implement each iteration of the
QSP protocol with error probability that scales with $O(n_{\rm sub})$. Because
the EBGC scaling is independent of the number of gates acting on each
subsystem, the resulting implementation is error-robust.

Finally, we showcase our approach and compare the error-robustness of the
Rydberg implementation of the QSP-based Hamiltonian simulation algorithm to
that of a simulation algorithm based on the fourth-order product formula. For
a fair comparison, we implement the product formula algorithm using the
biased-error Rydberg atom gate-set designed for QSP protocols. Hence,
implementations of the two algorithms enjoy increased robustness to errors.
Still, when EBGC is valid, the scaling of error probability is the same as the
optimal gate complexity, and the associated overhead is reduced with respect
to the fourth-order product formula by more than an order of magnitude.

##  III Block encoding by LCU

Here we discuss the method of LCU [47], which offers a generic and
constructive strategy to implement block-encoding unitaries for linear
combinations of multi-qubit Pauli operators. In order to assess the time and
space complexities of the LCU method, we introduce the scaling variable $N$
which denotes the number of Pauli operators that constitute the target
operator $A$. In particular, we decompose $A$ as

$\displaystyle A=\sum_{i=1}^{N}|\alpha_{i}|^{2}P_{i},,$ (1)

where we set $\sum_{i=1}^{N}|\alpha_{i}|^{2}=1$. In the context of Hamiltonian
simulation, the number of coefficients required to implement a $k$-local
Hamiltonian on a system consisting of $n_{\rm site}$ qubits is $N=O(n_{\rm
site}^{k})$, while for geometrically local Hamiltonians where the number of
atoms within an interaction range is $N_{I}$, we have $N=O(N_{I}^{k}n_{\rm
site})$. It is important to note that in this decomposition we assume that the
coefficients $\\{\alpha_{i}\\}$ are given and cannot be further compressed
into a smaller set.

In the following, we first review the LCU method formally, and then discuss
how its structure can be interpreted as a in a circuit that loads the
classical data describing $A$ into a quantum processor.

###  III.1 Algorithm:

The LCU decomposition of the block-encoding unitary in Eq. (6) consists of
three unitaries [47].

$\displaystyle U=V^{\dagger}\bar{U}V.$ (2)

The block-encoding unitary acts on $n_{a}$ ancilla qubits and $n_{\rm site}$
system qubits. The unitary $V$ rotates the $n_{a}$-qubit initial ancilla state
$\left|0\right\rangle^{\otimes n_{a}}$ to a linear combination of the
computational basis states $\\{\left|x_{i}\right\rangle\\}$ which encode the
pre-computed classical coefficients $\alpha_{i}$

$\displaystyle\left|\Psi\right\rangle_{a}\equiv V\left|0\right\rangle^{\otimes
n_{a}}=\sum_{i=1}^{N}\alpha_{i}\left|x_{i}\right\rangle.$ (3)

The operator $V$ can be understood as an amplitude-encoding state-preparation
unitary [56]. We note that the number of ancilla qubits
$n_{a}>\lceil\log{N}\rceil$ depends on the choice of the basis
$\\{\left|x_{i}\right\rangle\\}$.

Then, we apply the following conditional unitary operation

$\displaystyle\bar{U}\equiv\sum^{N}_{i}\left|x_{i}\right\rangle\langle
x_{i}|\otimes P_{i}.$ (4)

The action of $\bar{U}$ entangles each Pauli operator with an orthogonal
address state of the ancilla register

$\displaystyle\sum_{i=1}^{N}\alpha_{i}\left|x_{i}\right\rangle\otimes\left|\Psi_{\rm
sys}\right\rangle\xrightarrow{\bar{U}}\sum_{i=1}^{N}\left|x_{i}\right\rangle\otimes\left(\alpha_{i}P_{i}\right)\left|\Psi_{\rm
sys}\right\rangle.$ (5)

Finally, a block-encoding of a superposition of multi-qubit Paulis
$\\{P_{i}\\}$ is obtained by rotating the address space by an application of
$V^{\dagger}$

$\displaystyle
V^{-1}\bar{U}\left|\Psi\right\rangle_{a}\otimes\left|\Psi_{sys}\right\rangle=\sum_{i}^{N}|\alpha_{i}|^{2}\left|0\right\rangle^{\otimes
n_{a}}\otimes
P_{i}\left|\Psi_{sys}\right\rangle+\left|\Psi^{\perp}\right\rangle$
$\displaystyle=\left|0\right\rangle^{\otimes
n_{a}}\otimes\left[A\left|\Psi_{sys}\right\rangle\right]+\left|\Psi^{\perp}\right\rangle$
(6)

where the unnormalized wavevector $\left|\Psi^{\perp}\right\rangle$ satisfies
$\left(\left(\left|0\right\rangle\left\langle 0\right|\right)^{\otimes
n_{a}}\otimes\mathbf{1}\right)\left|\Psi^{\perp}\right\rangle\equiv\Pi_{0}\left|\Psi^{\perp}\right\rangle=0$.
Consequently, $\Pi_{0}U\Pi_{0}=A$, and the block-encoding unitary has the form

$\displaystyle U\dot{=}\left(\begin{array}[]{cc}A&*\\\ &*\end{array}\right).$
(9)

We remind the reader that the unitarity of $U$ implies that the Hermitian
operator block-encoded in this way satisfies $||A||\leq 1$. Moreover, the
block-encoding unitary implemented through LCU is Hermitian (i.e.,
$U^{\dagger}=U$).

####  III.1.1 Freedom to design the address register

As we noted before, the ancillary Hilbert space is not constrained in the
above discussion. While the original discussion of block-encoding unitary sets
$n_{a}=\lceil\log{(N)}\rceil$ [45], we refrain from this choice. Indeed, we
show that by designing the address register (i.e., the bitstrings
$\\{x_{i}\\}$) is useful for constructing error-robust implementations of the
block-encoding unitary.

Indeed, there are infinitely many ancillary states which result in a block-
encoding of the same signal operator. To see this, divide the ancilla register
into two parts $a_{1}$ and $a_{2}$ consisting of $n_{a_{1}}$ and $n_{a_{2}}$
ancillary qubits, respectively. Then we can construct two state-preparation
unitaries $V_{a}$ and $V_{p}$ that are equivalent from the perspective of LCU-
based block-encoding, if $\bar{U}$ acts on only the system and second ancilla
register $a_{2}$:

$\displaystyle\left|0\right\rangle^{\otimes
n_{a_{1}}}\left|0\right\rangle^{\otimes n_{a_{2}}}\xrightarrow{V_{\rm
p}}\left|0\right\rangle^{\otimes
n_{a_{1}}}\sum_{i}^{N}\alpha_{i}\left|x_{i}\right\rangle$
$\displaystyle\left|0\right\rangle^{\otimes
n_{a_{1}}}\left|0\right\rangle^{\otimes n_{a_{2}}}\xrightarrow{V_{\rm
a}}\sum_{i}^{N}\alpha_{i}\left|\Psi_{i}\right\rangle\left|x_{i}\right\rangle,$

where the states $\\{\left|\Psi_{i}\right\rangle\\}$ can be any state of the
Hilbert space of $n_{a_{1}}\geq n_{a_{2}}$ qubits. This property will be
important in our discussion of the scalable and error-robust implementation of
the state-preparation unitary in Section VI.

###  III.2 Processing of block encoded matrices by QSP

Next, we review QSP framework introduced in Refs. [42, 57]. From the
perspective of compilation of quantum subroutines, QSP can be understood as a
efficient way of manipulating a block-encoded operator $A$ to realize the
block-encoding of a polynomial function $P(A)$. The polynomial $P(A)$ is
defined through an ordered list of $n$ angles $\\{\phi_{i}\\}$, whose size
determines the order of the polynomial as well as the query complexity of QSP.
Here, we only give a brief discussion of the QSP protocol such that the
requirements for its error-robust implementation are evident. For an
introduction to QSP see Appendix A.

The QSP protocols proceed by iterating between a controlled oracular unitary
C$W$ derived from the block-encoding unitary $U$ in Eq. (2), and a signal
processing step, which consists of single qubit rotations on the “exit”
ancilla that controls $W$ (see Fig. 1). Formally, the QSP protocol has the
form

$\displaystyle\mathcal{U}=\left[\prod_{i=1}^{n}e^{i\phi_{i}\sigma_{x}^{(e)}}\mathrm{C}_{e}W\right]e^{i\phi_{0}\sigma_{z}^{(e)}},$
(10)

where $\sigma_{x}^{(e)}$ acts on the exit ancilla. The phases associated with
the single qubit rotations in the processing step define the polynomial
function $P(A)$ that is block-encoded by the resulting unitary transformation.
In the case of a qubitized block-encoding unitary $U=U^{\dagger}$ oracular
unitary $W$ is simply expressed as

$\displaystyle W=(2\Pi_{0}-\mathbf{I})U,$ (11)

where $\Pi_{0}$ is the projector to the all-zeros address state.

Figure 1: The circuit diagrams for the protocols discussed in this work. a)
The multi-qubit controlled Pauli operation $C_{x_{i}}P_{i}$ where the conrol
register is ancillary and the target register is the system which is
controlled. b) The decomposition of the QSP iterate $W$ (notice the factor of
$i$ difference with the definition in Ref. [42]), consisting of a multi-qubit
controlled phase gate where the target register is a single “phase” ancilla
and the LCU-based block-encoding protocol. c) The circuit decomposition of the
QSP method for producing polynomials of block-encoded matrices, which consists
of controlled versions of the walk operator $W$ conditioned on the state of an
additional “exit ancilla”. In this work we show how to realize error-robust
implementations of these circuits on the Rydberg atom platform.

###  III.3 Requirements for an error-robust implementation of the QSP
protocols

The QSP protocols can be thought of as a compilation strategy for quantum
algorithms. The structure of the LCU-based QSP protocols allows one to reduce
the adverse effects of errors when (i) the required controlled unitaries are
implemented in a way that the errors are induced only when the control
condition is satisfied, and (ii) the state preparation unitary $V$ can be
implemented with constant error scaling.

To see how these requirements result in a drastic reduction of errors in the
implementation of the QSP oracle $W$, first consider the two components of the
QSP protocols that use controlled gates extensively: the unitary $\bar{U}$ in
Eq. (2) and the reflection operator $2\Pi_{0}-\mathbf{I}$. It is crucial to
notice that when each of the controlled Pauli gates in Eq. (4) are implemented
in a way that errors are induced only when the address register is in the
desired state, then the total error probability associated with $\bar{U}$ is
constant with respect to $N$ and scales linearly with the highest weight
$k=O(n_{\rm site})$ of the Pauli strings $\\{P_{i}\\}$. A similar
implementation of the controlled unitary implementing the reflection operator
$2\Pi_{0}-\mathbf{I}$ result in a constant error per reflection gate. As a
result, the oracular unitary $W$ which involves only $k$-local Paulis can be
implemented with constant error if the state preparation unitary $V$ can be
implemented with constant error.

An implementation of each QSP iterate which has only a constant error
probability entails that the error probability of implementations of QSP
protocols has the same scaling as that of the query complexity, which is
optimal query with respect to the approximation error when $P(A)$ approximates
a smooth function [42]. In summary, the (i) biased-error controlled unitaries
and (ii) constant error state preparation unitary are sufficient for
implementing QSP protocols with near optimal scaling of the error probability
with respect to the approximation error. In the next section, we design the
ancillary address register for the QSP protocol in a way that allows the above
requirements to be satisfied for the implementations of $\bar{U}$,
$2\Pi_{0}-\mathbf{I}$, and $V$ on the Rydberg atom platform.

##  IV Rydberg atom Gates

In this section, we introduce the building blocks for error-robust
implementions of QSP protocols on the Rydberg atom platform. We start the
section with an introductory discussion of what constitutes an error-bounded
gates, and how to calculate the error-bounded gate count (EBGC) of a
particular protocol implemented using idealized versions of the proposed
Rydberg gates. Crucially, EBGC does not correspond to the gate complexity of
the circuit decomposition of the protocols in terms of the Rydberg gates, as
it takes into account the information of the input states. Indeed, that the
error probability does not have to scale as the gate complexity is what makes
error-robust implementations possible.

We briefly review the relevant level diagrams and single-qubit gates in
Section IV.2. In Sections IV.3 and IV.4, we introduce two multi-qubit gates
utilizing the Rydberg blockade mechanism. Each multi-qubit gate serves a
different function in the error-robust implementation of the LCU-based block-
encoding unitary. The first multi-qubit gate, which we name “One-Hot Encoding”
(OHE) gate, (see Section IV.3) allows us to load the classically-stored
coefficient data $\\{\alpha_{i}\\}$ efficiently to orthogonal ancillary
address states. The OHE gate is the building block of the state preparation
unitary $V$ of the LCU protocol [see Eq. (2) ]. Surprisingly, when the Rydberg
blockade radius is infinite, the gate takes constant time and EBGC. In Section
IV.4, we introduce a multi-qubit controlled Pauli operation, which can be
expressed formally as,

$\displaystyle C_{x_{i}}P_{i}\equiv\left|x_{i}\right\rangle\left\langle
x_{i}\right|\otimes
P_{i}+\left[\mathbf{1}-\left|x_{i}\right\rangle\left\langle
x_{i}\right|\right]\otimes\mathbf{1},$ (12)

where the bitstring $x_{i}$ will be referred to as the address or the control
condition. Intuitively, the unitaries $\\{C_{x_{i}}P_{i}\\}$ are the building
blocks of $\bar{U}$ in Eq. (4) and they “load” the classical data describing
the Pauli strings $\\{P_{i}\\}$ in the decomposition of the block-encoded
operator $A$ (see Section III) into quantum mechanical address states
$|x_{i}\rangle$.

The results of this section sets the stage for a concrete blueprint of an
efficient and scalable implementation of the QSP-based optimal Hamiltonian
simulation of Refs. [57, 58], including the geometric arrangement Rydberg
atoms and pulse sequences.

###  IV.1 Error-bounded gate counts (EGBCs) and the subadditivity of errors

In the following, we define an error-bounded gate count (EBGC) to quantify the
way that the error probability grows as a function of scaling variables
$n_{\rm site}$ and $N$. Conventionally, the gate counts are equated to the
size of a quantum circuit. Here, the relationship between the circuit size and
the error probability is established by via the subadditivity property of
errors [59], which gives an upper bound for the spread of the errors
introduced with each additional gate. However, the subadditivity bound may be
extremely loose for a given protocol as it completely disregards both the
structure of input states as well as the structure of the errors specific to
an experimental implementation, which may be biased to introduce increase the
error probability differently for different input states. Here, on the other
hand, we count gates in a way that is dependent on their input states, with
the aim of capturing when biased error model can be leveraged to achieve an
error probability that scales slower than the gate complexity as a function of
$N$.

The gate counting method, which we call the Error-Bounded Gate Count (EBGC) is
based on an idealization of the Rydberg atom gates proposed in this work. It
considers only the fundamental sources of error, given by non-adiabatic
contributions and radiative decay processes, and assume that the error rates
of each source is the same. In principle, the unwanted transitions due to
blackbody radiation can also be included, given that we use optical pumping
methods to convert such errors to dephasing errors [34]. Our method assumes
that the errors due to laser phase and amplitude fluctuations, as well as
those due to the finite temperature atomic motion and the associated Doppler
shift can all be eliminated [60, 61]. The finite lifetime of the hyperfine
states is neglected given the orders of magnitude separation between this
lifetime and the time it takes to implement the proposed gates [62]. We
emphasize that although our error-bounded gate count is specific to the
Rydberg atom platform, the strategy to design control protocols that take
advantage of the biases in the relevant error model can be applied to any
experimental platform.

####  IV.1.1 Subadditivity of errors

To put the discussion on firm footing, we sketch the proof of subadditivity of
errors, and underline its shortcomings. Consider a circuit $C$ that can be
described by an ordered product of $T$ unitaries $\\{W_{i}\\}$ [not to be
confused with the walk operator $W$ in (11)] $C=\prod_{i}^{T}W_{i}$, and an
imperfect implementation $\tilde{C}$ of $C$, where each $W_{i}$ is replaced by
$\tilde{W}_{i}$. We assume $\tilde{W}_{i}$ to be unitary for simplicity. Now,
given the same input state $\left|\phi_{0}\right\rangle$, we are interested in
the difference between the outputs $\left|\phi_{T}\right\rangle$ and
$\left|\tilde{\phi}_{T}\right\rangle$ of $C$ and $\tilde{C}$, respectively.
Define

$\displaystyle\left|\phi_{1}\right\rangle$ $\displaystyle\equiv
W_{1}\left|\phi_{0}\right\rangle$ (13)
$\displaystyle\left|\tilde{\phi}_{1}\right\rangle$
$\displaystyle=\tilde{W}_{1}\left|\phi_{0}\right\rangle=\frac{1}{\mathcal{N}}\left(\left|\phi_{1}\right\rangle+\left|E_{1}\right\rangle\right),$
(14)

where we define the error vector $\left|E_{1}\right\rangle$ and the
normalization $\mathcal{N}$. The size of the error vector satisfies the
following inequality

$\displaystyle\left|\left|\frac{\left|E_{1}\right\rangle}{\mathcal{N}}\right|\right|=\left|\left|\left(\tilde{W}_{1}-W_{1}\right)\left|\phi_{0}\right\rangle\right|\right|\leq\left|\left|\left(\tilde{W}_{1}-W_{1}\right)\right|\right|_{\rm
sup}\equiv\epsilon_{1},$ (15)

where the error $\epsilon_{1}$ associated with $\tilde{W}_{1}$ is defined via
the spectral norm, which, crucially, is completely oblivious to the input
vector $\left|\phi_{0}\right\rangle$. The worst case scenario is that all
errors from each $W_{i}$ constructively interfere. Since $\\{W_{i}\\}$ are all
unitary, the errors introduced by the $i^{\rm th}$ step is not amplified for
any later step, and we obtain the inequality

$\displaystyle\left|\left|\left(C-\tilde{C}\right)\left|\Phi_{0}\right\rangle\right|\right|\leq\sum_{i}\left|\left|\tilde{W}_{i}-W_{i}\right|\right|_{\rm
sup}=\sum_{i}\epsilon_{i}.$ (16)

As a result, decomposing each $W_{i}$ using a universal gate-set with known
error rates, we can relate the size of the circuit to the total error of the
circuit. However, we emphasize again that in the above discussion the
definition of errors $\epsilon_{i}$ in Eq. (16) is independent of the
structure of the input state. To understand the shortcomings of this
definition, notice that in the context of the LCU protocol, the omission of
the particularities of $\left|\phi_{0}\right\rangle$ corresponds to forgetting
about the fact that the ancillary registers are initiated in the
$\left|0\right\rangle^{\otimes n_{a}}$ state and that we know how this initial
state transforms at each step of our circuit. Our goal, on the other hand, is
to use our knowledge of the trajectory of ancilla qubits to design error
robust protocols. Hence, if we want to verify if any of our proposed
implementations are error-robust, we need to make sure that we know how to
calculate a bound for error probability given the knowledge of the states of
the ancillary address register.

EBGC is the tool that we develop to this end. In particular, we use the error-
bounded gate count to take into account our knowledge of the biases of the
error model and the knowledge of the input state at each step. Not
surprisingly, we show that for most of our protocols, we obtain a better
scaling of the number of gates than as indicated by Eq. (16). In the
following, we introduce the rules for calculating the gate count for single-
qubit rotations and controlled unitaries in the form $C_{x_{i}}U_{1}\cdots
U_{k}$ in an ad-hoc manner. We support the models and assumptions that go into
the EBGC with the physical error mechanisms relevant to the Rydberg atom
system in Sections IV.2, IV.3, IV.4, and IV.4.2.

####  IV.1.2 Error-bounded gate count (EBGC)

We distinguish three factors which determine EBGC. These factors constitute
the additional knowledge which makes error-robust implementations possible:
(i) the rotation angle of single-qubit rotations (ii) the dimensionality of
the local Hilbert space of each Rydberg atom, and (iii) the dependence of the
errors introduced during controlled unitary operations on the state of the
control register. In the following, EBGC is normalized such that the Rydberg
atom implementation of a CNOT gate requires at most 1 error-bounded gate.

As for the first factor, we observe that our protocols often use a continuous
family of gates, such as single-qubit rotations by an arbitrary angle. In our
error model, we assume that the error rate increases monotonically with the
rotation angle. For example, given the single qubit rotation

$\displaystyle
R_{\theta}\left|0\right\rangle\equiv\cos{(\theta)}\left|0\right\rangle+\sin{(\theta)}\left|1\right\rangle,$
(17)

the error associated with implementation of $R_{\theta}$ on the Rydberg atom
platform is proportional to $|\theta/\pi|$. More precisely, we assign an EBGC
of $\left|\frac{\theta}{3\pi}\right|$ to $R_{\theta}$. Notice that this rule
associates $1/3$ error-bounded gates (in units of the error probability of a
CNOT gate) for each single qubit Pauli operator.

Second, the protocols discussed in the rest of the paper take advantage of the
fact that each Rydberg atom has more than two-states. A local Hilbert space of
more than two-dimensions entails that the experimentalist can choose laser
pulses which only acts on a two-dimensional subspace of the local Hilbert
space. As a result, the errors are introduced only when the Rydberg atom is in
a state with a non-zero overlap with the subspace influenced by the laser
pulse. Consider as an example a laser pulse sequence implementing the unitary
that transfers an atom from the logical hyperfine state $\left|1\right\rangle$
to the Rydberg state $\left|R\right\rangle$ [the level diagram associated with
each atom is discussed in more detail in Section IV.2.2]. Given the initial
state $\sqrt{1-|\alpha|^{2}}\left|0\right\rangle+\alpha\left|1\right\rangle$,
the transfer has an EBGC of $1/3|\alpha|^{2}$ error-bounded gates.

We also use a generalization of this rule to count the number of gates
associated with our multi-qubit One-Hot amplitude-encoding gate $V_{\rm OHE}$
in Section IV.3 and its controlled counterpart in Section IV.4.2. The most
important property of these gates is that they utilize the strong Rydberg
blockade effect in order to constraint the dynamics of, say, $N$ atoms onto a
two-dimensional qubit-like subspace, and the EBGC calculates the gate count
similarly to that of a single-qubit gate. As a result, the EBGC of $V_{\rm
OHE}$ is independent of the number of qubits involved, and it is equivalent to
that of a single CNOT gate.

Lastly, our gate count makes sure that the cost of controlled unitaries
$C_{x_{i}}P_{i}$ are assessed in accordance with a physical error model in the
limit that dipolar interactions set the highest energy scale. The EBGC sums up
the error probability due to errors in the target and control registers
separately. While the errors in the control register occur while checking
whether a control condition $x_{i}$ is satisfied, the errors in the target
register are assumed to be introduced only when the state of the control
(address) register satisfies the control condition. Hence, the contributions
to the total error probability should be weighed by the probability that the
control condition is satisfied. In Section IV.4, we discuss the concrete
experimental protocol which can realize such a biased error model, assuming
that the system is in a certain parameter regime.

As a concrete example, consider a single CNOT gate, where the control register
is initially in
$\left|\psi_{c}\right\rangle=\sqrt{1-|\alpha|^{2}}\left|0_{c}\right\rangle+\alpha\left|1_{c}\right\rangle$.
We assume that the contribution to the error probability from the control
register during the CNOT gate operation scales with

$\displaystyle\left\langle\psi_{c}\right|\hat{n}_{1}^{(c)}\left|\psi_{c}\right\rangle\equiv\left\langle\psi_{c}\right|1_{c}\rangle\langle
1_{c}\left|\psi_{c}\right\rangle=|\left\langle
1_{c}\right|\psi_{c}\rangle|^{2}.$ (18)

Moreover, if the input state of the target register is not known, the errors
introduced to the target register is proportional to the probability that the
control condition is satisfied (i.e.,
$\left\langle\psi_{c}\right|\hat{n}_{1}^{(c)}\left|\psi_{c}\right\rangle$).
Hence, in this case, the EBGC count assigns an error probability of
$|\alpha|^{2}$ to the CNOT gate implemented on the Rydberg platform, given
that the control atom is in state $\left|\psi_{c}\right\rangle$.

The knowledge of the target register’s state can be also be used to reduce the
EBGC (see Section IV). In particular, implementing the controlled unitary
which exits the target atom from $\left|1\right\rangle$ to
$\left|R\right\rangle$ conditioned on the state of a control atom. Given the
target input state
$\left|\psi_{t}\right\rangle=\sqrt{1-|\beta|^{2}}\left|0\right\rangle+\beta\left|1\right\rangle$,
results in an EBGC of $\frac{1}{3}|\alpha|^{2}(2+|\beta|^{2})$. In the
following, we denote this gate as $CX^{(R)}$. Notice that this gate count is
identical to that of the CNOT gate when $|\beta|^{2}=|\alpha|^{2}=1$, when the
error probability of the Rydberg atom implementation of the CNOT gate is
maximized.

Extending EBGC for single-control multi-target unitaries of the form
$CU_{1}\cdots U_{k}\equiv CP_{i}$ is straightforward. In this case, assuming
no knowledge of the target register, the error introduced into the target
register is proportional to the $k$ times the probability that the control
condition is satisfied. As before, the EBGCs are subject to modification when
the state of the target register is known.

The gate counts are summarized in Table 1, for a given input state
$\left|\psi_{c}\right\rangle$ of the control register and the control
condition $\left|x_{0}\right\rangle$. The unit of the gate count is determined
by the maximum error cost of a CNOT gate, which is 3 single-qubit gates in our
gate count [3]. We evaluate the depth to implement each gate using the time
unit $t_{\rm{step}}$, given by the time it takes to achieve a complete
transfer of the $\left|0\right\rangle$ state to $\left|1\right\rangle$ state.
In Section IV.4.1, we discuss the parameter regime that the EBGC is valid.

| $R_{\theta}$ | $V_{\rm OHE}$ | $CV_{\rm OHE}$ | $CU_{1}\cdots U_{k}$
---|---|---|---|---
gates | $\left|\theta/(3\pi)\right|$ | 1 | 4/3 $|\left\langle 1\right|\psi_{c}\rangle|^{2}$ | $(2+k)/3|\left\langle 1\right|\psi_{c}\rangle|^{2}$
${\rm depth}$ | $\left|\theta/\pi\right|$ | 2 | 4 | 3
Table 1: The EBGCs for the native gates of the Rydberg system. All gate countd
are normalized by the maximum error probability of a single CNOT gate. The
input state of the control register is $\left|\psi_{c}\right\rangle$, and
$\theta$ is the single-qubit rotation angle. The error model takes into
account only errors caused by the radiative decay rate of the Rydberg states
and the non-adiabatic errors due to imperfect blockade. Most importantly, the
cost of single-qubit-controlled unitary depends on the probability that the
control condition is satisfied.

Our gate count not only assesses an experimental scenario, but also guides us
to design algorithms with lower EBGC by taking full advantage of the structure
of the errors relevant for that experimental scenario. More specifically, EBGC
allows us to demonstrate that the structure of the errors relevant for the
proposed Rydberg atom gates can leveraged to design error-robust
implementations of quantum algorithms.

###  IV.2 Rydberg Interactions, Level Diagrams and Single Qubit Rotations

####  IV.2.1 Dipolar interactions:

Although all the gates that we will be discussing rely on the same Rydberg
blockade mechanism as discussed in Ref. [3, 22, 31], we require both short-
and long- range dipolar interactions in order to implement the full variety of
multi-qubit gates that we utilize in this work. The two main factors which
effect the range of dipolar interaction between Rydberg atoms are (i) whether
the dipolar interactions are of long-ranged resonant dipole-dipole type or of
short-ranged Van der Waals type and (ii) the dipole moments associated with
different Rydberg states [8, 61]. While the long-ranged dipolar interactions
between the Rydberg states are useful for the One-Hot amplitude encoding gate
we discuss in Section IV.3, the possibility of controlling the range of short-
ranged interactions will play an important role in implementing a parallelized
version of our scheme in Section VII. Fortunately, the required
characteristics can be in principle realized with the current experimental
setups [63, 8, 61].

####  IV.2.2 Level Diagrams and Single Qubit Rotations:

Figure 2:  The level diagrams used in the proposed protocols. a) The level
diagram for the Rydberg atoms in the control registers, where a hyperfine
state is excited to the Rydberg manifold. b-d) Three different level diagrams
for the Rydberg atoms in the target registers, each use the EIT mechanism [see
$b)$] to introduce errors that are biased on the state of the control
register. c) The level diagram for the target atom of the $CX^{(R)}$ gate. The
transfer between $\left|1\right\rangle$ and $\left|r\right\rangle$ is
controlled by the energy shift of state $\left|R\right\rangle$, followed by an
excitation to the Rydberg state. d) the level scheme of the multi-qubit
control register for the $CV_{\rm OHE}$ gate. The coupling between the
hyperfine level $\left|r\right\rangle$ and the Rydberg state
$\left|R\right\rangle$ is omitted for simplicity. The state
$\left|\rm{ohe}\right\rangle$ the One-Hot encoding gate of the Rydberg states.
Similarly, $\left|\rm{ohe}^{(\psi)}\right\rangle$ replaces the Rydberg states
in $\left|{\rm ohe}\right\rangle$ with the single-qubit state
$\left|\psi\right\rangle$. The Rabi frequency $\Omega_{MW}$ of the microwave
drive couples $\left|R\right\rangle$ and $\left|R_{p}\right\rangle$.

The four level diagrams that are relevant to our implementation are shown in
Fig. 2 c). The diagrams consist of three types of states. Although these
diagrams greatly simplify the experimental reality, the three types of states
provide sufficient correspondence between our work and the experimental setup.
First, we have long-lived hyperfine states $\left|0\right\rangle$,
$\left|1\right\rangle$, and $\left|r\right\rangle$, which make up the two
logical states and an auxilliary state for each Rydberg atom. Second, we have
an intermediate state $\left|P\right\rangle$ which is useful to implement
rotations within the hyperfine manifold, but which have a much shorter
lifetime than the hyperfine states due to a larger radiative decay rate. The
intermediate state is also crucial for the realization of the EIT scheme that
we will discuss in the Section IV.4.1. Lastly, the high-energy Rydberg states
$\left|R\right\rangle$ which not only have a shorter lifetime than the
hyperfine states, due to radiative decay, but also evolve under an interacting
Hamiltonian, which can be written as

$\displaystyle H_{R}=\sum_{i}J_{ij}\left|R_{i}R_{j}\right\rangle\left\langle
R_{i}R_{j}\right|,$ (19)

where
$\left|R_{i}R_{j}\right\rangle\equiv\left|R_{i}\right\rangle\otimes\left|R_{j}\right\rangle$
is the two-particle state where the $i^{\rm th}$ and $j^{\rm th}$ atoms
located at positions $r_{i}$ and $r_{j}$ are in the Rydberg state. Although in
reality the interaction strength has the form
$J_{ij}\propto\frac{1}{|r_{i}-r_{j}|^{\nu}}$ with $\nu\in\mathbf{N}$, it is
reasonable to model such a spatial dependence as a step function which takes
the value $J$ when $|r_{i}-r_{j}|<R_{b}$ and vanishes otherwise. We refer to
the distance $R_{b}$ as the “blockade radius”. The interaction strength $J$ is
finite. As a consequence, even when the radiative decay rate is not taken into
account, the two-qubit blockade gate cannot be implemented perfectly. The
errors due to the imperfect blockade will be referred to as non-adiabatic
errors, whose error-probability is $\propto J^{2}/\Omega^{2}$, where $\Omega$
is the characteristic Rabi frequency of the laser drive connecting the low
energy states to the Rydberg state. In the following, we assume that these
non-adiabatic errors are as large as the errors introduced by the radiative
decay rate, unless otherwise specified.

For the implementation of single-qubit rotations, we choose to use
$\left|P\right\rangle$ as the intermediate state (see Fig. 2 a). Specifically,
we can drive transitions between the logical states $\left|0\right\rangle$ and
$\left|1\right\rangle$ using a Raman scheme which virtually excites the short-
lived intermediate state $\left|P\right\rangle$. The errors associated with
the virtual occupation of $\left|P\right\rangle$ motivate our rule for
counting single-qubit gates in Section IV.1.2. Specifically, given
$\left|0\right\rangle$ as our initial state, the errors scale with the time
that the short-lived state is virtually occupied during the rotation to the
superposition state
$\sqrt{1-|\alpha|^{2}}\left|0\right\rangle+\alpha\left|1\right\rangle$,
resulting in the EBGC of $\arcsin(\alpha)/(3\pi)$ as in Table 1. The EBGC does
not change as long as we choose one of 3 hyperfine states of the Rydberg atom
(i.e., $\left|0\right\rangle$, $\left|1\right\rangle$, and
$\left|r\right\rangle$).

###  IV.3 One-Hot amplitude encoding gate

In the following, we introduce a new gate which can be thought of as a multi-
qubit generalization of the single-qubit gate. The reason that $V_{\rm OHE}$
is a generalization of the single-qubit gate is that the long-range Rydberg
interactions constrain the many-body Hilbert space relevant for the evolution
to a two-dimensional subspace. Consequently, both the single-qubit gate and
the One-Hot encoding gate are used to store classical information encoded in
the duration $t_{0}$ and the amplitude $\Omega$ of the laser drive in quantum
mechanical degrees of freedom. More specifically, the single-qubit rotation
loads a single amplitude $\alpha\equiv\arcsin{(\Omega t)}$ on a single qubit.
Similarly, the One-Hot amplitude encoding gate $V_{\rm OHE}$ is a way of
loading $M$ amplitudes $\\{\alpha_{i}\\}$ where $\alpha_{i}\propto\Omega_{i}$
into $M$ qubits in constant time. Because our scheme implements $M$ amplitudes
in the computational basis states with only one excitation (i.e., one qubit in
the $\left|1\right\rangle$ state), we refer to it as the “One-Hot” amplitude-
encoding gate. From a physical point of view $V_{\rm OHE}$ gate achieves to
load all of the information encoded in the relative local intensity of the
laser field into orthogonal computational basis states of a quantum register.

The sequence of unitaries that implement $V_{\rm OHE}$ builds on a similar
gate discussed in the context of preparing the W state on the Rydberg platform
[64]. Starting from the state $\left|0\right\rangle^{\otimes M}$, we
coherently drive the ancillae with $M$ amplitudes $\\{\Omega_{0}\alpha_{i}\\}$
where $\left(\Omega_{0}/J\right)^{2}\ll 1$. Starting from the
$\left|0\right\rangle^{\otimes M}$ state, and assuming that each Rydberg level
causes an energy shift of $J$ on the Rydberg states of all other qubits, the
dynamics is constrained to a two-dimensional Hilbert space spanned by

$\left|0\right\rangle^{\otimes
M}\quad\mathrm{and}\quad\sum_{i}\alpha_{i}\left|{\rm
ohe}^{(R)},i\right\rangle,$

where we define the One-Hot encoding basis states $\left|{\rm
ohe}^{(R)},i\right\rangle\equiv\left|0\cdots 0R_{i}0\cdots 0\right\rangle$,
each of which has only one Rydberg excitation. Projecting the drive
Hamiltonian $H_{d}=\sum_{i=1}^{M}\Omega_{0}\alpha_{i}\sigma^{+}+h.c.$ onto
this subspace yields the effective Hamiltonian

$\displaystyle\bar{H}$ $\displaystyle\equiv P_{1}H_{d}P_{1}$
$\displaystyle=\Omega_{0}\left(\sum_{i=1}^{M}\alpha_{i}\left|{\rm
ohe}^{(R)},i\right\rangle\right)\left\langle 0^{\otimes M}\right|+h.c.,$ (20)

which is analogous to a Pauli operator in the constrained Hilbert space
(notice $\bar{H}^{2}=\mathbf{1}$). A schematic for the implementating
$V_{\rm{OHE}}$ is given in Fig. 3.

Hence, given the initial state $\left|0\right\rangle^{\otimes M}$, evolving
the system under $\bar{H}$ for time $t^{*}=\frac{\pi}{|\Omega_{0}|}$, prepares
the following OHE state

$\displaystyle U_{0r}\left|0\right\rangle^{\otimes M}$
$\displaystyle=e^{-it^{*}\bar{H}}\left|0\right\rangle^{\otimes M}$
$\displaystyle=\sum_{i=1}^{M}\alpha_{i}\left|{\rm
ohe}^{(R)},i\right\rangle\equiv\left|\rm{ohe}^{(R)}\right\rangle.$ (21)

While the time to implement $U_{0r}$ scales as $O(1/\sqrt{M})$, when each atom
is driven by an independent laser of fixed amplitude the run-time of One-Hot
encoding gate is increased (i.e., $\sqrt{M}$-fold) due to the requirement that
our final state needs to be within the long-lived logical subspace of each
atom. In other words, we are required to transfer each ancilla atom excited to
their Rydberg state to the long-lived hyperfine $\left|1\right\rangle$
$\left|r\right\rangle$ states using the following evolution operator

$\displaystyle U_{\sigma
r}=\exp{\left(it_{1}^{*}\sum_{i=1}^{M}(\Omega_{1}\left|r_{i}\right\rangle\langle\sigma_{i}|+h.c.)\right)},$
(22)

where $\sigma=\\{1,r\\}$ and $t_{1}^{*}=\left|\frac{\pi}{\Omega_{1}}\right|$.
Assuming that the Rabi frequencies of local drives are the same,
$\Omega_{0}/\Omega_{1}=O(\sqrt{M})$, as the second part of the evolution does
not take advantage of the collective enhancement of the effective Rabi
frequency in the presence of blockade interactions. Given this bottleneck, we
chose the single-qubit drive strengths in the implementation of $U_{0r}$ as
$\Omega_{0}=O(1)$ such that the runtime of the $V_{\rm OHE}$ gate is
$2t^{*}_{1}=2t_{\rm step}$. Thus, $V_{\rm OHE}$ has an implementation depth of
2. We emphasize that this result holds only in the limit of infinite blockade
radius. We discuss the case of finite maximum blockade radius in Section VI.

To arrive at the relevant EBGC, we consider two sources of errors: (i) those
that result from the radiative decay rate of the atoms in their Rydberg states
and (ii) the non-adiabatic errors that result from the imperfect blockade
interactions. Because we have at most one atom in the Rydberg state during the
implementation of $V_{\rm OHE}$, the errors due to the radiative decay
mechanism is the same as those associated with a single-qubit gate where the
initial $\left|0\right\rangle$ state is completely transferred to the
$\left|1\right\rangle$ state. On the other hand, the non-adiabatic errors
resulting from the finite value of the strength $J$ of dipolar interactions
grow as $O\left((\Omega_{0}/J)^{2}\right)=O(1)$, since the bottleneck induced
by $U_{1r}$ entails that we set $O(\Omega_{0})=O(1)$, as explained in the
previous paragraph. Including the errors introduced by the radiative decay of
the Rydberg states during $U_{1r}$, the number of gates involved in
implementing $V_{\rm OHE}$ is 3/3=1. It is important to emphasize that the
above error cost of $V_{\rm OHE}$ is calculated assuming that the coupling
between the Rydberg and hyperfine manifolds is induced by a single photon
transition, as the introduction of intermediate states which do not experience
an energy shift due to dipolar interactions result in radiative errors that
scale as $O(M)$. Such an excitation can be realized in the alkali-earth metal
atoms as in Ref. [23].

Before we continue, we emphasize another important property of the $V_{\rm
OHE}$ gate which allows for a hardware efficient implementation of the
reflection operator $2(\left|0\right\rangle\left\langle 0\right|)^{\otimes
n_{a}}-\mathbf{I}$ required for the QSP walk operator. Let us define
$\tilde{V}_{\rm OHE}\equiv U_{0r}U^{\dagger}_{1r}$. Then, we have

$\displaystyle\tilde{V}_{\rm OHE}\left|{\rm
ohe},l\right\rangle=U_{0r}\left|{\rm ohe}^{(R)},l\right\rangle$
$\displaystyle=U_{0r}\left[\alpha_{l}\left|{\rm
ohe}^{R}\right\rangle+\sum_{j=1}^{n_{a}-1}\big{\langle}{\rm
ohe}^{(R)}\left|{\rm ohe}_{\perp}^{(R)},l\right\rangle\left|{\rm
ohe}_{\perp}^{(R)},j\right\rangle\right]$
$\displaystyle=i\alpha_{l}\left|0\right\rangle^{\otimes
n_{a}}+\sum_{j=1}^{n_{a}-1}\big{\langle}{\rm ohe}^{(R)}\left|{\rm
ohe}_{\perp}^{(R)},l\right\rangle\left|{\rm ohe}_{\perp}^{(R)},j\right\rangle$
(23)

where $\left\\{\left|\rm{ohe}^{(R)}\right\rangle,\left\\{\left|{\rm
ohe}_{\perp}^{(R)},j\right\rangle\right\\}\right\\}$ is a set of $n_{a}$
orthogonal OHE states. To reach the final equality, we used the fact that the
action of $U_{0r}$ on $\left\\{\left|{\rm
ohe}_{\perp}^{(R)},j\right\rangle\right\\}$ is trivial. Given Eq. (23), we
find that

$\displaystyle\tilde{V}_{\rm OHE}\bar{U}V_{\rm
OHE}=(\mathbf{1}-2\Pi_{0})V_{\rm OHE}^{\dagger}\bar{U}V_{\rm OHE}.$ (24)

The equation above allows us to realize a hardware-efficient implementation
the reflection operation using Rydberg atoms.

Figure 3:  a) The experimental scheme for implementing $V_{\rm{OHE}}$. All
atoms are within each others blockade radii. The spatial dependence of the
drive amplitude is utilized to encode complex-valued classical data stored in
the laser amplitudes $\Omega_{i}\equiv\Omega(x_{i})$ into a quantum register.
b) The level diagram of $M$ Rydberg atoms for the configuration in a). The
One-Hot encoding computational basis states $\left|\rm{ohe},i\right\rangle$
have a single Rydberg excitation on the $i^{\mathrm{th}}$ atom.

###  IV.4 Biased-error controlled unitary gates $CU_{1}\cdots U_{k}$

While the unitary $V_{\rm OHE}$ offers a way of loading the classical data
stored in $\vec{\alpha}$ into quantum degrees of freedom, the controlled
unitary gates load the classical data describing the Pauli strings
$\\{P_{i}\\}$ ( see Section III) into the quantum processor. In particular,
implementation of each single-qubit rotation $U_{j}\equiv
e^{i\theta_{j}\hat{n}_{j}\cdot\vec{\sigma}_{j}}$ on the $j^{\rm th}$ target
atom load the information regarding the position of that single qubit as well
as the axis $\hat{n}_{j}\in\\{\hat{x},\hat{y},\hat{z}\\}$, and the angle
$\theta_{j}$ associated with its rotation. By conditioning products of single-
qubit rotations on the ancillary address states $|x_{i}\rangle$, we can make
sure the relevant Pauli string can be retrieved conditionally on orthogonal
address states.

In Section IV.1, we considered an error model which assumes that the error
probability is completely conditional on the state of the control qubit. Here,
we describe the concrete protocol for which such an error model is valid. In
particular, we discuss the multi-target controlled unitary proposed in Ref.
[53], which utilizes an interference phenomenon called Electrodynamically
Induced Transparency (EIT) to ensure that the evolution of the target atoms
can be made near trivial and error-free when the control condition is not
satisfied. This protocol thus motivates the way we count the gates for each
single-control conditional unitary using EBGC (see Section IV.1.2). In the
physical implementation the errors are not perfectly biased, and the
contribution to the error probability when the control condition is not
satisfied is not completely negligible. The ratio between the error
contributions when the control condition is satisfied and not satisfied can be
increased by increasing the strength of a laser drive. However, unlike the
conventional dependence of the error probability to the amplitude of the drive
laser, where the error probability is inversely proportional to the amplitude
of the laser drive, our scheme realized a two-qubit gate where the error
probability is inversely proportional to the intensity of the laser drive,
providing a quadratic advantage. Moreover, the drive amplitude can be
increased up to an order of magnitude above the strength $J$ of dipolar
interactions. While these caveats are crucial for experiments on the Rydberg
atom platform, we emphasize that the result “LCU-based block-encoding unitary
can be implemented with constant error scaling with respect to the system
size” is independent of how the biased-error controlled-Pauli operations can
be implemented on an experimental platform.

As it will become apparent from the following discussion, the single-qubit
controlled Pauli operations conditioned on One-Hot encoding states can be used
to realize an error-robust implementation of the LCU-based block-encoding
unitary. However, if we only consider One-Hot Encoding address states, the
error robust implementation comes at the expense of an address registers of
size $N$, which is not scalable. In order to reduce the size of the ancillary
address register, we propose to use $k$-Hot Encoding ($k$HE) address states.
An $n$-qubit $k$-Hot Encoding state $\left|k{\rm he}^{(1)}\right\rangle$ is
defined as a linear superposition of computation basis states which have $k$
atoms in the $\left|1\right\rangle$ state. Crucially, using $\left|k{\rm
he}^{(1)}\right\rangle$ as address states increases the number of address
states exponentially with $k$, while increasing the size of the address
register only linearly in $k$. We discuss the Rydberg atom gates necessary for
preparing a $k$HE state as well as implementing $k$-qubit controlled Pauli
operations conditioned on the $k$HE address state in Section IV.4.2.

Figure 4: The pulse sequences for implementing the three conditional unitaries
that are used to implement the algorithms in the QSP framework. The strengths
of each laser pulse are given in Fig. 2. figure: a) The pulse sequence for the
conventional two-qubit conditional gate (CNOT) on the Rydberg atom platform
implemented via the blockade mechanism. Notice that there is substantial error
probability both when the control condition is satisfied and violated. b)
Implementation of the EIT-based blockade gate which results in an error model
that is strongly biased on the state of the control atom. Notice that the
control laser on the target register is always on, and hence does not have a
number associated to it. c) The laser pulse sequence for implementing the
conditional excitation to the Rydberg state, denoted $CX^{(R)}$ in the main
text. The same pulse sequence is used to implement the $CV_{\rm OHE}$ gate.

####  IV.4.1 EIT-based single-control multi-target unitary on the Rydberg
platform

The EIT-based controlled unitary operations utilize interference to ensure
that if the control condition is not satisfied, the evolution of the target
atoms initiated in the logical subspace stays in a non-radiative “dark”
subspace, thereby drastically reducing the errors due to radiative decay from
both the intermediate state $\left|P\right\rangle$ and the Rydberg state
$\left|R\right\rangle$. Moreover, the Rydberg interactions become relevant to
the evolution only when the control condition is satisfied and therefore, the
non-adiabatic corrections are only relevant to this case. As a result, the
EIT-based blockade gates introduce errors in a biased way, and the error
probability depends on whether the control condition is satisfied or not.
Thus, the central quantity of our analysis is the ratio $\eta_{\epsilon}$ of
the error probabilities conditioned on the satisfaction of the control
condition.

We show that the ratio $\eta_{\epsilon}$ can be reduced by a factor of $N$ by
increasing the amplitude of a laser drive by $O(\sqrt{N})$. This is in
contrast to the more well-known Rydberg-blockade based gates where the total
error probability decreases linearly with increasing drive amplitude [3, 46].
Moreover, the error probability of these conventional Rydberg-blockade gates
are dominated by errors due to the unwanted population of the Rydberg state
when the drive amplitude is of the order of the dipolar interactions $J$. In
contrast, the EIT-based scheme allows for the strength of the drive amplitude
to be increased above the blockade interactions strength $J$ while still
resulting in an error-robust implementation. The results of this section are
the core justification of our error model for single-qubit-controlled
unitaries discussed in Section IV.1.

Next, we demonstrate that when $\eta^{-1}_{\epsilon}=N$, we can achieve a
constant error implementation of $\bar{U}$ for $N$ Pauli strings (see Section
III), using $N$ EIT-based single-qubit controlled Pauli gates acting on an
$N$-qubit One-Hot Encoding address state $V_{\rm
OHE}\left|0\right\rangle^{\otimes N}$. The implementation uses $O(N)$
ancillary address qubits, and is therefore not scalable. We address this
problem by designing protocols to utilize $k$HE states in Sections IV.4.2 and
V.

Protocol: We start the discussion of the EIT-based blockade-gates with the
implementation of a CNOT gate [53]. The scheme uses the level scheme in Fig. 2
$(a)$ and $(b)$ for the control and target qubits, respectively. The target
qubit is continuously driven by a control field $\Omega_{c}$ during the three-
step protocol. In the first step, the control atom is excited to a Rydberg
state if it satisfies the control condition. Secondly, lasers inducing the two
probe Rabi frequencies $|\Omega_{p1}|e^{i\theta_{1}}$ and
$|\Omega_{p2}|e^{i\theta_{2}}$ are shone on for the target atom. The
frequencies of the control and probe frequencies are such that the excitation
to the Rydberg state is two-photon resonant. Denoting the detuning between the
hyperfine and intermediate state as $\Delta$, and defining the radiative decay
rates $\gamma_{R}$ and $\gamma_{P}$ of the states $\left|R\right\rangle$ and
$\left|P\right\rangle$, respectively, we consider an experiment satisfying a
set of inequalities that define the perturbative regime,
$\\{\Delta,J\\}\gg\\{\Omega_{1},\Omega_{2},\Omega_{c}\\}\gg\\{\gamma_{R},\gamma_{P}\\}$.
The second step of the protocol takes time
$\tau_{g}\equiv\pi\frac{\Delta}{\Omega_{p}^{2}}$.

Two scenarios are relevant for the second step of the EIT-based blockade gate

  1. 1.

If the control atom is not in the Rydberg state, then both logical states of
the target atom evolve adiabatically in a dark (non-radiative) subspace
spanned by

$\displaystyle\left|\psi_{d}\right\rangle$
$\displaystyle=\frac{1}{\sqrt{1-x^{2}}}\left(\left|\psi_{l}\right\rangle+x\left|R\right\rangle\right)$
$\displaystyle\left|\tilde{\psi}_{d}\right\rangle$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle-e^{i(\theta_{1}-\theta_{2})}\left|1\right\rangle\right),$

and eventually return back to the initial state [53]. In the above expression
we defined $x\equiv|\sqrt{2}\Omega_{p}/\Omega_{c}|$ as a time-dependent
dimensionless quantity. The logical state
$\left|\psi_{l}\right\rangle=\frac{1}{\sqrt{2}}(\left|0\right\rangle+e^{i(\theta_{1}-\theta_{2})}\left|1\right\rangle)$
is orthogonal to $\left|\tilde{\psi}_{d}\right\rangle$. Most importantly, the
two dark-states have no contribution from the short-lived intermediate state
$\left|P\right\rangle$. Hence, the errors during the adiabatic evolution come
solely due to decay of the small occupation in the Rydberg state
$\left|R_{t}\right\rangle$, which scales as $x^{2}$.

  2. 2.

If, on the other hand, the control condition is satisfied and the control atom
is excited to its Rydberg state, then the EIT condition that ensure an
evolution only within the dark-state manifold is no longer satisfied, and the
transitions between the two logical states $\left|0_{t}\right\rangle$ and
$\left|1_{t}\right\rangle$ are mediated by the virtual excitation of the
short-lived state $\left|P\right\rangle$, introducing errors due to the finite
decay rate $\gamma_{P}$.

The last step of the gate simply brings the control atom back to the hyperfine
manifold. Whether the Pauli gate applied on the target qubit is
$\sigma_{x}^{(t)}$ or $\sigma_{y}^{(t)}$ is determined by the phase difference
between the control pulses $\Omega_{p1}$ and $\Omega_{p2}$. The multi-target
generalization of the EIT-based controlled unitary is obtained by simply
increasing the number of target qubits within the blockade radius of the
control qubit.

Controlling biases of error processes: We discussed above how the evolution of
the target atom depends on whether the control condition is satisfied or not.
As a result, the probability that the target atom will suffer an error depends
on the state of the control atom. Here, we calculate the ratio
$\eta_{\epsilon}$ between the error probability of the target atom when the
control condition is satisfied to that when the control condition is violated.

The error probability when the control condition is not satisfied is given by
the population of the target Rydberg state

$\displaystyle\epsilon_{v}\equiv\pi\frac{\Delta}{\Omega_{p}^{2}}\gamma_{R}\left(\frac{\Omega_{p}}{\Omega_{c}}\right)^{2}=\tau_{g}\gamma_{R}x^{2},$
(25)

where the factor of $\pi$ is because we are implementing a NOT operation on
the target qubit. Here, we neglected the diabatic corrections associated with
the probe pulse, which are proportional to $x^{6}$ [53].

On the other hand, when the control condition is violated, there are multiple
contributions to the error probability

$\displaystyle\epsilon_{s}=\tau_{g}\left[\left(\frac{\Omega_{p}}{\Delta}\right)^{2}\gamma_{P}+\gamma_{R}+\left(\frac{\Omega_{p}\Omega_{c}}{\Delta
J}\right)^{2}\gamma_{R}\right],$ (26)

where the first term in the brackets is the radiative decay probability from
the intermediate state $\left|P\right\rangle$ of the target atom. The second
and the third terms in the brackets correspond to the errors due to the
perturbative occupation of the Rydberg state of the control and the target
atoms, respectively. In the following, we take
$(\Omega_{p}/\Delta)^{2}\gamma_{P}\leftarrow\gamma_{R}$ to fix the free
parameters $\Omega_{p}/\Delta$ and ensure that the two error sources
contribute to the error probability the same way. In Eq. (26), we assume
$\tau_{g}$ is chosen such that the occupation of the target Rydberg state at
the end of the protocol is negligible. As a result, because the ratio
$\eta_{\epsilon}\equiv\frac{\epsilon_{v}}{\epsilon_{s}}$ depends on $x^{2}$
when $\left(\frac{\Omega_{p}\Omega_{c}}{\Delta J}\right)^{2}\leq 1$, it can be
lowered $\propto\Omega_{c}^{-2}$ as long as

$\displaystyle\Omega_{c}<J\frac{\Delta}{\Omega_{p}}=J\sqrt{\frac{\gamma_{P}}{\gamma_{R}}}.$
(27)

The above result is the main justification for the Error Bounded Gate Count
(EBGC) for a single-qubit-controlled Pauli operation described in the Section
IV.1.2, which neglects the error-probability conditioned on the violation of
the control condition. Then given the control condition
$\left|0_{C}\right\rangle$ and the input state of the control register
$\left|\psi_{c}\right\rangle$, the single-control k-target unitaries
$CU_{1}\cdots U_{k}$ can be implemented using $(2+k)/3|\left\langle
0_{c}\right|\psi_{c}\rangle|^{2}$ error-bounded gates and a depth of 3. Next,
we discuss the conditions under which the error-probability conditioned on the
violation of the control condition can be neglected for an implementation of
$\bar{U}$.

Error probability for $\bar{U}$ using OHE address states: In order to
demonstrate the advantage of single-qubit controlled Pauli operators, we
consider their action on a control register prepared in an $N$ qubit One-Hot
encoding state. Then each single-qubit controlled Pauli operation conditioned
on the state of the $j^{\rm th}$ control atom is equivalent to a controlled
Pauli operation conditioned on a One-Hot encoding bitstring $\left|{\rm
ohe},j\right\rangle$. Assuming that $\epsilon_{v}N\ll 1$, total error
associated with $N$ single-qubit controlled Paulis acting on the $N$-qubit
One-Hot encoding state is

$\displaystyle\epsilon_{\rm
tot}=\left[\epsilon_{s}+\epsilon_{v}(N-1)\right]=\epsilon_{s}\left[1+\eta_{\epsilon}(N-1)\right].$
(28)

The expression for $\epsilon_{\rm tot}$ follows from the fact that the
probability that the control condition is satisfied for any one of the $N$
controlled Pauli operations add up to 1. When the condition in Eq. (27) is
satisfied, $\epsilon_{s}$ does not scale with $\Omega_{c}$, while
$\eta_{\epsilon}\propto\Omega_{c}^{-2}$. Hence, if we chose
$\Omega_{c}~{}=~{}O(\sqrt{N})$, $\epsilon_{\rm tot}$ remains constant. As a
result, in this regime, the unitary $\bar{U}$ can be implemented with a
constant error probability, although the gate complexity is $O(N)$ and the
implementation of the protocol is error-robust.

Surprisingly, there is also a regime biased errors still help realize an
error-robust implementation, although the condition Eq. (27) is no longer
satisfied. In this strong-drive limit, the total error is not constant, but
scales as $\epsilon_{\rm tot}=O(\sqrt{N})$. To see this, we simply note that
in the regime $\Omega_{c}\gg J\sqrt{\gamma_{P}/\gamma_{R}}$, we have
$\eta_{\epsilon}\propto\Omega_{c}^{-4}$, while
$\epsilon_{s}\propto\Omega_{c}^{2}$. Hence, picking $\Omega_{c}=O(N^{1/4})$,
we obtain a total error probability scaling as $O(\sqrt{N})$. This scaling is
error-robust, since the error probability scales quadratically slower than the
gate complexity of the protocol. Notice that the property that the error
reduction scaling quadratically with the drive strength is preserved.

Suppression using reported parameters: Whether the Rabi frequency $\Omega_{c}$
can be increased at will depends both on the intensity of the laser field and
the ability to single out the desired Rydberg states during the excitation
between the hyperfine and Rydberg manifolds. While a more detailed discussion
of the internal structure of Rydberg atoms is beyond the scope of our work, we
can simply use the reported values for (i) the Rabi frequencies $\Omega_{c}$
achieved as well as (ii) the lifetimes $2\pi/\gamma_{P(R)}$ from the
literature.

To determine the maximum suppression of errors, use the reported values for
the lifetimes $\tau_{R}=146\,\mu s$ for the Rydberg state
$\left|n=70,J=1/2,m_{j}=-1/2\right\rangle$ and $\tau_{P}=115\,ns$ for the
intermediate state $\left|n=6\,P_{3/2},F=3,m=-3\right\rangle$ [12]. Hence, we
set
$\frac{\Omega_{p}}{\Delta}\leftarrow\sqrt{\frac{\gamma_{R}}{\gamma_{P}}}=\approx
1/36$. On the other hand, we use the Rabi frequency $\Omega_{R}\approx
2\pi\times 120$ MHz reported by Ref. [12] for a transition between the
intermediate state $\left|P\right\rangle$ and the $\left|R\right\rangle$.
Thus, if we would like to have a 100 fold suppression of errors if the control
condition is not satisfied (i.e., $\eta_{\epsilon}=1/100$), then we need to
set $\Omega_{P}=\Omega_{R}/10=2\pi\times 12$ MHz. To determine the error
probability for 100 gates, we calculate the error probability

$\epsilon_{s}=1-\exp{\left(-2\pi*\frac{\Delta}{\Omega_{P}^{2}\tau_{R}}\right)}\approx
2\pi*\frac{36}{\Omega_{P}\tau_{R}}\approx\frac{1}{50}.$

As a result, up to 100 gates conditioned on a One-Hot Encoding state can in
principle be achieved with below $5\%$ error probability.

The size of the ancillary register: The results of this section allows one to
implement the walk operator $W$ [see Eq. (11)] with constant error probability
if the ancillary control register is prepared in a One-Hot Encoding state.
However, if we only use One-Hot Encoding states, then the cost of the error-
robustness is an ancillary register of size $N$ for a block-encoding operator
that can be decomposed into $N$ Pauli strings. In this case the size of the
ancillary register makes the implementation unfeasible. In order to address
this issue, we propose to use $k$-Hot Encoding states realized by a tensor
product of $k$ One-Hot Encoding states. In Section V, we show that the error-
probability associated with the action of $N$ single qubit controlled
operations on a $k$-Hot encoded state scales as $O(k)$. Before we do so, we
introduce two additional Rydberg gates which enables us to use the $k$HE
states in our protocols.

####  IV.4.2 Utilizing $\left|k{\rm he}\right\rangle$ states: $CX^{(R)}$ and
C$V_{\rm OHE}$ gates

If we want to realize an error-robust implementation of QSP protocols using
$k$-Hot Encoding states, we have to overcome two challenges. First, to
implement the relevant $\bar{U}$, we need an error-robust implementation of
$k$-qubit controlled unitaries. Second, we need to be able to prepare
$\left|k{\rm he}\right\rangle$ through an error-robust implementation of $V$.
Here, we introduce two additional gates that will be instrumental in meeting
these challenges.

$CX^{(R)}$: In order to implement $k$-qubit controlled Pauli operations using
their single-qubit controlled counterparts, we use a controlled transfer of a
logical states of the target atom to the Rydberg state conditionally on the
state of the control atom. We denote this gate as $CX^{(R)}$. To this end, we
use an additional hyperfine state $\left|r_{t}\right\rangle$ [see Fig.
$\ref{fig:CZ}\,c)$], and apply the EIT-based blockade gate where the probe
lasers on the target atom induce transitions between
$\left|1_{t}\right\rangle$ and $\left|r_{t}\right\rangle$. Then, the
population in $\left|r_{t}\right\rangle$ can be transferred to the Rydberg
state $\left|R_{t}\right\rangle$ using an additional $\pi$ pulse. As a result,
the depth of the implementation is 4. The EBGC depends on the input state of
both the control and the target registers. Given the input state
$\left|\psi_{c}\right\rangle=\sqrt{1-|\alpha|^{2}}\left|0_{c}\right\rangle+\alpha\left|1_{c}\right\rangle$
and
$\left|\psi_{t}\right\rangle=\sqrt{1-|\beta|^{2}}\left|0_{t}\right\rangle+\beta\left|1_{t}\right\rangle$,
the EBGC of the controlled unitary is $2/3|\alpha|^{2}(1+|\beta|^{2})$ for a
single target qubit. The calculation of the EBGC for larger number of target
atoms is straightforward.

$CV_{\rm OHE}$: We prepare the $k$HE address state using a controlled version
of $V_{\rm OHE}$. Unlike the situation with the tensor products of Pauli
operators, a controlled version of the $V_{\rm OHE}$ gate is challenging
because $V_{\rm OHE}$ utilizes interactions between the Rydberg states amongst
all atoms. Thus, we need to introduce a new mechanism to implement $CV_{\rm
OHE}$. Our strategy is to use the One-Hot encoding state Rydberg state
$\left|\rm{ohe}^{(R)}\right\rangle$ [see Eq. (21)] as the intermediate state
$\left|P\right\rangle$ discussed in Section IV.1.2. We are allowed to make
such a substitution because the strong and long-range dipolar interactions
between Rydberg states constrain the system of $n$ atoms to only a a two-
dimensional subspace.

During the implementation of the $CV_{\rm OHE}$ gate, the dynamics of the
target register can be described by a 5 level system depicted in Fig. 2.
Besides the initial state $\left|0\right\rangle^{\otimes n}$, our scheme uses
four One-Hot Encoding states which are distinguished by the state which
specifies the type of excitation present. We denote these states as
$\left|{\rm ohe}^{(\eta)}\right\rangle$, where
$\left|\eta\right\rangle\in\\{\left|1\right\rangle,\left|R\right\rangle,\left|r\right\rangle,\left|R_{p}\right\rangle\\}$
denoting different single atom states. Crucially, Moreover, starting from the
state $\left|\rm{ohe}^{(\eta_{\rm{in}})}\right\rangle$ and transferring each
qubit to a their corresponding state $\eta_{\rm{fin}}$ results in
$\left|\rm{ohe}^{(\eta_{\rm{fin}})}\right\rangle$. The newly introduced
Rydberg state $\left|R_{p}\right\rangle$ has two important properties. First,
it is only accessible from $\left|R\right\rangle$ via a microwave transition
(see Fig. 2) [65, 66]. Secondly, the angular momentum quantum numbers of
$\left|R\right\rangle$ and $\left|R_{p}\right\rangle$ are different, such that
the two states experience different energy shifts due to dipolar interactions.
Thus, for our intents and purposes, we can assume that it is possible to have
an energy shift on $\left|R_{p}\right\rangle$ while the energy of
$\left|R\right\rangle$ stays constant.

The gate protocol is based on an EIT scheme where the two states in the
hyperfine subspace are $\left|0\right\rangle^{\otimes n}$ and
$\left|\rm{ohe}^{(r)}\right\rangle$, and the intermediate state of the EIT
scheme is the One-Hot encoding Rydberg state
$\left|\rm{ohe}^{(R)}\right\rangle$. Finally, the state which controls whether
the EIT condition is satisfied is $\left|\rm{ohe}^{(R_{p})}\right\rangle$. The
first step of $CV_{\rm OHE}$ is to implement a transition between
$\left|0\right\rangle^{\otimes n_{a}}$ and $\left|\rm{ohe}^{(r)}\right\rangle$
controlled by the energy shift of $\left|\rm{ohe}^{(R_{p})}\right\rangle$. In
the second step, $\left|\rm{ohe}^{(r)}\right\rangle$ is transferred to the
$\left|\rm{ohe}^{(R)}\right\rangle$ state by a tensor product of single-qubit
rotations. The depth of the implementation is 4 and the EBGC given the state
of the control register
$\left|\psi_{c}\right\rangle=\sqrt{1-|\beta|^{2}}\left|0\right\rangle+\beta\left|1\right\rangle$
is $5/3|\beta|^{2}$. The prefactor 5 is a result of taking into account both
the radiative and non-adiabatic errors into account. We emphasize that the
One-Hot encoding keeps EBGC small during the transfer between $\left|\rm
ohe^{r}\right\rangle$ and $\left|\rm ohe\right\rangle$.

##  V Error-Robust implementation of LCU-based block-encoding unitary

In this section, we describe protocols for implementing LCU-based QSP walk
operators using $k$HE ancillary address states, using the Rydberg atom gates
described in Section IV. The resulting implementation is has an EBGC scaling
as $O(k^{2})$ when the block-encoded operator $A$ is a linear combination of
$k$-local Pauli strings acting on $n_{\rm site}$ qubits. The size ancilla
register, on the other hand grows only linearly with $k$.

In Section V.1, we present the $k$-Hot state preparation unitary based on
C$V_{\rm OHE}$ gates (see Section IV.4.2), which efficiently prepares
ancillary states that are customized for an error-robust implementation of
LCU-based block-encoding. In Section V.2, we discuss the implementation of
$\bar{U}$ that complement the state preparation protocol in V.1.

###  V.1 Implementation of state preparation unitary $V$

We demonstrate that it is possible to reduce the EBGC of state preparation to
a constant even when the number of atoms in the address register is increased
polylogarithmically with respect to the number of addresses in the LCU
protocol. To this end, we construct a protocol that only consists of $V_{\rm
OHE}$ and its single-qubit-controlled counterpart $CV_{\rm OHE}$.

As a first step, we describe a state preparation protocol which uses 2 ancilla
registers $a_{1}$ and $a_{2}$, and prepares the following 2-Hot encoded state

$\displaystyle\left|\Psi_{\rm
2HE}\right\rangle=\sum_{l=1}^{L}\beta^{(1)}_{l}\left|{\rm
ohe},l\right\rangle\otimes\left(\sum_{i=1}^{n_{l}}\beta_{i}^{(2;l)}\left|{\rm
ohe},i\right\rangle\right),$ (29)

where $\beta_{i}^{n;l}$ is the coefficient of the state $\left|{\rm
ohe},i\right\rangle$ of the $n^{\rm th}$ ancillary register $a_{n}$,
conditioned on the $(n-1)^{\rm st}$ ancilla register being in the state
$\left|{\rm ohe},l\right\rangle$. To prepare $\left|\Psi_{\rm
2HE}\right\rangle$, we use two ancilla registers $a_{1}$ and $a_{2}$
consisting of $n_{a_{1}}$ and $n_{a_{2}}$ qubits, respectively. The state
preparation unitary can then be implemented by first applying $V_{{\rm
OHE},a_{1}}$ on the first ancilla register, followed by an application of
$V^{(l)}_{{\rm OHE},a_{2}}$ on the second ancilla register conditional on the
$l^{\rm th}$ qubit in $a_{1}$ being in state $\left|1\right\rangle$ (we denote
this operation by $C_{1;a_{1,l}}V^{(l)}_{{\rm OHE};a_{2}}$). The state-
preparation protocol requires $n_{\rm tot}=n_{a_{1}}+n_{a_{2}}$ ancillary
qubits and as an EBGC of only
$\frac{1}{3}\left(3+5\sum_{l=1}^{L}|\beta^{(1)}_{l}|^{2}\right)=8/3$. The
depth of the protocol is $2+4n_{a_{1}}$ (see Section IV.4.2 for EBGC
calculation for single-qubit-controlled $V_{\rm OHE}$).

The preparation of the 2HE clearly exhibits a space-time trade-off. When we
prepare a state with $N$ address components with $n_{a_{1}}=1$, the protocol
takes constant time, but the number of ancillae scales as $O(N)$. Increasing
$n_{a_{1}}$ by $L$, results in a protocol that takes $O(L)$ time but the
number of ancillae is $O(N/L)$. The space-time trade-off can be made more
advantageous for smaller ancillary registers if we encode the addresses in
$k$HE states. In particular, the protocol for the preparation of the 2HE state
above can be concatenated over $k$ ancillary registers [see Fig. 5], with size
$n_{j}$. The size of the ancillary address register grows linearly with $k$,
while the number of address states grow as $\prod_{j=1}^{k}n_{j}$. If we set
$n_{j}=n_{\rm site}$ for a system register of size $n_{\rm site}$, the
concatenated protocol requires $O(kn_{\rm site})$ ancillae and $O(n_{\rm
site}^{k-1})$ time. More importantly for the discussion of error-robustness
the EBGC of the state preparation of $k$HE states is

$\displaystyle\frac{1}{3}\Bigg{[}3+\sum_{l_{k-1}=1}^{n_{k-1}}|\beta^{(k-1)}_{l_{k}}|^{2}$
$\displaystyle\times\Bigg{(}5+\sum_{l_{k-2}=1}^{n_{k-2}}|\beta^{(k-2;l_{k-1})}_{l_{k-2}}|^{2}\left(5+\stackrel{{\scriptstyle
k-3\,\mathrm{times}}}{{\cdots}}\right)\Bigg{)}\Bigg{]}$
$\displaystyle=\frac{3+5(k-1)}{3}=O(k).$ (30)

Figure 5: a) The recursion relation for constructing the $k$-Hot Encoding
state preparation unitary. b) The controlled version of the $k$-Hot Encoding
state preparation unitary. That at each step of the state preparation only
controlled one-Hot encoding gates $V_{\rm OHE}$ are used, the controlled state
preparation requires a single additional C$V_{\rm OHE}$.

The prepared state is a product of $k$ One-Hot encoded states, each associated
with a different ancillary register

$\displaystyle\left|\Psi_{k{\rm HE}}\right\rangle=$
$\displaystyle\sum_{l_{1}=1}^{n_{1}}\sum_{l_{2}=1}^{n_{2}}\cdots\sum_{l_{k}=1}^{n_{k}}\beta^{(1)}_{l_{1}}\beta_{l_{2}}^{(2;l_{1})}\cdots\beta_{l_{k}}^{(k;l_{k-1})}\bigotimes_{j=1}^{k}\left|{\rm
ohe},l_{j}\right\rangle.$ (31)

We emphasize that our protocol allows one to adjust the amplitude associated
with each $k$-Hot computational basis state, for instance by using a
regression tree decomposition of the sorted list of coefficients
$\\{\alpha_{i}\\}$ [74].

Lastly, notice that the protocol for preparing a $k$HE state shares the same
characteristic of $V_{\rm OHE}$ [see Eq. (24)] in that we can implement a
reflection operator $\mathbf{I}-2\Pi_{0}$ by simply changing the phases of the
laser drives that implement each $CV_{\rm OHE}$ gate.

###  V.2 Implementation of $\bar{U}_{k{\rm HE}}$

When the control conditions are encoded in $k$-Hot Encoding basis states,
$\bar{U}_{k{\rm HE}}$ can be implemented as a sequence of $k$-qubit controlled
Pauli operations. Here, we give a protocol for an error-robust implementation
of $k$-qubit controlled unitaries made out of their biased-error single-qubit
controlled counterparts. We show that the $k$-qubit controlled unitary
preserves the biased error characteristics of its single-qubit controlled
counterpart. However, the error probability when the control condition is
satisfied scales as $O(k)$.

| $\tilde{V}_{k{\rm HE}}$ | $\bar{U}_{k{\rm HE}}$
---|---|---
EBGC | $\left(5k-2\right)/3$ | $O\left(k^{2}\right)$
${\rm depth}$ | $2(1+2L)$ | $9L$
Table 2: The EBGCs and the depth associated with the protocols introduced in
Section V. $L$ is the number of atoms in the $a_{1}$ register for
$\tilde{V}_{k{\rm HE}}$ and the number of Pauli operators that can be
implemented in parallel for $\bar{U}_{k{\rm HE}}$. The controlled versions of
the LCU protocol can be implemented with an additional $2/3$ error-bounded
gates and 2 steps.

In the case when we have only 2 ancillary registers (as in Section V.1) a two-
qubit controlled Pauli operation can be implemented by using two single-qubit
controlled Pauli operations. First, we apply a unitary that excites the second
control atom from the $\left|1\right\rangle$ state to the Rydberg manifold
conditionally on the state of the first control atom (we denote this operation
as $C_{1}X_{2}^{(R)}$). Next, the Pauli operation is implemented on the target
register. If the second control atom is in the Rydberg state, then a Pauli
operation $C_{R,2}P_{t}^{(l)}$, which is implemented on the target qubit
conditioned on the second control atom being in its Rydberg state. If the
second control atom is not excited to the Rydberg state, then the target qubit
remains in the dark state due to the EIT effect (see Section IV.4). Crucially,
the two-qubit controlled unitary only induces errors when both control atoms
satisfy the control condition because if the first control atom is not excited
to its Rydberg state no other atom is excited to the Rydberg state. By
repeating this protocol using $k$ control atoms, we obtain a $k$-qubit
controlled Pauli operation which induces errors only if all $k$ bits of the
control condition is satisfied. In the case that the $k$-qubit control
condition is satisfied, then the EBGC of the implementation scales as $O(k)$.

The unitary $U_{k{\rm HE}}$ can be implemented as a series of $k$-qubit
controlled Pauli operations. When $k=2$, $U_{2{\rm HE}}$ can be implemented by
the following protocol. For each layer ancillary qubit $l$ in the first
ancillary register $a_{1}$

  1. 1.

Apply $C_{a_{1l}}X^{(R)}_{a_{2,1}}\cdots X^{(R)}_{a_{2,n_{l}}}$ to excite the
qubits in the second ancilla register to the Rydberg state conditionally on
the state of the $l^{\rm th}$ qubit in $a_{1}$ being in state
$\left|1\right\rangle_{a_{1,l}}$.

  2. 2.

Apply $\\{C_{R;a_{2,i}}P_{i}^{(l)}\\}$ in parallel

  3. 3.

Apply $C_{a_{1,l}}X^{(R)}_{a_{2,1}}\cdots X^{(R)}_{a_{2,n_{l}}}$.

The implementation depth of the above protocol is
$(2*4+1)n_{a_{1}}=9n_{a_{1}}$. We note that the second step requires depth 1
as the control register is already excited to the Rydberg manifold. The EBGC
is

$\displaystyle
1/3\sum_{l=1}^{L}|\beta^{(1)}_{l}|^{2}\left\\{8+\sum_{i=1}^{n_{a_{2}}}\left[|\beta_{i}^{(2;l)}|^{2}\rm{supp}(P_{i}^{(l)})\right]\right\\}$
(32) $\displaystyle=O(\max_{i,l}{\rm supp}(P_{i}^{(l)}))=O(k),$

where in order to obtain the last equality, we assumed that the Pauli strings
$\\{P_{i}^{l}\\}$ are $k$-local. We emphasize that the EBGC that does not
scale with $n_{\rm site}$ or $N$, but only depends on the maximum support of
the multi-qubit Pauli operators in the decomposition of the signal operator.
Note also how we take advantage of the Rydberg state to avoid introducing new
ancillae in the implementation of a two-qubit controlled unitary [41].

The above scheme can be extended to the case of $k$ ancillary registers usign
$k$-qubit controlled operations and its EBGC is increased by an additional
factor of $O(k)$. In Fig. 6 $b)$, we depict the circuit identity which
recursively implement $\bar{U}_{k{\rm HE}}$. Considering a scheme where the
atoms in their Rydberg states in the $l^{\rm th}$ register are transferred to
the $\left|r\right\rangle$ state when they are not needed, EBGC of
$\bar{U}_{k{\rm HE}}$ conditioned on a $k$HE state is

$\displaystyle\sum_{l_{k}=1}^{n_{a_{k}}}|\beta^{(k)}_{l_{k}}|^{2}\left(8+\sum_{l_{k-1}=1}^{n_{a_{k-1}}}|\beta_{l_{k-1}}^{(k-1;l_{k})}|^{2}\left(8+\stackrel{{\scriptstyle
k-2\,\mathrm{times}}}{{\cdots}}\right)\right)$ $\displaystyle=O(k^{2}),$ (33)

where we again consider $k$-local Pauli operators.

Figure 6: The circuit diagrams for implementing the unitaries: (a)
$\bar{U}_{2{\rm HE}}$ and (b) $\bar{U}_{k{\rm HE}}$. The ancillary registers
are denoted as $a_{i}$. In $a)$, the conditional Pauli operations with the
curly brackets indicate a parallelized application. The same building block is
repeated $n_{a_{2}}$ times to complete the application of $\bar{U}_{2{\rm
HE}}$. In $b)$, we depict the concatenation of unitaries which result in the
application of $\bar{U}_{k{\rm HE}}$. The building block is to be repeated
$n_{a_{(k-1)}}$ times. Although the circuit suggests that the atoms in $a_{l}$
remain in the Rydberg manifold as we apply $\bar{U}_{l-1{\rm HE}}$, the atoms
occupying the Rydberg state should be de-excited to the long-lived
$\left|r\right\rangle$ state, to achieve an error-robust implementation.

Controlled-$W$ gates: In order to implement QSP protocols where the processing
step of each iteration contribute only a constant error probability to the
EBGC, we need to implement a single-qubit controlled version of the walk
operators $W$ in Eq. (11). This can be easily implemented by conditioning the
first step of the $k$HE state-preparation unitary. The controlled walk
operator has a additional EBGC of $2/3$, and the depth of the protocol is
increased by 2.

As a result, using the multi-qubit gates described in this section, the QSP
walk operator [see Eq. (11)] block-encoding an operator that is a linear
combination of $k$-local Pauli operators can be implemented with a total EBGC
that scales as $O(k^{2})$

Figure 7: The problem of scalability and its resolution through FANIN and
FANOUT protocols a) Due to the finite length scale of the Rydberg blockade,
the conditional unitary gates cannot be applied when the size of the target or
control register is larger than the maximum blockade volume $V_{b,{\rm max}}$.
b) The communication between registers whose size exceeds $V_{b,{\rm max}}$
can be facilitated by an additional network of ancillae, and c) the
implementation of FANIN ($\uparrow$) and FANOUT ($\downarrow$) protocols.

##  VI Scalable implementation of LCU on the Rydberg atom platform

So far we have considered the situation where the largest blockade radius
attainable is infinite. In this section, we consider the more realistic
situation where the maximum range $R_{b,\rm max}$ of blockade interactions is
finite. In a typical experiment the range of the resonant dipole interactions
that result in Förster processes do not exceed $30\,\mu$m, while the
separation of the Rydberg atoms trapped by holographic optical tweezers is
around $2\,\mu$m [75]. Hence, the scalability of the protocols introduced in
the last two sections is restricted ultimately by $R_{b,{\rm max}}$ because
they assume a blockade radius larger than the system size. To engineer
scalable protocols, we divide the system and ancilla qubits into a total of
$n_{\rm sub}$ modules whose sizes are determined by $R_{b,{\rm max}}$. The
main challenge in designing a scalable implementation of QSP protocols on the
Rydberg atom platform is to make sure that the different subsystems can
communicate efficiently.

Remarkably, the scalable protocols for implementing LCU-based QSP walk
operators only require the $n_{\rm sub}$ subsystems to communicate a single
qubit of information between themselves. This information can be communicated
either by what we call “connector” ancillae which serve as wires connecting
different modules, or by physically transporting the ancillae appropriately
using optical tweezers [30]. The incoming information is processed and then
output by a gadget we refer to as the telecommunication port, which introduces
only three ancilla qubits per subsystem.

Here, we describe explicit protocols to realize a modular and distributed
implementation of the QSP walk operator constructed out of multi-qubit gates
$V_{\rm OHE}$ and $C_{x_{0}}U_{1}\cdots U_{k}$. The main contributions of this
section is the demonstration of a scalable LCU protocol which maintains an
error-robust implementation, with an EBGC scaling $O(n_{\rm sub})$. Hence,
when the EBGC is valid, the implementation of the LCU-based QSP walk operator
has an error probability that does not scale with the number of Pauli
operations in Eq. (1) and thus has an error-robust implementation. The
analysis below demonstrates that the EBGC scaling is dominated by the
implementation of the state-preparation step.

###  VI.1 Telecommunication ports and the implementation of FANIN and FANOUT
protocols

In the absence of additional ancillae, blockade interactions cannot be used to
entangle registers larger than the blockade volume $V_{b,{\rm max}}\propto
R_{b,{\rm max}}^{d}$ in $d$ dimensions. We depict the geometric constraints
resulting from a finite $R_{b,{\rm max}}$ in Fig. 7. Similarly, the finite
blockade radius does not allow the implementation of the $V_{\rm OHE}$ gate
when the qubits in the relevant register occupy a volume larger than the
blockade volume. The solution to this problem requires the ability (i) to
broadcast the information regarding a single subsystem to many others (1-to-
many communication), and (ii) to bring the relevant information of many
subsystems to one particular subsystem (many-to-1 communication). We satisfy
these requirements by utilizing FANOUT and state transfer protocols. Because
both of these protocols are implemented through single-qubit controlled
unitaries introduced in Section IV.4, the resulting implementations are
subject to EBGC.

In the following we consider a protocol involving where the ancillary target
registers with $n_{\rm sub}^{(t)}$ subsystems. On the other hand, each one of
the $k$ control registers encoding $k$HE addresses is divided into $n_{\rm
sub}^{(c)}$ subsystems. We denote the $i^{\rm th}$ subsystem of the target
register as $s_{i}^{(t)}$, and the $i^{\rm th}$ subsystem of the $k^{\rm th}$
control register as $s_{i,k}^{(c)}$.

Telecommunication ports: For each subsystem $s_{i}$, we also introduce a
telecommunication port (see Fig. 8) consisting of 3 ancilla qubits referred
as: antenna ($A_{i}$), receiver ($R_{i}$), and processor ($Q_{i}$). For
simplicity, we also assume that a set of connector ancillae $\\{T_{ij}\\}$
connecting $A_{i}$ to $R_{j}$. The role of $A_{i}$ and $R_{j}$ is to
facilitate the communication of whether a control condition is satisfied or
violated between $s_{i}$ and $s_{j\neq i}$. The processor ancilla $Q_{i}$, is
only necessary for the scalable version of the One-Hot Encoding state
preparation unitary, and is used to load the required amplitude information
into each subsystem (see Section VI.2.2).

Figure 8:  The schemes for a scalable implementation of unitaries
$C_{m}U_{1}\cdots U_{k}$ and $V_{\rm OHE}$ in $a)$ and $b)$, respectively. The
direction of the arrows convey the flow of the information of whether the
control condition is satisfied. The yellow arrows connect the ancillary
address and the system register to the network of telecommunication ancillae,
and the red arrows depict the routing of the condition satisfaction
information. The labels $A$, $T$, $R$, and $Q$ on the ancillary network stand
for antenna, transmission, receiver, and processor ancillae described in the
text, respectively.  Figure 9: The schematic for the scalable protocols
implementing $C_{x_{0}}U_{1}\cdots U_{k}$ (a) and $V_{\rm OHE}$ (b) gates, on
a distributed network. The blue circles depict the telecommunication port of
each subsystem. In (a) pattern of the arrows show the FANOUT of the state of
the central atom (in green) to the target modules. The red triangles depict
the regions where the information from one module is fanned-out to more than a
single target module. The FANOUT protocol has optimal depth given the locality
of the problem. In (b) we depict the path that the information regarding
whether a unitary $V_{\rm OHE}^{(i)}$ is applied on subsystem $s_{i}$. The
depth of the implementation scales linearly with $n_{\rm sub}$, which is
optimal in one-dimensions, but suboptimal otherwise.

FANOUT and single-qubit state transfer: The FANOUT protocol broadcasts the
state of a single qubit to the receiver ancillae of many subsystems [76]. It
can be implemented using single control multi-target $\mathrm{CNOT}_{k}$ gates
assuming that the target qubits are all initiated in the
$\left|0\right\rangle$ state. Considering the 2D layout depicted in Fig. 9,
the state of the central “source” atom $A_{c}$ (in green) can be broadcasted
using a parallelized implementation of CNOT and ${\rm CNOT}_{3}$ gates in
accordance with the arrows connecting the subsystems in Fig. 9. This scheme,
and its extension to $d$ dimensions implements the FANOUT gate using $O(n_{\rm
sub})$ gates and in $O(n_{\rm sub}^{1/d})$ steps, which is optimal for local
systems. Because we are using single-qubit-controlled unitaries at each step,
this protocol has an error-robust implementation. In particular, the EBGC for
broadcasting a state $\left|\psi_{c}\right\rangle$ to $n_{\rm sub}$ subsystems
scale as $|\langle 1_{c}\left|\psi_{c}\right\rangle|^{2}O(n_{\rm sub})$. As a
result, when the Pauli strings implemented are $k$-local with $k<n_{\rm sub}$,
the EBGC for implementing $\bar{U}$ in Eq. (4) scales a $O(kn_{\rm
sub}^{1/d})$.

The error-robust implementation of state transfer is similar to the FANOUT
protocol. Starting from a source qubit in state $\left|\psi_{c}\right\rangle$,
and all target qubits initialized to $\left|0\right\rangle$, each step of the
state transfer is implemented by two CNOT gates, where the second CNOT gate
has the control and target qubits swapped. This state transfer protocol
preserves the biased error model and the induced error is
$O(m|1_{c}\langle\left|\psi_{c}\right\rangle|^{2})$ for a state transfer of
$m$ steps. We emphasize that the error-robust implementation of the FANOUT and
state-transfer protocols is possible because the state of all qubits is known
at each step of the evolution.

###  VI.2 Scalable implementation of $C_{x_{0}}U_{1}\cdots U_{k}$ and $V_{\rm
OHE}$

In this section, we utilize the FANOUT and state transfer protocols discussed
above to construct the modular and distributed versions of the
$C_{x_{0}}U_{1}\cdots U_{k}$ and $V_{\rm OHE}$ gates. We assume that the
control conditions are given by $k$HE bistrings, and all telecommunication
ports are initiated to $\left|0\right\rangle$. Given these constructions, the
implementation of modular and distributed versions of LCU-based QSP walk
operators, and their controlled versions are straightforward.

####  VI.2.1 $C_{x_{0}}U_{1}\cdots U_{k}$

A modular and distributed version of $C_{x_{0}}U_{1}\cdots U_{k}$ can be
implemented by first applying a $k$-qubit controlled NOT operation on an
additional ancilla $A_{c}$ conditionally on the $k$-bit control condition
$x_{0}$ being satisfied. Then, the state of $A_{c}$ can be broadcasted to the
$O(k)$ receiver ancillae $\\{R^{(t)}_{i}\\}$ associated with the subsystems of
the target register, using a FANOUT protocol as depicted in Fig. 9. Lastly,
(denoting the length of the Pauli string on the $i^{\rm th}$ subsystem of the
target register as $k_{i}$), the controlled unitary
$C_{R^{(t)}_{i}}U_{1}\cdots U_{k_{i}}$ is applied to the $i^{\rm th}$
subsystem of the target register and the control and FANOUT circuits are
uncomputed. Next, we discuss how the FANOUT and the state transfer protocols
introduced in the previous subsection allows each step of
$C_{x_{0}}U_{1}\cdots U_{k}$ to be implemented in an error-robust manner.

First, in order to apply a $k$-qubit controlled unitary over $O(k)$ subsystems
of the $k$HE control register, we make use the state transfer protocol
described in the last subsection. To describe our protocol, we first determine
the subsystems of the control register that are relevant for the desired
$k$-qubit control condition. Then, because each of the $k$ control registers
is in a OHE state, the control condition $x_{0}$ can be checked via one
subsystem per control register. We denote the relevant subsystem of the
$i^{\rm th}$ ($i\in[k]$) control register as $s_{i;j(i,x_{0})}$ (notice that
$j$ is a function of the control condition $x_{0}$). The state transfer
protocol is used to transfer whether the control condition is satisfied in
subsystem $s_{i;j(i,x_{0})}$ to the receiver ancilla $R_{i-1,j(i-1,x_{0})}$ of
$s_{i-1;j(i-1,x_{0})}$ (See Fig. 8). Repeating this state transfer protocol
starting from the $k^{\rm th}$ control register to the $1^{\rm st}$ control
register, we ensure that the $A_{c}$ is excited to the Rydberg state only if
the $k$-bit control condition is satisfied. The $k$-qubit controlled NOT
operation does not induce errors when the first control register violates the
control condition, in which case all ancillae used for state transfer steps
remain in the $\left|0\right\rangle$ state. Hence, the $C_{x_{0}}$NOTc gate
has an EBGC of $O(kn_{\rm sub}^{(c)1/d}|\beta^{1}_{l}|^{2})$, where $n_{\rm
sub}^{(c)}$ is the number of subsystems per One-Hot-Encoding ancillary
register.

Next, to implement the conditional $k$-local Pauli operation acting on $O(k)$
subsystems in the target register, we use the FANOUT protocol to transfer the
state of $A_{c}$ to the $O(k)$ subsystems of the target register. Because the
FANOUT protocol preserves the error bias, the associated EBGC scales as
$O(kn_{\rm sub}^{(t)1/d}|\beta^{(1)}_{l}|^{2})$, with $n_{\rm sub}^{(t)}$ is
the total number of subsystems in the target register.

Finally the required Pauli operations are applied on each subsystem of the
control register conditionally on the state of the corresponding receiver
ancillae. Again, the biased error model is preserved, and the EBGC associated
with the implementation of Pauli operations is only
$O(k|\beta^{(1)}_{l}|^{2})$, . As a result, the total error probability of
implementing a $k$-qubit controlled $k$-local Pauli operation scales as
$O(k(n_{\rm sub}^{(c)1/d}+n_{\rm sub}^{(t)1/d})|\beta^{1}_{l}|^{2})$. On the
other hand, the implementation of $C_{x_{0}}U_{1}\cdots U_{k}$ has a gate
complexity that scales as $O\left(k(n_{\rm sub}^{(c)1/d}+n_{\rm
sub}^{(t)1/d})\right)$, and our implementation is error-robust. The time
complexity of the protocol is $O(n_{\rm sub}^{1/d})$.

We can implement $\bar{U}_{k{\rm HE}}$ in a scalable way by applying a
sequence of $N$ $k$-qubit controlled Pauli operations conditioned on a $k$-HE
control register. The EBGC of this implementation is $O(k(n_{\rm
sub}^{(c)1/d}+n_{\rm sub}^{(t)1/d}))$, and is independent of the number $N$ of
$k$-qubit controlled Pauli operations.

####  VI.2.2 $V_{\rm OHE}$

The unitary $V_{\rm OHE}$ acting on $n_{\rm sub}$ subsystems of size $n_{j}$
achieves the following transformation

$\displaystyle V_{\rm OHE}\prod_{j}^{n_{\rm sub}}\left|0\right\rangle^{\otimes
n_{j}}=$ $\displaystyle=\sum_{j=1}^{n_{\rm
sub}}\beta_{j}\sum_{i=1}^{n_{j}}\alpha_{i}^{(j)}\left|0\right\rangle^{\otimes
n_{0}}\cdots\left|0\right\rangle^{\otimes
n_{j-1}}\otimes\left|\rm{ohe},i\right\rangle_{j}\otimes$
$\displaystyle\quad\left|0\right\rangle^{\otimes
n_{j+1}}\cdots\left|0\right\rangle^{\otimes n_{\rm sub}},$ (34)

where $\left|\rm{ohe},i\right\rangle_{j}$ is a One-Hot Encoding computational
basis state of the subsystem $s_{j}$, and $\alpha_{i}^{(j)}$ are the OHE
amplitudes of the $j^{\rm th}$ subsystem. Unitarity entails $\sum_{j}^{n_{\rm
sub}}|\beta_{j}|^{2}=\sum_{i=1}^{n_{j}}|\alpha_{i}^{(j)}|^{2}=1$.

In order to implement $V_{\rm OHE}$ in a scalable manner, we need to design a
protocol where the unitary $V_{\rm OHE}^{(j)}$ is applied only (i) with a
probability amplitude $\beta_{j}$ and (ii) if all the atoms in the register
are in the $\left|0\right\rangle$ state. To overcome these challenges, we
introduce the processor ancillae $Q_{j}$ for each subsystem. Then $V_{\rm
OHE}$ can be implemented over $n_{\rm sub}$ subsystems using single-qubit
controlled version of $V_{\rm OHE}^{(j)}$ conditioned on $Q_{j}$ being in the
$\left|1\right\rangle_{Q_{j}}$ state. The single-qubit controlled $V_{\rm
OHE}^{(j)}$ allows us to (i) impose the probability amplitude $\beta_{j}$ to
each $V_{\rm OHE}^{(j)}$, and (ii) determine whether $V_{\rm OHE}^{(j)}$ is
implemented without using a multi-qubit controlled measurement.

The protocol that we propose for implementing the distributed version of
$V_{\rm OHE}$ is the following. First, set all antenna ancillae to the state
$\left|0\right\rangle$. Then, for each subsystem $s_{i}$ with $i\geq 1$
[arranged along a line as in Fig. 9 b)],

  1. 1.

(Query whether $V^{(j)}_{\rm OHE}$ applied for $1<j<i$.) Transfer the state of
$A_{i-1}$ to $R_{i}$. Uncompute the ancillary qubits $\\{T_{i-1,i}\\}$.

  2. 2.

(Input coefficient $\beta_{i}$) Apply a single-qubit rotation to $Q_{i}$ along
the $x$-axis by an angle $\theta_{i}\equiv\arcsin{(\beta_{i})}$

  3. 3.

Apply $C_{01;R_{i}Q_{i}}V^{(i)}_{\rm OHE}$

  4. 4.

(if $V^{(l)}_{\rm OHE}$ for $l\leq i$ is applied, turn on antenna ) Apply
$C_{\neq 00;R_{i}Q_{i}}X_{A_{i}}$.

  5. 5.

Repeat for the $i+1$-st subsystem, until $i=n_{\rm sub}$.

The protocol completes in $O(n_{\rm sub})$ steps, which is optimal in one-
dimensions, but suboptimal in higher dimensions. However, the condition that
each subsystem should receive the information from every other subsystem is a
constraint that likely makes an implementation with circuit depth $O(n_{\rm
sub}^{1/d})$ impossible. The EBGC of the above protocol is $O(n_{\rm sub})$
due to the gates applied to on the telecommunication port of each subsystem.
Lastly, note that as discussed in Section III, the ancillary qubits do not
need to be uncomputed for a successful implementation of the LCU-based block
encoding.

##  VII Implementation of Optimal Hamiltonian simulation protocols on the
Rydberg atom platform

In the previous section, we demonstrated that the implementation of the
algorithmic primitives of the QSP framework in Rydberg atoms is error-robust
and scalable. Next, we focus on Hamiltonian simulation as a particular
application of QSP. We first give an overview of different approaches to the
Hamiltonian simulation problem, including (i) Hamiltonian simulation
algorithms based on product formulas, (ii) QSP-based optimal Hamiltonian
simulation of generic Hamiltonians, and (iii) optimal simulation algorithm of
Ref. [58] for geometrically local Hamiltonians (which we oversimplistically
refer to as block-decimated QSP). In Section VII.2, we compare these three
approaches by comparing the EBGC counts and circuit depths for implementations
on the Rydberg atom platform. The details of each Hamiltonian simulation
algorithm, as well as the explicit calculations of EBGC and circuit depth are
presented in Appendix D

###  VII.1 Hamiltonian simulation

The use of physical quantum systems to simulate quantum dynamics has a rich
tradition. The task of quantum Hamiltonian simulation is simply stated: given
any initial state $\left|\psi_{0}\right\rangle$ of $n$ qubits, a Hamiltonian
$H$ and evolution time $t$, construct a sequence of quantum gates, which
approximates the final state
$\left|\psi_{f}\right\rangle=e^{-iHt}\left|\psi_{0}\right\rangle$. In Ref.
[49], Lloyd provided the first demonstration that this task is feasible. The
strategy of what is now known as product formulas (PF) [41] is to make use of
the algebraic structure of the local terms in the expansion
$H=\sum_{l=1}^{L}H_{l}$ through the Baker-Campbell-Haussdorf identity

$\displaystyle\exp{(-iHt)}=$
$\displaystyle=\left(e^{-iH_{1}t/r}e^{-iH_{2}t/r}\cdots
e^{-iH_{N}t/r}\right)^{r}+O\left(\frac{(L\Lambda t)^{2}}{r}\right),$

where $\Lambda=\max_{l}|H_{l}|$, and $r$ is the number of time slices used in
the approximation. For a fixed error tolerance $\epsilon$, and a geometrically
local Hamiltonian for which $O(L)=O(n)$ the number of time slices required is
quadratic in the simulated space-time volume $r=O((nt)^{2}/\epsilon)$. Since
each time slice has $O(n)$ operations, the total gate complexity of the PF
algorithm is $O(n^{3}t^{2}/\epsilon)$. Higher order PF exist [77], and at
order $2k$ the dependence of the the gate complexity on the system size
improves to $O(5^{2k}n^{2}t/\epsilon^{1/2k}))$, although in the limit of large
$k$ the prefactor becomes prohibitive. Recently Ref. [78] showed that in the
case of a one-dimensional system with nearest-neighbor interactions, the gate
complexity can be reduced by a factor of $n$ using an integral representation
of the Trotterization error, and the resulting algorithm has a gate complexity
of $O((nt)^{1+1/2k}/\epsilon^{1/2k})$ which scales almost linearly in the
simulated space-time volume.

The PF algorithm of Ref. [78] for the 1D system with nearest-neighbor
interactions analytically demonstrates the validity of arguments put forward
by Jordan, Lee, and Preskill [79] which claimed that the simulation of quantum
dynamics generated by geometrically local Hamiltonians requires a gate
complexity at least linear in the simulated space-time volume. The more
general question: “Can the same gate complexity be obtained for any time-
dependent local Hamiltonian?” was answered affirmatively by Haah, Hastings,
Kothari, and Low [58], and the gate complexity of the algorithm, $O(nt{\rm
polylog}(nt/\epsilon))$ was proved to be optimal even for simulating only
local observables. Optimal Hamiltonian simulation algorithm of Ref. [58] makes
use of two facts. The first is known as Lieb-Robinson bounds [80, 81], which
constrain how information spreads in local Hamiltonian systems. The second is
that the novel algorithmic frameworks of LCU and QSP enables optimal
Hamiltonian simulation in a small subsystem with respect to all parameters
(i.e, with polynomial cost in the system size while achieving a
polylogarithmic dependence on the error threshold)[57].

For generic Hamiltonians, [57] showed that the QSP-based simulation algorithm
has optimal query complexity. However, whether the gate complexity of the
algorithm is optimal depends on the gate complexity of the QSP walk operator.
Considering the implementation of the walk operator described in our work, the
gate complexity of implementing the walk operator scales as $O(N)=O(n^{k})$
for a $k$-local Hamiltonian, resulting in a total gate complexity of
$O(N^{2}t)$, which is not optimal even for geometrically local Hamiltonians.
On the other hand, our results show that it is possible to implement the walk
operator for $k$-local Hamiltonians with constant EBGC. Together with the
optimal query complexity of the QSP-based Hamiltonian simulation, we
conjecture that the scaling of the error probability is optimal for $k$-local
Hamiltonians.

Figure 10: a) The EBGCs and b) the circuit depth of Hamiltonian simulation
algorithms (i) based on the fourth-order product formula (blue, Ref. [48]),
(ii) QSP-based local Hamiltonian simulation (orange , Ref. [58]) which uses
block-decimation, and (iii) QSP-based Hamiltonian simulation (green, Ref.
[57]). We assume that the QSP-based Hamiltonian simulation of Ref. [57] can be
implemented without the scalable protocols discussed in Section VI. While from
the point of view of depth complexity, the fourth-order product formula is
superior in all system sizes considered, the QSP-based Hamiltonian simulation
of Ref. [57] exhibits the lowest implementation overhead in terms of EBGCs,
achieving more than an order of magnitude reduction compared to the fourth
order product formula, while simultaneously exhibiting better asymptotic
scaling.

###  VII.2 Results

We calculate the EBGC and circuit depth of three Hamiltonian simulation
algorithms for the one-dimensional disordered transverse field Ising model:
(i) fourth-order product formula, (ii) block-decimated QSP of Ref. [58], and
(iii) QSP-based simulation algorithm of Ref. [57]. The results are displayed
in Fig. 10.

Most strikingly, the QSP-based Hamiltonian simulation of Ref. [57] has an EBGC
(green in Fig. 10 a) ) that is more than an order of magnitude smaller than
that of the simulation based on the fourth-order product formula (in blue),
for $n_{\rm site}=50$. The optimal local Hamiltonian simulation algorithm of
Ref. [58] has an increased overhead (in orange) due to the block-decimation,
which results in a substantial overhead in the query complexity in comparison
to the algorithm of Ref. [57]. Note that since the scaling of EBGC for both
QSP-based Hamiltonian simulations are optimal, there is no system size for
which the fourth order product formula is more robust to errors than its QSP-
based counterparts.

From the point of view of the circuit depth, the fourth order product formula
results in the shortest circuit depth Hamiltonian simulation for NISQ devices,
although the optimal local Hamiltonian simulation of Ref. [58] has a better
scaling. Note that the time complexity of the QSP-based Hamiltonian simulation
of Ref. [57] shows suboptimal scaling as it does not take advantage of the
geometric locality to parallelize the simulation.

As a result, the choice of using product formula vs. QSP-based Hamiltonian
simulation on the Rydberg atom platform depends on the errors relevant for the
implementation. If the lifetime of the logical states are the main contributor
to the decoherence, then using the product-formula-based Hamiltonian
simulation is the most advantageous. On the other hand, if the logical states
are long-lived and the majority of errors are introduced during gate
operations, and it is possible to implement controlled unitaries with biased
errors, then QSP-based Hamiltonian simulation has a clear advantage.

##  VIII Conclusions and Outlook

Conclusions: Our work has two main messages. First, it is possible to design
implementations of a wide range of quantum protocols where the error-
probability scales slower than the gate complexity, by co-tailoring the
relevant error-model and the compilation method. Second, the Rydberg atom
platform is exceptionally well-suited for realizing such error-robust
implementations in a hardware efficient manner.

To design error-robust implementations, we took the structure of two general
compilation methods, LCU-based block-encoding unitaries and QSP, as a guide to
determining a structured error model, as formalized in the EBGC we introduce
in Section IV.1.2. Besides being very general and having near-optimal query
complexity, the iterative QSP protocols allowed us to focus solely on an
error-robust implementation of a walk operator. On the other hand, the most
decisive property of the LCU method was that it allowed the address states
(see Section III) to be chosen from $k$-Hot Encoding bitstrings, which
drastically reduced the ancillae requirements.

Two observations on the Rydberg atom platform were crucial in achieving an
error-robust implementation. First is the availability of biased-error single-
qubit controlled Pauli operations using Rydberg atoms. Physically, the
protocol for these gates minimizes the laser power that is absorbed by the
Rydberg atoms during the implementation, conditionally their initial state. As
a result, the gate induced errors are only relevant when the control condition
is satisfied. The second observation is the availability of a One-Hot Encoding
(OHE) state preparation using Rydberg atoms. Concatenation of OHE state
preparation unitaries result in a $k$-Hot Encoding state, which can be used to
encode many address states for the LCU method without drastically increasing
the size of the control register. The versatility of the Rydberg atoms was
also crucial in demonstrating that the error-robust implementations of QSP
protocols are scalable ( see Section VI).

We also highlighted the efficiency of our proposed implementation of
Hamiltonian simulation in terms of the error-bounded gate complexity, by
comparing it to a state-of-the-art implementation of product-formula-based
Hamiltonian simulation algorithm.

We determined the error-robustness of our implementations based on the Error
Bounded Gate Count (EBGC) introduced in Section IV.1.2. The accuracy of EBGC
relies crucially on whether one can implement a single-qubit controlled Pauli
with a strong suppression of the error probability conditionally on the state
of the control register. We showed that such a suppression is possible at the
expense of increased laser drive amplitude. Most importantly, the suppression
of the error rate is proportional to the intensity of the drive amplitude,
rather than the amplitude as is the case of conventional implementations of
multi-qubit gates [3, 46]. The quadratic improvement of error-robustness with
respect to the laser amplitude sets our proposed implementation apart from
other gate protocols in Rydberg atoms. Lastly, we showed in Section IV that
using currently available Rabi frequencies, it is possible to suppress the
gate induced error rate up to a factor of hundred.

Outlook: Given the generality of QSP and LCU frameworks, and the recent
successes of the Rydberg atom platform [15, 30], we foresee many promising
avenues of research that originate from our work. First, our techniques can be
extended to implementing algorithms based on Quantum Singular Value
Transformation (QSVT) in a straightforward manner. A crucial question in this
direction is whether the properties of Rydberg atoms provide other substantial
advantages in realizing specific QSVT-based algorithms. In particular, whether
the versatility of Rydberg atoms allow for efficient and error-robust
implementations of the phase rotations of the form
$\exp{i\phi(2\Pi-\mathbf{I})}$ [43] is an open question. Second, our work
demonstrates that block-encoding unitaries for geometrically local operators
have error-robust implementations using shallow circuits. It is therefore
important to understand the power of QSP protocols which process geometrically
local signal operators.

Our work also provides opportunities to explore important questions for the
realization of fault-tolerant quantum computation using Rydberg atoms. In
particular, a demonstration of the compatibility of the error-robust
implementation presented and the fault-tolerant architecture proposed by Ref.
[34] would greatly ease the resource requirements for realizing FTQC on the
Rydberg atom platform. Moreover, our results motivate the search for new and
more versatile biased-error gate protocols which can further improve error-
robustness with reduced classical resource requirements. Lastly, the question
of whether sparse encodings (e.g., the $k$-Hot Encoding address states) are
useful in the context of quantum algorithmic frameworks, such as variational
quantum algorithms, seems to be a widely open.

###### Acknowledgements.

S.Z. and S.S. thank I. Chuang, M.D. Lukin, D. Bluvstein, I. Cong, S. Ebadi,
and A. Keesling for insightful comments and helpful discussions. S.Z.
acknowledges the financial support from the Swiss National Science Foundation
through the Early Postdoc.Mobility grant (P2EZP2_184320) and from the Army
Research Office, ARO MURI (grant no W911NF1910517). S.S. and S.Z. acknowledges
NTT Research for their financial and technical support.

##  Appendix A Quantum Signal Processing

We begin our discussion with the quantum control theory of a single qubit. The
pioneering work of Ref. [42] asked the following question. Given two unitary
operations on a single-qubit $G(\phi)=e^{i\phi\sigma_{z}}$, and
$R(\theta)=-ie^{i\pi/4\sigma_{z}}e^{i\theta\sigma_{x}}e^{-i\pi/4\sigma_{z}}$,
with Pauli operators $\sigma_{i=x,y,z}$, what single-qubit transformations can
we design by the following sequence of gates

$\displaystyle G(\phi_{k})R(\theta)G(\phi_{k-1})R(\theta)\cdots
G(\phi_{1})R(\theta)G(\phi_{0})$ (35)

alternating between $G(\phi)$ and $R(\theta)$ while keeping $\theta$ constant
and varying $\phi_{i}$ between each iteration.

The concept of signal processing is established by considering $cos(\theta)=x$
as the signal encoded in the signal unitary

$\displaystyle R(\theta)=\left(\begin{array}[]{cc}x&\sqrt{1-x^{2}}\\\
\sqrt{1-x^{2}}&-x\end{array}\right),$ (38)

which is to be processed by the control angles $\\{\phi_{i}\\}$. We emphasize