#  Assessing requirements to scale to practical quantum advantage

M. E. Beverland  Microsoft Quantum, Redmond, WA 98052, USA  P. Murali
Microsoft Quantum, Redmond, WA 98052, USA  M. Troyer  Microsoft Quantum,
Redmond, WA 98052, USA  K. M. Svore  Microsoft Quantum, Redmond, WA 98052, USA
T. Hoefler  ETH Zurich, Department of Computer Science, Zürich, 8006,
Switzerland  V. Kliuchnikov  Microsoft Quantum, Redmond, WA 98052, USA  G. H.
Low  Microsoft Quantum, Redmond, WA 98052, USA  M. Soeken  Microsoft Quantum,
Zurich, Switzerland  A. Sundaram  Microsoft Quantum, Redmond, WA 98052, USA
A. Vaschillo  Microsoft Quantum, Redmond, WA 98052, USA

###### Abstract

While quantum computers promise to solve some scientifically and commercially
valuable problems thought intractable for classical machines, delivering on
this promise will require a large-scale quantum machine. Understanding the
impact of architecture design choices for a scaled quantum stack for specific
applications, prior to full realization of the quantum system, is an important
open challenge. To this end, we develop a framework for quantum resource
estimation, abstracting the layers of the stack, to estimate resources
required across these layers for large-scale quantum applications. Using a
tool that implements this framework, we assess three scaled quantum
applications and find that hundreds of thousands to millions of physical
qubits are needed to achieve practical quantum advantage. We identify three
qubit parameters, namely size, speed, and controllability, that are critical
at scale to rendering these applications practical. A goal of our work is to
accelerate progress towards practical quantum advantage by enabling the
broader community to explore design choices across the stack, from algorithms
to qubits.

##  I Toward quantum applications with practical impact

With rapid progress in quantum computing, there is a shift in focus from
scientific demonstrations on a small number of noisy qubits arute2019 ;
Preskill2018NISQ  towards large quantum systems solving valuable business
problems and resolving long-standing scientific questions that are classically
intractable Schoelkopf21 . But just how large does a quantum computer need to
be to achieve these forms of practical quantum advantage, and how long will
such a computation take? Are some qubit technologies better suited than others
for solving such problems? What are the best architecture choices across the
hardware and software stacks to enable scaled quantum computation?

While many quantum algorithms have asymptotic speedups over their non-quantum
counterparts jordan2011 , scaling up to problem sizes with a practical quantum
advantage Babbush2020  will demand high-precision quantum computers. Quantum
operations at the physical level are noisy, and so the long computations
required for practical quantum advantage necessarily require error correction
to achieve fault tolerance. Quantum computers are complex, and the overheads
required to ensure fault-tolerant quantum computing will significantly outpace
the resources required for fault-tolerant classical computing which is based
on small, cheap, and reliable transistors. A fault-tolerant operation on a
quantum computer requires orders of magnitude more space – including many
transistors for qubit control and readout – and runs with much slower clock
speeds than a classical computer. With these overheads, practical quantum
advantage will be achieved, albeit only for algorithms with small I/O
requirements and superquadratic (ideally exponential) speedups over their
classical counterparts Love2020 ; Babbush2020 ; TroyerQ2B2020 .

One algorithm with superquadratic speedup for which the cost of error
correction is well studied is Shor’s period finding algorithm Shor1994 .
Estimating the resources required for Shor’s algorithm is important for
assessing the vulnerability of some of today’s public key cryptosystems to
future quantum threats. With the fastest quantum hardware operations proposed
to date, factoring a 2048-bit integer using Shor’s algorithm could be done in
minutes with an array of twenty five thousand perfect, noiseless qubits. Yet
in reality, qubits are noisy and must have error correction to enable long
computation, and so as we will reconfirm later, the implementation cost
increases to about a day with tens of millions of qubits Gidney2021 .

Some of the most compelling quantum algorithms with scientific and commercial
interest, however, are those which leverage the ability of a quantum computer
to efficiently simulate quantum systems, with applications across chemistry,
materials science, condensed matter, and nuclear physics. The exact simulation
time of the dynamics of such quantum systems scales exponentially with
classical algorithms, but has a favorable polynomial scaling for quantum
algorithms lloyd1996 . The earliest application of scientific interest may be
simulating the dynamics of around one hundred quantum spins in a quantum
magnet daley2022 . The earliest commercially relevant applications will likely
be quantum simulations of chemistry and materials science problems, where a
quantum-accelerated elucidation of catalytic reaction mechanisms has
applications to fertilizer production Reiher2017 , carbon fixation vonBurg2021
, among many other problems bauer2020quantum ; vonBurg2021 ; delgado2022 ;
kim2022 .

We propose a framework to understand the requirements of applications
promising quantum advantage, determine their practicality, and assess changes
in the underlying architecture to accelerate their implementation. The
framework is composed of layers of abstractions capable of estimating the
performance and required resources of quantum applications and algorithms on
current and future quantum architecture designs. Starting with an algorithm
implemented in a high-level programming language, the framework compiles the
algorithm onto the architecture of a specified quantum device and models the
resource requirements at the architecture level, considering qubit layout,
allowed operations, and other design parameters. We specify models for each
layer and implement a tool, the Azure Quantum Resource Estimator, that
calculates based on those models an estimate of the resources required to
implement a given quantum algorithm on a given architecture with an underlying
qubit technology. We focus on _digital_ quantum computers using gates and
measurements for computation, rather than analog quantum simulators and
annealers daley2022 ; however, similar layers of abstraction may also be
valuable to analyze these other systems.

We analyze the resources that would be required to implement three specific
high-impact applications on various quantum architectures. The first considers
the _quantum dynamics_ of a simple quantum magnet, the so-called two-
dimensional (2D) transverse field Ising model, where we consider a parameter
regime that is on the boundary of what can be done by classical computation
Pearson2020 . The second is for _quantum chemistry_ where we analyze the
activation energy of a catalyst for carbon fixation vonBurg2021 . Lastly, we
analyze _factoring_ a large integer with Shor’s algorithm. While we do not
foresee running this application in practice, it is arguably the best-studied
quantum algorithm and can help provide security requirements of our classical
cryptosystems. Our analysis reveals that practical quantum advantage for
scientific and commercial problems requires hundreds of thousands to millions
of qubits which satisfy the following requirements.

Requirements for scale.— To achieve practical quantum advantage, quantum
computers will require an underlying qubit technology that at scale is:

  * •

Controllable: Practical quantum error correction requires reliable control of
more than a million well-connected qubits, with parallel operations that fail
in under one part in a thousand.

  * •

Fast: To achieve a practical runtime of one month or less, while targeting a
physical qubit count of around one million, operations will need to be
performed in under a microsecond.

  * •

Small: Scaling to a million and more qubits constrains the size of the qubit
to tens of microns in diameter; this size is determined to avoid the
complexity of coherent high-bandwidth quantum interconnects between qubits on
different modules.

We see these requirements as necessary to scale to practical quantum
advantage, and as valuable additions, for scale, to the criteria for building
a quantum computer proposed by DiVincenzo in the year 2000 Divincenzo2000 .
They stem from incorporating research developments spanning the last two
decades, insights across algorithms to qubits, and an empirical end-to-end
resource analysis of several applications and qubit parameter settings. We
hope they reveal new considerations and valuable insights in considering how
to engineer and architect for scale.

##  II Resource estimation for classical and quantum computing

Estimating the resources required for computation, also known as performance
modeling, plays a central role in classical high-performance computing.
Elaborate techniques have been developed to understand application scaling
characteristics, their portability across architectures, and resource
consumption. These models consider some resources as a measure of cost, such
as time, energy, number of instructions, and more recently, data movement. In
this section, we first reflect on the mature field of classical computational
resource estimation, and then leverage this perspective to present a framework
for quantum resource estimation.

Figure 1:  The stacks for classical (left) and quantum (center) computing. At
the top of the stack the program is expressed in a natural, high-level
language such as C/C++ (classical) or Q# (quantum). This program is re-
expressed as different program representations (manilla scrolls) in a sequence
of languages (blue boxes) which are represented here as layers, with each
layer being a lower-level language than that above, down to the physical
signals controlling the device. A complementary viewpoint is that the
instruction set available to the language at one layer can be combined to form
a more elaborate instruction set for the layer above. The scrolls are shortest
at the top, symbolizing that program representations are simplest when
expressed in higher-level languages, while the blue boxes are smallest at the
base of the stack, symbolizing that instruction sets are simplest at the lower
levels. (right) Our quantum resource modeling framework is a modular
representation of the layers of the quantum computing stack, which collects
together the upper layers as _quantum program representations_ , and the lower
layers as _quantum machine models_ , with the quantum ISA connecting both.

In the classical computing stack, the program is initially expressed in a
high-level language at the top and is sequentially re-expressed in more and
more explicit representations down the stack; see the left column of Fig. 1.
We can consider each layer in the stack as having a language with a specific
instruction set of allowed instructions, which can be broken down in terms of
simpler instructions in the layer below, or combined together to form more
abstract instructions for the layer above. For example the program could be
expressed in C++, which is compiled into an intermediate representation (IR)
for optimizations, e.g., LLVM’s static single assignment form (SSA)
intermediate representation LLVM . The IR is then lowered to assembly code in
a specific instruction-set architecture (ISA) that is the interface to the
classical processor. Such assembly code could consist of x86 x86 , ARM arm ,
or RISCV riscv  instruction sets. Some complex instruction set computers such
as Intel’s Haswell translate the x86 code into a microcode representation for
execution by the arithmetic logical units (ALUs). The microarchitecture then
executes those micro-instructions and eventually translates them to electrical
signals to be implemented by transistors. For some processors, microcode and
microarchitecture are combined, but we illustrate them in separate layers here
to draw parallels with the quantum stack.

The goal of resource estimation is to model the stack in order to estimate
some physical resources such as the run time required to implement a high-
level program. One approach could be to consider a chain of re-expressions of
the program from the very top of the stack all the way to the bottom and then
read off the physical resources needed. Near the top of the stack this is an
appealing approach as it is very natural to think of a program being compiled
down into a sequence of lower-level representations. Towards the bottom of the
stack however this approach becomes very difficult because of the intricacies
of the microarchitecture, runtime dependencies of the program execution, and
the overall length of the representation itself. However, the instruction sets
within which the program is expressed typically become simpler for lower
layers, which can be exploited to model resources more conveniently. The
strategy is then to choose a layer towards the middle of the stack, and model
the layers above by re-expressing the high-level program down to the
instruction set at this layer, and estimate the physical resources required to
implement those instructions by building them up from the more basic
instructions in the layers below.

There is of course a choice about where to draw the line between the top and
the bottom in this view of the stack, and the best choice can depend on the
precise goals of the model. For most purposes, the ISA layer has emerged as
the natural interface because it provides an implementation-independent
interface that can be used to ground modeling efforts. ISAs such as x86, ARM
and RISCV represent program executions across a wide variety of classical
processors. Performance modeling frameworks can leverage this powerful
abstraction to model the resources of the full stack by first establishing the
requirements of the program when expressed as instructions the ISA level, and
then identifying the resources required at the device level to implement the
ISA-level program.

The quantum computing stack is less established and abstractions are still in
their definition phase. Some aspects are similar, for example while a quantum
program includes instructions which are executed as quantum operations, the
quantum program itself is just a sequence of instructions similar to a
classical program. However, in stark contrast with the classical stack, which
is built upon extremely reliable transistors, the quantum stack must account
for the unavoidable fact that all forms of physical qubit implementations are
inherently noisy Preskill2018NISQ . To execute a quantum application
successfully, quantum error correction (QEC) gottesman1998  must be used to
build logical qubits that can be used to store and manipulate quantum
information better than raw physical qubits. This QEC capability is central to
scalable quantum computers, but the costs are formidable, often multiplying
the number of qubits needed by a factor of thousands, and runtimes by a factor
of hundreds. Therefore, the specific QEC approach used impacts design
decisions across the quantum computing stack, both at the hardware layers
which must be capable of implementing it, and at the software layers which
must compile to logical operations compatible with it.

Prior works that address the design of a flexible quantum stack and resource
estimation span vastly different viewpoints. For example, prior quantum
architecture and compilation proposals ibmstack ; triq ; shicompilation ;
bertels  develop stacks for near-term small quantum computers, but do not
incorporate QEC. These works either ignore noise bertels , or reduce its
impact with error mitigation techniques ibmstack  which unfortunately do not
scale to larger systems quek2022 . On the other hand, works comparing
resources for multiple QEC codes and logical operations, such as beverland2021
; Chamberland2022b ; Chamberland2019 ; Bombin2021 ; Litinski2019b , typically
address lower layers of the stack without incorporating the software layers.
There is a growing number of informative end-to-end resource analyses, but
typically these single out very specific algorithms and hardware and make very
different assumptions across the stack, making direct comparisons of different
approaches challenging Fowler2012 ; Gidney2021 ; gouzien2021 ; Chamberland2020
; rotteler17 ; beauregard03 ; vanmeter10 ; lee22 ; suchara13 .

###  II.1 A framework for quantum resource estimation

We present a quantum resource estimation framework that aims to capture the
essential aspects of a full-stack quantum computer with the flexibility to
allow direct and easy comparisons across a range of algorithms, software
techniques, QEC codes, hardware specifications and other aspects. To form the
skeleton of our framework, we propose the stack shown in Fig. 1 (center) for
large-scale quantum computers. This framework builds upon the previous work
mentioned above, but seeks to clearly delineate the different layers, clarify
the functions of each layer and define how they inter-operate to attain the
computation capabilities required for large-scale applications. We find that
it is possible to draw broad parallels between the classical and quantum
computing stacks, allowing us to leverage established resource modeling
strategies from classical performance modeling.

In what follows we describe the layers in this stack, briefly stating the main
characteristics of each layer, and listing some known examples from the
quantum computing literature which naturally fit into it. As we will see, the
layers are modular, allowing them to be designed either collectively or
independently, provided that the interfaces between layers remain consistent.
Consistency of the interfaces is ensured by providing explicit maps:
compilation algorithms for program representations down to the ISA from above,
and explicit constructions of instruction sets from those below up to the ISA
from below. These maps are themselves a crucial part of the stack and the
modeling framework. We start at the top of the stack, where the layers are
conceptually similar to the classical case.

