#  LILLIPUT: A Lightweight Low-Latency Lookup-Table Based Decoder for Near-
term Quantum Error Correction

Poulami Das  Google Quantum AI, Google Research, Mountain View, CA, USA
Department of Electrical and Computer Engineering, Georgia Institute of
Technology, Atlanta, GA, USA  Email<EMAIL_ADDRESS>Aditya Locharla
Google Quantum AI, Google Research, Mountain View, CA, USA  Cody Jones  Google
Quantum AI, Google Research, Mountain View, CA, USA

###### Abstract

The error rates of quantum devices are orders of magnitude higher than what is
needed to run most quantum applications. To close this gap, Quantum Error
Correction (QEC) encodes logical qubits and distributes information using
several physical qubits. By periodically executing a syndrome extraction
circuit on the logical qubits, information about errors (called syndrome) is
extracted while running programs. A decoder uses these syndromes to identify
and correct errors in real time, which is required to use feedback implemented
in quantum algorithms [32]. Unfortunately, software decoders are slow and
hardware decoders are fast but less accurate. Thus, almost all QEC studies so
far have relied on offline decoding.

To enable real-time decoding in near-term QEC, we propose LILLIPUT– a
Lightweight Low Latency Look-Up Table decoder. LILLIPUT consists of two parts–
First, it translates syndromes into error detection events that index into a
Look-Up Table (LUT) whose entry provides the error information in real-time.
Second, it programs the LUTs with error assignments for all possible error
events by running a software decoder offline. LILLIPUT tolerates an error on
any operation in the quantum hardware, including gates and measurement, and
the number of tolerated errors grows with the size of the code. It needs <7%
logic on off-the-shelf FPGAs that allows it to be easily integrated alongside
the control and readout circuits in existing systems [9]. LILLIPUT incurs a
latency of few nanoseconds and enables real-time decoding. We also propose
Compressed LUTs (CLUTs) to reduce the memory needed by LILLIPUT. By exploiting
the fact that not all error events are equally likely and only storing data
for the most probable error events, CLUTs reduce the memory needed by up-to
107x (from 148 MB to 1.38 MB) without degrading accuracy.

##  1 Introduction

Quantum computers promise substantial speedup over conventional machines for
many important applications [38, 52]. Unfortunately, high error-rates of
quantum devices (about 1% on existing hardware [6]) limit us from running
these applications as they require lower error-rates (below $10^{-10}$) [37,
36, 27, 34]. To bridge this gap, quantum information must be protected by
using Quantum Error Correction (QEC). QEC codes encode a logical qubit by
distributing information over many physical qubits [51, 5, 7, 29, 24]. With
increasing redundancy of the QEC code, the logical error-rate reduces
exponentially if the physical error-rate is below a threshold [5]. Thus, by
controlling the redundancy, QEC enables us to achieve the error-rate needed to
run a particular application.

QEC consist of both quantum and classical counterparts. On the quantum side, a
logical qubit encodes quantum information in the combined state of multiple
data qubits and uses parity qubits interspersed between them to gather
information about errors, as shown in Figure 1(a). Each parity qubit
periodically extracts the parity information of a subset of data qubits by
executing a syndrome extraction circuit and projects the errors encountered by
the data qubits into discrete errors. The process is repeated from the time
qubits are initialized and until the data qubits are measured (called logical
measurement). Each iteration of syndrome extraction is termed as a QEC cycle
or round and the measurement outcome of all the parity qubits is called a
syndrome. On the classical side, a decoder uses the syndromes to detect errors
and determine the optimal correction for the data qubits. The logical error-
rate depends on the physical error-rate as well as the performance of the
decoder. High physical error rates make QEC codes ineffective [5]. Similarly,
if a decoder is inaccurate or fails to determine the correction in real-time,
errors can accumulate. Real-time decoding refers to the detection and
correction of errors dynamically as syndromes are received in each QEC cycle
and before the arrival of the syndrome in the next cycle. Inaccurate decoding
or failure to decode in real-time may lead to logical failure during program
execution. Therefore, accurate and real-time decoders are essential for QEC.

Figure 1: (a) In QEC, a logical qubit is encoded using a set of data and
parity qubits. The parity qubits repeatedly extract the syndrome between qubit
initialization and logical measurement. (b) LILLIPUT takes the syndrome and
logical measurement outcomes as inputs, detects errors, obtains the error
assignments for each data qubit from a Look-Up Table (LUT), and tracks an
error log every QEC cycle. Finally, it computes the logical error by comparing
the logical measurement and the error log.

In recent years, several preliminary QEC experiments involving repetition
codes and Bacon-Shor codes have been successfully demonstrated [14, 50, 41,
62, 47, 58, 48, 15, 60, 59, 13, 21, 39]. However, reaching low logical error
rates requires implementation of more efficient QEC codes such as surface
codes [33], and recent studies [13, 8, 11, 40] have taken a step in this
direction. Unfortunately, QEC studies so far have mainly resorted to offline
decoding because most software decoders are slow [22]. Alternately hardware
decoders are faster but have poor accuracy. Additionally, hardware decoders
require custom design [16] or superconducting devices [30, 57] and therefore,
building them in near-term requires significant engineering effort, are
expensive, and sometimes impractical due to technology limitations
(superconducting decoders for example). With improving device quality and size
of quantum systems, QEC studies involving small surface codes that span
multiple QEC cycles and use real-time decoding represent the next significant
milestone in QEC. Consequently, there is a growing demand and need for
accurate, fast, and low-cost decoding solutions in near-term QEC. To address
this challenge, in this paper, we propose LILLIPUT– a Lightweight Low Latency
Look-Up Table decoder for small surface codes.

Our proposed design LILLIPUT is an end-to-end system that directly interfaces
with the qubit readout circuits, detects and corrects errors in real-time, and
computes the logical error. LILLIPUT performs three key steps in hardware,
shown in Figure 1(b)– (1) translates the syndromes every QEC cycle into error
detection events, (2) assigns errors to each data qubit from a Look-Up Table
(LUT) and maintains an error log in real-time, and (3) computes the logical
error by comparing the logical measurement outcomes with the most up-to-date
error log. Additionally, LILLIPUT programs the LUT by running a software
decoder offline for all possible error events.

For high accuracy, a decoder must correct (a) errors that accumulate on data
qubits, (b) gate and (c) measurement errors in the syndrome extraction
circuit, and (d) errors on data qubit measurements during the logical-
measurement stage. LILLIPUT tackles all these errors by decoding multiple
rounds of syndrome and by converting the logical measurement data into an
appropriate syndrome in the last cycle. The accuracy and complexity of a
decoder depends on the decoder configuration, a combination of the QEC code
redundancy and the number of syndrome rounds used in decoding. As LILLIPUT is
fully modular and reconfigurable, it can be implemented across a wide range of
decoder configurations. LILLIPUT programs the LUTs offline using the software
Minimum Weight Perfect Matching (MWPM) decoder [25, 23], widely used for its
combination of high accuracy and polynomial time complexity. The MWPM decoder
may produce multiple possible error assignments for a single error event. For
greater accuracy, LILLIPUT considers the error model of the device (we use
Google Sycamore [6]) and selects the most probable error. As LILLIPUT is
reconfigurable, it can be adapted to other decoding algorithms, device error
models, and QEC codes.

Instead of determining errors using hardware or software at run time, LILLIPUT
transforms this step into a single memory access and therefore, incurs a
deterministic low latency depending on the decoder configuration. LILLIPUT has
low hardware complexity and fits on off-the-shelf FPGAs. As most existing
quantum systems [9, 1] use FPGAs for delivery of control instructions to
qubits and implementation of readout interface, it can be seamlessly
integrated on these systems. Overall, LILLIPUT is accurate, fast, and
lightweight which makes it an ideal candidate for decoding in near-term QEC.

LILLIPUT incurs high memory overhead to store the LUTs and requires a memory
external to the FPGAs for some decoder configurations. To address this
challenge, we propose Compressed Look-Up Tables (CLUTs). CLUTs exploit the
fact that not all entries of a LUT are accessed with equal probability. This
behavior arises from the nature of surface codes, where errors on data qubits
only flip adjacent parity qubits. Infrequent errors flip a few parity qubits.
Alternately, more errors affect multiple locations that are more likely to
flip the parity qubits back and forth and result in few bit flips overall.
Consequently, the Hamming weight (number of ones) of the memory address
accessed is typically low. CLUTs leverage this insight and only store entries
corresponding to addresses of low Hamming weights that are most likely to be
accessed. CLUTs determine the cut-off Hamming weight such that LILLIPUT
encounters a decoder failure due to missing LUT entries with probability equal
to or lower than the logical error rate and thus, does not impact the overall
accuracy.