High-level quantum language.— This layer hosts the explicit representation of
an algorithm as a program expressed in a high-level programming language. The
language should enable the expression of any quantum algorithm. At this level
of abstraction, users need not know the requirements of quantum error
correction, and may assume their program and its operations are fault
tolerant. Languages ideally include support for loops, functions, rich type
systems, debugging and other functions that are common in classical computing
in order to allow quantum applications to be developed and tested efficiently.
Similarly, supporting hybrid quantum-classical computation which allow
applications to use phases of classical and quantum operations seamlessly is
valuable for practical applications. Examples of languages include Q#
svore2018 , Quipper green2013 , Scaffold abhari2012 , QWire paykin2017 , Quil
quil  and others.

Quantum IR.— To execute a high-level quantum program, that program’s
instructions need to be _compiled_ and expressed in terms of quantum ISA
instructions. It is appealing to support executions of programs expressed in a
diverse set of high-level languages across a range of hardware back ends that
may have different quantum ISAs. In analogy with classical computing, we
propose the use of a quantum intermediate representation (quantum IR) that
expresses high-level operations in a language-agnostic and ISA-agnostic manner
mccaskey2021 ; Ittah2022 ; qir . A compiler then includes three components —
the front end, the optimization layer and the back end. The front end
component translates high-level language instructions to the quantum IR. The
back end component translates the quantum IR into the quantum ISA operations.
The middle optimization layer performs transformations on the quantum IR to
reduce resource requirements Ittah2022 . To support a new quantum language or
quantum ISA, we simply need to add the corresponding front end or back end
components, rather than reinventing the whole compiler. An example of a
quantum IR is the aptly named QIR qir , which includes support for expressing
logical operations, measurements and other quantum constructs that are
required for applications.

The parallels of these two upper layers with the classical stack can be
leveraged. For instance, later we consider high-level quantum programs
expressed in Rust, and the classical IR LLVM has been applied to quantum
compilation tasks Ref. javadiabhari2014 ; Meuli2020 . Next we address the
layers at the bottom of the stack and describe how their instruction sets
build up to form the instruction set of the logical qubits at the quantum ISA
layer (which the quantum IR compiles down to).

Device control.— There is a wide range of hardware approaches to build the
quantum device at the base of the stack, including those based on photonic
knill2001 ; carolan2015 ; bombin2021a , trapped atom Jaksch1999 ;
bluvstein2022 , trapped ion Cirac1995 ; pino2021 , Majorana kitaev2001 ;
sarma2015 ; Karzig2017 , spin kane1998 ; Hanson2007 ; Jnane2022 ,
superconducting transmon transmonSchoelkopf ; schreier2008 ; kjaergaard2020 ;
arute2019 ; hong2020 ; Steffen2011 , and electro-acoustic Guillaud2019 ;
Chamberland2022a  platforms. Quantum devices themselves are not sufficient for
computation, we require classical computing resources to bring up, calibrate
and control the devices as well as the ability to transmit and process
information from quantum measurements. The nature of how qubits are stored
within the device, the range of control available, and the nature of that
control are all very device-dependent and form the instruction set at the
device level – the constraints on ion traps will be different than the
constraints on transmon qubits, for example, simply because their physical
realizations are fundamentally different. It is at this level that resources
are typically most forthright - one may consider run time, number of qubits,
control bandwidth, device size and other cost metrics.

Microarchitecture (physical).— In this layer, low-level details of the qubit
device design are abstracted away, leading to a viewpoint consisting of a set
of abstract physical qubits, along with a discrete set of physical
instructions such as single-qubit measurements and CNOT gates. These
instructions can be characterized by simple properties such as their action on
the physical qubits, how long they take to apply, and their probability of
failure (their so-called _error rate_). This abstraction allows
microarchitectural components to be reused across a variety of qubit device
implementations, while flexibly supporting the needs of different QEC schemes.
Each of the operations in the physical instruction set is built from
operations available at the device control level (for example, in ion traps a
CNOT may be implemented by a sequence of Mølmer-Sørensen Molmer1999  gates,
while in spin qubits it may be implemented by a sequence of exchange
interactions Hanson2007 ). In planar device platforms like superconducting
qubits or Majorana qubits, the ability to support such device-level operations
can lead to connectivity restrictions such as 2D nearest-neighbor connectivity
at this level.

Microcode (QEC).— The microcode instruction set consists of the primitives
required to implement a QEC strategy, which uses a QEC code to form reliable
logical qubits using noisy physical qubits. These logical qubits support
logical operations (which form the instruction set for the quantum ISA level
above) that have better error rates than raw physical operations. For example,
if the QEC strategy uses the surface code Kitaev2003 ; Bravyi1998 , the
primitives which form the instruction set will include syndrome measurement
circuits expressed in the physical instruction set of the microcode layer
below. For the surface code, syndrome measurements provide the information
required to diagnose and correct faults at the physical level by measuring
stabilizers, but can also induce logical operations by deforming the code
Litinski2019 ; Horsman2012 .

Quantum ISA (logical).— This layer forms the interface between the software
and hardware layers. It abstracts the details of how QEC is implemented in the
layer below, retaining only a set of fault-tolerant logical operations as its
instruction set. It is crucial that the instruction set is universal, meaning
it is complete for quantum computing. In this formulation of the stack, it is
the map from the microcode level to the quantum ISA level that actually
implements the error correction, using a classical algorithm known as a
decoder to identify and correct faults while implementing specific logical
operations. Clearly, the instructions in this layer must be chosen such that
they can implemented by the underlying hardware; that is, when choosing an
ISA, it is important to consider the constraints of the system architecture
such as connectivity of logical qubit representations and ability to construct
the logical operations with known sequence of micro-operations and physical
qubit control operations. At the same time, the ISA operations should be
chosen such that the software layers above can efficiently express common
application operations using it. The planar quantum ISA is an example we will
discuss later which arises from the logical operations of two different QEC
approaches, one based on surface codes and the other on Hastings-Haah codes.
For instance, the planar quantum ISA instruction set includes single-qubit
initializations, single-qubit measurements and multi-qubit measurements, which
are all examples of Clifford operations. Clifford operations by themselves are
not universal GottesmanKnill , but when combined with a fault-tolerant T state
initialization, the resulting set becomes universal.

Estimating resources.— Our goal here has been to define the layers of the
quantum stack at a sufficiently high-level of abstraction, so that a broad
range of known and yet-to-be discovered approaches can be readily
incorporated. This forms the basis of a _modular_ framework for quantum
resource modeling, in which layers can be considered together or
independently. We find it convenient to – similar to the classical case –
split the quantum stack in two at the quantum ISA and analyze the upper layers
from the top down in terms of programs, and the lower layers from bottom up in
terms of instruction sets; see Fig. 1 (right). To use the framework to make
explicit estimates, one models a consistent instantiation of each layer and
each of the maps between layers with an explicit example. Later, we will
specify examples of these layers and maps in more detail to answer questions
regarding system requirements for scaling.

This framework enables the estimation of resources (such as the number of
qubits, the run time and the power consumption) which would be required to
implement a given quantum algorithm using a given qubit technology and with a
fixed set of architectural choices. Within the framework, architectural
choices can be viewed as explicit specifications for each layer and map in the
hardware and software parts of the quantum stack. There is no single answer to
questions on architectural design trade-offs, with different choices resulting
in different estimation results which can be explored to make informed
decisions as researchers and engineers work to scale up a complete system. One
can, for example, trade off more qubits against shorter run times, or trade
off faster qubit gate operations against lower fidelities. One can also use
the framework much more broadly, to compare new error correction proposals, to
evaluate the potential for quantum advantage for new or optimized quantum
algorithms, and to motivate future research directions by identifying
bottlenecks in the stack which generate large resource contributions.

The modular nature of the framework allows for future modifications and
extensions. For some purposes it may be desirable to combine some layers
together, and to split other layers into sub-layers. In this work our focus is
on resource estimates for the quantum accelerated parts of the computation,
however more layers can be added to model the hybrid aspects of the
computation.

###  II.2 Fault-tolerant design considerations

Before discussing specific implementations of the quantum resource estimation
framework, we address several significant design considerations that arise
from the need for QEC. Typically, a QEC approach is centered around a QEC code
family which stores the logical qubits. A wide range of QEC codes have been
discovered over the last three decades with wide ranging properties, including
small codes such as the Shor shor1995  and Steane steane1996  codes, 2D local
codes such as surface codes Kitaev2003 ; Bravyi1998 , color codes bombin2006 ,
Hastings-Haah codes Hastings2021  and Bacon-Shor codes bacon2006 ; shor1996 ,
and more exotic families of positive-rate low-density parity check codes
Tillich2014 ; panteleev2022 ; guth2014 ; leverrier2015 . The choice of QEC
code has impact up and down the stack since different codes can place
different implementation demands on the physical instructions provided by the
microarchitecture level below, while also exposing different logical
operations to the quantum ISA level above.

Here we focus on the requirements that QEC imposes on the physical operations
at the microarchitecture level of the quantum stack, corresponding to the
setting known as circuit-level analysis in the QEC literature. It is common in
this setting to assume QEC is implemented with Clifford operations (state
preparation, Clifford unitary gates, and Pauli measurement) for single qubits
and across pairs of qubits coupled by a specified connectivity, and that those
operations fail independently with a uniform error rate (see Appendix A). An
important metric for a QEC approach in this setting is its threshold, which
specifies the maximum error rate that it can tolerate. In what follows, we
leverage known threshold results for a range of QEC schemes to extract a
number of key design parameters pertaining to error rates, parallelism and
connectivity.

The theoretical upper limit for any threshold is not known, but the highest
threshold discovered to date is about 3% using the scheme described in Ref.
knill2005 , and a range of schemes Wang2011 ; beverland2016 ; tremblay2022 ;
Paetznick2022  have been found with thresholds approaching 1%. To avoid
prohibitive QEC overheads, error rates at least an order of magnitude smaller
than the threshold are much preferred. For this reason, we require physical
error rates on Clifford operations below 0.1%.

The aforementioned schemes obtain high threshold values only in the setting
where operations can be applied in parallel, which may pose a significant
hardware challenge for some platforms such as trapped ions Wang2017 . However,
the necessity of parallel operations has long been believed necessary for any
QEC scheme to exhibit a non-zero threshold steane1998 ; gottesman2010 . We
therefore require that physical operations can be applied in parallel.

Next we consider connectivity. Probably the most practically relevant classes
of connectivity correspond to arrays of qubits with neighboring connections in
one or two dimensions, which we refer to as 1D and 2D connectivity
respectively. For connectivity with any fixed dimension, the thresholds of
many of the more exotic code families are believed to drop to zero Bravyi2010
; delfosse2021 . With 2D connectivity the thresholds of some QEC schemes based
on concatenating small codes are reduced svore2005 . Fortunately, many 2D
local codes (including the surface code Wang2011 , the Hastings-Haah code
Paetznick2022  and the color code beverland2016 ) are naturally implementable
with 2D connectivity and achieve high thresholds approaching 1% in this
setting despite the connectivity restrictions. Further restricting to 1D
connectivity leaves very few code families known to have finite thresholds,
and those that do are around 0.01% and below jones2018 ; szkopek2006 ;
stephens2009 . Moreover, 1D connectivity is vulnerable to hardware defects
that some qubits permanently unusable. To avoid such potentially fatal
conditions, we require that qubits are well connected, for example with 2D
connectivity but not 1D connectivity.

There are a number of important subtleties that we have ignored so far. First,
the simple uniform discrete error model is not a true refection of most
systems. Including some realistic aspects of noise, such as asymmetries in the
probabilities of different error channels Brown2020 ; Chamberland2022a  and
richer information from noisy measurements pattison2021  can improve error
correction performance. On the other hand, including other realistic aspects,
such as correlated errors klesse2005  and permanent hardware defects which
must be worked around to implement QEC strikis2021 ; Stace2009  can worsen
error correction performance. To partially allow for these subtleties, we
require that the _worst_ error rates for Clifford operations that are employed
by the QEC approach are below 0.1%. Next, we have required the qubits are well
connected to enable practical QEC, and make it clear that 2D connectivity
falls into this class, while 1D connectivity does not. However, we leave the
formulation of a more complete definition which applies to more general
connectives to future work.

In summary, we require physical qubits to be well connected such as having 2D
connectivity, with the ability to perform parallel operations with error rates
below one part in a thousand. This holds for all examples we consider in this
paper, and forms the basis of one of our criteria for scale.

##  III Estimating resources for three quantum applications

In this section we introduce an implementation of the quantum resource
modeling framework, hereafter referred to as ‘the tool’, which is publicly
available in Microsoft Azure Quantum as the first version of the Azure Quantum
Resource Estimator toolLink . Our primary goal in this work is to identify
architecture features which will be crucial to achieve practical quantum
computing advantage. To do so, we estimate the resources for select
applications with the potential for practical quantum advantage (Section
III.1), using qubit parameters which are relevant for a number of prominent
qubit technologies. We fix a set of consistent architectural options for the
quantum stack based on established approaches from the literature.

Following our framework, estimates obtained using the tool can be viewed as
consisting of two broad components as shown in Fig. 2. The first component
(Section III.2) involves an explicit front end compilation from a high-level
language to a quantum IR, which is fed to the tool. The tool then models the
back end compilation down to a quantum ISA, yielding ISA-level resource
estimates including the number of logical qubits and the number of logical
time steps. In the second component (Section III.3), specific qubit parameters
are fed to the tool which performs a bottom-up estimation of the hardware
resources required to implement ISA instructions by modeling error correction
with specific QEC codes. In Section III.4 we combine these components to
obtain concrete resource estimates.

In the appendices we provide a more detailed and self-contained description of
the material in this section, including our modeling assumptions. Our examples
are available as samples at samplesLink .

Figure 2:  A sketch of how the tool estimates resources for the three example
applications and six qubit parameter examples we consider. Note the stack is
represented left-to-right rather than top-to-bottom. Applications, addressed
by a high-level quantum program, are first translated explicitly to a QIR
program which is input into the tool, where its compilation down to an ISA-
level executable is modeled. All our examples flow to the same planar quantum
ISA, which has an instruction set consisting of logical surface code
operations. On the hardware side, we input physical qubit parameters to the
tool including the physical qubit instruction set and the times and error
rates of those instructions. The tool then models how these noisy qubits are
used to build up protected logical qubits and to fault-tolerantly implement
the planar quantum ISA instructions using configurable QEC models. The tool
outputs resource estimates such as the number of physical qubits and time
required to run the application.

###  III.1 Quantum applications

The first of our three example applications is a _quantum dynamics_ simulation
that is one of the smallest scientifically interesting problems that is out of
reach for classical computation. Specifically, we consider a 2D transverse-
field Ising model with 100 quantum spins, propagated for ten time steps using
a fourth-order Trotter algorithm as described in Ref. Pearson2020 . This is
among the simplest models to exhibit a quantum phase transition. Its dynamics
are representative of strongly entangled quantum systems and as such is
believed to be classically intractable bauer2020quantum .

Our second example is a _quantum chemistry_ application to calculate the
energy of a ruthenium-based catalyst for carbon fixation which could have
implications for reversing the effects of global warming. More specifically,
to estimate the energy of Complex XVIII in Ref. vonBurg2021  to chemical
accuracy of 1 mHa using the so-called ‘double-factorized qubitization’
algorithm described in Ref. vonBurg2021 .

Our third application is _factoring_ , specifically to identify the pair of
prime factors of a $2048$-bit integer. Solving this problem would form the
basis of an attack on widely used RSA-based encryption schemes. In our
resource estimation model, we use a high-level program to implement Shor’s
factoring algorithm based on that described in Ref. Gidney2021 .

To achieve the desired solution accuracy for each application, we also set a
minimum probability that the overall algorithm succeeds, which we call the
algorithm execution accuracy. For the quantum dynamics and quantum chemistry
examples we assume that algorithm execution accuracies of $0.999$ and $0.99$
will be required. However factoring admits a lower algorithm execution
accuracy since it is easy to check if a proposed solution is correct (by
multiplying the purported prime factors to identify if they recover the
original integer), and so we take it to be $2/3$ in this case.

###  III.2 Requirements at the quantum ISA level

Here we describe how we obtain ISA-level resource estimates needed to target
our three example applications. To identify the physical-level costs of
implementing an ISA-level executable, we will not only need to know parameters
capturing the size of the program, but also the required quality of the ISA
operations needed to achieve the desired algorithm execution accuracy. This is
because different quality requirements will result in different error
correction solutions being preferred.

As a starting point, we assume explicit high-level implementations of the
quantum-accelerated components of each of the three target applications, using
Rust for quantum chemistry and factoring and Q# for quantum dynamics111These
implementations are available as samples at samplesLink . First we use an
explicit front end compilation to a specific quantum IR, namely QIR qir  using
the Q# compiler or the Rust compiler based on the application. The tool then
models the back end stage of compilation which translates QIR into operations
supported by the quantum ISA.

In this work we use the planar quantum ISA, which is based on the logical
operations of the most well-established QEC code, namely the surface code
Kitaev2003 ; Bravyi1998 , and also applies to the recently developed Hastings-
Haah codes Hastings2021 ; Paetznick2022 . Logical qubits are stored in patches
laid out in a 2D plane, along with ancilla regions. We sketch some key
features of the planar quantum ISA instructions in Fig. 2, and provide a full
specification in Fig. 6 in Appendix B. Only Clifford operations involving
patches (purple) that are connected by ancilla regions (grey) are permitted,
and two such operations can only be performed simultaneously only if the
ancilla regions they require are disjoint. Non-Clifford T states are produced
in dedicated T factories (yellow).

There are two primary conceptual challenges that need to be overcome to
implement the back end compilation phase. Firstly, the QIR instruction set
contains fine-angle rotation unitaries, which must be approximated with
sufficient accuracy by sequences of operations from the planar quantum ISA, a
process known as synthesis. Secondly, one requires methods to layout qubits
and perform communication in order to map from the QIR, which has no
connectivity restrictions, to the planar quantum ISA, which has geometric
constraints. Standard layout and communication methods can be applied to
address this second aspect of compilation, including SWAP-based schemes where
qubits are moved by swapping neighbors, as well as teleportation-based schemes
where qubits are moved using quantum teleportation. In Appendix D, we provide
an alternative back end compilation scheme which we refer to as Parallel
Synthesis Sequential Pauli Computation (PSSPC), which is based on a
combination of favorable features from existing approaches Litinski2019 ;
Chamberland2021 ; Beverland2022 ; Kliuchnikov2022 . The tool first takes a
trace of the QIR program and then uses accurate formulas to calculate the
planar quantum ISA resource requirements that would result from back end
compiling with PSSPC.

Table 1 presents the ISA-level resource requirements of our three example
applications, which are seen to vary significantly across the applications.
Our quantum dynamics example, selected as being among the smallest
applications of scientific interest, requires only 200 logical qubits after
mapping to the planar quantum ISA. However, even this application requires
logical qubits with error rates that are below $10^{-11}$, which puts it
beyond the capabilities of current noisy quantum hardware. Applications like
chemistry and factoring require several thousand logical qubits, with each
logical qubit having error rates in the range of $10^{-15}$ to $10^{-18}$ and
T states with error rates in the range of $10^{-12}$ to $10^{-15}$. These
applications require mature QEC implementations and large-scale, reliable
quantum hardware which we discuss in the next subsection.

application | algorithm execution | quantum executable parameters | quality requirements
---|---|---|---
accuracy $1-\epsilon$ | $Q$ | $C_{\text{min}}$ | $M$ | max $P$ | max $P_{T}$
quantum dynamics | $0.999$ | 230 | $1.5\cdot 10^{5}$ | $2.4\cdot 10^{6}$ | $9.7\cdot 10^{-12}$ | $1.4\cdot 10^{-10}$
quantum chemistry | $0.99$ | 2740 | $4.1\cdot 10^{11}$ | $5.4\cdot 10^{11}$ | $3.0\cdot 10^{-17}$ | $6.1\cdot 10^{-15}$
factoring | $0.667$ | $25481$ | $1.2\cdot 10^{10}$ | $1.5\cdot 10^{10}$ | $3.5\cdot 10^{-16}$ | $7.4\cdot 10^{-12}$
Table 1:  Estimates of the ISA-level requirements to implement our
applications. The application is compiled down from a high-level application
program to a program expressed in the quantum ISA, with parameters as shown.
These requirements include the number of logical qubits $Q$, the minimum
number of logical time steps (also called logical time steps) $C_{\text{min}}$
and the number of T states $M$ consumed by the program. To ensure that the
algorithm fails with probability at most $\epsilon$, the tool also estimates
the maximum allowed error rate for each logical qubit $P$ and the maximum
allowed error rate for the distilled T states $P_{T}$.

###  III.3 Requirements at the device level

To understand the high-level impact of physical qubit parameters on
application resource estimates, we configure the tool to model the underlying
qubit technology relatively abstractly in terms of operation times and error
rates, and consider parameter configurations which are relevant for a range of
prominent hardware approaches. These features are captured at the
microarchitecture level of the quantum stack. Along with the operation time
and error rate, the tool takes as input one of two physical operation sets:
gate-based instructions (including CNOTs and single-qubit measurements)
relevant for technologies such as superconducting qubits, trapped ion qubits
etc., and Majorana instructions (including non-destructive two-qubit Pauli
measurements) which are relevant for Majorana qubits Karzig2017 ; Plugge2016 .
Both of these instruction sets have 2D connectivity and allow the parallel
application of disjoint operations.

qubit parameter | operation times | error rates
---|---|---
examples | gate | measurement | Clifford | non-Clifford
$(\boldsymbol{\mu}$s, $\mathbf{10^{-3}}$) qubit | 100 $\mu$s | 100 $\mu$s | $10^{-3}$ | $10^{-6}$
$(\boldsymbol{\mu}$s, $\mathbf{10^{-4}}$) qubit | 100 $\mu$s | 100 $\mu$s | $10^{-4}$ | $10^{-6}$
(ns, $\mathbf{10^{-3}}$) qubit | 50 ns | 100 ns | $10^{-3}$ | $10^{-3}$
(ns, $\mathbf{10^{-4}}$) qubit | 50 ns | 100 ns | $10^{-4}$ | $10^{-4}$
(ns, $\mathbf{10^{-4}}$) Majorana qubit | 100 ns | 100 ns | $10^{-4}$ | 0.05
(ns, $\mathbf{10^{-6}}$) Majorana qubit | 100 ns | 100 ns | $10^{-6}$ | 0.01
Table 2:  We consider a set of examples of qubit parameters which represent
various regimes of interest. Each example is labelled with the units of its
operation times (either $\mu$s or ns), and the limiting error rate of its
Clifford operations. The parameter values and instruction set chosen for each
example is informed by published proposals for various hardware approaches. We
assume that the first four examples have gate-based instruction sets, while
the last two examples have Majorana instruction sets.

As listed in Table 2, we consider six qubit parameter examples, each labelled
with the unit of its operation time and error rate. In Fig. 2, we use an
asterisk to differentiate the two examples which use Majorana-based
instructions rather than gate-based instructions. With operation times in the
microsecond range, the ($\mu$s, $10^{-3}$) and the ($\mu$s, $10^{-4}$) qubits
are relevant for trapped ions Cirac1995 , while the (ns, $10^{-3}$) and (ns,
$10^{-4}$) qubits are more relevant for superconducting transmon qubits
transmonSchoelkopf  or spin qubits kane1998 . We also include the (ns,
$10^{-4}$) and (ns, $10^{-6}$) Majorana qubit examples, to account for future
topological qubits based on Majorana zero modes Karzig2017 . These latter
qubits are also expected to have operations in the nanosecond regime, and
owing to topological protection in the hardware, they also have the potential
for higher fidelities at the physical level. In Appendix A we provide more
explanation of these qubit parameter examples and provide the full
specifications of the aforementioned instruction sets in Fig. 5.

In this work, we assume that logical qubits are encoded in patches (purple in
the ISA instructions of Fig. 2) of either the surface code Kitaev2003 ;
Bravyi1998  or the recently discovered Hastings-Haah code Hastings2021 . We
make this restriction primarily because these codes have high fault-tolerance
thresholds, have relatively well-understood logical operations, and can be
implemented using physical qubits with 2D connectivity. We model QEC to relate
properties at the ISA (logical) level to properties at the microarchitecture
(physical) level. For both the surface code and Hastings-Haah code, error
suppression can be tuned by scaling the patch’s code distance $d$. For fixed
qubit parameters, increasing the distance costs quadratically more physical
qubits $n(d)$ and has a linearly longer logical time step $\tau(d)$, but
reduces the probability $P(d)$ of a logical qubit failing during a logical
time step exponentially. A number of fault-tolerant logical Clifford
operations have essentially no time cost in these codes, including state
initialization, readout and Pauli gates. On the other hand, logical qubit
movement and multi-qubit Pauli measurements are implemented via lattice
surgery with the use of ancilla regions (grey in Fig. 2) and require a logical
time step. For counting resources, it is convenient to partition the physical
qubits into tiles, where each tile contains $n(d)$ physical qubits, and can
either be used to encode a logical qubit in a code patch, or can form part of
an ancilla region. The total number of physical qubits used for code patches
and ancilla regions is then $Q\cdot n(d)$, where $Q$ is the number of tiles
(which we also refer to as the number of logical qubits). See Appendix B for
details.

For the ISA-level instruction set to be universal, we also require non-
Clifford operations, such as a logical T gate. This is achieved via the
generation of T states (also known as magic states) using T factories (yellow
in Fig. 2), which typically requires many more resources than other quantum
ISA operations. These T factories typically involve a sequence of rounds of
distillation, where each round takes in many noisy T states encoded in a
smaller distance code, processes them using a distillation unit, and outputs
fewer less noisy T states encoded in a larger distance code, with the number
of rounds, distillation units, and distances all being parameters which can be
varied. There are therefore many options when selecting a T factory. We use
the symbol $\mathcal{D}$ to label a particular T factory choice which requires
$n(\mathcal{D})$ physical qubits, and takes a time $\tau(\mathcal{D})$ to
produce a T state with error rate $P_{T}(\mathcal{D})$. We assume T factories
that are space and time efficient implementations of the well-known 15-to-1
distillation circuit; see Appendix C for details.

For each application, the code distance $d$ and T factory $\mathcal{D}$ must
be chosen to ensure that the ISA requirements from Table 1 are satisfied,
namely that $P(d)\leq\text{max}~{}P$ and
$P_{T}(\mathcal{D})\leq\text{max}~{}P_{T}$, but with minimal cost. As an
example, Table 3 shows the resource costs to satisfy the ISA-level
requirements for the factoring application across different physical qubit
parameters. We can see that the number of physical qubits and the duration of
a logical time step reduce as physical error rates improve. For this example
application, improving physical error rates from $10^{-3}$ to $10^{-4}$ can
reduce the number of qubits by a factor of four, and can halve the logical
time step. Comparing qubits with microsecond and nanosecond operating times,
we see the impact of physical operation time at the ISA level — logical time
steps are several orders of magnitude higher than physical operating times,
underscoring the importance of fast physical operations. T factories incur
significant physical overheads, requiring several thousand physical qubits and
only producing new T states once every 10 to 15 logical time steps, motivating
the need for multiple parallel T factories to meet application T state demand.