The reconfigurability of LILLIPUT allows us to perform a design space
exploration across various decoder configurations and understand the trade-off
between the accuracy and complexity of a decoder. Our studies with small
surface codes show that LILLIPUT achieves high accuracy. The decoding latency
(time from the arrival of syndrome to error assignment) ranges between 29-42
ns for the decoder configurations studied in this paper. LILLIPUT requires up-
to 7% logic utilization on off-the-shelf FPGAs [3, 2, 4] and thus, is
extremely lightweight. Lastly, CLUTs reduce the memory requirement of LILLIPUT
by up-to 107x (from 148 MB to 1.3 MB) without sacrificing decoding accuracy.

Overall, this paper makes the following contributions:

  1. 1.

We propose LILLIPUT, a lightweight low latency lookup table decoder for small
surface codes (requires <7% logic elements on FPGAs). It offers high accuracy
as it can tolerate errors on both data qubits as well as in the syndrome
extraction circuit; and requires a decoding latency within 42 ns.

  2. 2.

To the best of our knowledge, LILLIPUT is the first fully reconfigurable
system-level decoding solution that can be seamlessly integrated with existing
quantum systems.

  3. 3.

We propose Compressed Look-Up Tables (CLUTs) to reduce the memory overhead of
LILLIPUT. By only storing data for the most probable error events, CLUTs
reduce the memory required by up-to 107x, without sacrificing the accuracy.

##  2 Background and Motivation

###  2.1 Qubits and Quantum Error Correction

A quantum bit, or qubit, is the fundamental unit of information in a quantum
computer. The state of a qubit can be represented as a superposition of its
basis states $\ket{0}$ and $\ket{1}$, with complex valued amplitudes for these
states [43]. Unfortunately, qubit devices retain information for only a short
span of time (about few microseconds) and quantum operations have very high
error rates (about 1%) [6]. These factors limit us from executing most quantum
applications on existing hardware. To run programs without encountering
errors, quantum information must be protected by using Quantum Error
Correction (QEC) [51, 5, 7, 29, 24].

QEC codes encode a logical qubit using a set of data and parity qubits. The
data qubits collectively store the quantum information, whereas the parity
qubits periodically extract information about errors on the data qubits by
executing a syndrome extraction circuit. Measuring the parity qubits every QEC
cycle allows the QEC code to project any errors on data qubits into a discrete
set of Pauli errors. The bit-flip (X) error swaps the probability amplitudes
of the basis states, whereas the phase-flip (Z) error introduces a relative
phase of -1 between them. The Pauli Y error denotes simultaneous X and Z
errors. The measurement outcomes of the parity qubits, called syndrome, is
analyzed by a decoder to detect and correct errors encountered by the data
qubits. To perform computations, fault-tolerant quantum computers must perform
error correction continuously while running an algorithm.

###  2.2 Surface Code

The surface code [26, 33, 20, 46] is widely considered to be the most
promising QEC code as it can tolerate high thresholds [54] and requires only
nearest-neighbor connectivity. It encodes a logical qubit into a 2-dimensional
lattice of alternating data and parity qubits. The size and layout of the
lattice depends on the code distance $d$ which determines the code redundancy
and the length of the shortest error chain ($\frac{d+1}{2}$) that cannot be
corrected. An error on a data qubit is detected by the adjacent parity qubits
by executing a syndrome extraction or stabilizer circuit, where each parity
qubit measures a four qubit operator called a stabilizer. X errors are
detected by the Z stabilizers, whereas Z errors are detected by the X
stabilizers [28]. For example, Figure 2(a) shows the layout of distance $3$
regular surface code that can correct error chains of length 1. It consists of
13 data qubits (qubits A to M) and 12 parity qubits (qubits $Z_{0}$ to $Z_{6}$
and $X_{0}$ to $X_{6}$). An X error on data qubit D is detected by the Z
stabilizers $Z_{0}$ and $Z_{2}$, whereas a Z error on this qubit is detected
by the X stabilizers $X_{0}$ and $X_{1}$.

Figure 2: Distance 3 (a) regular and (b) rotated surface code. X errors are
detected by the Z stabilizers (in blue) and Z errors are detected by the X
stabilizers (in red). (c) Z stabilizer circuit

Figure 2(b) shows the layout of distance $3$ rotated surface code that is
obtained by rotating the lattice of a regular surface code by 45 degrees and
removing some of the data and parity qubits. The rotated code requires fewer
qubits and gate operations to extract a syndrome. Therefore, the rotated
surface code is preferred over regular lattices for near-term experiments, so
we focus on rotated codes in this paper.

###  2.3 Error Decoding in Real-time

A decoder uses the output of stabilizer measurements, the syndrome, to
determine a set of corrections that must be applied to the data qubits. By
convention, the syndromes generated by the X stabilizers are called X
syndromes and are decoded using an X decoder. Similarly, the syndromes
generated by the Z stabilizers are called the Z syndromes and decoded using a
Z decoder. Decoders must accurately identify errors in real-time to prevent
accumulation of errors. The maximum latency that can be tolerated by a decoder
is the latency of the syndrome extraction circuit, an example of which is
shown in Figure 2(c). The circuit has a latency of about 1 $\mu$seconds which
is derived existing device technology [6, 13]. Errors must be corrected within
this time and designing accurate and fast decoders is an active area of
research. Typically, software implementations are slow [22] and hence, more
recently decoders have been proposed that uses custom hardware [16] and
superconducting devices [30, 57] to enable fast decoding.

###  2.4 Motivation: Near-term QEC

QEC is essential to realize the potential of quantum computers in practice. As
the device quality and system size continues to improve, there is increasing
interest in studying QEC codes and real-time decoding. Several demonstrations
of repetition codes, Bacon-Shor code have been successful [14, 50, 41, 62, 47,
58, 48, 15, 60, 59, 13, 21, 39]. While these experiments represent a
significant milestone in QEC, unlike surface codes, these codes can only
correct either phase-flip or bit-flip errors but not both. Also, QEC
experiments so far have mainly relied on offline software-based error
decoding. The largest surface code demonstrated so far is distance 2 [13, 8,
11, 40]. With improving device quality, quantum hardware may soon reach the
level of 1% error per data qubit per syndrome cycle, where quantum error
correction can function (involving surface codes of distance 3 and beyond).
Thus, QEC experiments that demonstrate small surface codes using real-time
decoding is a reasonable major milestone for QEC in the next few years.

###  2.5 Challenges in Real-time Decoding

Real-time decoding is necessary to prevent accumulation of errors on data
qubits. If errors are not corrected within a QEC cycle before the arrival of
the next syndrome, errors may accumulate resulting in a logical failure. The
decoding complexity depends on the error events and software decoders may be
too slow for real-time decoding [22]. They also incur significant
communication overheads in transmitting the syndromes into software running on
a CPU. This high latency of software decoders limits the use of general
purpose computing for online decoding and therefore, almost all QEC
experiments that use software decoders have resorted to offline decoding. In
the first instance of real-time decoding [49], software decoders have been
used for color codes [53]. However, this study uses trapped-ion systems that
can tolerate up to few milli-seconds of decoding latency, about 3 orders of
magnitude higher than superconducting systems. The alternative is hardware
decoders that are faster and promise real-time decoding. However, they have
poor accuracy due to algorithmic and implementation limitations and rely on
custom hardware [16] or specialized devices [30, 57]. Given the current state
of superconducting device technology, it is not even feasible to implement the
SFQ decoders [30, 57] in the near-term. The number of devices required to
fabricate these decoders far exceeds the device densities of existing
superconducting technologies.

###  2.6 Goal: Decoding in Real-time for Near-term QEC

Ideally, we want a low-cost and accurate decoder that can be seamlessly
integrated with existing quantum devices while enabling real-time decoding for
near-term QEC experiments. To achieve this goal, we propose LILLIPUT– an
accurate Lightweight Low Latency Look-Up Table decoder for small surface codes
in this paper.

##  3 Evaluation Methodology

In this section we describe the benchmarks, experimental setup, and the
figure-of-merit used to evaluate our policies before discussing our design.

###  3.1 Surface Code Parameters

In this paper, we consider rotated surface codes of distance 3, 4, and 5. The
details of the layouts are described in Table 1. The total number of physical
qubits required ranges from 17 to 49. In the near-term, we expect systems with
few hundreds of qubits which would be able to fit these layouts.

Table 1: Parameters of Rotated Surface Codes Code | Data | X-ancilla | Z ancilla | Total Physical
---|---|---|---|---
Distance | Qubits | Qubits | Qubits | Qubits
3 | 9 | 4 | 4 | 17
4 | 16 | 8 | 7 | 31
5 | 25 | 12 | 12 | 49

###  3.2 Monte Carlo Simulation Infrastructure

Figure 3 shows an overview of the Monte Carlo simulator used for our studies.
The simulator generates a surface code lattice for a given code distance.
Depending upon the noise model and the physical error rate $p$, the simulator
injects errors onto the data qubits and measurement errors onto the parity
qubits, producing a syndrome every cycle. The X and Z syndromes are then
decoded independently and an error log is maintained for both error types. To
model a QEC experiment, the simulator repeats the process for multiple cycles
and terminates when the maximum number of cycles is reached. The simulator
maintains the internal state of the qubits throughout the experiment which is
then used to compute the logical measurement outcome and the logical error. We
call each such execution as a trial. For our evaluations, we use 1 million
random trials. The simulator also generates the traces used to verify the
proposed LILLIPUT micro-architecture.

Figure 3: Monte Carlo simulation framework Figure 4: Overview of LILLIPUT

###  3.3 Noise Model

We implement the phenomenological noise model [20], which inserts errors on
both data qubits and on the measurement of parity qubits. This is a standard
noise model used in QEC and has been used in several prior works. In this
noise model, a data qubit encounters an error with probability $p$ in each
cycle. The type of error is chosen uniformly from Pauli X, Y, and Z errors.
Additionally, each parity qubit encounters measurement error with probability
$p$. For simplicity, we assume the probabilities for data qubit errors to be
the same as measurement errors. This assumption is consistent with prior works
in QEC. For our studies, we consider physical error rates ranging from
$p=10^{-3}$ to $p=5\times 10^{-2}$. We consider this to be a suitable range of
error rates for quantum devices in the near term. Nonetheless, if the device
quality improves further, our design can still support those quantum
architectures.

###  3.4 Target Hardware Platforms

Our target is to implement the decoder on commercially available FPGAs as
existing quantum systems already use FPGAs for control and readout interface
logic [10, 9, 1]. For our studies we use FPGA from the Intel Cyclone 10 LP
[3], Arria V [2], and Stratix 10 [4] family as these are commercially
available.

##  4 Overview of LILLIPUT

The classical counterpart of QEC comprises of three key steps– (1) error
detection from the stabilizer measurements, (2) identification of errors and
error assignment to data qubits every cycle, and (3) computation of logical
error. The micro-architecture of LILLIPUT shown in Figure 4 accomplishes these
steps. It communicates with the readout interface, translates the stabilizer
measurement outcomes into error detection events, identifies errors, and
computes the logical error. Note that X and Z errors are decoded
independently. In the next subsections, we describe the implementation of the
design.

###  4.1 Detection of Errors from Stabilizer Measurements

In QEC, syndromes are generated every cycle by measuring the stabilizers.
LILLIPUT generates error detection events by comparing the stabilizer
measurement outcomes from two consecutive QEC cycles. Any change in the
measurement outcome of the stabilizers between two cycles indicates an error.
Alternately, no event is detected if the stabilizer measurement outcomes
remain the same. For example, Figure 5 shows Z stabilizers measurements
outcomes of a distance 3 surface code, where an error event is detected in
cycles 1 and 3, whereas no error event is detected in cycle 2. This step is
accomplished by the Event Detection Logic block shown in Figure 4. Detection
events enables us to track errors in a given cycle and are used to identify
the optimal correction.

Figure 5: Steps involved in translating the stabilizer measurement outcomes
(red denotes an error is identified) to error detection events in each QEC
cycle. The bitstream for stabilizer measurements is specified from left to
right (convention used in this paper) on the surface code lattice.

###  4.2 Error Identification as a Matching Problem

Error identification is the step in which a decoder assigns errors to each
data qubit which is tracked throughout the QEC cycles. To perform this step,
the detection events are represented on a graph, often termed as the decoding
graph, where the nodes and edges represent the parity and data qubits
respectively. The minimum weight perfect matching algorithm [25] uses the
decoding graph and matches each detection node with another or to the surface
code boundary such that the total weight of the matched edges is minimal. MWPM
is considered to be the most accurate algorithm. 111A more recent approach,
the Union-Find algorithm [19, 18], uses a different approach to matching to
generate the error assignments. It is faster than MWPM but has lower accuracy
[31]. In LILLIPUT, this step is accomplished using Look-Up Tables (LUTs), as
shown in Figure 4, and the details are described in Section 5.

###  4.3 Handling Data and Measurement Errors

For greater accuracy, a decoder must handle both errors on the data qubits as
well as errors in the syndrome extraction circuit. Overall, there are four key
sources of errors: (a) errors on data qubits (b) errors in the gate operations
during syndrome extraction (c) measurement errors on parity qubits during
stabilizer measurements, and (d) measurement errors on data qubits during
logical measurement. Next, we discuss how LILLIPUT handles each of these
errors, where we use “space” and “time” directions to describe when detection
events are generated in the same round or two consecutive cycles,
respectively.

(a) An error on a data qubit is detected by its neighboring parity qubits,
producing a space-like detection event on them in the same cycle. For example,
Figure 6(a) shows a space-like error detection event in cycle 1.

(b) Two-qubit gate errors during syndrome extraction are detected across
consecutive cycles. They produce space-time like detection events, as shown in
cycles 1 and 3 in Figure 6(b).

(c) Measurement errors on parity qubits exhibit temporal behavior and
translates into time-like detection events in two consecutive cycles, as shown
in cycles 2 and 3 of Figure 6(b).

(d) Measurement errors on the data qubits are handled in the last boundary
cycle by generating an extra syndrome of either X or Z type and is discussed
in detail in the next subsection.

To tackle the first three sources of errors, LILLIPUT processes more than a
single cycle of syndrome and performs matching on a 3-dimensional decoding
graph spanning space and time (multiple cycles). For errors in logical
measurement, LILLIPUT uses an extra syndrome as discussed in Section 4.4.

Figure 6: A distance 4 repetition code decoding graph, where nodes and edges
denote parity and data qubits respectively. Note that this is for illustration
only and our evaluations in this paper are based on surface codes. Examples of
(a) space-like (b) space-time like and (c) time-like detection events.

LILLIPUT assumes the readout logic writes the measurement outcomes on a buffer
which gets overwritten every cycle. This interface works on a much slower
clock (e.g. with 1 $\mu s$ latency) that depends on the duration of the
syndrome extraction circuit. LILLIPUT polls for new syndromes and tracks the
most recent history in a FIFO, as shown in Figure 4. The FIFO must store the
history of the last $m$ cycles, where $m$ is the number of syndrome rounds
that are simultaneously decoded. Since LILLIPUT decodes in real-time, storing
only the last $m$ rounds is sufficient. We discuss the impact of number of
measurement rounds on the logical error rate in Section 6.

###  4.4 Handling Boundary Cycles

A QEC experiment has two time boundary cycles- one at the beginning and the
other at the end. 222In QEC, cycles are also called rounds. We use the term
cycles in this paper to avoid confusion with the number of syndrome rounds
used for decoding. For the beginning time boundary cycle, the detection event
is computed by comparing the first round of stabilizer measurements and the
qubit initialization data. In the last time boundary cycle, the data qubits
are measured. To tolerate measurement errors in data qubits, LILLIPUT
translates the measurement outcomes of the data qubits into a detection event
of either X or Z type by comparing with the stabilizer measurement data from
the second-last cycle. Since a logical measurement in surface codes is
implemented by performing a transversal measurement (measuring all the data
qubits in either X or Z basis), the measurement basis of the data qubits
determines the type of the stabilizer that can be constructed from the
measurement outcomes. By default, LILLIPUT translates the data qubit
measurement outcomes into a Z syndrome because we assume the data qubits are
measured in the Z basis, as shown in Figure 4.

##  5 Error Assignments in LILLIPUT

LILLIPUT determines the most optimal error assignment by using Look-Up Tables
(LUTs). Every cycle, the history of detection events is used to index an LUT
and the LUT entry assigns errors to the data qubits in the oldest cycle. The
length of the history depends on the number of syndrome rounds used for
decoding. LILLIPUT also maintains an internal state which is updated every
cycle. The details of using LUTs in LILLIPUT and tracking the internal state
is described next.

###  5.1 Streaming Mode of Operation

LILLIPUT operates in streaming mode and maintains an error log for each data
qubit. The log is updated every cycle as errors are identified. LILLIPUT
considers a fixed number of cycles at a time which is equal to the number of
syndrome rounds used in decoding. We call this a sliding window because it
slides forward as an experiment proceeds. For example, Figure 7 shows the
sliding window for four consecutive decoding steps. LILLIPUT uses the
detection events in the sliding window and the internal state to determine the
LUT address every cycle.

Figure 7: (a) The sliding window uses detection events from cycles 1, 2, and 3
and assigns error to the oldest layer i.e. cycle 1. Note that all detection
events in the window are considered for matching but only the edges touching
the oldest cycle are considered during error assignments, shown in blue. (b-d)
The sliding window streams forward one cycle at a time.

###  5.2 Error Assignment