|  | logical qubit parameters | T factory parameters
---|---|---|---
qubit parameter | QEC code | for $P(d)\leq 3.5\cdot{10^{-16}}$ | for $P_{T}(\mathcal{D})\leq 7.4\cdot{10^{-12}}$
examples | selected | distance | # qubits | logical time step | # qubits | duration
|  | $d$ | $n(d)$ | $\tau(d)$ | $n(\mathcal{D})$ | $\tau(\mathcal{D})$
($\mu$s, $10^{-3}$) qubit | surface | 27 | 1458 | 16 ms | 17640 | 163 ms
($\mu$s, $10^{-4}$) qubit | surface | 13 | 338 | 7 ms | 4840 | 85 ms
(ns, $10^{-3}$) qubit | surface | 27 | 1458 | 10 $\mu$s | 33320 | 128 $\mu$s
(ns, $10^{-4}$) qubit | surface | 13 | 338 | 5 $\mu$s | 5760 | 72 $\mu$s
(ns, $10^{-4}$) Majorana qubit | Hastings-Haah | 15 | 1012 | 4 $\mu$s | 21840 | 52 $\mu$s
(ns, $10^{-6}$) Majorana qubit | Hastings-Haah | 7 | 244 | 2 $\mu$s | 16416 | 23 $\mu$s
Table 3:  Physical resources required to implement a single logical qubit and
to produce a single T state with a T factory for factoring across the qubit
parameter examples specified in Table 2. For the logical qubit we also show
which QEC code was selected and the corresponding code distance.

###  III.4 Combining the requirements into application resource estimates

We now outline how the tool combines the aspects described in Section III.2
and Section III.3 to estimate thew physical resources required our three
application examples with our six qubit parameter examples. According to
Section III.2, the tool provides detailed estimates of the ISA-level
executable, including the number of logical qubits, the minimum number of
logical time steps, and also number of logical T states required. The tool
also estimates the maximum logical error rates for logical qubits and logical
T states that achieve the required algorithm execution accuracy.

Then, according to Section III.3, the tool selects the QEC code and code
distance for logical qubits and the T factory configuration which have the
smallest physical space-time footprints while achieving the required logical
error rate and logical T state error rate respectively. This choice depends on
the physical qubit parameters, and sets the number of physical qubits per
logical qubit and per T factory, and also the duration of a logical time step
and the T factory. Next, the tool selects the number of T factories to balance
the rate of production of T states against the rate of T state consumption
demanded by the algorithm222 In some cases, the number of T factories required
to meet demand may be very large, prompting the exploration of a trade-off by
slowing down the algorithm allowing for a reduced number of T factories and
lower qubit count. . Finally, the tool computes the total number of physical
qubits as the sum of physical qubits required to implement all logical qubits
and all T factories. It computes the overall computation time using the number
of logical time steps, and the duration of a single logical time step.

Figure 3:  Estimates of the resources required to implement three
applications, assuming the qubit parameter examples specified in Table 2. We
explore a trade-off in the quantum dynamics application by considering two
implementations: one which uses sufficient T factories to supply the needs of
the shortest-depth algorithm and another which slows the algorithm down,
allowing for a reduced number of T factories.

As can be seen in Fig. 3, qubit counts and runtimes vary by orders of
magnitude based on the physical qubit parameters for all three applications.
Even the smallest practical applications such as quantum dynamics involve
devices with more than 100K physical qubits and applications in chemistry and
factoring require upwards of 1M qubits. Unsurprisingly, the three orders of
magnitude longer operation time for the ($\mu$s, $10^{-3}$) and ($\mu$s,
$10^{-4}$) qubit models compared with the other models results in about three
orders of magnitude longer application run times. For quantum chemistry, this
leads to impractical runtimes of more than a century.

To build the tool and obtain these estimates we have made many choices
including what algorithmic, compilation and QEC options to include and also
what approximations and assumptions to make. Other resource estimation works
have made different choices, which leads to small differences in estimates
Gidney2021 . In the appendices, we point out more explicitly these choices,
assumptions and approximations, and in particular, collect together our
primary assumptions in Appendix G. We anticipate that future work will extend
and improve the tool and framework in two ways. Firstly, the estimates for a
given stack will become more accurate as assumptions and approximations are
honed and made more realistic, for example by including more detailed and
nuanced noise models. Secondly, the estimates will become more favorable as
improved solutions and optimizations are included in the stack and resource
models, such as algorithmic improvements and hand-optimized compilation of
important subroutines. We expect the broad conclusions that we draw from these
results in the next section to hold true despite these choices, approximations
and assumptions. This is because our conclusions are relatively insensitive to
order of magnitude changes in resource estimates.

##  IV Technological implications and conclusions

More than two decades ago, DiVincenzo Divincenzo2000  specified a set of
fundamental requirements that any usable quantum computer should satisfy. For
example, DiVincenzo identified the necessity of low error rates, by requiring
long relevant decoherence times, much longer than the gate operation time.
Since then, a variety of qubit technologies that satisfy DiVincenzo’s criteria
have been developed, including technologies such as superconducting and
trapped ion qubits. However, it is an open question as to what additional
conditions beyond DiVincenzo’s criteria a qubit technology must satisfy to
scale to practical quantum advantage, and whether or not current technologies
are on the path to do so.

Our work sheds light on this question, by estimating and analyzing the
resources needed for quantum applications with practical value implemented on
fault-tolerant architecture designs assuming a variety of underlying qubit
technologies. Our analysis rests on several assumptions including qubit
technology trends, QEC schemes, instruction sets, and choices across other
parts of the stack. We have attempted to reflect the community’s current best
understanding of the quantum stack and its future evolution in these
assumptions. Our resource estimates indicate that while scaling requirements
to achieve the first scientifically interesting demonstrations of quantum
advantage are not too stringent, scaling to commercially valuable
applications, such as those using computational catalysis in chemistry,
presents significant challenges. We deduce based on the results that to
overcome these challenges and achieve scale, a qubit technology will need to
be:

Controllable.— While most quantum hardware is controllable at small qubit
counts, scaling qubit control to millions of fast and reliable qubit
operations without introducing new noise channels is important.
Controllability is at the core of scaling up, and has implications on several
aspects of the physical qubit device, including its connectivity, error rates,
operation speed and size.

Regarding connectivity, it has been shown that 2D connectivity is sufficient
to implement fault-tolerant quantum error correction and build logical qubits
Fowler2012 ; Paetznick2022 ; svore2005 , however such an array may present
challenges for control and readout wiring. In contrast, while 1D connectivity
is simpler for control wiring, it requires prohibitively low error rates
jones2018  and seems unlikely to be viable with fabrication defects which
permanently eliminates some qubits and operations. All-to-all connectivity is
challenging to realize in many architectures, and may not be practically
beneficial for large-scale implementations unless QEC schemes with good fault
tolerant logical operations are developed to take advantage of such
properties.

At the heart of fault-tolerant QEC is the requirement that the error rate of
each physical operation (including qubit preparations, measurements, and
gates) is below a threshold value. With no connectivity restrictions, the
highest known threshold knill2005  is 3%, and 1% can be achieved with 2D
connectivity Fowler2012 ; Paetznick2022 . The qubit overhead of QEC goes down
significantly as error rates are reduced further below this threshold value;
however the overheads may still be prohibitive if error rates are not an order
of magnitude better, say below around 0.1%. Even so, error rates have to be
well below threshold while allowing for parallel operations at a scale of
millions of qubits.

Controllability means being able both to control those millions of parallel
operations with the desired error rates, and to readout out those millions of
qubits in parallel to enable decoding of the errors at speed; all while
ensuring the overarching logical clock time is fast enough to complete the
computation within a month runtime or less. To execute syndrome measurements
on these qubits and communicate the quantum measurements to the decoder, we
require large quantum-classical bandwidth and processing power for decoding.
The exact estimates of bandwidth requirements depend on the choice of QEC
code, system size and physical operation times, but roughly, for system with a
few million qubits, we estimate that several terabytes per second of bandwidth
will be required beteween the quantum and classical plane. Furthermore,
processing these measurements at a rate that is sufficient to effectively
correct errors demands petascale classical computing resources that are
tightly integrated with the quantum machine.

Fast.— The run times identified in our study help determine the desired speed
of physical operations for a given quantum architecture to be practical. We
find that logical gate times under 10 $\mu$s, in turn requiring physical gate
times around 100 ns, would be needed to complete the quantum chemistry
algorithm within a month, using a few million physical qubits. While these
gate times are realistic for solid state or photonic qubits bombin2021a , this
is several orders of magnitude faster than current proposals for large ion
trap or neutral atom-based devices blueprintTrappedIon ; Saffman_2016 . For
some algorithms, it may be possible to compensate for slower qubit speeds by
using parallelization techniques, most likely resulting in increasing the
required number of physical qubits.

Small.— Bringing together a million and more physical qubits along with their
control and readout systems presents another challenge: the size of the
quantum computer. We foresee a monolithic, single-wafer approach as desirable
and estimate that a linear extent of a micron or more is needed for wiring,
defining a ‘sweet spot’ for the size of a qubit of around 10 microns
Franke2019 .

To understand this sweet spot, consider estimating the approximate footprint
of the quantum plane by multiplying the number of physical qubits by the size
of a physical qubit, including control electronics. While precise estimates on
the size of leading qubit platforms are not available in the literature, we
estimate that a system with 10M superconducting transmon qubits would require
an area of $\sim 10$ square meters based on current designs arute2019 . At
such scale, a dilution refrigerator that provides the operating environment
for the qubit plane will no longer be able to accommodate a monolithic quantum
module. While modular quantum architectures that span multiple dilution
refrigerators have been proposed Bravyi2022 , the reliability of the
components, such as high bandwidth interconnects and low latency coherent
quantum networks with associated distributed fault-tolerance schemes, and the
ability to scale up while maintaining low error rates is not yet known. In
contrast, the pursuit of a monolithic architecture in which ten million
physical qubits must fit onto a single wafer suggests that shrinking the qubit
to a linear extent of less than 100 microns would be needed. This presents
another set of challenges, including not making the qubit too small. If qubits
are too tightly packed, then scalable control and readout of arrays of qubits
will become hard.

While no qubit technology currently implemented satisfies all of these
requirements, two architecture proposals, while not yet implemented, appear to
satisfy the requirements from a design perspective. These include recent
proposals of electro-acoustic qubits Guillaud2019 ; Chamberland2022a , and the
topological qubit approach based on Majorana Zero Modes Karzig2017 .
Understanding these requirements on the path to scaling up, for these and
other existing technologies, illuminates the opportunities and advancements
needed to achieve practical quantum advantage. It will be through studying the
tradeoffs across the stack, from the algorithm to the qubit device, and then
verifying them in implemnetation, that we will accelerate the development of
scalable quantum computers. Both the framework and Azure Resource Estimator
tool pave the way for the community to better understand the path to scaling
up, the dependencies across the stack on the ultimate qubit numbers and
runtimes, and the opportunities to bring down the costs at every layer.
Practical quantum advantage is on the horizon; it may be accelerated through
breakthrough techniques, including improved quantum error correction
protocols, faster and more accurate decoders enabling improvements in the
thresholds, richer logical operations and logical connectivity, improved
algorithm compilation and optimization, and the discovery of low-cost, useful
quantum algorithms with the promise of advantage. These research directions,
and more, can be studied in the context of resource estimation, and just may
be key to unlocking quantum at scale.

## Acknowledgements

We thank Bela Bauer, Nicolas Delfosse, Alan Geller, Jeongwan Haah, Thomas
Häner, Matthew Hastings, Christina Knapp, Chetan Nayak, Adam Paetznick and
Marcus da Silva for discussions.

## Appendices

In these appendices, we provide a self-contained, more detailed description of
how the resource estimates presented in Section III of the main text are
obtained. Since these estimates are calculated using the first release version
of the Azure Quantum Resource Estimator, hereafter called ‘the tool’, these
appendices also serve to specify the choices, assumptions and approximations
of the tool.

Fig. 4 summarizes the set of examples and major options that form the stacks
that we model to estimate resources, and Table 4 collects together the input,
output, and intermediate data used to calculate the estimates for each
application example using each qubit parameter example, which are used to
produce Fig. 3 in the main text. The appendices methodically address each
aspect of this estimation calculation.

Figure 4:  The examples and options included in the quantum stack for our
resource estimates. We consider three application examples at the top, and a
range of hardware parameter examples relevant for a variety of hardware
approaches at the base of the stack. We label layers of the quantum stack on
the right, and the maps between these layers on the left. To highlight our
qubit parameter examples, we separate the microarchecture layer into two sub-
layers. All our examples flow through the same planar quantum ISA.
Applications are translated down the software stack and the resulting ISA-
level executable is input to the tool. The tool also takes as input
configurable architecture models that include fault-tolerance details and
physical qubit models. The tool outputs resource estimates such as the number
of physical qubits or time required to run the application.

While it is impossible to fully model every aspect of a future large-scale
quantum computing system, here we strive to model system components that are
expected significantly impact performance; we abstract away or neglect aspects
which are expected to have small contributions to the cost. In this tool we
have made a number of assumptions to enable simple and efficient, yet
effective, resource estimation. The formulas used in our estimates are
expressed to the lowest order in parameters which are expected to be small
(such as error rates). These formulas are therefore only valid for
sufficiently small values of those parameters. (Various checks are included in
the tool to flag when this is not the case given user inputs.) We anticipate
that the resource estimates we present here will be further improved by
incorporating additional details and relaxing a number of our assumptions. The
primary assumptions that are made throughout the various aspects of this
analysis are collected together and listed in Appendix G.

The remaining appendices are divided into three parts. The first part,
Appendix A-Appendix D, describes models for different components of a large-
scale quantum computer. In Appendix E, we use these models to estimate
physical resources (qubit counts, runtime) required for executing quantum
applications. The third part, Appendix F, details the applications and
algorithmic optimizations used to reduce resource requirements.

application | planar quantum ISA |  | QEC | resource
---|---|---|---|---
requirements | qubit | optimization | requirements
$Q$ | $C_{\text{min}}$ |  $C$ | $M$ | parameters | $d$ | $F$ | factory | physical | physical
| ratio | qubits | run time
|  |  | $1.5\cdot 10^{5}$ |  | $(\mu\textbf{s},~{}10^{-3})$ | 19 | 199 | 95% | 3.0M | 29 mins
|  |  | $1.5\cdot 10^{5}$ |  | $(\mu\textbf{s},~{}10^{-4})$ | 9 | 199 | 95% | 0.68M | 14 mins
quantum | 230 | $1.5\cdot 10^{5}$ | $1.5\cdot 10^{5}$ | $2.4\cdot 10^{6}$ | $(\textbf{ns},~{}10^{-3})$ | 19 | 242 | 98% | 8.2M | 1.1 secs
dynamics | $1.5\cdot 10^{5}$ | $(\textbf{ns},~{}10^{-4})$ | 9 | 199 | 95% | 0.68M | 0.56 secs
|  |  | $1.5\cdot 10^{5}$ |  | $(\textbf{ns},~{}10^{-4})^{*}$ | 9 | 260 | 99% | 5.8M | 0.42 secs
|  |  | $1.5\cdot 10^{5}$ |  | $(\textbf{ns},~{}10^{-6})^{*}$ | 5 | 224 | 95% | 0.62M | 0.23 secs
|  |  | $1.5\cdot 10^{6}$ |  | $(\mu\textbf{s},~{}10^{-3})$ | 21 | 18 | 56% | 0.46M | 5.3 hours
quantum |  |  | $1.5\cdot 10^{6}$ |  | $(\mu\textbf{s},~{}10^{-4})$ | 11 | 17 | 50% | 0.11M | 2.8 hours
dynamics | 230 | $1.5\cdot 10^{5}$ | $1.5\cdot 10^{6}$ | $2.4\cdot 10^{6}$ | $(\textbf{ns},~{}10^{-3})$ | 21 | 22 | 78% | 0.94M | 13 secs
(reduced | $1.5\cdot 10^{6}$ | $(\textbf{ns},~{}10^{-4})$ | 11 | 17 | 50% | 0.11M | 6.7 secs
T factories) |  |  | $1.5\cdot 10^{6}$ |  | $(\textbf{ns},~{}10^{-4})^{*}$ | 11 | 22 | 79% | 0.61M | 5.0 secs
|  |  | $1.5\cdot 10^{6}$ |  | $(\textbf{ns},~{}10^{-6})^{*}$ | 5 | 23 | 66% | 0.09M | 2.3 secs
|  |  | $4.1\cdot 10^{11}$ |  | $(\mu\textbf{s},~{}10^{-3})$ | 33 | 15 | 6.9% | 6.4M | 260 years
|  |  | $4.1\cdot 10^{11}$ |  | $(\mu\textbf{s},~{}10^{-4})$ | 17 | 14 | 5.9% | 1.6M | 130 years
quantum | 2740 | $4.1\cdot 10^{11}$ | $4.1\cdot 10^{11}$ | $5.4\cdot 10^{11}$ | $(\textbf{ns},~{}10^{-3})$ | 33 | 17 | 14% | 6.9M | 2.0 months
chemistry | $4.1\cdot 10^{11}$ | $(\textbf{ns},~{}10^{-4})$ | 17 | 17 | 15% | 1.9M | 1.0 month
|  |  | $4.1\cdot 10^{11}$ |  | $(\textbf{ns},~{}10^{-4})^{*}$ | 17 | 19 | 22% | 4.5M | 24 mins
|  |  | $4.1\cdot 10^{11}$ |  | $(\textbf{ns},~{}10^{-6})^{*}$ | 9 | 19 | 22% | 1.3M | 12 days
|  |  | $1.2\cdot 10^{10}$ |  | $(\mu\textbf{s},~{}10^{-3})$ | 27 | 13 | 0.6% | 37M | 6.2 years
|  |  | $1.2\cdot 10^{10}$ |  | $(\mu\textbf{s},~{}10^{-4})$ | 13 | 14 | 0.8% | 8.6M | 3.0 years
factoring | 25481 | $1.2\cdot 10^{10}$ | $1.2\cdot 10^{10}$ | $1.5\cdot 10^{10}$ | $(\textbf{ns},~{}10^{-3})$ | 27 | 15 | 1.3% | 37M | 1.5 days
$1.2\cdot 10^{10}$ | $(\textbf{ns},~{}10^{-4})$ | 13 | 18 | 1.1% | 8.7M | 18 hours
|  |  | $1.2\cdot 10^{10}$ |  | $(\textbf{ns},~{}10^{-4})^{*}$ | 15 | 15 | 0.9% | 26M | 15 hours
|  |  | $1.2\cdot 10^{10}$ |  | $(\textbf{ns},~{}10^{-6})^{*}$ | 7 | 13 | 1.2% | 6.2M | 7.1 hours
Table 4:  Estimated resource costs to implement some example applications
using hardware devices with various parameters. The application is compiled
down from a high-level quantum program to a program expressed in the planar
quantum ISA, with parameters as shown. To supply the planar quantum ISA with
the capability to run this program, QEC is used. The code distance $d$ of the
error correcting code and the number of T state distillation factories $F$ are
carefully optimized to minimize the resources needed while providing enough
fault protection that the overall computation runs reliably. We also show the
percentage of the physical qubits which are used for T state distillation
factories. We use an asterisk to indicate Majorana qubits. In the second
implementation of the quantum dynamics example we slow the algorithm down by
setting $C=10C_{\text{min}}$, which allows for a reduction in the number of T
factories, thereby reducing the qubit overhead.

##  Appendix A Physical qubit models

We begin by specifying the instruction sets and noise models for the physical
qubits representation in our analysis, at the level of the microarchitecture
in our quantum stack. We also provide a set of example qubit parameters.

We assume that physical qubits are capable of implementing one of two
instruction sets; see Fig. 5. The _gate-based_ instruction set implements
unitary operations such as CNOT or CZ as its native entangling operations. On
the other hand, the _Majorana_ instruction set implements parity checks such
as ZZ and XX measurements as its native entangling operations.333Note that in
some literature, the Majorana instruction set is known as ‘measurement-based’,
but this can cause confusion with quantum computing using cluster states,
which is also commonly referred to as measurement-based. With Majorana
instruction sets, unitary operations are realized using a sequence of
measurements. For both gate-based and Majorana instruction sets in Fig. 5, we
specify the allowed operations by visualizing the qubits laid out in a array
with nearest neighbor connectivity. This visualization can either represent
the true layout of the qubits in the hardware, such as for solid-state based
approaches or can be considered as no more than a visualization to ensure that
all operations in the instruction set are available, such as for trapped ions.
Note that a particular hardware approach may have other allowed operations not
in one of these instruction sets — these additional operations are not
relevant for our analysis as we assume only operations from the instruction
sets are used.

Figure 5: We consider gate-based and Majorana instruction sets for physical
qubits. Both sets include state preparation in the Pauli basis (green), T
state preparation (yellow), T gate application (yellow), and measurement in
all Pauli basis (blue). (a) The gate-based instruction set also includes
Hadamard H and S gates, and CNOT and CZ entangling gates between adjacent
qubits (all orange). (b) The Majorana instruction set also allows non-
destructive joint Pauli measurements of adjacent qubits (blue).

We assume the standard noise model known as _circuit noise_ , wherein each
operation on the physical qubits fails independently. More specifically, we
assume each Clifford operation fails with probability $p$, where Clifford
operations include the Hadamard and phase gates, the Controlled NOT (CNOT) and
Controlled Z (CZ) gates, single-qubit basis state preparation, and one-qubit
and two-qubit Pauli measurements. We consider an idle qubit for a single time
step to be an identity operation which can also fail with probability $p$. The
preparation of a single-qubit T state, which is a non-Clifford operation, is
assumed to fail with probability $p_{T}$. Failures are modeled by introducing
random Pauli operators on qubits targeted by the operation. When the operation
which fails is a measurement, the outcome is randomly flipped in addition to
applying a Pauli operator to the support of the measurement. We also use the
terminology of error rate in place of infidelity when describing noisy states,
by making the simplifying assumption that the noise on the state arose from
circuit noise (or logical Pauli noise where appropriate) with a given error
rate.

In Table 2, we consider a range of example qubit parameters which abstractly
represent different regimes of operation fidelity and time. These values of
parameters are selected to be relevant for different hardware approaches. For
readability, we label each example by the approximate operation time, Clifford
operation error rate and instruction set. For example, the first qubit has a
gate time $t_{\text{gate}}$ and measurement time $t_{\text{meas}}$ of 100
$\mu$s, a Clifford error rate $p$ of $10^{-3}$ with a gate-based instruction
set; therefore, we label it ($\mu$s, $10^{-3})$. The first four examples are
gate-based qubits and the remaining two are Majorana qubits. To fit the simple
circuit noise model which we assume, we choose a uniform error rate for all
Clifford operations, which can be assumed to equal the highest of the error
rates for any Clifford operation in the instruction set (including single-
qubit gates and measurements and two-qubit gates and measurements). We select
the parameters for each example as follows:

  * •

$(\boldsymbol{\mu}$s, $\mathbf{10^{-3}}$) qubit and $(\boldsymbol{\mu}$s,
$\mathbf{10^{-4}}$) qubit may be relevant for future versions of trapped ion
qubits Cirac1995 ; pino2021 , which typically have operations times in the
microsecond regime. We choose 100 $\mu$s as the gate and measurement time
based on typical assumptions for ion qubits Leung2018 ; Murali2020 . We assume
high-quality single qubit gates with an error rate of $10^{-6}$ and two cases
for two-qubit gates with error rates of $10^{-3}$ and $10^{-4}$ based on the
architectural assumptions in Ref. blueprintTrappedIon .

  * •

(ns, $\mathbf{10^{-3}}$) qubit and (ns, $\mathbf{10^{-4}}$) qubit may be
relevant for future versions of superconducting transmon qubits
transmonSchoelkopf ; schreier2008 ; kjaergaard2020 ; arute2019 ; hong2020 ;
Steffen2011  or spin qubits kane1998 ; Hanson2007 ; Jnane2022 , which
typically have operation times in the nanosecond regime. We project 50 ns gate
times and 100 ns measurement times for future systems based on recent system
implementations googleSurfaceCode ; ibmMontreal , which can be viewed as
relatively optimistic (particularly for measurements). We evaluate two cases,
with $10^{-3}$ and $10^{-4}$ two-qubit gate error rates, respectively, as
realistic and optimistic targets for a scaled up system ibmMontreal ;
Gidney2021 .

  * •

(ns, $\mathbf{10^{-4}}$) Majorana qubit and (ns, $\mathbf{10^{-6}}$) Majorana
qubit may be relevant for future Majorana qubits kitaev2001 ; sarma2015 ;
Karzig2017 . For these qubits, we assume that measurements and the physical T
gate each take $100$ ns. Owing to topological protection in the hardware, we
assume single and two-qubit measurement error rates (Clifford error rates) of
$10^{-4}$ as a realistic target and $10^{-6}$ as an optimistic target. Non-
Clifford operations in this architecture do not have topological protection,
so we assume a $5\%$ and $1\%$ error rate for non-Clifford physical T gates
for the realistic and optimistic models respectively.

Together, these examples cover a range of operation times and error rates,
enabling sufficient exploration of the resource costs anticipated to enable
practical quantum applications. Note that in Fig. 4 and Table 4, we use an
asterisk to indicate the Majorana qubit for notational convenience.

##  Appendix B Quantum error correction and the planar quantum ISA

Here we review two quantum error correction (QEC) schemes, focusing on
estimates of the resources required for their implementation and for applying
fault-tolerant logical operations on the encoded information. For qubits with
a gate-based instruction set, we assume the surface code. It is the best-
understood QEC scheme for this class of qubits and offers a high threshold for
practical implementation. For qubits with a Majorana instruction set, we
consider both the surface code and also the Hastings-Haah code, which is a
recently developed QEC scheme that offers better space-time costs than surface
codes on Majorana qubits in many regimes Hastings2021 ; Paetznick2022 . It is
also in principle possible to implement the Hastings-Haah code with qubits
that use a gate-based instruction set, but the overhead is higher than the
surface code in all regimes of interest in this case so we do not include it
Gidney2022 .

In Table 5 we provide formulas to estimate the physical qubit and time
overheads required to implement logical qubits with the surface code and the
Hastings-Haah code as a function of qubit design parameters. We estimate the
logical error rate $P(d)$ of a patch of surface code or Hastings-Haah code of
distance $d$ with physical error rate $p$ using the formula

$\displaystyle P(d)=a\left(\frac{p}{p^{*}}\right)^{\frac{d+1}{2}},$ (1)

where the pre-factor $a$ and threshold value $p^{*}$ can be extracted
numerically from simulations.

QEC scheme | logical error rate | qubits per logical qubit | logical time step
---|---|---|---
surface code | $P_{\text{sur}}(d)=0.03\left(\frac{p}{0.01}\right)^{\frac{d+1}{2}}$ | $n_{\text{sur}}(d)=2d^{2}$ | $\tau_{\text{sur}}(d)=(4t_{\text{gate}}+2t_{\text{meas}})d$
(gate-based qubits)
surface code | $P_{\text{sur,meas}}(d)=0.08\left(\frac{p}{0.0015}\right)^{\frac{d+1}{2}}$ | $n_{\text{sur,meas}}(d)=2d^{2}$ | $\tau_{\text{sur,meas}}(d)=20t_{\text{meas}}d$
(meas-based qubits)
Hastings-Haah code | $P_{\text{HH}}(d)=0.07\left(\frac{p}{0.01}\right)^{\frac{d+1}{2}}$ | $n_{\text{HH}}(d)=4d^{2}+8(d-1)$ | $\tau_{\text{HH}}(d)=3t_{\text{meas}}d$
(meas-based qubits)
Table 5:  Options of error correction schemes. We model each logical qubit as
having a probability $P$ of failing during a single logical time step, which
can be tuned by changing the code distance $d$, which is an odd integer.
Increasing $d$ increases the number of qubits $n(d)$ required to store each
logical qubit and the time $\tau(d)$ required for each logical time step. The
formulas are based on Refs. Fowler2012  and Wang2011  for gate-based surface
codes, on Refs. Tran2020  and Chao2020  for surface codes implemented with
Majorana instruction sets (replacing 8 steps to measure a single stabilizer in
Ref. Tran2020  by 20 steps to measure all stabilizers), and on Ref.
Paetznick2022  for Hastings-Haah codes.  Figure 6: Fault-tolerant logical
operations: instruction set of the planar quantum ISA. (a) Patches of physical
qubits encode logical qubits in either the surface code or the Hastings-Haah
code, with error correction performed using operations from the instruction
set. We group the array of physical qubits into tiles, each containing $n(d)$
physical qubits, and count logical operations in units of logical time steps
$\tau(d)$ as defined in Table 5. (b) We focus here on one-tile patches, and
two-tile patches, which encode one and two qubits into $n(d)$ and $2n(d)$
physical qubits respectively. We label sections of the boundary of these
patches which are relevant for the logical operations of the planar quantum
ISA. Preparation of qubits in one-tile and two-tile patches in computational
basis states can be applied in $0\tau(d)$. Arbitrary Pauli unitaries can be
applied to qubits in one-tile and two-tile patches in $0\tau(d)$. Destructive
measurement of a qubit in a one-tile patch in the X or Z basis and of both of
the qubits in a two-tile patch (either both in the X basis or both in the Z
basis) can be done in $0\tau(d)$. (c) Hadamard and phase unitaries can be
applied to a qubit in a one-tile patch with an adjacent ancilla tile in
$3\tau(d)$ and $2\tau(d)$ respectively. The ancilla can be on any boundary for
the Hadamard, and next to a Z boundary for the phase. (d) A move of a qubit in
a one-tile patch to a different tile along a path connecting any boundaries of
the starting and ending tiles in $1\tau(d)$. (e) A non-destructive multi-qubit
X, Z type measurement of the qubits in a set of one-tile patches can be
implemented in $1\tau(d)$. This can be done by forming a connected region of
tiles, where each tile hosting a qubit to be measured in the X (Z) basis
connects through one or both of its X (Z) boundaries, and connections can be
between adjacent qubit tiles, or mediated by ancilla tiles. (h) A non-
destructive multi-qubit arbitrary Pauli measurement of a set of qubits stored
in two-tile patches can be performed in $1\tau(d)$. This can be achieved with
a connected region of ancilla tiles with access to all of the X and Z
boundaries of each of the two-tile patches. (i) T state preparation in either
a one-tile patch or a two-tile patch can be achieved using a distillation
factory as described in Appendix C, using a non-integer number of tiles and
logical time steps which depends on the quality requirements of the state.