LILLIPUT determines the best correction by using all the detection events in
each sliding window and assigns errors only to the oldest layer. For example,
Figure 7 shows the subset of edges that the decoder uses to make the error
assignment for the current sliding window. The optimal error assignment is
stored in the LUTs and targets to neutralize the effect of all of the errors
in the oldest cycle and decoding completes once the sliding window covers all
the syndromes. The error assignments are made only to the oldest layer in each
sliding window to prevent any premature matching. Premature matching may
result in sub-optimal performance if syndromes in the future cycles can change
the assignment. Premature matching may also result if we use disjoint windows
where the window proceeds forward by its full length. In that case, errors
that span over two non-overlapping windows can cause inaccurate error
assignments. As LILLIPUT uses a sliding window, it does not encounter this
problem and therefore, does not suffer from sub-optimal performance. For the
time boundary cycles, LILLIPUT constructs a full sliding window by padding
zeros. Figure 8(c) shows a time boundary cycle where additional zeros are
padded. Since the LUT is programmed such that it assigns the most optimal
error for a sliding window, it is guaranteed to never assign errors to the
zero-padded regions.

###  5.3 Syndrome Updates and Tracking the Internal State

LILLIPUT assigns errors only to the oldest layer. However, as it performs
matching across all the events in a sliding window, it can neutralize some
errors in the second oldest cycle if the detection event has a time-like or
space-time like behavior. For example, Figure 7(d) shows a time-like detection
event that requires neutralizing events in both cycles 4 (oldest cycle) and 5
(second oldest cycle). Consequently, matching within this window removes the
detection event from the second oldest layer. Similarly, detection events may
be added as well. For example, Figure 8(a) shows an example of decoding steps
where detection events are added. To accommodate these scenarios, LILLIPUT
maintains a record of the detection events added or removed in an internal
state register. To obtain the LUT address to be accessed in a cycle, LILLIPUT
concatenates the detection events in the current window and modifies the
oldest detection event using the most recent internal state, as shown in
Figure 8. Each LUT entry provides the error assignment for the oldest layer as
well as the detection events that are added or removed in the current cycle (1
bit per parity qubit). This value is used to update the internal state
register every cycle.

Figure 8: (a) LILLIPUT finds the optimal matching in current window but adds a
detection event in cycle 2 which is tracked in the internal state register.
(b-c) The additional event is taken into account from the register. In the
boundary cycle, zeros are padded. By convention, the detection events of the
oldest cycles occupy the least significant bits. The bits for each cycle run
bottom to top from most significant position to the least.

###  5.4 Programming the LUT

LILLIPUT programs the LUT entries offline by generating all possible detection
events for a given code distance and size of the sliding window. We use the
software Minimum Weight Perfect Matching (MWPM) decoder [23]. For some events,
the MWPM decoder may provide more than one possible error assignment. In other
words, a single detection event may have multiple matching possibilities on
the decoding graph that result in minimal weight. For example, Figure 9 shows
possible error assignments on a distance 4 surface code lattice for the same
detection event. Here, the Z stabilizer at the center of the lattice indicates
an error. The MWPM decoder can assign X errors to either data qubits (a) E and
F or (b) G and H or (c) I and J. For high accuracy, we account for the error
model of the quantum hardware (we consider Google Sycamore [13]) to select the
most probable error assignment. LILLIPUT can also accommodate variability in
device error rates [55, 42] on existing systems by re-programming the LUTs. As
device characteristics remain stable over short periods of time and mainly
exhibit variability over extended periods (weeks or months) [17], the LUTs
need not be re-programmed too frequently. The reconfigurability allows
LILLIPUT to be adapted to other QEC codes, decoding algorithms, and quantum
systems.

Figure 9: Valid possible error assignments for the detection event at the
center of the distance 4 surface code lattice.

###  5.5 Determination of Logical Error

Early demonstrations of QEC will perform a memory experiment, simply showing
that error correction preserves the initial quantum state. The probability of
logical error is determined by comparing the logical measurement outcome with
the expected outcome for the state prepared. This logical measurement is
computed using the error log. Which error log (X or Z) is used depends on the
measurement basis of the logical measurement. The logical measurement bit is
computed by using a reduction XOR operation on the bitwise XOR results of the
error log and the logical measurement outcome.

##  6 Final Evaluations

In this section, we discuss the accuracy, latency, and hardware complexity of
our decoder. We consider a wide range of decoder configurations for our
evaluations to understand the trade-off between the complexity and accuracy of
a decoder.

###  6.1 Results for Accuracy

Figure 10 shows the logical error rate (LER) for distances ($d$) 3 and 4
respectively. By default, we assume 5 cycles in the experiments. The LER
scales O($p^{2}$) which is expected because distances 3 and 4 can correct at
least one error, but they sometimes fail with two errors; quadratic scaling
results from errors being independent in the model used for simulation. We
also study the impact of the number of syndrome rounds on decoding accuracy.
While $m=(d-1)$ rounds are needed to detect as many errors as the code is
capable of correcting [54], we observe that LILLIPUT performance saturates at
$m=2$ syndrome rounds for $d=4$. The LER reduces by 1.23x and 1.21x on average
for distance 3 by going from 1 to 2 and 2 to 3 rounds respectively. Similarly,
the LER reduces by 1.99x and 1.24x on average for distance 4 by going from 1
to 2 and 2 to 3 rounds respectively.

Figure 10: Accuracy of distance (a) 3 and (b) 4 surface codes for different
number of syndrome measurement rounds (m)

Figure 11 shows the logical error rate for distance 5 surface codes using 1
and 2 rounds of syndrome measurements. We restrict the number of rounds to 2
to keep the LUT sizes tractable for our simulations. We observe that the LER
scales O($p^{2}$), which is expected as using just $m=2$ rounds will lead to
some configurations of two errors not being accurately corrected by the
decoder. We also study the impact of number of cycles on the LER which is
shown in Figure 12. This allows us to budget cycles in a QEC experiment based
on the device error rates by accounting for the decoder performance.

Figure 11: Accuracy of distance 5 surface codes for different number of
syndrome measurement rounds (m) Figure 12: Impact of number of cycles on LER

###  6.2 Results for Hardware Complexity

The key component of LILLIPUT are the LUTs for both error types (X and Z). The
size of each LUT depends on decoder configuration. We denote a decoder
configuration as $[d,m]$, where $d$ and $m$ are the code distance and number
of syndrome rounds considered for decoding respectively. The address size is
the length of the detection event which is equal to the syndrome length
multiplied by the number of syndrome rounds. The length of each LUT entry is
equal to the sum of the number of data (for error assignment) and parity
qubits (for internal state). Table 2 shows the size of LUTs for different
decoder configurations. Asymmetry in the code leads to X and Z syndrome
lengths being different for distance 4, so the LUT sizes are different for X
and Z syndromes. We use Cyclone 10 LP FPGAs for the decoder configurations
$[d=3,m=2]$, $[d=3,m=3]$, and $[d=4,m=2]$ as it only supports up to 486 KB of
embedded memory [3]. To support configurations with larger LUTs such as
$[d=4,m=3]$, and $[d=5,m=2]$, we use Arria V FPGAs where the LUTs are accessed
from an external SRAM (using QDR II) or SDRAM (using DDR2) [2]. Alternately,
the LUTs can be compressed (discussed in Section 7) and does not require
external memory [4].

Table 2: LUTs for different decoder configurations Decoder | Address | Entry | LUT | Total | Memory
---|---|---|---|---|---
Configuration | Size | Size | Size | Memory | Type
$[d=3,m=2]$ | 8 | 13 | 416 B | 832 B | Embedded
$[d=3,m=3]$ | 12 | 13 | 6.5 KB | 13 KB | Embedded
$[d=4,m=2]$ | 14/ 16 | 23/ 24 | 46/ 192 KB | 238 KB | Embedded
$[d=4,m=3]$ | 21/ 24 | 23/ 24 | 5.75/ 48 MB | 53.75 MB | External
$[d=5,m=2]$ | 24 | 37 | 74 MB | 148 MB | External

The FPGA utilization is mentioned in Table 3. The logic utilization for
LILLIPUT is less than 7%, making it extremely lightweight and leaving enough
room for other circuits such as readout interface logic and logic for
delivering control instructions to the qubits. The LUTs consume up to 40% of
the memory bits for designs that use embedded memory. We use different Cyclone
devices for distance 3 and $[d=4,m=2]$ for higher performance. Configuring the
distance-3 design on the latter FPGA reduces the maximum frequency to 245 MHz.

Table 3: Post synthesis results for different configurations Decoder | FPGA | Total LEs/ | Total | Utilization
---|---|---|---|---
Configuration | Family | ALMs | Registers | Area | Memory
$[d=3,m=2]$ | Cyclone 10 | 353 | 209 | 6% | 1%
$[d=3,m=3]$ | Cyclone 10 | 418 | 239 | 7% | 21%
$[d=4,m=2]$ | Cyclone 10 | 557 | 340 | < 1% | 40%
$[d=4,m=3]$ | Arria-V | 217 | 409 | < 1% | –
$[d=5,m=2]$ | Arria-V | 246 | 486 | < 1% | –

###  6.3 Results for Latency

LILLIPUT requires only a single memory access to the LUT and incurs fixed
latency, irrespective of the error detection event. LILLIPUT is fully
pipelined and requires 7 cycles to determine the correction after a cycle of
stabilizer measurements are received. The maximum clock-frequency values
depend on the decoder configuration and are listed in Table 4. To compute the
latency of the decoder configurations that rely on external memory access, we
account for the most conservative off-chip memory access time (slowest clock
frequency and maximum number of cycles) and add it to the latency of the rest
of the logic. The decoding latency is up-to 24x lower than the target latency
of $1\mu$seconds in the worst-case (considering the largest decoder
configuration studied in this paper). LILLIPUT also meets the 400 ns target
latency considered in few prior works [30, 57, 16] and thus, will remain
useful even if the duration of syndrome extraction decreases in future with
improving device quality.

Table 4: Maximum Frequency (in MHz) and Latency (in ns) Metric | Decoder Configurations
---|---
[d=3,m=2] | [d=3,m=3] | [d=4,m=2] | [d=4,m=3] | [d=5,m=2]
Frequency | 250 | 240.7 | 209.8 | 244.4 | 232.9
Latency | 28 | 29.1 | 33.4 | 40.8 | 42

The low logic utilization and re-usability of the LUTs allows LILLIPUT to
support QEC experiments spanning more than one logical qubit. As there is
sufficient slack between the decoding latency and the target latency for all
the decoder configurations studied in this paper, the real-time decoding
capability will not be impacted.

##  7 A Case for Compressed LUTs

The size of a lookup table increases exponentially in the code distance
because there is an entry for every possible syndrome bitstring. This limits
the scalability of LILLIPUT, and some of the decoder configurations studied in
this paper rely on memory external to the FPGAs. Moreover, it is infeasible to
scale the LUT to higher configurations, $[d=5,m=4]$ for example. To implement
these configurations without external memory or scale LILLIPUT to other higher
configurations, we propose the use of Compressed LUTs (CLUTs).

###  7.1 Insight: Not all Error Events are equally likely

Each LUT entry corresponds to an error event. However, not all error events
are equally likely, and Compressed LUTs exploit this using the following
insights:

  1. 1.

On surface codes, errors are detected by neighboring parity qubits. When error
rates are low, fewer bit flips are observed in the detected events.
Alternately, higher error-rates cause errors in multiple locations that result
in longer chain of errors. However, it results in only few bit flips overall
as the parity qubits inside the chain are likely to be zeros (can be thought
of as flipped twice). Thus, the average Hamming weight of the accessed memory
addresses is low. For example, the $[d=3,m=2]$ configuration requires LUTs
with 8-bit address ranging from 0x00 to 0xFF. Figure 13 shows the probability
distribution of the Hamming weight of addresses accessed over 1 million trials
for different error rates and both X and Z LUTs of this decoder configuration.
We observe that not all addresses are accessed with equal probability and some
are seldom or never accessed (address 0xFF for example). Therefore, the memory
required for the LUTs can be reduced by removing entries that are unlikely to
be accessed.

(a)  (b)

Figure 13: Probability distribution of the Hamming Weight of memory addresses
for (a) p = 0.1% and (b) p=1% for 5 cycles

  2. 2.

As for small distances, a decoder can assign only a limited number of errors,
the LUT entries contain a large number of zeros. Thus, the LUT entries
themselves are compressible.

To summarize, not all LUT entries are accessed with equal probability and
therefore, the size of the LUTs can be reduced by eliminating entries that are
unlikely to be accessed. Furthermore, the data entries corresponding to the
most probable error events that must be stored can be compressed too.

###  7.2 Compression in Software

We investigate the scope of compression using the $[d=3,m=2]$ configuration.
Figure 13 shows that the probability of accessing LUT addresses with 3 or more
ones is equal to or lower than the logical error rate. Even if these entries
are not stored, the decoder accuracy is unlikely to be affected as the events
would result in a logical error with low probability.

To implement the CLUT, we split the address space into two groups– Segments A
and B, as shown in Figure 14(a). These segments comprise of data frames (DFs)-
a contiguous block of 16 and 10 entries respectively. A block of 16
consecutive LUT entries are assigned a 16-entry or 10-entry DF depending on
the Hamming weight. Addresses with all zeros or a single one in the four most
significant bits are assigned a 16-entry DF, whereas addresses with two ones
in the four most significant bits are assigned a 10-entry DF. For example, as
shown in Figure 14(a), 0x00 to 0x0F correspond to a 16-entry DF in Segment A,
whereas 0xA0 to 0xAA are assigned a 10-entry DF in Segment B. Addresses 0xAB
to 0xAF are not stored as their Hamming weight is more than 3. Although we
want to store LUT entries for addresses of Hamming weights up-to 3 only, as
memory addresses are not contiguous in terms of Hamming weight, this results
in memory fragmentation. Instead, we use data frames that cause some addresses
with higher Hamming weights to be stored as well (such as 0x1F), but this
ensures a simpler addressing scheme. This reduces the number of entries by
1.83x from 256 to 140.

Figure 14: Steps (in software) involved in compressing LUTs.

Next, the DF entries are compressed by re-encoding using the least number of
bits and Base-Delta-Immediate [45] compression. For example, 9-bit error
assignments from four consecutive entries are packed into a 16-bit word, as
shown Figure 14(b). First, each 9-bit data is encoded into 6-bit data using an
encoding table. Next, four 6-bit entries are vertically sliced (Slice A and B)
and packed into a 16-bit word. The 2-bit compression mode is needed because
other memory regions require packing slice A and B differently. For example,
when all slice B bits are 0s and slice A is stored using a 3-bit base and four
2-bit deltas, the mode is 10. We investigated other compression schemes and
found these to be most effective. Our studies show that for this
configuration, compressing the internal state part of the DF entries needs a
different scheme and the overheads of decompression exceed the benefits of
compression as the data is only 4 bits. Finally, each CLUT reduces to 140
bytes, 3x lower than the full LUT (416 bytes). As this is done in software, it
does not incur hardware overheads.

Figure 15: Steps involved in obtaining data from CLUTs.

###  7.3 Accessing CLUTs and Decompression in Hardware

Unlike the baseline design, the decoding request cannot be directly used to
index into the LUT. In order to service a decoding request, it is routed to
the appropriate CLUT segment and DF. The CLUT entry is decompressed to obtain
the error assignments and internal state, as shown in Figure 15. The hardware
overhead to use CLUTs is the logic to obtain the segment address and perform
decompression.

###  7.4 Performance and Overheads of CLUTs

Figure 16(a) compares the logical error rate of the baseline design with
respect to LILLIPUT using CLUTs. We observe that CLUTs offer similar
performance as the baseline and does not degrade the LER. Figure 16(b) shows
the decoder failure rate (due to missing LUT entries) and we observe that
using CLUTs does not lead to events that increase the failure rate. A decoder
failure here refers to failure to decode because the LUT address requested is
not present in the CLUT.

(a)  (b)

Figure 16: (a) Comparison of logical error rate for the baseline and LILLIPUT
with CLUTs (b) Logical error rate and decoder failure rate for LILLIPUT with
CLUTs

Table 5 shows the logic overhead (increases from 6% to 11%) and memory
reduction (by 3x) in using CLUTs on Cyclone FPGAs. On Arria V, both designs
require less than 1% logic utilization and thus, the overhead is acceptable.

Table 5: Logical Overhead for Implementing CLUTs LILLIPUT (Baseline) | LILLIPUT with CLUT
---|---
LEs | Registers | Memory | LEs | Registers | Memory
353 (6%) | 209 | 832 Bytes | 688 (11%) | 261 | 280 Bytes

###  7.5 Scaling to Other Decoder Configurations

The LUTs for distance 4 and 5 surface codes can be reduced in a similar
fashion. Figure 17 shows the probability distribution of the Hamming weight of
the LUT addresses accessed for decoder configurations $[d=4,m=3]$ and
$[d=5,m=2]$ respectively. We observe that storing only the LUT entries
corresponding to Hamming weights 5 and below in the CLUTs are sufficient for
both of these configurations.

(a)  (b)

Figure 17: Probability distribution of Hamming weight of LUT accesses for (a)
[d=4,m=3] and (b) [d=5,m=2] configurations.