Protected logical operations can be applied to logical qubits stored in the
surface code or the Hastings-Haah code. We assume precisely the same types of
logical patches, set of logical operations and costs (in units of number of
tiles and logical time steps) for surface codes and Hastings-Haah codes, which
forms the logical instruction set which we call the planar quantum ISA shown
in Fig. 6. The differences that we account for between these two QEC codes are
all captured by the different formulas for the logical error rate $P(d)$,
number $n(d)$ of physical qubits in a tile and the time $\tau(d)$ for a
logical time step for a given distance $d$, as specified in Table 5. The
logical operations can be inexpensive, almost perfect and instantaneous (Pauli
unitaries, single-qubit preparations and measurements), medium cost, requiring
ancilla tiles and one logical time step (multi-qubit Pauli measurements), or
expensive, such as T state preparation for the execution of so-called non-
Clifford gates, which requires a significant number of time steps and
auxiliary qubits, which is discussed in detail in Appendix C. The patch
choices and logical Clifford operations and costs are largely based on Refs.
Litinski2019 ; Bombin2021 .

As a simplification, we do not account for the overhead contributions
associated with a number of known challenges. The circuits expressed in the
physical-level instruction set which are used to implement QEC codes and
logical operations fault-tolerantly are referred to as syndrome measurement
circuits. For surface codes, the two-tile patches may require additional
technical challenges to implement the necessary syndrome measurement circuits,
such as measuring higher-weight stabilizer generators Chamberland2021 ;
Chamberland2022b . Two-tile patches for Hastings-Haah codes have not been
studied in detail in the literature but may pose similar implementation
challenges. Moreover, the size and shape of a tile may need to be altered to
accommodate the non-standard patches (such as the two-tile patch) and to
account for ancillas between patches that can aid lattice surgery. We also
assume that a Clifford operation which takes $A$ logical time steps to
implement and involves $B$ tiles fails with probability $A\cdot B\cdot P(d)$.

##  Appendix C T state distillation factories

The non-Clifford T state preparation in the planar quantum ISA in Fig. 6 is
crucial because the other operations in that quantum ISA, which are all
Clifford operations, and are not sufficient for universal quantum computation
GottesmanKnill . To implement non-Clifford operations for practical-scale
algorithms, we require low error rate T gates or T states, however these can
be difficult to directly implement on logical qubits Bravyi2013 ;
beverland2016a , and can also be difficult for some physical qubits sarma2015
; Karzig2017 . Instead, the required low error rate T states are produced
using a _T state distillation factory_ knill2004 ; bravyi2005 , which we
sometimes refer to as a ‘T state factory’, a ‘distillation factory’ or even
just a ‘factory’ for short. Here we consider the resources required to
implement factories which produce T states in distance-$d$ surface or
Hastings-Haah codes with error rate $P_{T}$.

The operation of a T state factory typically begins by first producing
imperfect T states using some means, for example, a low-quality physical T
gate acting on a physical qubit. These T states are then typically transferred
to a logical qubit and is refined using a distillation unit, which uses only
Clifford operations. This procedure can be iterated, where the output T states
of one round are fed into the next round as inputs. In the error rate of
physical T gates $p_{T}$ is much larger than that of physical Clifford
operations $p$, it can make sense to do some distillation in physical qubits
before transferring the state to a logical qubit.

Figure 7: An example of a two-round T state distillation factory. First, a
transfer unit encodes $c_{0}=34\cdot 15=510$ noisy T states into
distance-$d_{1}$ code patches (not shown). (a) Next, in the first distillation
round, each of these T states are input into one of $c_{1}=34$ copies of a
15-to-1 distillation unit are applied on the distance-$d_{1}$ code patches. It
is possible that not all of the 34 copies of the distillation unit are
accepted. (b) For those copies which are accepted, the code patch hosting the
T state produced is expanded from distance $d_{1}$ to distance $d_{2}$, and
moved into place for the next distillation round using a transfer unit. (c) In
the second distillation round, $30$ T states (provided at least that many
remain) are fed into $c_{2}=2$ copies of a 15-to-1 distillation unit. If fewer
than $30$ T states remain (but more than 14), then just one of the $c_{2}=2$
copies of the distillation unit can be implemented. The T states encoded in
distance-$d_{2}$ codes produced by round two form the output of the
distillation factory.

We consider T state distillation factories which are implemented in a sequence
of rounds, where each round consists of a set of identical distillation units
run in parallel; see Fig. 7. We focus on factories composed of two types of
units. Distillation units (see Table 6) take in a set of T states with a given
quality, and output a smaller set of T states, but which typically have a
higher quality. We assume that distillation units have the same kind of qubits
as input and output, for example distance-$d$ surface codes. Distillation
units typically involves a post selection test - if it is passed, then the
output is accepted, otherwise the output is discarded. Transfer units take T
states stored in qubits of one type in one location and transfer them to T
states stored in qubits of a different type at another location. For example a
transfer unit could take a set of T states stored in physical Majorana qubits,
and transfer them into a set of distance-$d$ Hastings-Haah codes positioned
where they are needed as inputs to a distillation unit in the next round.
Another example would take qubits in distance-$d_{1}$ surface codes at the
locations output from a previous round of distillation, and transfer them into
distance-$d_{2}$ surface codes at the locations where they are needed as
inputs to a distillation unit in the next round. In our analysis we neglect
additional overheads required for implementing the transfer units and any
noise they introduce. We specify a distillation factory $\mathcal{D}$ by
stating: the number of rounds it uses $R$, and for each round
$r\in\\{1,2,\dots R\\}$, both the distillation unit $M_{r}$ (including the
qubit type, such as a specific physical qubit example, or a logical surface
code or logical Hastings-Haah code, and code distance) and the number of
copies $c_{r}$ of that unit. We do not specify the transfer units between
rounds because we do not include the associated costs in our resource
estimates. See Table 7 for some example distillation factories.

distillation | # input Ts | # output Ts | acceptance | # qubits | time | output
---|---|---|---|---|---|---
unit |  |  | probability |  |  | error-rate
15-to-1 space-eff. | 15 | 1 | $1-15p_{T}-356p$ | $12$ | $46t_{\text{meas}}$ | $35p_{T}^{3}+7.1p$
physical |  |  |  |  |  |
15-to-1 space-eff. | 15 | 1 | $1-15P_{T}-356P$ | $20n(d)$ | $13\tau(d)$ | $35P_{T}^{3}+7.1P$
logical |  |  |  |  |  |
15-to-1 RM prep. | 15 | 1 | $1-15p_{T}-356p$ | $31$ | $23t_{\text{meas}}$ | $35p_{T}^{3}+7.1p$
physical |  |  |  |  |  |
15-to-1 RM prep. | 15 | 1 | $1-15P_{T}-356P$ | $31n(d)$ | $13\tau(d)$ | $35P_{T}^{3}+7.1P$
logical |  |  |  |  |  |
Table 6:  Distillation units. Physical distillation units assumes Majorana
qubits with error rates of $p$ and $p_{T}$ for Clifford and input T states
respectively. Logical distillation units assume either the surface code or the
Hastings-Haah code, with each logical qubit requiring $n$ physical qubits,
each logical time step requiring a time $\tau$, and logical error rates of $P$
and $P_{T}$ for Clifford and input T states respectively. The units are
implemented by circuits of allowed operations as shown in Fig. 8 and Fig. 9.
The coefficients for $p$ and $P$ are estimates based on numerical results for
similar circuits, but may be inaccurate.

The outputs of each distillation round are fed into the next, which leads to
the following sequence of calculations which can be used to identify the
overall properties of the factory. First we set the input error rate $Q_{0}$
for the first round to be the physical error rate of the T, i.e.,
$Q_{0}=p_{T}$. Then let $Q_{r-1}$ be the error rate of the encoded T state
that is input into round $r$, and let $P_{r}$ be the Clifford error rate of
the unit at that round (where $P_{r}$ is calculated from the physical qubit
type and the distance and type of error correcting code used by the unit). The
acceptance probability $P^{\text{acc}}_{r}$ and output T state error rate
$Q_{r}$ for each unit in round $r$ are then calculated by setting $P_{T}$ to
$Q_{r-1}$ and setting $P$ to $P_{r}$. In Table 6 we show the relevant formulas
for the four explicit distillation units specified in Fig. 8 and Fig. 9, which
are all different explicit implementations of the standard 15-to-1 protocol
bravyi2005 .

Figure 8: Space-efficient 15-to-1 distillation units. (a) and (b) show the
logical and physical layouts using 20 patches and 12 physical qubits
respectively. (c) A unitary version of the distillation circuit based on Ref.
Litinski2019b . Four T states are fed in at the beginning of the circuit, and
then a sequence of diagonal non-Clifford rotations are applied (yellow boxes,
with the rotation $\exp(-iP\frac{\pi}{8})$ applied for a box containing Pauli
$P$). (d) A diagonal non-Clifford rotation $\exp(-iP\frac{\pi}{8})$ can be
implemented using a small Clifford circuit given an ancilla prepared in the T
state. First, a multi-qubit Z measurement is applied with the support of $P$
extended to include the ancilla, the outcome is $a$. Then the ancilla is
measured in the basis $P_{a}$, where $P_{0}=X$ and $P_{1}=Y$. A Pauli
correction is applied conditioned on the outcome of this ancilla measurement.
(e) For physical-level distillation, the multi-qubit Pauli measurement must be
broken down further into smaller pieces. Up until the dashed line involves the
construction of a cat state on neighboring ancilla qubits. Note that if the
support of the multi-qubit Z measurement is not over all six qubits, we
replace the upcoming ZZ measurement for any qubits not in the support, and
replace it by a single Z measurement. The Pauli correction at the end depends
on the outcomes of the measurements in the circuit. Logical distillation.—
These operations allow the distillation circuit to be re-expressed as surface
code operations using 20 tiles to form a logical distillation unit. The five
blue tiles store the qubits shown in the original circuit, and as such, four
of them contain T states at the start of the distillation unit. The three
green tiles also host T states, and these will be refreshed as the circuit
proceeds. Each of the diagonal non-Clifford rotations is implemented using the
gadget from (d), where the T state is held in one of the green tiles, and the
five grey tiles represent ancillas that are used to facilitate the multi-qubit
Z measurement, which takes a single logical time step. Following the multi-
qubit Z measurement, that green ancilla is measured in either the X (taking
zero logical time steps) or the Y basis (taking one logical time step with the
aid of three adjacent ancilla tiles). Following this, another T state is
transferred to the green tile, which we assume can be done in a single logical
time step. As we have three green tiles, we can overlap this procedure for
consecutive rotations such that the 11 non-Clifford rotations are each
implemented in a total of 13 logical time steps. This represents the full time
of the distillation unit since the initial X basis preparation and final
single-qubit measurements take zero logical time steps. Physical
distillation.— The physical distillation unit can be run on 12 physical qubits
laid out as shown. Each of the 11 non-Clifford rotations requires five time
steps, but the ancilla preparation in the X basis for all but the first round
since the X basis at the end of the previous round deems it unnecessary. As
the operations at the very start and end of the circuit are not supported on
the ancillas, the can be done in parallel to the first and last steps of the
non-Clifford rotations, such that this physical distillation unit requires
$5+10\cdot 4+1=46$ physical time steps.  Figure 9: Reed-Muller state
preparation 15-to-1 distillation units. Each of the 31 squares represents a
physical Majorana qubit or a logical qubit in a one-tile patch. In steps
(a-g), a Reed-Muller state is prepared, using the gadgets shown on the right,
which are available for both physical Majorana qubits and logical operations.
We consider the grey squares ancillas, and the blue squares are those qubits
which have been set and acted upon and host the Reed-Muller state. A naive
counting of these first seven steps requires $(4+1+4+6+6+4+4)=29$ physical
time steps, however overlapping consecutive steps with disjoint support
reduces this to 21 physical time steps. At the logical level, these seven
steps require $(2+0+2+2+2+2+2)=12$ logical time steps. (h) Next a T gate is
applied to all but one of the qubits in the Reed-Muller state. For physical
qubits, this can be done directly in a single physical time step. For logical
qubits, this is instead achieved by transferring a T state to one of the grey
qubits, and applying a $ZZ$ measurement as in Fig. 8(b). As we do not account
for the transfer time, this requires a single logical time step. (i) Finally,
each of the qubits to which T gates had been applied are measured in the X
basis, which takes a single physical time step, or zero logical time steps.
The overall time for the physical distillation unit is therefore 21+1+1= 23
physical time steps, and for the logical distillation unit is 12+1+0=13
logical time steps.

The overall output T states of a distillation factory $\mathcal{D}$ are those
output from its last round, and therefore have error rate

$\displaystyle P_{T}(\mathcal{D})=Q_{R}.$ (2)

We estimate the run time and qubit requirements as:

$\displaystyle\tau(\mathcal{D})$ $\displaystyle=$
$\displaystyle\sum_{r=1}^{R}\tau(M_{r}),$ (3) $\displaystyle n(\mathcal{D})$
$\displaystyle=$ $\displaystyle\text{max}_{r\in\\{1,2,\dots
R\\}}(c_{r}n(M_{r})),$ (4)

where $n(M_{r})$ is the number of qubits needed for a single copy of
distillation unit $M_{r}$ and $c_{r}$ is the number of copies of the unit in
round $r$. Each unit in a factory can fail, therefore the number of T states
output by a factory is a random variable. We choose to address this by
defining the number of output T states from the factory $M(\mathcal{D})$ as
follows:

$\displaystyle M(\mathcal{D})$ $\displaystyle=$ $\displaystyle\\#~{}\text{T
states output in at least 99\% of runs of}~{}\mathcal{D}.$ (5)

In principle, many factories have $M(\mathcal{D})=0$ according to this
definition, which would occur for example if the final round consists of a
single unit with an acceptance probability below 99%. Therefore many of the
distillation factories that we consider over-provision units so that after
accounting for some units failing the required number of T states is passed on
to the next round. We assume that such decisions are specified to our
framework by setting the appropriate distillation factory parameters such as
$R$, $c_{r}$ and choice of unit types for each round.

$P_{T}$ | round 1 | round 2 | resources
---|---|---|---
unit | qubits | time | copies | unit | qubits | time | copies | qubits | time
| 15-to-1 |  |  |  |  |  |  |  |  |
$5.6\cdot 10^{-11}$ | space-eff. | 3240 | 46.8 $\mu$s | 1 |  |  |  |  | 3240 | 46.8 $\mu$s
| $(d=9)$ |  |  |  |  |  |  |  |  |
| 15-to-1 |  |  |  | 15-to-1 |  |  |  |  |
$2.1\cdot 10^{-15}$ | space-eff. | $16000=16\cdot 1000$ | 26 $\mu$s | 16 | RM prep. | 10478 | 57.2 $\mu$s | 1 | 16000 | 83.2 $\mu$s
| $(d=5)$ |  |  |  | $(d=13)$ |  |  |  |  |
| 15-to-1 |  |  |  | 15-to-1 |  |  |  |  |
$5.51\cdot 10^{-13}$ | space-eff. | $5760=16\cdot 360$ | 15.6 $\mu$s | 16 | space-eff. | 4840 | 57.2 $\mu$s | 1 | 5760 | 72.8 $\mu$s
| $(d=3)$ |  |  |  | $(d=11)$ |  |  |  |  |
Table 7:  T state distillation factories to target the required error rates
for our three application examples with the (ns, $10^{-4}$) qubit parameter
example.

##  Appendix D Compilation from QIR to the planar quantum ISA

The planar quantum ISA, consisting of the Clifford operations defined in Fig.
6 and non-Clifford T states distilled as described in Appendix C, forms a set
of basic instructions that is sufficient for universal quantum computation.
Here we describe how the program expressed in QIR, is mapped to the
instructions of the planar quantum ISA, which we refer to as back end
compilation.

Here we describe the back end compilation scheme that we assume in this paper
at a high level. Our compilation scheme is formed by combining sequential
Pauli-based computation (SPC), as described in Ref. Litinski2019  and
elaborated upon in Ref. Chamberland2021 , with an approach to synthesize sets
of diagonal non-Clifford unitaries in parallel, as was done in Ref.
Beverland2022 . We call this compilation scheme Parallel Synthesis Sequential
Pauli Computation (PSSPC).

We assume that the input is a QIR program which has first been re-expressed as
a sequence of Clifford layers and non-Clifford layers, which we refer to as
the input circuit. A Clifford layer of the input circuit consists of a set of
basic instructions, which are either Clifford unitaries, basis state
preparations, or Pauli measurements. Non-Clifford layers of the input circuit
require T states to implement, and include operations such as T gates, Toffoli
gates, and single-qubit arbitrary angle rotations (where the angle is not an
integer multiple of $\pi/4$) around either the X, Y or Z axis. The input
circuit can be dynamic in the sense that the measurement outcomes in one
Clifford layer can affect the instructions applied in subsequent layers of the
input circuit. In the following description, we describe a compilation
strategy which can be applied to compile a dynamic input circuit layer by
layer444When estimating resources to implement a dynamic algorithm, we
randomly pick outcomes of measurements in the algorithm such that each layer
is specified for explicit analysis. to produce an equivalent output circuit
which is expressed in terms of the logical instruction set in Fig. 6.

To orchestrate the execution of this algorithm, PSSPC performs the following
circuit transformations (see Fig. 10).

  * Step 0.— We first re-express the input algorithm such that it consists of a sequence of Clifford layers and diagonal non-Clifford layers. This is straight-forward: a rotation around the X or Y axis can be converted by conjugation of a Clifford into a rotation around the Z axis $R_{z}(\theta)=|0\rangle\langle 0|+e^{i\theta}|1\rangle\langle 1|$. The Cliffords that are used to implement this transformation are then absorbed into the Clifford layers before and after the non-Clifford layer. Similarly, a Toffoli gate can be re-expressed as a CCZ gate with a Hadamard applied before and after on the target qubit.

  * Step 1.— Delegating expensive operations to synthesis qubits to increase parallelism: Non-Clifford rotations $R_{z}(\theta)$ are frequently used in quantum algorithms, but are among the most resource intensive operations when we consider implementation costs. To improve algorithm performance, PSSPC seeks to delegate these operations to ancilla qubits, referred to as synthesis qubits. By delegating these operations, multiple rotations can be synthesized in parallel to increase the T consumption rate and improve algorithm runtime.

As shown in Fig. 10(b), PSSPC first re-expresses rotation operations on
algorithm qubits using ancillary synthesis qubits. To implement a rotation
such as $R_{z}(\theta)$ on an algorithm qubit, it is first entangled with an
ancilla by measuring a Pauli supported on both that qubit and the ancilla.
Then a sequence of operations are performed on the ancilla to apply the
rotation’s phase using Clifford gates and also T gates. The phase is kicked
back to the algorithm qubit by measuring out the ancilla and applying a Pauli
correction to the algorithm qubit. All other diagonal non-Clifford unitaries
(including the T gate and the CCZ) are applied similarly (see Figure 20 in
Beverland2022 ).

  * Step 2.— Eliminating Clifford unitaries: After delegating the synthesis of rotations and Toffoli gates to ancillas, operations on the algorithm qubits are a series of Clifford unitaries and Pauli measurements. While these operations can be implemented using the instruction set in Fig. 6, we can further optimize the circuit by eliminating Clifford unitaries.

Clifford unitaries map Pauli operations to other Pauli operations. Using this
property, PSSPC commutes each Clifford unitary through the subsequent Pauli
operations. This transforms the local Pauli operations to multi-qubit Pauli
measurements and Pauli corrections. This optimization allows us eliminate the
Cliffords at the cost of executing multi-qubit Pauli measurements.

Figure 10:  (a) The initial circuit consists of alternating Clifford (orange)
and diagonal non-Clifford layers (blue). For illustrating the principles
behind PSSPC, we show the implementation details for the first non-Clifford
(the single rotation $R_{1}$ between Clifford unitaries $C_{1}$ and $C_{2}$),
but the concepts extend to parallel distinct rotations. (b) $R_{1}$ is
delegated to an ancilla qubit, where the operation is synthesized using T
states and the phases are kicked back to the algorithm qubit. (c) $C_{1}$ is
eliminated by commuting it through the Pauli operations that follow it,
transforming them into multi-qubit Pauli operations. (d) After eliminating all
Clifford unitaries, the circuit consists of a sequence of Pauli measurements
and Pauli corrections, along with synthesis on ancilla qubits. For the second
set of non-Cliffords (between $C_{2}$ and $C_{3}$ in the input circuit), we
have a series of Pauli measurements and synthesis, followed by a final Pauli
correction after synthesis and then the Pauli measurements from the original
circuit. We assume that the Pauli correction for the current non-Clifford
layer is completed before moving on to the next layer.

Like SPC, a major benefit of PSSPC is that all Clifford unitaries in the input
algorithm are eliminated and do not need to be applied. SPC differs from PSSPC
by synthesizing the non-Clifford gates in place rather than in external
ancillas, and the Ts resulting algorithm which has the drawback of serializing
all T gates in the circuit. This drawback is partially overcome by PSSPC by
parallelizing the synthesis of rotations which appear in the same layer of the
input circuit, but the phase kickback of the synthesized rotations within a
layer is still serial. Other layout and compilation approaches have been
proposed JavadiAbhari2017 ; Lao2018 ; Steiger2018 ; Murali2019 ; Zulehner2019
; Childs2019 ; Beverland2022 ; Leung2010 ; Hahn2019 ; Beaudrap2020a , but are
more involved to implement and analyze in detail.

We estimate the resources required to implement an algorithm using PSSPC in
terms of the following parameters of the input algorithm. Let $Q_{\text{alg}}$
be the number of logical qubits used by the algorithm. Let $M_{R}$ be the
number of single-qubit rotations, $M_{T}$ be the number of T gates, and
$M_{\text{Tof}}$ be the number of Toffoli gates, and $M_{\text{meas}}$ be the
number of Pauli measurements of the input algorithm. Let $D_{R}$ be the number
of non-Clifford layers in which there is at least one arbitrary angle rotation
(note this can be smaller than the total number of non-Clifford layers since
it excludes those layers consisting entirely of T gates and Toffoli gates).
Let the target error budget for synthesis in the overall program be
$\epsilon_{\text{syn}}$ (measured in the diamond norm).

We assume the fast block layout from Ref. Litinski2019  (also shown in Fig.
11), such that each pair of algorithm qubits is stored in a two-tile surface
code patch, surrounded by ancilla tiles which can be used to measure an
arbitrary Pauli operator on the algorithm qubits in one logical time step.
This results in the number of logical qubits555More precisely, $Q$ is the
number of tiles, some of which are allocated to ancillas, and some of which
are allocated to store algorithm qubits in two-tile patches. $Q$ given by

$Q=2Q_{\text{alg}}+\left\lceil\sqrt{8Q_{\text{alg}}}\right\rceil+1.$ (6)

We account for the resources required for distillation separately in Appendix
E, and in this section we assume that T states are produced on command and
simply count how many T states are needed to implement the algorithm.

Figure 11:  Overall layout of qubits in the quantum computer, using the PSSPC
layout. The main block of logical qubits is purple and grey. Each purple
rectangle denotes a pair of algorithm qubits encoded in a two-tile patch of
surface or Hastings-Haah code, while the grey boxes are tiles of ancillas to
facilitate multi-qubit Pauli measurements. A block of qubits is dedicated for
distilling T states which are used to apply T gates and Toffolis, or are
passed on to the synthesis block to synthesize rotations. We neglect the
qubits needed for synthesis. In the overall program, we use $Q$ to denote the
number of tiles in the main block, $M$ to denote the number of T states that
are produced, and $C$ to denote the number of logical time steps needed to run
the program.

Synthesizing a single-qubit rotation to diamond-norm accuracy
$\epsilon^{\prime}$ re-expresses the unitary as Cliffords and at most
$R_{T}(\epsilon^{\prime})$ non-Clifford T gates, where

$\displaystyle R_{T}(\epsilon^{\prime})=\left\lceil
A\log_{2}(1/\epsilon^{\prime})+B\right\rceil,$ (7)

for constants $A$ and $B$. We assume the Clifford+T synthesis in Table 1 of
Ref. Kliuchnikov2022 , which results in $A=0.53$ and $B=5.3$.666For
simplicity, we use this formula for all single-qubit arbitrary angle
rotations, and do not distinguish between best, worst and average cases. We
also do not incorporate further improvements from Kliuchnikov2022  that use
Clifford+$\sqrt{\mathrm{T}}$ synthesis and known improvements for special
cases, for example when many rotations are applied in parallel with the same
angle Gidney2018halvingcostof . To meet the accuracy requirement for the
overall algorithm, which involves $M_{R}$ single-qubit rotations, we set
$\epsilon^{\prime}=\epsilon_{\text{syn}}/M_{R}$.

As described in Fig. 10(d), the computation proceeds in layers. Each diagonal
non-Clifford unitary is applied as part of a layer of non-Clifford rotations
from the input circuit. The first step to implement such a unitary is to
couple the algorithm qubits to the synthesis ancilla qubits. This requires one
multi-qubit Pauli measurement for each algorithm qubit in the support of the
unitary. Therefore one logical time step is used for a T gate or a single-
qubit rotation $R_{z}(\theta)$, while each Toffoli requires three logical time
steps. We assume that T gates and CCZ gates require no additional synthesis
time beyond the time required for these measurements, justified by techniques
in Ref. Gidney2019 ; Haner2022 . To estimate the time required to synthesize
an arbitrary angle rotation $R_{z}(\theta)$, we note that the synthesis
consists of $R_{T}(\epsilon_{\text{syn}}/M_{R})$ non-Clifford T gates
interleaved with Clifford unitaries. We assume this can be implemented by a
sequence of $R_{T}(\epsilon_{\text{syn}}/M_{R})$ Pauli measurements supported
on the synthesis ancilla and other ancillas to which the T states are
delivered from distillation factories, taking
$R_{T}(\epsilon_{\text{syn}}/M_{R})$ logical time steps. The final step to
implement a rotation, after the synthesis has finished, is to apply a
measurement of the ancilla and then a Pauli correction to the algorithm
qubits, both of which can be done instantaneously.