Table 6 compares the size of CLUTs for distance 4 and 5 decoder
configurations. We observe that using CLUTs can reduce the memory requirement
by up-to 107x. The CLUTs fit within the embedded memory available on Arria
II/V [2] and Stratix 10 devices [4] and does not require any external memory
access. Note that this estimate does not take into account compression of the
DF entries in the CLUT (second step discussed in Section 7.2 as distances 4
and 5 require a different compression scheme and a detailed discussion is
beyond the scope of this paper. To avoid the address translation for CLUT
lookups, an alternative option is to use Cuckoo hashing [44] which incurs 2x
memory overhead, but still fits the budget of these FPGA boards. Lastly, to
support LILLIPUT for higher decoder configurations $[d=5,m=3]$ and
$[d=5,m=4]$, the LUTs can be compressed and accessed from an external memory.

Table 6: Memory Requirement for LILLIPUT with CLUTs Decoder | Design | Memory (Baseline)
---|---|---
Configuration | X | Z | Total
$[d=4,m=3]$ | Baseline | 5.75 MB | 48 MB | 53.75 MB
W/ CLUT | 245 KB | 457 KB | 702 KB (78.4x)
$[d=5,m=2]$ | Baseline | 74 MB | 74 MB | 148 MB
W/ CLUT | 704.6 KB | 704.6 KB | 1.38 MB (107x)

##  8 Related Work

We discuss the related work on decoders and compression and compare as
appropriate.

Decoders for QEC: Developing accurate and fast decoders for QEC have been an
area of research for several years. Recently, several hardware decoders [30,
57, 16] have been proposed for real-time decoding. However, these decoders
have lower accuracy or rely on emerging technologies. In contrast, LILLIPUT is
very accurate, requires a constant latency, is reconfigurable, and can be
seamlessly integrated with existing quantum systems, making it an ideal
candidate in the near future. Tomita et al. first investigated software LUT
decoders using a fixed set of rules to determine the error assignments [56].
However this design is only limited to distance 3 surface codes and 3 cycles.
In contrast, LILLIPUT is an end-to-end solution that uses MWPM, accounts for
device error models, and can be implemented over a wide number of
configurations and QEC cycles. Most recently, Ryan-Anderson et al. used
software decoders to achieve real-time decoding for color codes on trapped-ion
systems [49]. However, this design requires access to general-purpose CPUs
with the associated overhead in time for transferring data. Unfortunately,
superconducting qubits may not tolerate such large latencies because unlike
trapped ions, superconducting qubits can retain information for only a few
microseconds. LILLIPUT on the other hand is more versatile and can be adapted
to both device technologies. In general, there is no widely accepted standard
decoding algorithm for color codes similar to MWPM for surface codes [35, 12].

Compression in conventional and quantum systems: Cache and memory compression
in traditional architectures are mainly designed to optimize for capacity,
bandwidth, and power. Their effectiveness varies depending on the sparsity of
the data. Recently, Das et al. investigated syndrome compression for reducing
the bandwidth needed for syndrome transmission in large quantum systems [16]
by exploiting the sparsity in syndrome data. In contrast, compression of LUTs
in LILLIPUT relies on the fact that not all error events are equally likely
and error assignments data tend to be sparse. In another work [61],
compression has also been found to be effective in simulating quantum circuits
for program verification, a necessary step to evaluate quantum algorithms and
machines.

##  9 Conclusion

Demonstration of small surface codes using real-time decoding represents a
significant milestone in quantum computing. In this paper, we propose
LILLIPUT- a Lightweight Low Latency Look-Up Table decoder that is accurate,
fast, and can be seamlessly integrated with near-term quantum hardware.
LILLIPUT interfaces with the readout logic, detects error events and corrects
them as they appear in real-time. LILLIPUT uses LUTs to identify errors
instead of running a decoding algorithm. The LUTs are programmed offline using
a software decoder and accounts for the error model of the quantum device. In
this paper, we use minimum weight perfect matching and error rates that are
representative of a Google Sycamore device [6]. LILLIPUT utilizes less than 7%
logic and requires up-to 148 MB of memory for distances up-to 5 on off-the-
shelf FPGAs. To reduce the memory overhead of LILLIPUT, we propose Compressed
LUTs (CLUTs). CLUTs exploit the fact that all error events are not equally
likely and store information only for the most probable events. This reduces
the memory required by up to 107x without deteriorating performance.

## Acknowledgement

We would like to thank Kunal Arya, Michael Newman, Evan Jeffrey, Craig Gidney,
and Austin Fowler for the technical discussions and feedback throughout the
project.

## References

  * [1] Quantum computing and ibm q: An introduction, Accessed: August 03, 2021.  https://www.e-shelter.de/sites/default/files/qubit_ibm_small.pdf.
  * [2] External memory interface handbook volume 1: Intel fpga memory solution overview, design flow, and general information, Accessed: July 22, 2021.  https://www.intel.com/content/www/us/en/programmable/documentation/hco1416493272601.html#hco1416492190668.
  * [3] Intel cyclone 10 lp device overview, Accessed: July 22, 2021.  https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/cyclone-10/c10lp-51001.pdf.
  * [4] Intel stratix 10 embedded memory user guide overview, Accessed: July 22, 2021.  https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/stratix-10/ug-s10-memory.pdf.
  * [5] Dorit Aharonov and Michael Ben-Or.  Fault-tolerant quantum computation with constant error rate.  arXiv preprint quant-ph/9906129, 1999.
  * [6] Google Quantum AI.  Quantum computer datasheet, Accessed: June 19, 2021.  https://quantumai.google/hardware/datasheet/weber.pdf.
  * [7] Panos Aliferis, Daniel Gottesman, and John Preskill.  Quantum accuracy threshold for concatenated distance-3 codes.  arXiv preprint quant-ph/0504218, 2005.
  * [8] Christian Kraglund Andersen, Ants Remm, Stefania Lazar, Sebastian Krinner, Nathan Lacroix, Graham J Norris, Mihai Gabureac, Christopher Eichler, and Andreas Wallraff.  Repeated quantum error detection in a surface code.  Nature Physics, 16(8):875–880, 2020.
  * [9] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [10] Joseph C Bardin, Evan Jeffrey, Erik Lucero, Trent Huang, Ofer Naaman, Rami Barends, Ted White, Marissa Giustina, Daniel Sank, Pedram Roushan, et al.  29.1 a 28nm bulk-cmos 4-to-8ghz¡ 2mw cryogenic pulse modulator for scalable quantum computing.  In 2019 IEEE International Solid-State Circuits Conference-(ISSCC), pages 456–458. IEEE, 2019.
  * [11] BA Bell, DA Herrera-Martí, MS Tame, Damian Markham, WJ Wadsworth, and JG Rarity.  Experimental demonstration of a graph state quantum error-correction code.  Nature communications, 5(1):1–10, 2014.
  * [12] Christopher Chamberland, Aleksander Kubica, Theodore J Yoder, and Guanyu Zhu.  Triangular color codes on trivalent graphs with flag qubits.  New Journal of Physics, 22(2):023019, 2020.
  * [13] Zijun Chen, Kevin J Satzinger, Juan Atalaya, Alexander N Korotkov, Andrew Dunsworth, Daniel Sank, Chris Quintana, Matt McEwen, Rami Barends, Paul V Klimov, et al.  Exponential suppression of bit or phase flip errors with repetitive error correction.  arXiv preprint arXiv:2102.06132, 2021.
  * [14] David G Cory, MD Price, W Maas, Emanuel Knill, Raymond Laflamme, Wojciech H Zurek, Timothy F Havel, and Shyamal S Somaroo.  Experimental quantum error correction.  Physical Review Letters, 81(10):2152, 1998.
  * [15] Julia Cramer, Norbert Kalb, M Adriaan Rol, Bas Hensen, Machiel S Blok, Matthew Markham, Daniel J Twitchen, Ronald Hanson, and Tim H Taminiau.  Repeated quantum error correction on a continuously encoded qubit by real-time feedback.  Nature communications, 7(1):1–7, 2016.
  * [16] Poulami Das, Christopher A Pattison, Srilatha Manne, Douglas Carmean, Krysta Svore, Moinuddin Qureshi, and Nicolas Delfosse.  A scalable decoder micro-architecture for fault-tolerant quantum computing.  arXiv preprint arXiv:2001.06598, 2020.
  * [17] Samudra Dasgupta and Travis S Humble.  Stability of noisy quantum computing devices.  arXiv preprint arXiv:2105.09472, 2021.
  * [18] Nicolas Delfosse and Naomi H Nickerson.  Almost-linear time decoding algorithm for topological codes.  arXiv preprint arXiv:1709.06218, 2017.
  * [19] Nicolas Delfosse and Gilles Zémor.  Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel.  arXiv preprint arXiv:1703.01517, 2017.
  * [20] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  Journal of Mathematical Physics, 43(9):4452–4505, 2002.
  * [21] Laird Egan, Dripto M Debroy, Crystal Noel, Andrew Risinger, Daiwei Zhu, Debopriyo Biswas, Michael Newman, Muyuan Li, Kenneth R Brown, Marko Cetina, et al.  Fault-tolerant operation of a quantum error-correction code.  arXiv preprint arXiv:2009.11482, 2020.
  * [22] Austin Fowler.  Towards sufficiently fast quantum error correction.  Conference QEC 2017, 2017.
  * [23] Austin G Fowler.  Minimum weight perfect matching of fault-tolerant topological quantum error correction in average $o(1)$ parallel time.  arXiv preprint arXiv:1307.1740, 2013.
  * [24] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland.  Surface codes: Towards practical large-scale quantum computation.  Physical Review A, 86(3):032324, 2012.
  * [25] Austin G Fowler, Adam C Whiteside, and Lloyd CL Hollenberg.  Towards practical classical processing for the surface code.  Physical review letters, 108(18):180501, 2012.
  * [26] Austin G Fowler, Adam C Whiteside, and Lloyd CL Hollenberg.  Towards practical classical processing for the surface code.  Physical review letters, 108(18):180501, 2012.
  * [27] Craig Gidney and Martin Ekerå.  How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits.  Quantum, 5:433, 2021.
  * [28] Daniel Gottesman.  Theory of fault-tolerant quantum computation.  Phys. Rev. A, 57:127–137, Jan 1998.
  * [29] Daniel Gottesman.  An introduction to quantum error correction and fault-tolerant quantum computation.  In Quantum information science and its contributions to mathematics, Proceedings of Symposia in Applied Mathematics, volume 68, pages 13–58, 2010.
  * [30] Adam Holmes, Mohammad Reza Jokar, Ghasem Pasandi, Yongshan Ding, Massoud Pedram, and Frederic T Chong.  Nisq+: Boosting quantum computing power by approximating quantum error correction.  arXiv preprint arXiv:2004.04794, 2020.
  * [31] Shilin Huang, Michael Newman, and Kenneth R. Brown.  Fault-tolerant weighted union-find decoding on the toric code.  Phys. Rev. A, 102:012419, Jul 2020.
  * [32] N Cody Jones, Rodney Van Meter, Austin G Fowler, Peter L McMahon, Jungsang Kim, Thaddeus D Ladd, and Yoshihisa Yamamoto.  Layered architecture for quantum computing.  Physical Review X, 2(3):031007, 2012.
  * [33] A Yu Kitaev.  Fault-tolerant quantum computation by anyons.  Annals of Physics, 303(1):2–30, 2003.
  * [34] Ian D Kivlichan, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, et al.  Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via trotterization.  Quantum, 4:296, 2020.
  * [35] Andrew J Landahl, Jonas T Anderson, and Patrick R Rice.  Fault-tolerant quantum computing with color codes.  arXiv preprint arXiv:1108.5738, 2011.
  * [36] Joonho Lee, Dominic W Berry, Craig Gidney, William J Huggins, Jarrod R McClean, Nathan Wiebe, and Ryan Babbush.  Even more efficient quantum computations of chemistry through tensor hypercontraction.  arXiv preprint arXiv:2011.03494, 2020.
  * [37] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin.  Resource estimate for quantum many-body ground-state preparation on a quantum computer.  Physical Review A, 103(5):052408, 2021.
  * [38] Seth Lloyd.  Universal quantum simulators.  Science, pages 1073–1078, 1996.
  * [39] Yi-Han Luo, Ming-Cheng Chen, Manuel Erhard, Han-Sen Zhong, Dian Wu, Hao-Yang Tang, Qi Zhao, Xi-Lin Wang, Keisuke Fujii, Li Li, et al.  Quantum teleportation of physical qubits into logical code-spaces.  arXiv preprint arXiv:2009.06242, 2020.
  * [40] JF Marques, BM Varbanov, MS Moreira, Hany Ali, Nandini Muthusubramanian, Christos Zachariadis, Francesco Battistel, Marc Beekman, Nadia Haider, Wouter Vlothuizen, et al.  Logical-qubit operations in an error-detecting surface code.  arXiv preprint arXiv:2102.13071, 2021.
  * [41] Osama Moussa, Jonathan Baugh, Colm A Ryan, and Raymond Laflamme.  Demonstration of sufficient control for two rounds of quantum error correction in a solid state ensemble quantum information processor.  Physical review letters, 107(16):160501, 2011.
  * [42] Prakash Murali, Jonathan M Baker, Ali Javadi Abhari, Frederic T Chong, and Margaret Martonosi.  Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers.  arXiv preprint arXiv:1901.11054, 2019.
  * [43] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [44] Rasmus Pagh and Flemming Friche Rodler.  Cuckoo hashing.  Journal of Algorithms, 51(2):122–144, 2004.
  * [45] Gennady Pekhimenko, Vivek Seshadri, Onur Mutlu, Phillip B Gibbons, Michael A Kozuch, and Todd C Mowry.  Base-delta-immediate compression: practical data compression for on-chip caches.  In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, pages 377–388. ACM, 2012.
  * [46] Robert Raussendorf and Jim Harrington.  Fault-tolerant quantum computation with high threshold in two dimensions.  Physical review letters, 98(19):190504, 2007.
  * [47] Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin, and Robert J Schoelkopf.  Realization of three-qubit quantum error correction with superconducting circuits.  Nature, 482(7385):382–385, 2012.
  * [48] Diego Riste, Stefano Poletto, M-Z Huang, Alessandro Bruno, Visa Vesterinen, O-P Saira, and Leonardo DiCarlo.  Detecting bit-flip errors in a logical qubit using stabilizer measurements.  Nature communications, 6(1):1–6, 2015.
  * [49] C Ryan-Anderson, JG Bohnet, K Lee, D Gresh, A Hankin, JP Gaebler, D Francois, A Chernoguzov, D Lucchetti, NC Brown, et al.  Realization of real-time fault-tolerant quantum error correction.  arXiv preprint arXiv:2107.07505, 2021.
  * [50] Philipp Schindler, Julio T Barreiro, Thomas Monz, Volckmar Nebendahl, Daniel Nigg, Michael Chwalla, Markus Hennrich, and Rainer Blatt.  Experimental repetitive quantum error correction.  Science, 332(6033):1059–1061, 2011.
  * [51] Peter W Shor.  Fault-tolerant quantum computation.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65. IEEE, 1996.
  * [52] Peter W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computers.  SIAM review, 41(2):303–332, 1999.
  * [53] Andrew M Steane.  Error correcting codes in quantum theory.  Physical Review Letters, 77(5):793, 1996.
  * [54] Ashley M. Stephens.  Fault-tolerant thresholds for quantum error correction with the surface code.  Phys. Rev. A, 89:022321, Feb 2014.
  * [55] Swamit S Tannu and Moinuddin K Qureshi.  A case for variability-aware policies for nisq-era quantum computers.  arXiv preprint arXiv:1805.10224, 2018.
  * [56] Yu Tomita and Krysta M Svore.  Low-distance surface codes under realistic quantum noise.  Physical Review A, 90(6):062320, 2014.
  * [57] Yosuke Ueno, Masaaki Kondo, Masamitsu Tanaka, Yasunari Suzuki, and Yutaka Tabuchi.  Qecool: On-line quantum error correction with a superconducting decoder for surface code.  arXiv preprint arXiv:2103.14209, 2021.
  * [58] Gerald Waldherr, Y Wang, S Zaiser, M Jamali, T Schulte-Herbrüggen, H Abe, T Ohshima, J Isoya, JF Du, P Neumann, et al.  Quantum error correction in a solid-state hybrid spin register.  Nature, 506(7487):204–207, 2014.
  * [59] James R Wootton.  Benchmarking near-term devices with quantum error correction.  Quantum Science and Technology, 5(4):044004, 2020.
  * [60] James R Wootton and Daniel Loss.  Repetition code of 15 qubits.  Physical Review A, 97(5):052313, 2018.
  * [61] Xin-Chuan Wu, Sheng Di, Emma Maitreyee Dasgupta, Franck Cappello, Hal Finkel, Yuri Alexeev, and Frederic T Chong.  Full-state quantum circuit simulation by using data compression.  In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–24, 2019.
  * [62] Jingfu Zhang, Dorian Gangloff, Osama Moussa, and Raymond Laflamme.  Experimental quantum error correction with high fidelity.  Physical Review A, 84(3):034303, 2011.


Methods sec:methods

To investigate the usefulness of TTE depth as both a modeling and
distributional inference tool, we perform several experiments. We first
develop an intuition as to how many texts should be sampled from a population
to ensure quality TTE depth results, and use this intuition throughout our
evaluation. Next, we explore the use of TTE depth as a ranking technique for
in-context learning prompt selection across six classification tasks. Finally,
we use TTE depth and the associated rank sum test to examine the
distributional differences between five {human-written dataset, synthesized
dataset} pairs.

Sample Size Recommendations sec:methods:samplesize

We wish to develop an intuitive understanding of how many samples are required
for consistent TTE depth measures, estimates of the $Q$ parameter, and
Wilcoxon rank sum test results. While it is theoretically possible to obtain
these metrics with access to full corpora, we choose to investigate sampling
techniques for two reasons. First, as TTE depth requires a pairwise distance
comparison across a corpus, it becomes computationally intractable to rank
each text within a large corpus. Second, there exist situations in which
obtaining exorbitantly large samples of two corpora for comparison is
expensive or time-consuming, for example, engineers who wish to measure a
distributional shift in responses of a deployed LLM. Hence, we are interested
in how many samples $n$ are required from two corpora $F$ and $G$ in order to
get a good estimate $Q(F_{n},G_{n})$ for $Q(F,G)$, thus a good TTE depth
measurement.

We run a simulation study on the Wilcoxon rank sum test for corpora on the
order induced by TTE depth. We use the natural language inference (NLI) corpus
bowman2015large and an associated synthetic NLI (SyNLI) corpus
chen2022generate for this study. We sample 5,000 texts from each of the NLI
and SyNLI corpora pair and treat them as the population corpora $F$ and $G$,
respectively. We then embed each text in each population corpus using S-BERT,
a popular general-purpose text embedding model reimers-2019-sentence-
bert††While TTE depth can be used in conjunction with any text embedding model
and either bounded distance, we use only S-BERT and cosine distance in our
evaluations for simplicity. A comparison of different embedding models and
bounded distances is provided in Appendix sec:appendix:comparison. . We then
use the order induced by TTE depth to compute the “true” $Q$ parameter of
these populations, $Q(F,G)$. To empirically determine a good sample size $n$
to draw from $F$ and $G$ for estimating $Q(F,G)$ with $Q(F_{n},G_{n})$, we
iterate over sample sizes $n\in\\{5,25,50,100,500\\}$, randomly draw samples
of size $n$ from $F$ and $G$, and compute $Q(F_{n},G_{n})$ 20 times. We are
interested in whether the distribution of $Q(F_{n},G_{n})$ accurately
represents the true value of $Q(F,G)$ consistently with different sample
sizes.

[width=]figures/q_estimate.png

Figure : Comparison of $Q(F_{n},G_{n})$ estimates for different values of $n$.
As expected, we see the center of each sample distribution centered around the
true $Q(F,G)$. Additionally, we see the spread of the distribution of
$Q(F_{n},G_{n})$ estimates decreases as sample sizes increases. As the
distribution of $Q(F_{n},G_{n})$ with $n=500$ has low variance, we henceforth
use $n=500$ for estimating $Q(F,G)$ in the Wilcoxon rank sum test.

The true value of $Q(F,G)$ was found to be $0.4118$. We can see the sample
distributions of $Q(F_{n},G_{n})$ for different values of $n$ in Figure . As
expected, each of the distributions of $Q(F_{n},G_{n})$ estimates is centered
around $Q(F,G)$, and the spread of the sample distribution decreases as the
sample size increases. We note that the distribution of $Q(F_{500},G_{500})$
estimates has a standard deviation of just $0.009$, indicating low variance
around the true value of $Q(F,G)=0.4118$ while running in a reasonable amount
of time. We propose that $n=500$ is a good enough sample size to test for
significantly different distributions of two sufficiently large embedded
corpora using the Wilcoxon rank sum test on the order induced by TTE depth,
and we sample $n=500$ texts from each corpus for the evaluations in this work.

##  In-Context Learning Prompt Selection

In-context learning (ICL) is a recent paradigm used for few-shot NLP tasks. In
text classification it involves prompting a pre-trained LLM to assign a label
to an unseen input after being given several examples [gao2020making]. Recent
work has investigated prompt selection, i.e. the task of selecting
representative examples from a labeled training dataset to prompt a LLM for
labeling an unseen test sample [gao2020making]. We propose the use of TTE
depth for the task of prompt selection in a model-agnostic setting.
Exploration into ICL has shown that an important component of ICL prompting is
the inclusion of in-distribution texts in the ICL prompt [min2022rethinking].
We hypothesize that texts which better represent the corpus distribution, i.e.
texts with higher TTE depth, will improve downstream ICL performance. Since
TTE depth is a statistical ranking procedure, we do not compare extrinsic
results against existing models for prompt selection. Instead, we
extrinsically evaluate test two TTE depth-based rankings against two naive
statistical baseline rankings across six text classification tasks. Random
(RAND) ranking simply randomly shuffles the training dataset, after which the
first $N$ texts are used as ICL examples for prompt selection. Label
Distribution Match (LDM) ensures that the label distribution of the training
dataset is matched by the selected ICL examples. For each label occupying
$l\%$ of the training data label space, after applying a random shuffle the
first $N\cdot l\%$ texts with that label are selected as ICL examples. This
ranking attempts to ensure that the LLM is able to accurately infer the label
distribution of the training data through the ICL examples. Depth (DEEP)
ranking ranks all embedded texts by their TTE depth. The $N$ deepest texts are
then selected as ICL examples. Depth with Label Distribution Match (DLDM)
ranking is a combination of both the DEEP and LDM techniques. This ranking
first ranks all embedded texts by their TTE depth. Then, the same selection
strategy as the label distribution match ranking is used. Hence, the $N\cdot
l\%$ deepest texts for each label are selected as ICL examples. We compare
ranking methods across six text classification tasks. The Corpus of Lingustic
Acceptability (COLA) [warstadt2018neural], Microsoft Research Paraphrase
Corpus (MRPC) [dolan2005automatically], Stanford Sentiment Treebank (SST2)
[socher2013recursive], and Recognizing Textual Entailment (RTE)
[bentivogli2017recognizing] tasks are selected from the GLUE benchmark
[wang2019glue]. The final 2 tasks, the tweet hate speech detection (THATE)
[basile-etal-2019-semeval] and tweet offensive language identification (TOFF)
[zampieri2019semeval] tasks are both tweet classification tasks. For each
task, we randomly sample 500 texts from the training corpus to represent the
labeled training dataset for prompt selection. We embed each of these texts
(for pairwise tasks we embed a joined version of the two texts) using S-BERT.
Next, we rank each embedded text according to each of the 4 baseline and TTE
depth-based ranking strategies described. The $N$ ICL examples given by each
ranking strategy are then used to create the ICL prompt. We use this prompt to
query ChatGPT, a popular LLM which has been shown to offer good performance
across several ICL text classification tasks [ray2023chatgpt], to label each
evaluation text in the evaluation corpus of each task. After post-processing
ChatGPT output, results are recorded for each ranking strategy and are
averaged over three values of $N$ for each task.

##  Distributional Characterization of Synthesized Training Datasets

The theory of data synthesis for training or fine-tuning language models is
straight-forward: more data is good for learning, and synthesized data is
cheaper and more accessible than human-generated and human-labeled data
[he2022generate]. However, most data synthesis techniques report only
extrinsic evaluations of the synthesized data, i.e. an increase in F1 on
hidden evaluation data. Intrinsic evaluations, such as the distributional
effects of synthesizing training samples for augmenting NLP datasets, require
further exploration [pillutla2021mauve]. Specifically, we’re interested in
whether synthesized training texts across various NLP tasks are significantly
different from their human-written training text counterparts in embedding
space. We use TTE depth to investigate the following synthesis strategies.
Inversion, Passivization, and Combination are NLI sample synthesis techniques
involving swapping the subjects and objects of sentences in the origin
dataset, taking active verbs in sentences and converting them to passive
verbs, and both simultaneously [min2020syntactic]. These synthesized samples
are obtained by inverting samples from the Multi NLI (MNLI) corpus from the
GLUE benchmark [N18-1101], hence we use TTE depth to measure the
distributional shift of the inverted corpus against MNLI in embedding space.
To embed sentence pair samples in the NLI task, we join them and embed them
afterwards. SyNLI is a dataset of synthetic NLI samples generated using a
generator/discriminator model trained on the NLI corpus (MNLI + Stanford NLI
corpus [bowman2015large]) to synthesize sentence pairs [chen2022generate].
SyNLI sentence pairs are generated using T5, a popular open-source LLM
[raffel2020exploring], and are compared against samples from NLI in our TTE
depth analyses. SRQA-AUTO is a dataset of stories involving spatial
relationships between objects and spatial reasoning questions corresponding to
the stories [mirzaee2021spartqa]. In SRQA-AUTO the stories are generated from
image captions using context-free grammars (CFGs) and a rule base is used to
generate the corresponding spatial reasoning questions. In our evaluation,
SRQA-AUTO is compared against the SRQA-HUMAN dataset containing human-written
{story, question} pairs. Samples in SRQA-AUTO and SRQA-HUMAN are embedded by
joining story and question pairs and embedding the resulting text, and these
embeddings are used in our TTE depth analysis. For each training data
synthesis technique, we use TTE depth to rank a sample of 500 synthesized
texts and 500 texts from the corresponding human-written corpus. We compare
the depth-induced distributions intuitively, reporting the TTE depth of the
median of the human-written text (Med Human) and the synthesized text (Med
Synth) with respect to the human-written embedding distribution. We then use
the Wilcoxon rank sum test on the order induced by TTE depth to compare the
distributions statistically, testing whether the human-written and synthesized
corpora differ significantly in embedding space and giving $Q$ estimates, $W$
statistics, and $p$ values. We further detail one analysis, examining the $Q$
measure of outlyingness obtained through TTE depth and discussing what it
means for the synthesis technique to produce more outlying texts than the
human-written corpus.