The time required to implement a non-Clifford layer depends on whether the
layer consists entirely of Toffoli and T gates, or whether it also contains
some arbitrary angle rotations. In the former case, the number of logical time
steps required is simply the number of measurements needed to entangle the
algorithm and synthesis ancillas. In the latter case, in addition to the time
needed for these entangling measurements, one also needs to add the time for
synthesis. It is possible to further compress this by overlapping synthesis
for one non-Clifford layer with the measurements for the following Clifford
and non-Clifford layers, but for simplicity we assume that consecutive layers
are executed sequentially without overlap. Within each layer however, the
synthesis of rotations that were parallel in the input quantum IR circuit is
performed in parallel. Since all Clifford unitaries in the Clifford layer are
eliminated, the time required for the Clifford layer is simply the time
required to implement the measurements it contains. The total number
$C_{\text{min}}$ of logical time steps is therefore

$C_{\text{min}}=(M_{\text{meas}}+M_{R}+M_{T})+\left\lceil
A\log_{2}(M_{R}/\epsilon_{\text{syn}})+B\right\rceil D_{R}+3M_{\text{Tof}}.$
(8)

Note that this is our estimate of the number of logical time steps that would
be needed if the T state factories produce T states at a sufficient rate so as
to not limit the algorithm speed. In practice, the time $C\geq
C_{\text{min}}$, and one could increase $C$ to slow the algorithm down if for
example it puts a strain on the qubit resources available to produce T states.

Finally, using Eq. (7) and noting that four T states are sufficient to
implement Toffoli, the number of T states $M$ is given by

$M=\left\lceil A\log_{2}(M_{R}/\epsilon_{\text{syn}})+B\right\rceil
M_{R}+4M_{\text{Tof}}+M_{T}.$ (9)

We neglect the ancilla qubits used for unitary synthesis and those that would
be required to transport the T states from distillation factories to where
they are consumed for synthesis.

##  Appendix E Putting the pieces together to estimate resources of an
algorithm

This appendix puts together components described over previous appendices in
order to estimate the resources required to implement a high-level language
quantum algorithm on a specified fault-tolerant architecture. After
compilation of the algorithm to the instruction set described in Fig. 6, the
problem reduces to estimating the resources required to implement a circuit
with $Q_{\text{alg}}$ algorithm qubits, with $M_{R}$ single-qubit rotations
spread among $D_{R}$ layers, $M_{T}$ T gates, and $M_{\text{Tof}}$ Toffoli
gates. Furthermore, let $1-\epsilon$ be the desired probability that the
overall algorithm succeeds.777 More formally, $\epsilon$ is the total
variational distance between the probability distribution of the final output
bit strings of the compiled circuit and the algorithm circuit. Commonly, the
circuits correspond to channels and the required total variational distance
can be bounded using the diamond norm distance between the compiled channel
and algorithm’s channel as explained in Appendix B in Kliuchnikov2022 .

The value of $\epsilon$, which we refer to as the error budget, depends on how
the samples from algorithm instances are to be post-processed, and its value
is set by taking the desired algorithm execution accuracy to be $1-\epsilon$.
For example, if one is running Shor’s algorithm for factoring integers, a
large value of $\epsilon$ may be tolerated as one can check that the output
are indeed the prime factors of the input. On the other hand, a much smaller
$\epsilon$ may be needed for an algorithm solving a problem with a solution
which cannot be efficiently verified. For the target architecture, we assume
that a specific physical qubit model and quantum error correction scheme has
been chosen from Appendix A and Appendix B. The target architecture implements
the logical instruction set described in Fig. 6.

To achieve the required algorithm success probability, we require that

$\epsilon_{\text{log}}+\epsilon_{\text{dis}}+\epsilon_{\text{syn}}\leq\epsilon,$
(10)

where $\epsilon_{\text{log}}$, $\epsilon_{\text{dis}}$ and
$\epsilon_{\text{syn}}$ are the probabilities of at least one logical failure,
at least one faulty T distillation, and at least one failed rotation synthesis
respectively. In our estimates, we retain only the first order terms in these
small probabilities. We ensure Eq. (10) is satisfied by requiring that each of
$\epsilon_{\text{log}}$, $\epsilon_{\text{dis}}$ and $\epsilon_{\text{syn}}$
are at most $\epsilon/3$.

We assume the PSSPC compilation strategy from Appendix D, which sets the
number of logical qubits $Q$ and the number of T states consumed $M$. This
also specifies a minimum possible logical runtime of the algorithm
$C_{\text{min}}$. In what follows we establish the code distance $d$ required
for error correction, the choice of distillation factory $\mathcal{D}$, the
number of distillation factories $F$, and the number of logical time steps
$C$. We then use these to identify the number of physical qubits $q$ and
runtime $t$.

Before computing these quantities, let’s consider the need to balance the
speed of the algorithm vs. the rate of T state production. From Appendix D, we
know that the algorithm requires at least $C_{\text{min}}$ time steps. That
is, we are free to run the algorithm at any desired speed by choosing $C\geq
C_{\text{min}}$. Similarly, we are allowed to choose the number of factories
$F$ and control how many T states are available for the algorithm per logical
time step. However, we require that for any chosen value of $C$, $F$ must be
chosen large enough to produce all the required T states for the algorithm
within $C$ time steps. Therefore, with large $C$, as we slow down the
algorithm, we can afford to reduce the number of T factories and save qubits
required for their implementation888Note that slowing down the algorithm may
not always result in a reduction in overall qubit counts. As the algorithm is
slowed down, we can use lesser T factories and incur less qubit overhead for
them. But for the algorithm’s logical qubits, the code distance depends on the
number of logical time steps (see Eq. (11)). We may require a higher code
distance to protect the algorithm qubits during a slower execution. Similarly,
as we speed up the algorithm to finish in the least number of logical time
steps possible, we require a large number of T factories to quickly supply the
required T states, and incur higher qubit overheads. To navigate this space-
time tradeoff, we fix a scenario such as space-optimal or time-optimal or an
intermediate case and choose suitable values for $C$ and $F$. In what follows,
we present the analysis for the general case where some $C\geq C_{\text{min}}$
has been selected.

Estimating resources for logical operations: We determine the number of
physical qubits and time required for the logical operations by selecting an
appropriate code distance used for the logical qubits. From Eq. (1), we see
that $d=2\log(a/P)/\log(p^{*}/p)-1$ for constants $a$ and $p^{*}$ that depend
on the type of physical qubit chosen in the architecture. Seeking the smallest
error correction overhead that achieves an acceptably low probability that
logical failure occurs in the implementation of the algorithm, i.e., that
$QCP=\epsilon_{\text{log}}\leq\epsilon/3$, we select the following distance,

$\displaystyle
d=\left\lceil\frac{2\log(a\epsilon/(3QC))}{\log(p^{*}/p)}-1\right\rceil_{\text{odd}}.$
(11)

We then obtain the physical run time by multiplying the number of logical time
steps $C$ by the time per logical time step $\tau(d)$ as defined in Appendix
B,

$\displaystyle t=\tau(d)C.$ (12)

Similarly, the number of physical qubits required for the logical operations
is $Qn(d)$. Note that the code distance is a function of $C$. If $C$ is chosen
to be much higher than $C_{min}$ to reduce the number of factories, we may
require a higher code distance to protect the algorithm qubits for the longer
execution duration.

Estimating resources for T distillation: Next, we determine $\mathcal{D}$, the
number of factories and the physical resources required for distillation.
Towards this, we first require the number of T states required by the
algorithm at the given error budget. That is, we need to satisfy Eq. (9) with
$\epsilon_{\text{syn}}\leq\epsilon/3$, which allows us to calculate $M$, the
minimum number of T states required. Next, we determine the quality of these T
states. In Table 3, we show the number of physical qubits $n(\mathcal{D})$ and
the time $\tau(\mathcal{D})$ to distill a single T state with error rate
$P_{T}$ with various choices of distillation factory $\mathcal{D}$. As we aim
for the $M$ injected T states to fail with low probability, we require that
$MP_{T}(\mathcal{D})=\epsilon_{\text{dis}}\leq\frac{\epsilon}{3}$. Given a
list of all the considered factories with the specified hardware type
$\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\dots,\mathcal{D}_{m}\\}$,
we therefore select $\mathcal{D}$ as the factory with the smallest space-time
footprint which satisfies this inequality, i.e.,

$\displaystyle\mathcal{D}=\operatorname*{arg\,min}_{\mathcal{D}_{i}\in\\{\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3},\dots,\mathcal{D}_{m}\\}}{\\{n(\mathcal{D}_{i})\tau(\mathcal{D}_{i})|P_{T}(\mathcal{D}_{i})\leq\epsilon/3M\\}}.$
(13)

Finally, the smallest number $F$ of distillation factories capable of
producing the demanded $M$ T states during the algorithm’s run time is
selected

$\displaystyle F=\left\lceil\frac{M\cdot\tau(\mathcal{D})}{M(\mathcal{D})\cdot
t}\right\rceil.$ (14)

At this point a check should be made to ensure that the factories execute
during the runtime of the algorithm, i.e., that
$\tau(d)C\geq\tau(\mathcal{D})$. This catches the case when the runtime of an
algorithm is less than the runtime of a single T factory. If this is not
satisfied, $C$ should be increased and the analysis repeated.

Total resources: The total number of qubits $q$ for the quantum computation is
then found from adding those qubits for distillation to those required to
build the logical qubits,

$\displaystyle q=Fn(\mathcal{D})+Qn(d).$ (15)

The total runtime of the algorithm is given by Eq. (12).

##  Appendix F Applications

Here we provide further details of the three example applications, and the
calculations that result in the resource estimates in Table 4.

Before getting into specifics about each of three application examples, we
make a remark about quantum algorithm sampling. Throughout this work, we are
focused on the resources required to implement a full quantum algorithm once,
however it is often the case that quantum algorithms must be repeated (even
when run perfectly). This is because the output of some quantum algorithms is
not a deterministic bit string, but instead is a drawn from a probability
distribution over bit strings, and the information from the algorithm may
require learning details of the distribution, requiring a set of samples. We
do not account for the resource costs that algorithms may need to be sampled
many times in this work. This could in principle be achieved by either re-
running the algorithm consecutively on the available quantum computer, or by
having many independent quantum computers running in parallel, or some
combination.

Quantum dynamics.— Here we outline the calculation that produced the resource
requirements of the quantum dynamics example in Table 4, following the
approach in Ref. Pearson2020 . We are interested in the time evolution
$e^{-iHt}$ by the 2D $\sqrt{N}\times\sqrt{N}$ transverse field Ising
Hamiltonian

$\displaystyle H=\underbrace{-J\sum_{\langle
j,k\rangle}Z_{j}Z_{k}}_{A}+\underbrace{g\sum_{j}X_{j}}_{B}$ (16)

with nearest-neighbour interactions is accomplished using fourth-order product
formulas. Trotter & Suzuki Hatano2005TrotterSuzuki  define a recursive
construction using

$\displaystyle U_{2}(\Delta)$
$\displaystyle=e^{-iA\Delta/2}e^{-iB\Delta}e^{-iA\Delta/2}=e^{-iH\Delta}+\mathcal{O}(\Delta^{3}),$
(17) $\displaystyle U_{4}(\Delta)$
$\displaystyle=U_{2}(\gamma\Delta)U_{2}(\gamma\Delta)U_{2}((1-4\gamma)\Delta)U_{2}(\gamma\Delta)U_{2}(\gamma\Delta)=e^{-iH\Delta}+\mathcal{O}(\Delta^{5}),$
$\displaystyle\gamma$ $\displaystyle=(4-4^{1/3})^{-1}.$

When applying $T>1$ time steps steps, the first and last terms may be merged,
leading to $10T+1$ exponentials in Eq. (17). Note that $A$ and $B$ may be
interchanged depending on which is more expensive. These product formulas
reduce the resource costs of quantum dynamics to evaluating the resource cost
of applying $e^{-iA\Delta}$ and $e^{-iB\Delta}$. All terms in $A$ commute and
similarly for $B$, and $e^{-iB\Delta}$ is the product of $N$ single-qubit
rotations $\prod_{j}e^{-iX_{j}g\Delta}$. The simulation can be carried out by
assigning a qubit to each of the $N$ sites in the lattice, such that
$Q_{\text{alg}}=N$. By conjugating with a CNOT gate, each nearest-neighbour
$Z_{j}Z_{k}$ term is transformed in to a single-qubit Pauli $Z_{j}$. Thus
$e^{-iA\Delta}$ can be implemented by eight depth-1 layers of $N/2$ CNOT gates
and four depth-1 layers of $N/2$ single qubit rotations
$\prod_{j}e^{iZ_{j}J\Delta}$. The number of rotations is therefore
$M_{R}=(5T+1)N+10TN=(15T+1)N$. Finally, the depth of the rotation gates over
the $T$ time steps is $D_{R}=5T+1+4(5T)=25T+1$.

In the example we consider, we take $\epsilon=0.001$, $N=100$ and $T=20$ such
that when the algorithm, which is initially written as a Q# program, is
explicitly compiled down to a QIR-level program with $Q_{\text{alg}}=100$,
$M_{R}=30100$, $M_{T}=0$, $M_{\text{Tof}}=0$ and $M_{\text{meas}}=1400000$ and
$D_{R}=501$. From Eq. (6), Eq. (8) and Eq. (9), we calculate that with the
PSSPC compilation and layout, the ISA-level executable that this QIR program
would compile down to has $Q=230$ logical qubits, which are needed for at
least $C_{\text{min}}=1.5\cdot 10^{5}$ logical time steps, consuming
$M=2.4\cdot 10^{6}$ T states.

At the physical level, here we illustrate the analysis with the (ns,
$10^{-4}$) qubit example (with the other qubit parameter examples being
analyzed analogously). In this example we will ultimately increase $C$ so that
it is significantly larger than $C_{\text{min}}$ to reduce the qubit count as
a trade-off paid for by an increase in run time. To see why we do so, let us
first consider the case where $C=C_{\text{min}}$. We use Eq. (11) to find the
distance $d=9$, such that $n(d)=2d^{2}=162$ and
$\tau(d)=(4t_{\text{gate}}+2t_{\text{meas}})d=400$ ns. This sets the algorithm