# Assessing the Benefits and Risks of Quantum Computers

Travis L. Scholten111Corresponding author<EMAIL_ADDRESS>IBM, T.J.
Watson Research Center, Yorktown Heights, NY 10598 USA  Carl J. Williams  CJW
Quantum Consulting LLC, Potomac, MD 20854 USA  Dustin Moody  Computer Security
Division, National Institute of Standards and Technology, Gaithersburg, MD
20854 USA  Michele Mosca  evolutionQ, Waterloo, ON, N2L3G3, Canada  Institute
for Quantum Computing, University of Waterloo, Waterloo, ON, N2L3G1, Canada
Perimeter Institute for Theoretical Physics, Waterloo, Ontario, N2L 2Y5,
Canada  William “whurley” Hurley  Strangeworks, Austin, TX 78702 USA  William
J. Zeng  Quantonation, 75010 Paris, France  Unitary Fund, San Francisco,
California 94104, USA  Matthias Troyer  Microsoft Corporation, One Microsoft
Way, Redmond, WA 98052, USA  Jay M. Gambetta  IBM, T.J. Watson Research
Center, Yorktown Heights, NY 10598 USA

###### Abstract

Quantum computing is an emerging technology with potentially far-reaching
implications for national prosperity and security. Understanding the
timeframes over which economic benefits and national security risks (in
particular, via cryptanalysis) may manifest themselves is vital for ensuring
the prudent development of this technology. To inform security experts and
policy decision makers on this matter, we review what is currently known on
the potential uses and risks of quantum computers, leveraging currently-
available research literature.

The maturity of currently-available quantum computers is not yet at a level
such that they can be used in production for large-scale, industrially-
relevant problems, and they are not believed to currently pose security risks.
We identify 2 large-scale trends – the development of new approximate methods
(variational algorithms, error mitigation, and circuit knitting) and the
commercial exploration of business-relevant quantum applications – which,
together, may enable useful and practical quantum computing in the near
future.

Crucially, the new approximate methods discussed do not appear likely to
change the required resources for cryptanalysis applied to currently-used
cryptosystems. From an analysis we perform of the current and known algorithms
for cryptanalysis, we find they require circuits of a size exceeding those
that can be run by current and near-future quantum computers (and which will
require error correction), though we acknowledge improvements in quantum
algorithms for these problems are taking place in the literature. In addition,
the risk to cybersecurity can be well-managed by the migration to new,
quantum-safe cryptographic protocols, which we survey and discuss.

Given the above, we conclude there is a credible expectation that quantum
computers will be capable of performing computations which are economically-
impactful before they will be capable of performing ones which are
cryptographically-relevant.

We hope this work proves informative and useful for those tasked with making
decisions about the use, and future of, quantum computing and quantum-safe
technologies.

###### Contents

  1. Paper Motivation and Overview
  2. 1 Introduction
  3. 2 The Political, Cultural, and Scientific Backdrop
  4. 3 Implications of Quantum Computing for National Prosperity
    1. 3.1 Encouraging Trends in the Research Literature
      1. 3.1.1 Variational Algorithms
      2. 3.1.2 Error Mitigation
      3. 3.1.3 Circuit Knitting
      4. 3.1.4 Commercial Exploration and Adoption of Quantum Computers
    2. 3.2 Realizing Near-Term Value of Quantum Computers
  5. 4 Implications of Quantum Computing for National Security
    1. 4.1 An Overview of Public-Key Cryptosystems
    2. 4.2 Quantum Computing for Breaking Public-Key Cryptography
  6. 5 Evolving Cryptography for the Quantum Era
    1. 5.1 Quantum Safe Approaches
      1. 5.1.1 Quantum key distribution (QKD)
      2. 5.1.2 Quantum random number generation (QRNG)
      3. 5.1.3 Post-quantum cryptography (PQC)
    2. 5.2 Laying the Foundations for Getting Quantum Safe
    3. 5.3 Practical Considerations for Getting Quantum Safe
  7. 6 Conclusion and Discussion
  8. 7 Acknowledgements
  9. A Logical Resource Estimates

## Paper Motivation and Overview

_For brevity, this summary omits nuances explicated in the main text._

Quantum computing poses a known, provable, and substantial risk to the
cybersecurity infrastructure that underpins our modern age. Ever since the
discovery of Shor’s factoring algorithm 30 years ago, the possibility that
quantum computers could be used to break commonly-used cryptographic systems
has loomed large over the development of the field.

Thus, one of the most pressing questions facing quantum computing is whether
the pursuits taken by industry and academia to build a quantum computer will,
at some point, yield the creation of a cryptographically-relevant quantum
computer (which can break cryptography) either prior to, or in parallel with,
the creation of a quantum computer useful for non-cryptographic applications.
This uncertainty is driven by 2 factors.

The first factor is the uncertainty over how the scaling of quantum computers
would proceed222Here, scaling refers to the size (number of gates) of the
quantum circuits a quantum computer could run. A rough proxy for the size of a
quantum circuit is the product of its width (the number of qubits it acts on)
and its depth (the number of primitive layers/timesteps). Note that “quantum
circuits” refers to programs which run on quantum computers.. Should quantum
computers scale rapidly (i.e., faster than the time period over which
organizations could transition to post-quantum cryptographic systems), then
the risk posed by the development of such computers is substantial. On the
other hand, should the scaling proceed more slowly (i.e., organizations have
sufficient time to transition their cryptographic infrastructure), then the
risk posed, while real and important, is more minimal.

The second factor is that when algorithms for cryptanalysis or useful use
cases are studied, the required resources for both kinds of uses appear
roughly comparable. That is, there exist relevant instances of cryptanalysis
whose quantum circuits require resources comparable to relevant instances of
potentially commercially-useful applications (see Figure 2 in the main text).

Regarding the first factor, many companies have published forward-looking
roadmaps describing the capabilities they envision their hardware will have.
These roadmaps help make clear the evolution of quantum computing hardware.
Many roadmaps envision a key ingredient to scale quantum computers – namely,
quantum error correction – should be available by the end of this decade.
While much research and development needs to take place, the physics and
engineering of quantum computers has been de-risked to the point where these
roadmaps should be given credence. Given this, we do not focus on this factor
in this work. This said, it is important to note that the quantum computers
envisioned in the roadmaps would not be useful for cryptanalysis, given what
is currently known about the resources required for those types of problems.

Instead, we survey the literature regarding the second factor. The primary
uncertainty facing quantum computers over the next few years is whether any
applications at all can be realized using current or near-future quantum
computers in the absence of (or with minimal) error correction.

Both error-corrected and non-error-corrected quantum computers are noisy, the
difference between them being how noisy they are. In general, error-corrected
quantum computers (with sufficiently-low physical error rates) can be made
substantially (exponentially) less noisy than non-error-corrected ones through
the use of error-correcting codes. Whether a given use case or application can
be realized hinges quite strongly on how much noise can be tolerated in the
execution of the requisite circuits before its output is corrupted. The
quantum algorithms community has devoted substantial effort to understanding
the properties of the circuits needed to realize both useful and cryptographic
applications (which we review in Section 3). The prevailing, commonly-held
perspective is “Realizing quantum applications (of any kind) requires running
a single, large-sized quantum circuit, and doing so is only possible with the
use an error-correcting code.”.

One of the defining features of the algorithms usually considered in those
works is the algorithm uses the repeated execution of a single, large-sized
circuit. (Here, “size” means the number of gates in the circuit, a rough proxy
for which is the product of the number of qubits the circuit acts on with the
number of elementary timesteps of the circuit.) Given this, it is not
surprising that error correction is needed: in order to run large-sized
circuits accurately, very low noise rates are required.

However, the above analysis also implies that the smaller the size of the
circuit required, the more likely the successful execution of that circuit can
be realized on current (or near-future) quantum computers and consequently,
the realization of any use cases or applications which require those circuits.
Thus, the question of whether near-future quantum computers can run useful
applications is directly related to the question of whether small-sized
circuits can be used to realize them.

From our survey of the research literature, we argue there are 3 major trends
which suggest this possibility: the development of new kinds of quantum
algorithms which require small-sized or shallow-depth circuits, new techniques
for managing the impact of noise when executing quantum circuits, and new
methods for decomposing large circuits into smaller ones. All of these trends
utilize the repeated execution of a diverse number of circuits. And all of
them are amenable to being used with current and near-future quantum
computers. Thus, while realizing quantum error correction continues to be
essential and vital for realizing the full potential of quantum computing, it
may be possible that near and near-future quantum computers can be put to use
to tackle interesting problems, even in the absence of fault-tolerance.

The first method – new kinds of quantum algorithms – concerns the development
of variational algorithms using circuits which can be customized to both the
problem at hand and the quantum computer on which the circuit is being run.
Importantly, this means these algorithms can be used in a flexible way to
scale up the size of the circuits run to the limits of what the hardware could
natively support. These algorithms do require the execution of numerous
circuits, though. These algorithms can be run on currently-available quantum
computers, and should make it easier for quantum computers to run
sufficiently-complex circuits as to be useful for scientific or commercial
purposes. We discuss variational algorithms in Section 3.1.1.

The second method – new techniques for managing the impact of noise – concerns
the development of quantum error mitigation. These techniques use the repeated
execution of an ensemble of circuits, along with classical post-processing, to
estimate the output which would be obtained from a noiseless quantum computer.
(Phrased another way, they extract more signal from the execution of quantum
circuits on noisy hardware.) Error mitigation can be used with both
variational and non-variational algorithms, and extend the reach of the
hardware with respect to the size of the circuits it can run. We discuss
quantum error mitigation in Section 3.1.2.

The third method – decomposing large-sized circuits into smaller-sized ones –
is called circuit knitting. This is a family of techniques which can be used
to reduce the size (or depth) of the circuit by reducing the number of qubits
(or timesteps) required, at the expense of needing to run more circuits. The
results which would be obtained from a larger circuit are computing using
classical post-processing of the results obtained from the set of smaller-
sized circuits. Since the circuit size is smaller, they can be run on current
and near-future quantum computers, and incur less error, than attempting to
run the larger circuit. We discuss circuit knitting in Section 3.1.3.

With these techniques, it becomes possible to successfully run circuits on
current and near-future quantum computers whose size exceeds that feasible for
brute-force classical computation. In addition, it is known that for some
problems, small-sized circuits offer provable advantage relative to classical
ones. However, both of these results say nothing about whether small-sized
circuits are useful for commercial or business applications. Thankfully, a
rapidly-expanding commercial ecosystem is exploring the adoption of quantum
computing by business. The fact that the commercial ecosystem is engaged in
this sort of work should enable the discovery of key business-relevant-
problems where a new approach is needed, and the efficacy of quantum is
evaluated. Crucially, these explorations can leverage all of the
aforementioned advances. Industry is preparing, and many hands make light work
of finding commercially-useful applications. We discuss the commercial
sector’s exploration of quantum computing in Section 3.1.4.

Thus far, we’ve noted that variational algorithms, error mitigation, and
circuit knitting allow for quantum computing hardware to run circuits whose
size (and depth) is larger than what the hardware might otherwise natively be
able to support. And we’ve said the commercial sector can use these methods to
explore problems of business relevance. A question arises, though: “What is
the significance of this for cryptanalysis?”. We discuss this question in
Section 4. We find that to date, the literature has not identified a viable
path by which these techniques could enable current or near-future quantum
computers to attack currently-used cryptosystems. What’s more, based on an
analysis of the key sizes of currently-used cryptosystems and known algorithms
for attacking them (e.g., Shor’s), we find that the size of the circuits
required to attack them is so large that it is extremely unlikely that such
circuits can be run without fault tolerance (see Section 4.2).

Further, the remedy to the cybersecurity threat is already known and
understood; namely, the need for organizations to transition to quantum-safe
cryptographic protocols as soon as possible. We discuss various approaches to
doing so in Section 5.1, and outline how organizations can begin getting
quantum safe in Sections 5.2 and 5.3.

The themes identified in this survey imply advances in hardware, software, and
algorithms are proceeding apace, and it is increasingly likely quantum
computers will be useful sooner rather than later. What’s more, given it is
highly-probable that the threat to cybersecurity will materialize only after
fault-tolerance has been prototyped – and that this development is anticipated
to happen in the late 2020s – it is reasonable to surmise that the quantum
computers being built for today and the next several years will not beget a
cybersecurity risk. Hence, it is probable that scientific or commercial
benefits will be attained through the use of quantum computers before
cybersecurity risks are realized.

In sum, while the cybersecurity concerns regarding quantum computing are valid
and should be taken seriously by agencies and organizations, those concerns
should not prevent taking seriously as well the potential end-benefits of
using quantum computers for practical problems. Getting both quantum-ready and
quantum-safe are crucial activities for agencies and organizations to engage
with. For policy makers and regulators, it is crucial to find the “middle way”
between the mania of overexuberance in response to quantum hype and the
despair of being afraid of cybersecurity threat. Principled and informed
regulations and controls can be crafted; such policies need to take a balanced
approach to ensuring the end-user- benefits of quantum computers are realized,
while ensuring the cybersecurity risks are managed.

##  1 Introduction

Although the subject of quantum computation has received much media attention
in recent years, the topic is not nearly as new as reports may suggest. One
could argue the idea was first introduced by Richard Feynman in a December
1959 speech “There’s Plenty of Room at the Bottom”[1], where he states:

> When we get to the very, very small world—say circuits of seven atoms—we
> have a lot of new things that would happen that represent completely new
> opportunities for design. Atoms on a small scale behave like nothing on a
> large scale, for they satisfy the laws of quantum mechanics. So, as we go
> down and fiddle around with the atoms down there, we are working with
> different laws, and we can expect to do different things. We can manufacture
> in different ways. We can use, not just circuits, but some system involving
> the quantized energy levels, or the interactions of quantized spins, etc.

In this speech, Feynman recognized the quantum-mechanical world provided an
opportunity to do things that wouldn’t normally be doable at the level of the
macroscopic, classical world. (Though it should be noted the use of the word
“circuits” above would not have been in reference to quantum circuits, defined
previously.) Feynman further elaborated on this idea in his 1981 speech
“Simulating Physics with Computers” [2], where he discussed the problem of
using computers to simulate physical systems. His conclusion – “…and if you
want to make a simulation of Nature, you’d better make it quantum mechanical,
and by golly it’s a wonderful problem, because it doesn’t look so easy.” – is
a profound one. Even at this early stage of the field of quantum information
science, the potential impact of computers operating on quantum-mechanical
principles was seen to be just as unprecedented in the history of computation
as the introduction of classical computers themselves. Feynman clearly
anticipated that quantum computing hardware would be able to efficiently solve
or emulate quantum problems, something which appeared to have exponential
overhead if done classically. A “second quantum revolution” – one in which
quantum-mechanical behavior was harnessed and directly put to use – was
beginning to occur, distinct from the advances of the first which had given
birth to the semiconductor industry, lasers, and atomic clocks [3, 4].

In the 1980’s, other individuals began to theoretically explore the concept
of, and applications for, a quantum computer. Paul Benioff proposed the idea
of a quantum Turing machine – an idea which ultimately lead to the definition
of a universal quantum computer [5]. This was followed by several
theoretically-interesting, yet largely impractical, quantum algorithms
including Deutsch’s quantum oracle algorithm [6], the Bernstein-Vazirani
algorithm [7], and Simon’s algorithm [8].

Peter Shor’s 1994 discovery of a polynomial time quantum algorithm for
factoring integers and computing discrete logarithms [9] was a breakthrough
which stimulated tremendous interest in quantum computing [10]. This was the
first quantum algorithm to show a super-polynomial speedup over classical
algorithms capable of solving the same problem. Shor’s algorithm was followed
by Grover’s unstructured search algorithm in 1996 [11], followed by a proof of
Feynman’s 1981 conjecture showing quantum computers could simulate quantum
systems without the exponential overhead incurred by classical computers [12].

While Feynman’s speeches clearly precede Shor’s algorithm, many scientists
believe the discovery of Shor’s algorithm stimulated the growing field of
quantum information science. Importantly, one of the key results from research
following Shor’s algorithm was the discovery of quantum error correction [13,
14], which established the conditions under which the inherently-fragile
information encoded and processed in a quantum computer could be manipulated
in a fault-tolerant manner [15, 16]. (For surveys on the topic of quantum
error correction, see [17, 18, 19, 20, 21].) Soon after this discovery was the
development of theory of fault-tolerant quantum computation [22]. Of
particular importance was the discovery of the threshold theorem, which
established that if the underlying error rates in a quantum computer could be
brought low enough, then error-correcting codes could be used to exponentially
suppress errors with a polynomial overhead [23, 22, 24, 25].

Together, Shor’s algorithm and the discovery of quantum error correction
further ignited interest in quantum information science. This can clearly be
seen by the explosive growth of papers and articles on quantum information and
quantum computation beginning around 1994. Crucially, this meteoric growth
also encompassed advances in harnessing and controlling quantum-mechanical
systems to make them do computation, with the first quantum gate in 1995 [26]
based on a concept introduced earlier that year [27], followed by a first
demonstration on Shor’s algorithm on a liquid state Nuclear Magnetic Resonance
system [28]. Shor’s algorithm, along with the proof of Feynman’s 1981
conjecture and the discovery of quantum error correction, implied that a
quantum computer, if successfully built, would have extraordinary impact on
society and mankind.

As a result of those early efforts, numerous groups began exploring the
possibilities of building quantum hardware based on various underlying qubit
modalities (types)333The qubit (“que-bit”) is the fundamental unit of
information in a quantum computer, and is the quantum analogue of the
classical bit.,444Modalities currently being investigated include
superconducting circuits [29, 30], trapped ions [31, 32, 33], neutral atoms
[34, 35], silicon [36, 37], photonics [38, 39, 40], and several others..
Simultaneously, but at a slower rate of progress, scientists developed and
improved the understanding of quantum complexity classes, and initiated the
difficult process of discovering other possible classes of algorithms
benefiting from the existence of a quantum computer. For most of the next two
decades, the exploration of quantum hardware, algorithms, and software largely
proceeded independently. It was only in the mid 2010’s that full-stack quantum
computing efforts emerged.

Against this backdrop, the spectre of whether, and/or when, a
crytographically-relevant quantum computer – one which would threaten
currently-used cryptographic systems – could be built has loomed large. (An
equivalent phrase also sometimes used is “cryptanalytically-relevant quantum
computer”.) In the early days of quantum computing, sufficiently little was
known about the potential benefits of quantum computers (besides their use for
simulating quantum-mechanical systems) that identifying whether the economic
benefits outweighed the national security risks was difficult. Over the past
decade though, a proliferation of work on the applications of quantum
computers to problems of commercial and scientific interest has taken place.
This work informs the analysis we give here.

The remainder of this paper will begin with a review of our broad
understanding of the potential benefits the use of quantum computers may bring
to society. We describe the rapid advances being made and the best
understanding of the required capabilities needed by a quantum computer to
bring such benefits in Section 3. In Section 4, we discuss the impact of
quantum computing on national security, by reviewing of the evolution of
public-key cryptography – as this appears to be the most pressing risk created
by quantum computers – in Section 4.1, and providing a careful analysis of the
capabilities a quantum computer would need to break current public-key
cryptosystems in Section 4.2. In Section 5 we discuss the advent of post-
quantum cryptography and the steps organizations can take to begin migrating
their cryptographic systems to ensure information safety and security as
quantum computing systems mature. We conclude in Section 6 with a few comments
which we hope will help drive informed discussions amongst security experts
and policy makers.

##  2 The Political, Cultural, and Scientific Backdrop

Ever since the early days of quantum computing, the United States government
(USG) has provided substantial support and funding to the development of this
technology, from a hardware, software, theory/applications, and computational
science perspective. The policy decisions taken by the USG have profoundly
influenced the trajectory by which quantum computing has developed. We briefly
review some of the key policy-related activities before turning to the
relatively recent uptake of quantum computing by the private sector.

In 2009, the National Science and Technology Council (NSTC), a Cabinet-level
council within the Executive Office of the President responsible for
coordinating USG science and technology policy, published the USG’s first
official policy recommendations for quantum information science [41]555It
should be mentioned the Department of Defense, in coordination with the
National Security Agency, had funded quantum computing research since the
mid-1990’s and that numerous agencies had previously written reports on both
quantum information science and quantum computing.. This document shows the
USG clearly understood quantum technology was going to be a disruptive one,
and have an impact on the $21^{\text{st}}$ century. It was understood that
sometime in the following decade, industry would begin to invest in this
nascent emerging technology. The 2009 NSTC report was followed by another NSTC
report in 2016 [42] identifying quantum information science as a priority for
Federal coordination and investment. Finally, in 2018 the NSTC produced a
report outlining a set of policy strategies the USG could take to further
foster the development of quantum technologies [43]. That same year, the
National Quantum Initiative Act (NQI Act) was passed and signed into law. The
act provided significant resources to grow the necessary workforce essential
to the commercial development and deployment of this technology that was
already underway666In reality, industry and venture capitalists in the United
States had already started aggressively moving into the quantum space a few
years earlier [44]., and to facilitate coordination amongst the private
sector, USG entities, and academia [45, 46, 47]. Additional history of US
policy in quantum computing (and quantum technologies777“Quantum technologies”
usually refers to the trio of quantum computation, communication/networking,
and sensing. more broadly) may be found at [48] and [49].

We note the USG is not alone in developing and establishing a strategy around
quantum computing and quantum technologies. Other governments have established
whole-of-government plans and strategies, including the European Union (and
member states), the United Kingdom, Canada, Australia, New Zealand, Japan,
Switzerland, Singapore, Thailand, Qatar, Israel, South Korea, India, South
Africa, Brazil, Canada, and China. A summary of these investments may be found
at [50]. Figure 1 presents an estimate of the cumulative announced investments
across the globe. Please note this figure shows the total announced (not
necessarily deployed) investment, and that the investments are being pursued
over different timescales, depending on the entity involved. Figure 1 clearly
shows that interest in quantum technologies is strong, and transcends socio-
cultural boundaries888We note in passing that, in addition to the initiatives
shown in Figure 1, quantum technologies are also featured prominently in
recently-announced international partnerships, being incorporated into “Pillar
2” of the 2021 AUKUS agreement between Australia, the United Kingdom, and the
United States [51], as well as being the subject of several bilateral
agreements between the US and various nations [52]. Many other agreements
exist as well, either between nation-states or regional ecosystem partners..

Figure 1: Estimated cumulative announced public-sector investments in quantum
technologies. Many governments have announced substantial investments in
quantum technologies. The numbers above represent estimates of the total
announced (not necessarily deployed) investment. In addition, these
investments span different time horizons, with different start and end dates.
Hence, a country-to-country comparison is complicated. Many details and
further references are provided in [50], from which this image is taken and
used with permission.

In the US, the passage of the NQI Act reinforced the importance of quantum
technologies for the USG. Its importance to private industry has been made
clear by developments starting almost a decade ago. By the mid 2010’s,
multiple big-tech and startup companies had created research and development
programs to develop quantum computers in the United States [53, 54]. Some of
these were fully integrated and others were hardware- or software-specific.

The private sector was the source of a disruptive moment in May of 2016, with
the launch of the first cloud-based platform for accessing gate-based quantum
computers by IBM [53]. This event highlighted that quantum computing was
moving out of the lab and into the world. This launch was followed a year
later by one from Silicon Valley startup Rigetti Computing [55]. Both launches
underscored that venture funded startups, in addition to establish tech
companies, were in the quantum computing race. The launches highlighted some
of the complexities of deploying quantum computing systems to the cloud in a
reliable and robust manner, which has spurred industry to adopt a holistic,
systems-engineering-based approach to standing up and deploying quantum
computers.

One of the key challenges in making quantum computers accessible (and useful!)
to end-users is dealing with the noise or errors, which degrade the quality of
the quantum computation and limit a quantum computer’s capabilities. Reducing
noise and errors is thus essential. In addition to driving down the rate of
errors in the underlying hardware, it is necessary to realize large-scale
error correction to unlock the full potential of quantum computers from an
end-user or application perspective. Error correction can reduce (to arbitrary
levels) the effect of noise. With it, from a large number of noisy physical
qubits $n$, a number of logical qubits $k$ which are substantially less
noisy999The exact relationship between $n$ and $k$ depends on a variety of
factors, including the error-correcting code used, assumptions about the
noise, the physical layout of the qubits, etc. . are generated101010Roughly
speaking, for a code with distance $d_{C}$ (a measure of the number of errors
it can correct) and threshold $p_{\mathrm{th}}$ (the maximal error rate below
which increasing the code distance $d_{C}$ results in an exponential
suppression of the error), if the _bare_ or _physical_ error rate is
$p_{\mathrm{ph}}$, then the _logical_ error rate $p_{\mathrm{L}}$ goes as
$p_{\mathrm{L}}\sim(p_{\mathrm{ph}}/p_{\mathrm{th}})^{\mathcal{O}(d_{C})}$..
In addition to generating logical qubits, error-correcting codes define
procedures for implementing error-corrected gates on them.

The “holy grail” for quantum computing is realizing a fault-tolerant quantum
computer. Doing so requires attaining all of the DiVincenzo criteria for
quantum computing [56] – originally proposed as criteria for physical
implementations of quantum computers – at a logical level; see Table 1. For a
quantum computer to be fault-tolerant, all of these “logical” DiVincenzo
criteria need to be attained simultaneously.

Physical |  Logical
---|---
A scalable physical system with well-characterized qubits |  A scalable encoding into well-characterized error-correcting codes
The ability to initialize the system to a simple fixed state |  The ability to initialize the system to a simple fixed state and inject magic states
Long relevant decoherence times |  The error-correcting code used suppresses errors far below the physical error rates, and larger codes suppress more errors
A universal set of quantum gates |  A universal set of logical quantum gates
A qubit-specific measurement capacity |  A qubit-specific measurement capacity
Table 1: The DiVincenzo Criteria. The physical version of these criteria was
introduced in [56] to describe the requirements needed to achieve scalable
quantum computation. The corresponding version of each criteria applicable to
fault-tolerant quantum computation is given.

In recent years, a new set of techniques has been developed for dealing with
errors in a manner different than error correction. These error mitigation
techniques were disseminated through a number of pioneering papers [57, 58,
59] in 2017 and 2018. Error mitigation uses classical post-processing of
results obtained from running an ensemble of quantum circuits to estimate what
results would have been obtained from a noise-free quantum computer111111The
quantum circuit is the fundamental unit of computation for a quantum computer.
Circuits act on qubits to encode and process information.. In addition to the
works just noted, subsequent ones from the community have indicated that error
mitigation could be a viable path to both unlocking utility from near-term
quantum computers, as well as achieving error-corrected quantum computation.
We defer an in-depth discussion of error mitigation to the next section.

As quantum computers were being made accessible to end-users, a publication in
2018 crystallized 3 key needs the quantum computing community (academics and
industry) needed to address [60]:

  1. (1)

Build and deploy quantum computing systems capable of performing tasks which
are, for all practical purposes, beyond the capabilities of purely-classical
computers.

  2. (2)

Leverage this hardware to explore problems of scientific and commercial
interest.

  3. (3)

Bridge from near-term towards fully fault-tolerant quantum computing.

The advent of quantum computing in the cloud, the passage of the NQI Act, and
the publication of the above-mentioned work were, collectively, a watershed
moment for the quantum computing industry. Big-tech companies continued making
substantial investments in their teams. Venture capital took even more of an
interest in this technology, and began supporting the nascent quantum
industry, with an annual investment exceeding $2 billion USD in each of 2021
and 2022 [61, 44] and estimated to reach approximately $1.5 billion USD in
2023 [44]. This funding has been deployed abroad across the broad quantum
industry, with the largest bets being made on quantum computing hardware and
quantum software companies.

Five years later, the quantum computing industry has made substantial progress
in realizing the ideas presented in [60]. Quantum computing systems are being
built and deployed that can run quantum circuits whose scale makes exact and
direct verification using classical computers difficult. These, and other,
systems, have been made accessible to academic and industrial end-users, who
have leveraged them to explore possible applications and use cases (see
Section 3). Finally, the theory and implementation of quantum error correction
has experienced significant progress. We highlight exciting aspects of this
progress in the paragraphs below.

(1) Build and deploy quantum computing systems capable of performing tasks
which are, for all practical purposes, beyond the capabilities of purely-
classical computers

The quantum systems made available via the cloud in 2016 were not, by any
means, capable of performing “beyond-classical”-type tasks. (And the nature of
the kinds of tasks which could be called “beyond classical” was unclear.) For
the systems themselves, the complexity of the circuits which could be run on
them – the circuit width (number of qubits) and circuit size (number of gates)
– was quite small, for at least 3 reasons. First, the systems had a small
number of qubits, limiting the width of the circuits which could be run.
Second, the systems had (comparatively) high levels of noise, limiting the
size of the circuits which could be run. Third, there was a dearth of
available software-defined techniques by which the effect of noise and
availability of a limited number of qubits could be managed.

Today, the situation has evolved. Systems are being built with increasing
numbers of qubits, and the error rates are going down. Further, software
capabilities are being deployed that enable quantum computers with a given
qubit count and error rates to execute circuits whose width exceeds the qubit
count and whose size is sufficiently high that extracting a signal from the
noise is difficult.

A first foray into beyond-classical computation occurred with experiments by
Google [62, 63] and Xanadu [64] using superconducting and photonics-based
quantum computers, respectively. In addition, Chinese researchers have also
demonstrated these experiments on both superconducting [65, 66] and photonic
[67, 68] platforms. For a history of these experiments, see [69]. The task
performed in these experiments was sampling from the output distribution of
random quantum circuits [70, 71]. (For a review of the task of random circuit
sampling and the analysis of its hardness, see [72].) However, while this task
is hard for classical computers to do assuming the quantum computer running
the circuits is noise-free [73], the addition of noise changes the difficulty
of the task for classical computers [74]. In addition, advances in classical
techniques have substantially lessened the relative advantages of using a
quantum computer for this task [75, 76, 77, 78, 79].

Recently, an additional foray has been pursued with quantum utility
experiments by IBM [80]. The task performed in this experiment was accurately
estimating expectation values (averages) of quantum-mechanical observables for
non-trivial circuits based on two-dimensional (2D) spin models. This
experiment showed that error mitigation techniques [81, 82] work for quantum
computers at the scale of 127 qubits and 2880 gates – well beyond exact
classical simulation of quantum circuits. However, due to the problem
considered being relatively simple, it triggered a number of works exploring
classical simulation methods beyond standard approaches [83, 84, 85, 86, 87,
88, 89]. This stream of results, both from quantum and classical methods, has
opened an interesting path where quantum computers could potentially be used
to validate and help develop classical simulation methods.

A key difference between these two forays is the way in which noise is
handled. In the first foray, noise is dealt with through improvements in
hardware. However, the effect of noise is still present in these experiments.
In the second foray, the effect of noise is mitigated, so the experiment
produces reliable results which can be trusted. However, due to the potential
exponential overhead of the error mitigation methods used, simple comparisons
to purely-classical methods do not exist (and remains an open research
question).

(2) Leverage this hardware to explore problems of scientific and commercial
interest.

In parallel with these developments, industry has been making quantum
computers accessible for academic and commercial users. Companies such as IBM
(2016) [53], Rigetti (2017) [55], Quantinuum (2020) [90], IonQ (2020) [91],
Xanadu (2020) [92], Google (2020) [93], Oxford Quantum Circuits (2021) [94],
QuEra (2022) [95], Pasqal [96] (2022), and Quandela (2022) [97], have made
their systems available via the cloud, and others such as Amazon (2020) [91],
Strangeworks (2021) [98], Microsoft (2021) [99], and T-Systems (2023) [100]
have enabled a reseller model through their web-based services. As a result,
the amount of research on, with, and for quantum computers has exploded [101].
For example, the number of scientific papers which used systems available via
IBM’s quantum cloud service alone since 2016 is up to around 2,800 at the time
of this writing, and the number of circuits executed via that service has
exceeded 3 trillion.

Further, industry and academia have defined new methods for evaluating the
quality of quantum computers [102, 103, 104, 105, 106, 107] as well as
developing frameworks by which performance measures can be consistently
evaluated across different quantum computers [108].

We defer to the next Section our discussion of the applications of quantum
computers to problems of scientific and commercial interest.

(3) Bridge from near-term towards fully fault-tolerant quantum computing.

Industry has continued to work on realizing a large-scale, fault-tolerant
quantum computation in several ways:

  1. 1.

Pursuing improvements in hardware error rates, to realize higher-quality
qubits and operations on them. These improvements have taken place across a
wide variety of qubit modalities [109, 112, 34, 113, 114, 115, 116, 117, 118,
110, 111]. Improving the quality of the qubits and operations is necessary for
realizing fault-tolerant quantum computing, as well as unlocking near-term
utility.

  2. 2.

Demonstrating some of the fundamental techniques required for error correction
[119, 121, 122, 123, 124, 125, 126, 127, 128, 120]. These constitute the first
steps toward unambiguous demonstration of logical qubits, and as the
previously-outlined “logical” DiVincenzo criteria are implemented, we expect
to see very small numbers of logical qubits used to run simple quantum
algorithms in a fault-tolerant manner in the near future.

  3. 3.

Advancing the theory of quantum error correction to yield insights about new
families of quantum error-correcting codes which have more favorable
properties than commonly-studied ones, and whose properties also most closely
match classical codes121212This will likely be crucial for scaling fault-
tolerant systems, as it is known that any planar code satisfies $k/n\leq
1/(cd^{2})$ for code distance $d_{C}$ and a constant $c$ [129]. That is, for a
fixed number of physical qubits $n$, as the code distance $d_{C}$ is increased
– and hence the code could correct more errors – the number of logical qubits
$k$ decreases. Breaking this bottleneck requires developing new
codes.,131313See [130] for a detailed list of error-correcting codes.. For
example, recently-discovered “quantum low-density parity-check” (qLDPC) codes
offer more favorable encoding rates (i.e., higher values of the ratio $k/n$)
than previously-studied qLDPC codes (such as the surface code [131, 132]), and
the number of errors they can correct is higher [133, 134, 135, 136, 137,
138]. In addition, qLDPC codes (and others) could potentially be used to
realize a fault-tolerant quantum memory [139, 140]. These codes are being
incorporated into industry roadmaps, and significantly increase the likelihood
of the successful introduction of a small-scale error-corrected system by the
end of this decade.

  4. 4.

Identifying new pathways for bridging the gap from near-term to fault-tolerant
quantum computing through the use of error-mitigation for certain sub-routines
in error correction (namely, $T$-state distillation) [141, 142]. By combining
error mitigation with error correction, it may be possible to more efficiently
realize the successful execution of circuits at a scale beyond error
mitigation alone [143, 144, 145, 146, 147].

In retrospect, the wide availability of quantum systems in the cloud along
with open source software to program them since 2016 constituted a turning
point towards creating a quantum computing industry. That activity, the
passage of the NQI Act in 2018, and the publication of [60] helped consolidate
this initial spurt. Stimulated by investments at enterprise companies and
venture capital firms, this industry has taken up the challenge of making
quantum computing useful and practical for the world. We turn next to
surveying the research literature about the kinds of problems commercial and
scientific groups are exploring, and developing a broad understanding of the
resources required to tackle them. As part of this survey, we will also see
how the spectre of cryptanalysis has loomed large in the background. We will
also look at 4 recent trends in the literature (circuit knitting, variational
algorithms, error mitigation, and commercial exploration of quantum
computers), and discuss what it might look like to realize near-term value
from quantum computers.

##  3 Implications of Quantum Computing for National Prosperity

One of the most important advances over the past 5 years has been the
development of quantum computing within the private sector. In particular, an
end-user base has come into existence, as enterprises seek to leverage quantum
computing to transform their businesses [148, 149, 150, 151, 152]. In
addition, academic groups have made substantial strides in understanding how
quantum computers could be used to tackle problems of scientific importance,
building on the notion of “simulating nature” as Feynman articulated almost 40
years ago. Both of these developments have triggered much work examining the
kinds of problems – commercial or scientific – where quantum computing could
make an impact.

That said, the exact timeframe by which quantum computing will deliver
meaningful impact remains open. One of the ways the research community has
tried to address such questions is through resource estimation. As the name
implies, resource estimation is the task of estimating the required resources
needed to realize a given use case or application with a quantum computer. A
full survey of resource estimation is beyond the scope of this
work141414Though we do provide in Table LABEL:tab:resource-estimates in
Appendix A some resource estimates, and a reference summary of some public
resource estimation results is available at https://metriq.info/progress. For
our purposes it suffices to note that resource estimation efforts may be
bucketed into 3 broad categories:

  * •

Logical resource estimates, which estimate the properties of the circuits
needed by the application. Usually these estimates are in terms of the number
of qubits required, the number of primitive operations (gates) needed, and/or
the total algorithmic runtime (depth). The estimates involve assumptions as to
the allowed operations by the computer; namely, whether some operations are
considered “native”, or whether they need to be re-written in terms of other
operations. That is, these estimates could also be seen as originating at the
level of the instruction set architecture (ISA) for the quantum computer,
after a given circuit has been compiled to that ISA.

  * •

Physical resource estimates, which estimate the physical properties of a
quantum computer needed to realize high-accuracy implementations of the
required circuits. These estimates are usually derived by compiling the
logical resource estimate to an underlying error-correcting code. The output
of these estimations is usually the number of physical qubits required, and
the amount of wall-clock time which would be needed to run the circuits.
Depending on the assumptions which go into this analysis (the code used,
spatial layout of the qubits, classical data transfer constraints, physical
error rates, etc.) these estimates vary greatly, even given the same
underlying circuit [153, 154, 155, 156, 157].

  * •

Practical resource estimates, which estimate end-user-relevant considerations
such as the total energy consumption or cost required to realize a given
application [158, 159]. These estimates can be derived from either starting
with physical resource estimates and making additional assumptions (i.e., how
much energy is required to operate a single physical qubit) [159], or
fundamental physics/thermodynamics considerations [160, 161].

Moving from the first to the third type of resource estimate involves making
additional assumptions about the operation of the quantum computer. While all
3 categories are useful, logical resource estimates hew most closely to the
underlying algorithms (and algorithmic primitives) of quantum computing, and
allow us to most clearly and cleanly understand what applications have the
greatest potential and ease of being realized. These estimates also show most
easily how improvements in the underlying quantum algorithms lessen the
resources required. So in this work, of these three, we focus on the first.

In contrast, physical resource estimates – being derived from the compilation
of circuits onto error-correcting codes – are highly susceptible to change as
the underlying error-correcting code does. At first glance this would be
useful: these estimates generally fall over time (i.e., fewer physical qubits
and wall-clock time are required) and could suggest quantum computers can
realize applications sooner rather than later (extrapolating from industry-
published roadmaps on progress for building systems with increasing numbers of
qubits). However, most of the physical resource estimates in the literature
today are based on one particular error-correcting code; namely, the surface
code [131, 132]. As noted in the previous section, there is a need to study
and develop new error-correcting codes with more favorable properties. Hence,
if the underlying error-correcting code which will be used by a future quantum
computer is not the surface code, then few of these existing physical resource
estimates would be useful for identifying the crossover point between the
resources required to realize a given application and the capabilities of a
given quantum computer.

Finally, practical resource estimates are few and far between. And while
considerations of the energetic or monetary cost of quantum computation are
useful and salient for end-users [158, 160, 161, 159, 162, 163], they do not
yield any indication or guidance as to what applications are most easily
realized using quantum computers.

So, in this work, we focus on logical resource estimates. Estimates of this
type usually report the number of qubits required, the circuit depth, and/or
the number of Toffoli or $T$ gates required. A variety of resource estimates
have been done for specific applications [164, 174, 177, 153, 178, 179, 180,
181, 182, 165, 166, 167, 168, 165, 169, 170, 171, 172, 173, 175, 176]. We
forgo a full enumeration of all existing resource estimates, and instead
present in Table LABEL:tab:resource-estimates of Appendix A a list of 66
logical based resource estimates for a variety of applications. We have
grouped the particular problem studied in each reference into one of five
application areas – physics, simulating nature (chemistry, materials),
financial engineering, machine learning, and cryptography – and have indicated
the relevant sub-area the problem falls into. This list is intended to be
illustrative, not exhaustive, and we welcome any comments or amendments.

Figure 2: Logical resource estimates for various uses of quantum computers.
Plotting the resource estimates of Table LABEL:tab:resource-estimates in
Appendix A, where all entries in the table are standardized to $T$ gates,
assuming the synthesis of 1 Toffoli requires 7 $T$ gates [183]. See main text
for a discussion of this choice of synthesis algorithm. Plusses indicate
estimates which are done natively with $T$ gates; hatches indicate conversion
from Toffoli to $T$. Markers are colored according to the colors of the
squares in the legend. Top: Comparing resources required based on whether the
application is relevant for cryptography. The strong overlap between the two
colors in the region of $\sim 10^{9}$ to $\sim 10^{12}$ $T$ gates suggests a
quantum computer which could run circuits useful for non-cryptographic
applications could also potentially be cryptographically-relevant. Bottom:
Removing the markers for cryptography and coloring the grey markers in the top
figure by application area. Applications in physics (primarily, the dynamics
of spin chains) require the fewest resources, both in terms of number of
qubits and gates. NOTE: The horizontal line is at a circuit width of 25, a
rough and crude limit for circuit widths below which classical simulation is
fairly tractable. Simulation remains feasible up to widths of approximately
50, though the compute resources required scale towards those of
supercomputers to do so.

We plot these resource estimates in Figure 2. The estimates given in Table
LABEL:tab:resource-estimates involve either Toffoli or $T$ gates. This is
because most references report the number of qubits and gates, without
focusing on circuit depth. To generate Figure 2, we explicitly assume the
target gate set (allowed/native primitive operations) is the Clifford + $T$
gate set. This gate set is known to be universal for fault-tolerant quantum
computation [184], and is one of the most popular gate sets researched in the
literature for synthesizing arbitrary quantum operations [185, 186, 187, 188].
There are many ways to synthesize a Toffoli into a circuit comprised of
operations from this gate set [183, 186, 188]. In the figure, we leverage of
the synthesis algorithms of [183], in which each Toffoli is synthesized into a
circuit using 7 $T$ gates151515For the expert reader, we acknowledge the
algorithm of [189], which requires only 4 $T$ gates. However, factors of 2
would not substantially influence the figure, nor the analysis which follows.
In addition, the algorithms of [183] does not require any additional ancillae,
whereas [189] does.. We do this acknowledging there are width/gate-count
tradeoffs for Toffoli decomposition into $T$ gates [190, 186], as well
tradeoffs in terms of optimizations which can be done at the circuit level to
minimize either Toffoli or $T$ gate count.

In addition to the above points, other rationales for using the Clifford + $T$
gate set include: (a) realizing high-quality $T$ gates is generally recognized
as being a key bottleneck to achieving fault-tolerant quantum computing [191,
192, 193, 194, 195], (b) the classical computational complexity of simulating
circuits with $T$ gates generally scales exponentially in their number [196,
197, 198], and (c) it is known that the output distributions of circuits which
include $T$ gates are difficult to model classically [199]. These facts, along
with the fact the Clifford + $T$ gate set is both universal and popularly-
studied, motivates our choice of $T$ gate count as a useful measure of the
number of operations required to realize a circuit.

While the cost of $T$ gates makes them a useful metric, it also encourages
algorithmic optimizations to reduce the number of $T$ gates. This can lead to
$T$ gates becoming subdominant as in Ref. [178], and then full resource
estimations [153] are needed for more accurate assessments.

We emphasize that in these resource estimates, it is assumed the algorithm
requires a problem-instance-specific, fixed, and single circuit. As we’ll
discuss below, advances in quantum algorithms, along with new methods for
running circuits of large size, actually reduce the size of the circuits
required at the cost of needing to run more (and different) circuits. Thus, as
advances in quantum algorithms and these methods occur, it may be possible to
shift the size of the circuits show in Figure 2 down and to the left.

From Figure 2, four things stand out. The first (via both images) is that
there are a fair number of data points on the plot! It is not a priori obvious
that the research community would have identified any specific problems at all
that are amenable to be tackled using quantum computers, much less perform the
required resource estimates. And while having more (and more commercially
relevant) entries in Table LABEL:tab:resource-estimates would be a boon, it
should not be overlooked that there are quite a few ideas in the literature
about what one could do with a quantum computer – although in many of these
cases a careful assessment of whether a quantum computer will outperform a
classical one [200] still needs to be done.

The second (via the top image) is that using quantum computers for
cryptanalysis requires circuits with properties quite similar to those needed
for non-cryptographic uses. That is, the resource estimates do not divide
“cleanly” into cryptographic vs. non-cryptographic applications. Thus, the gap
in the resources required between an academic or commercially-relevant
application and a cryptographically-relevant one could be argued to be quite
small. These analyses could be construed to argue that a quantum computer
capable of running circuits useful for some problems of commercial or
scientific interest would also be capable of running circuits necessary for
cryptanalysis.

The third (via the bottom image) is that of the application buckets we used,
applications in physics require circuits with lower complexity than other
applications. This suggests that the former might be realized more easily than
the latter. However, it is also clear that a quantum computer that can run
circuits acting on $\sim 100$ to $\sim 1000$ qubits can realize a wide variety
of applications, assuming it can run on the order of millions to trillions of
$T$ gates on those qubits.

And finally, the fourth observation concerns the lack of data points in the
region of the figure where the circuit width is below $\sim 1000$, and the
number of $T$ gates required is $\sim 1K\leavevmode\nobreak\ -\sim 10K$.
Circuits in this region should, roughly, be achievable by near or medium-term
quantum computers. So to date, there is a gap between the capabilities of such
quantum computers and what is provably known about what one could do with them
when looking at such “single-circuit” resource estimates.

Based on just the resource estimates in Figure 2, a question suggests itself
as to whether, in the near-term, it might be possible to realize useful
applications of quantum computers without almost concurrently realizing a
cryptographically-relevant threat. A Nature news feature from 2019 states that
for general applications “30 years is not an unrealistic timescale” (though
others are confident that “something significant will happen soon.”) [201]. It
is the opinion of the authors that the answer is “yes”, for the reasons
discussed in the rest of this section, along with those discussed in Section
4.2.

###  3.1 Encouraging Trends in the Research Literature

That the resource estimates in Figure 2 do not divide cleanly into two sets of
(namely, cryptographic and non-cryptographic applications) increases the
difficulty of determining whether a quantum computer capable of being used for
a variety of non-cryptographic applications is not also concomitantly capable
of realizing cryptographic ones. Now, Figure 2 does show some physics-based
applications require both comparatively low circuit width and $T$-count
relative to cryptanalysis, and some financial engineering applications require
lower $T$-count (though with comparable circuit width). So from that
perspective, it may be possible to realize useful quantum computing without
necessarily realizing a cybersecurity threat.

However, there are additional reasons for optimism. We identify at least 3.
First, there have been new advances in quantum algorithms themselves, in which
multiple circuits (of lower size) are used. For example, just last year, a new
version of Shor’s factoring algorithm was proposed [202]. This algorithm
requires fewer gates than Shor’s algorithm, but requires an additional number
of circuits to be run which scales as the square root of the key size. (We
further discuss this algorithm in Section 4.2.) Second, new approximate
methods for running quantum circuits may shift the results in Figure 2. These
approximate methods are161616Note that approximate methods also exist for
fault-tolerant computers [203, 204, 205, 206]. : variational quantum
algorithms, error mitigation techniques, and circuit knitting. Third, the
commercial sector has begun aggressively investing in the exploration of
quantum computers and leveraging access to them. This increases the
possibility that heretofore-as-yet-unknown, commercially-relevant applications
or use cases may be uncovered.

The remainder of this subsection discusses the approximate methods mentioned
above, as well as surveys the literature to date on the commercial exploration
of quantum computers.

####  3.1.1 Variational Algorithms

The first is the development of _near-term heuristic_ or _variational_
(hereafter, variational) algorithms specifically designed to be run on near-
term quantum computers. At the core of most of these algorithms is a
particular integration of classical compute with quantum [207]171717Note that
running algorithms in a fault-tolerant manner also requires the integration of
purely-classical and quantum compute. The difference being that for
variational algorithms, the purely-classical operations can take place on
timescales several orders of magnitude larger than those required to realize
the error-correction operations necessary for fault-tolerant computers..
Specifically, these algorithms usually rely on a parameterized trial _ansatz_
(i.e., a quantum – not classical – guess), denoted here as
$|\psi(\boldsymbol{\theta})\rangle$, which is prepared on a quantum computer
using a quantum circuit, measured, and which is iteratively improved through
adjusting the classical parameters $\boldsymbol{\theta}$ using some kind of
optimization method running on a classical computer. These parameters are
adjusted based on some cost function $C(\boldsymbol{\theta})$, at which point
the circuit is re-run (with the new parameters) until convergence is achieved.
After the parameters are optimized, the resulting state might be used to
generate a sample (bitstring), estimate an expectation value, etc. (see Figure
3). An advantage of these algorithms is that the ansatz can be tailored to
both the hardware it runs on and the problem being studied. In addition, the
study of variational algorithms generally does not assume the quantum computer
running them does so with any degree of error correction.

Although variational algorithms are designed for near-term quantum computers,
they could also be run on fault-tolerant ones [208, 209]. Though in such an
implementation, the algorithms would most likely experience a slowdown in
runtime due to both the fact that logical operations take longer than their
“bare”/physical counterparts, as well as the fact that the circuits used in
these algorithms would need to be compiled to a fault-tolerant gate set.

Figure 3: Components of a Variational Quantum Algorithm. A variational
algorithm consists of some inputs, a methodology for engaging in an
interactive and iterative (“hybrid”) quantum-classical compute loop over a
timescale exceeding the typical lifetime of the qubits, and produces an
output. The purple box shows common inputs to the algorithm. The dashed box
shows the loop, which typically features a classical computer adjusting the
parameters of a quantum circuit. The red box shows typical outputs once the
loop has achieved convergence. NOTE: Image taken from the arXiv version of
[207] with permission.

Examples of variational algorithms include the variational quantum eigensolver
(VQE) [210, 211, 212, 213, 214, 213, 215], the quantum approximate
optimization algorithm (QAOA) [216, 217, 218, 219, 220], the variational
linear systems solver (VQLS) [221, 222, 223, 224], quantum (and quantum-
enhanced) models [225, 226, 227, 228, 229, 230, 231], low depth amplitude
estimation [232, 233, 234, 235, 236, 237], and others [238, 240, 241, 242,
243, 231, 244, 245, 246, 239]. A thorough discussion of the research to date
on variational algorithms is found in [207] and [247]. Furthermore, recent
work has explored expanding the scope of variational algorithms to include
those in which the tunable parameters of the algorithm are offloaded to a
classical computer [248], or where the classical computer uses the outputs
from running circuits to develop a surrogate model which can be optimized
without the use of parameterized quantum circuits [249]. Such methods may also
be rightly considered under the umbrella of variational algorithms.

Fault-tolerant implementations of quantum algorithms under reasonably well-
behaved noise models often come with performance bounds which can be proven
even in the absence of hardware on which to run them. Similarly, performance
bounds for variational algorithms have been devised, though these bounds tend
to depend on more contexts/assumptions and be more narrowly applicable than
those for fault-tolerant ones [250, 254, 255, 256, 257, 258, 259, 260, 261,
251, 252, 253, 254, 245]. In addition, for some variational algorithms and
some problems, work does exist analyzing regimes where superior performance
may be observed compared to classical methods [262, 268, 269, 270, 271, 272,
273, 274, 275, 263, 264, 265, 266, 267, 232, 234], or providing insights into
the contexts in which variational algorithms offer a useful benefit or
advantage [263, 276, 277, 258, 251]. Of course, there are many open questions
as to the contexts (specific problem, algorithm, data set used, etc.) in which
such variational algorithms could be efficiently simulated or otherwise
emulated through purely-classical means [249, 278, 279, 280].

The performance of variational algorithms is often assessed empirically
through experimentation on hardware. Considered one way, this is an apparent
weakness: how can one know whether a given variational algorithm is going to
do well for a given problem instance and hardware? The only answer seems to be
“try it and see”. Considered another way, this is a strength: these algorithms
are amenable to being run on currently-available hardware. Furthermore, the
research community has identified classes of shallow-depth circuits which are
hard to simulate classically [281, 282], and short-depth circuits have been
shown to be applicable to physical experiments [283]. However, issues such as
barren plateaus can make such circuits difficult to use in a variational
algorithm [251, 284, 285, 286]. It is an open question as to what sort(s) of
circuits should be used: too much structure in the circuit makes it easier to
simulate classically, and if they are fairly unstructured (i.e., close to
random), then finding optimal parameters is difficult [287, 249].

In the absence of well-characterized noise models describing how the hardware
behaves, predicting analytically and in advance the behavior of algorithms is
hard. So being able to run these algorithms and explore in practice how they
behave can help one get a handle on them. This is similar to some advances in
purely-classical computing, in which hardware helped improve algorithms, and
also led to the discovery of new ones181818For example, the linear-scaling
behavior of the simplex algorithm in practice (while the worst-case scaling
behavior was exponential) led researchers to develop the notion of _smoothed
analysis_ as a measure of computational complexity (and under which, the
simplex algorithm has polynomial complexity) [288]. Or, numerical methods for
calculating properties of spin chains led to the development of the
renormalization group method [289]..

Variational algorithms require hardware which is “good enough” to run them
with high accuracy. Of course, better (i.e., less noisy) hardware makes it
easier to attain better performance with such algorithms, and in addition,
variational algorithms do have some resilience to noise [290, 291]. One way to
estimate a low enough error rate such that the algorithm can be successfully
run is to assume that at each time step of the algorithm, each qubit has an
independent and identical probability of suffering an error. In turn, this
means the number of “error opportunities” of an algorithm requiring a given
number of qubits $q$ and having depth $d$ is $q*d$, which can be used as a
rough proxy for the size of the circuit191919The subtlety here is that the
total number of gates which could be fit in a circuit is upper bounded by this
quantity (saturated when the circuit consists of $d$ layers of single-qubit
gates on all $q$ qubits in each layer), but depending on how the gates are
structured in the algorithm, the actual number could be quite a bit less.. The
inverse $(q*d)^{-1}$ is a loose upper bound on the acceptable error rate
successfully run the algorithm. Estimates with this flavor (primarily, inverse
in the circuit size) have been used for estimating the success probability of
variational algorithms [292, 293, 294, 295] (In Section 4.2, we adopt a
similar approach for estimating the number of error opportunities of quantum
algorithms for cryptanalysis, but at the logical level). What’s more, for some
classical simulation methods, the error rate of the hardware influences the
complexity of doing so [296, 297, 298]. Both of these analyses point to the
importance of improving error rates of hardware so that variational algorithms
can be successfully run at qubit counts and circuit depth which are of
meaningful size to end-users, and also in regimes where classical simulation
methods may struggle.

In sum, the line of research in variational algorithms has generated insights
about the kinds of circuits a near-term quantum computer could run to explore
problems in physics, simulating nature, financial engineering, optimization,
and machine learning. However, the success of executing these circuits is
hindered by the presence of noise.

####  3.1.2 Error Mitigation

Thankfully, researchers have also explored techniques to reduce the effect of
noise, without having to resort to improving the error rates of the underlying
hardware and the gates they perform. This second line of work has resulted in
techniques are called _error mitigation_. At its heart, an error mitigation
technique works by replacing 1 instance of a circuit an end-user would like to
run with an _ensemble_ of $N$ circuits, where $N$ is set by the technique
itself and the error rates of the hardware. The output from running each of
those $N$ circuits are then post-processed (in a manner defined by the
technique) to yield an estimate of what an ideal quantum computer would have
output when running the original circuit; see Figure 4. This makes error
mitigation a powerful tool for getting more performance or accuracy from a
near-term quantum computer [283, 299, 300, 301, 302, 303, 304].

Figure 4: Quantum Error Mitigation Overview. Quantum error mitigation replaces
a single circuit $C$ with an ensemble $\\{C_{1},\cdots,C_{N}\\}$, and using a
classical post-processing function $F(y_{C_{1}},\cdots,\lambda)$ on the
results of those circuits to estimate the result of what a noise-free quantum
computer would output. Here, $f_{\mathbf{C}}$ is the output of an ideal
quantum computer, and $y^{\prime}_{\mathbf{C}}$ is the output of the error
mitigation technique. Some techniques enable unbiased estimates, but at the
expense of an increased variance in the estimator. Note: image taken from
[305, Figure 1] and is used in accordance with the Creative Commons
Attribution 4.0 International License [306] under which it was published.

A variety of error mitigation techniques have been developed. Some are used to
mitigate the erroneous readout of the state of a qubit (“measurement error
mitigation”) [307, 308, 309]. Others used to extrapolate to a zero-noise limit
(“zero-noise extrapolation”) [57, 310]. Still others are used to cancel the
effect of the noise (“probabilistic error cancellation”) [303, 57, 81, 58].
Additional techniques exist as well [311, 312, 313, 314, 315, 316, 317, 318,
319]; note more exist than are cited here. With such techniques, end-users of
quantum computers can achieve more accuracy in the results they obtain from a
quantum computer. However, error mitigation comes with unavoidable tradeoffs
[320, 321, 322]. Two tradeoffs are the overhead $N$ (usually, exponential in
the circuit size) and the variance of the resulting estimate (usually,
increased). A full discussion of error mitigation is beyond the scope of this
work; see [323, 324, 325, 326] for more details.

Error mitigation protocols have been used in several recent demonstrations in
conjunction with running circuits acting on approximately 100 qubits [327,
328, 329, 330]. These demonstrations showcase the usefulness of error
mitigation techniques, and highlight how they can be successfully applied to
current quantum computers.

With variational algorithms and error mitigation, the underlying hardware on
which the algorithms is run has less stringent requirements placed on it to
ensure accurate results are obtained. This is because error mitigation allows
for the noise to be mitigated, and variational algorithms can be noise
resilient. As such, these approaches should allow a quantum computer to run
circuits with a higher gate count, thereby advancing along the $x$-axis of
Figure 2.

But what of the $y$-axis? Must we wait until systems with large numbers of
sufficient-quality qubits are available before running circuits acting on
large numbers of qubits becomes feasible? The answer is “no”, due to the
development of certain circuit knitting protocols. These protocols, discussed
in the next sub-section, provide a way to decompose high-width circuits into
numerous smaller-width ones, thereby emulating what a larger-scale quantum
computer could do. In addition, circuit knitting can be used to advance along
the $x$-axis of the figure, as we will discuss below.

####  3.1.3 Circuit Knitting

Circuit knitting refers to protocols whereby a quantum computational problem
is broken down into multiple quantum circuits whose outputs are then post-
processed (“knit”) asynchronously using classical computing. Circuit knitting
protocols can be used to extend the circuit width or depth, depending on the
protocol. Here, we will discuss on 4 examples of knitting protocols:
decomposition protocols, forging protocols, embedding protocols, and time
evolution protocols.

Decomposition protocols are used to decompose a high-width (large-qubit-count)
circuit into $N$ smaller-width ones, where $N$ depends on the method and how
it is applied. In general, $N$ scales exponentially with the number of
partitions used in the decomposition (in a manner to be made more precise
below), and this scaling appears to be a general property of decomposition
methods, regardless of the specific method used [331]. In addition,
decomposition protocols can be used to emulate circuits of a larger depth
through the use of shallower ones [332].

Forging protocols leverage the fact that entangled quantum states can be
expressed as a linear combination of non-entangled ones (via the Schmidt
decomposition), which allow for the calculation of expectation values with
respect to entangled states of $2N$ qubits to be re-written as a sum of
expectation values of $N$ non-entangled states [333, 334]. These methods would
be most useful in the context of problems related to simulating the behavior
of physical systems (e.g., molecules). The overhead of forging methods depends
on the amount of entanglement in the state (as measured by the number of
Schmidt coefficients). In the worst case, this overhead is $2^{N}$, but in
general, a smaller number of coefficients may be used, substantially lessening
the overhead.

Embedding protocols (mostly used in quantum chemistry problems) isolate the
most quantum-mechanically difficult part of a simulation, and address that
part using a quantum computer [335, 336]. (Note that embeddings are used in
purely-classical quantum chemistry as well [337]; the novelty of the
aforementioned works is the use of a quantum computer as part of the method.)
The part of the simulation which is more tractable classically is solved using
purely-classical compute, and the two approaches are yoked together to yield a
self-consistent and convergent solution to the problem.

Time evolution protocols are used to simulate the time dynamics (evolution) of
quantum-mechanical systems. One protocol, introduced in [338], uses multi-
product formulas to emulate Trotterized time evolution over a fixed interval
using time evolution over smaller intervals. An advantage of this protocol is
that the number of circuits required scales linearly with the order of the
Trotter evolution. In addition, the approximation error of this method is
quadratically improved relative to standard Trotter time evolution approaches,
even over arbitrary time intervals.

$U_{\\!1}$$U_{\\!2}$$U_{\\!3}$$\bar{A}$$\bar{B}$ Figure 5: Circuit Cutting
Example. The circuit on the left has 3 gates which cross a partition of the
qubits into 2 clusters, $\bar{A}$ and $\bar{B}$, indicated by the background
colors. Using a quasi-probability decomposition of each gate, it becomes
possible to express the output of the circuit on the left as a sum of outputs
of circuits having the form on the right, where each of the indicated gates is
replaced gates which act locally on qubits in each cluster. The total number
of circuits needed (the sampling overhead depends on specific properties of
each gate being cut, along with the particular details of the cutting method
used. NOTE: Image is taken from [339], and is used with permission.

Of these 3 categories, circuit knitting for decomposition (aka, “circuit
cutting”) has been the most actively explored category in the literature. We
focus on that category in the remainder of this sub-section, and show in
Figure 5 an example of circuit cutting. The basic idea of circuit cutting was
first introduced in [340], which showed that sparse circuits of width $n+k$
could be simulated using quantum computers with $n$ qubits and classical post-
processing, where the simulation time required scaled as
$2^{\mathcal{O}(k)}*\mathrm{poly}(n)$. Since then, two additional lines of
work have emerged. One method, introduced in [341], uses a decomposition of
the relevant tensors across the partition to generate a set of state
preparations and measurements which are inserted into the circuit at the
location of the cut. The overhead of this method is exponential in the number
of cuts. Another, introduced in [339], the gate being cut is randomly replaced
by one of those from a quasi-probabilility decomposition of the gate. (A
quasi-probability decomposition is one where the coefficients of the
decomposition can be negative.) The overhead is also exponential in the number
of cuts. Interestingly, for some cutting problems based on this method, the
use of classical communication does help [339, 342], whereas for others, it
does not [343].

Some implementations of circuit cutting have shown improvements in the
accuracy of the results obtained with the method as compared to running the
original circuit on a larger-qubit-count computer [344, 345, 346, 347].
Combined with improvements in the underlying hardware, these implementations
validate the usefulness of circuit cutting for realizing high-accuracy
implementations of large-width circuits. In addition, implementations of
cutting have shown how to reduce the risk of barren plateaus in variational
algorithms [348], improve circuit compilation and runtime performance [349],
and enable new approaches for simulating highly-correlated spin chains [350].
In addition, several software packages have been developed to support the use
of circuit cutting. These include CutQC [351], ScaleQC [352], and the Qiskit
Circuit Knitting Toolbox [353].

Addressing the exponential overhead associated with circuit cutting is an
active area of research. Ideas being explored include using randomly-inserted
state preparations and measurements [354], approximate cutting [355, 356], and
ancilla-free methods [357, 358].

Overall, circuit knitting protocols can enable current and near-future quantum
computers to run circuits at a scale (and depth) larger than what they would
natively allow given the number of physical qubits available. As such, circuit
knitting is a powerful approach for emulating larger-scale (and higher-
quality) quantum computers with currently-available systems.

These recent developments of variational algorithms, error mitigation, and
circuit knitting lay a foundation for running larger-sized circuits than what
hardware could natively support, and help find approximate, “good enough”
circuits for problems. Having discussed these metods, we turn next to the
question of the kinds of “commercial problems” for which quantum computing
could make an impact, and what the private sector has done with access to
quantum computers and quantum computing expertise.

####  3.1.4 Commercial Exploration and Adoption of Quantum Computers

As noted in Section 2, the private sector has taken a keen interest in quantum
computing. Many companies have created teams to explore the potential uses of
quantum computers to business-relevant problems. In this sub-section, we
review and summarize some of the predominant themes from the body of
literature which has resulted from commercial end-user activity around quantum
computing202020Note there is a wide variety of literature on the topics below
which touches on similar or adjacent matters, but was not necessarily pursued
in – or directed toward – a commercial/practical context. We omit such
literature and references here, lest our bibliography expand to one of
biblical proportions. We invite the reader to consider [247], [359], and [360]
as useful resources for such information.. We emphasize that our purpose here
is not to make any claims regarding the attainment of quantum advantage in any
of these industries, nor to argue that the topics considered by the teams
within those industries are the definitive ones which will provide commercial
value. Instead, we seek to simply inform the reader of the predominant themes
which have emerged as the private sector has begun engaging with quantum
computing, and refer the reader to Ref. [200] for a perspective on where
quantum advantage is most likely to be obtained.

We consider the intersection of broad “quantum application areas” and specific
industry segments/verticals. The application areas can be broken down into 3
categories: simulating nature, data processing (including machine learning),
and operations research (which includes financial engineering, search, and
optimization). There are a wide variety of industries investigating quantum
computing; thus, for each combination of application area and industry
vertical, there are many possibilities as to how quantum computing could make
an impact. In addition, a quantum algorithm developed for one particular
industry or application very often can be used across others. Although some
amount of application or use-case tailoring is necessary, a given quantum
algorithm finds wide applicability.

We focus our review on 3 example industries which have been most active in
exploring the promise of quantum computing: finance, aerospace/automotive, and
high-technology manufacturing. Collectively, the value at stake within these
industries may exceed on the order of hundreds of billions of dollars over the
next decade [361, Exhibit 4].

Although the idea of quantum computing was first developed around the
application area of simulating nature, an important industry where quantum
computing is explored is finance. The abstract of a recent survey paper by JP
Morgan Chase [362] states “Quantum computers are expected to … have
transformative impact on numerous industry sectors, particularly finance.”

This sentiment was further echoed by work from Hyperion Research [363] which,
based off of survey results of companies in the quantum space, suggest the
finance sector will be one of the largest users of quantum computation by
2025. Numerous financial firms are exploring the use of quantum computing
[364, Table 1]. Areas being investigated by them include risk management [365,
373, 374, 375, 376, 377, 378, 379, 180, 366, 362, 367, 368, 369, 370, 367,
368, 371, 372, 176], customer segmentation and other machine learning problems
[380, 381, 370, 382], portfolio optimization [366, 362, 383, 384, 385, 386,
359], and fraud detection [387, 388, 389, 390, 391, 392]. For further
reference, Tables 5 and 6 of [366], Table 1 of [370], and Table 1 of [393]
show how various quantum algorithms can be used for risk management,
optimization, and machine learning in finance, and provides the relevant
financial services which are impacted by these approaches.

The aerospace/automotive industry is another exploring the adoption of quantum
computing [394, 395]. Several major companies in these industries have
launched “quantum challenges” [396, 397, 398, 399, 400] to generate research
and activity around potential use cases. In doing so, these companies are
stimulating research in areas of key concern to their business, and driving
awareness in the quantum computing industry and community of these problems:

> “We organised this competition to make a bridge to the quantum computing
> community,” … “And the response from the community was enthusiastic! We
> believe this challenge can serve as a new template for how businesses like
> Airbus can link with quantum computing researchers across the globe to
> transform this fundamental research topic into an impactful computing
> solution for a wide range of industrial applications.” [398]

Further, companies have conducted their own assessments of business-relevant
problems for which additional work is required [401, Table 1]. Specific topics
in aerospace which have been investigated include materials corrosion [402],
aircraft design [403], and airline logistics/planning [404, 405, 406, 407,
408, 409], and computational fluid dynamics [410, 411]. In the automotive
industry, topics explored include predictive process monitoring [412], supply
chain logistics optimization [413, 414], batteries [415, 416, 167, 417, 418,
419, 420], catalysis/materials [421, 422, 423], and several others [424, 425,
426, 427, 428, 429, 430].

Finally, the high-technology manufacturing and materials and chemistry
industry will benefit from quantum computing. Here, the primary application of
quantum computation is simulating the behavior of novel molecules and
materials [174, 431, 432, 433, 434, 435, 436, 178], though data processing (in
the form of generative modeling [437, 229]) and operations improvements [438]
are also promising. For this industry, it is anticipated it may benefit in the
near-term from the fact that problems in chemistry/materials generally require
a comparative small amount of classical data as part of the quantum
computation (typically, a description of the molecule or system to be
simulated). Such “big (quantum) compute, small data” problems have been
identified as the most promising ones to consider for realizing useful quantum
computing in the near-term [200, 439, 336]. What’s more, this industry has
been recognized as one of the top industries for finding end-use applicability
of quantum computers [440].

Beyond those industries described above, substantial work has taken place
exploring the use of quantum computing in many other industrial sectors,
including biosciences, lifesciences & healthcare [441, 445, 177, 446, 447,
448, 449, 450, 451, 442, 443, 444], telecommunications [452, Table 2] [453,
454, 455], logistics [361, 456, 457, 458, 459], and the energy/utilities
sector [460, 454, 464, 465, 466, 467, 468, 369, 368, 461, 462, 463].

In total, quantum computing appears to be likely to impact many computational
problems across a variety of industrial sectors. Additional exploration is
needed to further identify and refine the most promising use cases, assess the
practicality of quantum advantage for those use cases, and understand how to
integrate quantum computing into industry-relevant workflows. Much has been
written on how the private sector can prepare for and embrace quantum
computing; see [469, 470, 361, 471, 472, 473, 474] and [475, 476, 477] for
further ideas and references. We emphasize that commercial entities are vital
partners for realizing the full commercial impact of quantum computing, and
private sector investments and engagement is crucial. A recent analysis of the
levels of investment and engagement are encouraging in this regard [470].

In sum, further research in the application of quantum computers for
commercial problems continues, and the possibility exists that some as-yet-
unexplored set of problems exist which are of importance, but which also could
be tackled with the kinds of quantum computers that will become available over
the next several years. In addition, further advances in hardware error rates,
variational algorithms, and error mitigation should also move closer to the
present the time horizon at which quantum computers provide commercial value.

Although the commercial value at stake is large, and the private sector has
made substantial strides in exploring the use of quantum computers, realizing
near-term commercial value has remained challenging. The remainder of this
section provides a discussion on what a path ahead could look like for quantum
computing to make an impact for national prosperity.

###  3.2 Realizing Near-Term Value of Quantum Computers

The past decade has given rise to a tremendous increase in the exploration of
quantum algorithms for a full range of hard problems. Resource estimates for
quantum algorithms have dropped substantially, though the resources implied by
many current estimates remain out of reach for the foreseeable future. As a
result, it is becoming clear that variational (or post-variational) algorithms
offer the most promise for realizing applications of quantum computers in the
near term. Combining these algorithms with the use of error suppression and/or
mitigation techniques (and possibly some very limited forms of error
correction) will likely create scientific and economic value from new quantum
hardware. And with more robust quantum computers, these algorithms will make
further progress.

In addition, as noted in the discussion of Figure 2, there is a gap in the
research literature as to problems which could be addressed by circuits
approximately $1K$ qubits in width and requiring $\sim 1-10K$ $T$ gates.
Further research would help clarify what useful applications (if any) exist in
that region, and also potentially help rule out the possibility of a
cryptographically-relevant threat residing in that space as well. In addition,
the use of circuit knitting techniques to break apart large-sized circuits
into smaller-sized ones may extend the reach of the applications addressable
by current and near-future quantum computers.

One of the challenges in assessing time frames over which quantum computing
attains an advantage over classical is that advances in classical methods can
“narrow the gap”, so speak, between quantum and classical compute. Examples of
this over the last few years have been discussed in the previous section. The
core argument for beyond-classical experiments has been showing that a quantum
computer could perform some task using fewer resources (usually, time) for
which the estimated classical resources are astronomically prohibitive to
attain or use in a reasonable amount of time. However, new classical methods
continue to be developed [478, 479, 480, 481, 480, 198, 482], especially for
simulating state-of-the-art quantum computing experiments [75, 76, 77, 78, 83,
84, 85, 86, 485, 483, 484], and “quantum-inspired” algorithms have been
proposed [486, 487, 488, 489, 490, 491, 492, 493, 494]. For a survey of
classical simulation methods, see [495, 496, 497, 498]. As a result, a kind of
“friendly competitive escalation” has developed between the quantum and
classical computing communities (however, the methods being explored on the
classical simulation side are approximate, not exact or brute-force in
nature).

While the back-and-forth between classical versus quantum computation will
probably continue for a while, how the research community has grappled with
the question of defining and attaining quantum advantage offers a powerful
lesson as quantum begins to impact the commercial sector; namely, that it
should be expected that the first demonstrations of the application of quantum
computing to practical problems (either of scientific or commercial value)
will be accompanied by both investigations of classical methods, and very
likely follow-on work of both quantum and classical research teams. In this
sense, the attainment of quantum advantage – however that ends up being
defined– should be considered as being defined less by one particular
experiment or result, and more by a general transition taking place over an
extended time period. It is reasonable to expect that back-and-forth to
continue for a while, and focusing on the general trends and relationship
between quantum and classical computing will be more important than, e.g.,
fixating on any one particular advance or announcement.

However, it is reasonable to expect that the near-term value of quantum
computers can also be realized outside of the commercial space, and for
problems where the scientific community has developed clearer guideposts to
help indicate where near-term quantum computers could make an impact.
Harkening back to quotations from Richard Feynman in the opening of this
paper, these problems will most likely relate to the topic of simulating the
behavior of Nature.

One particular problem singled out is simulating the time evolution (dynamics)
of a particular family of spin systems; namely, a one-dimensional (1D)
Heisenberg spin system with a random magnetic field [499]. (For other families
of spin systems, simulating their dynamics has also been proposed as a
possible path to demonstrating beyond-classical quantum computation [500, 501,
502].) Spin systems can exhibit strong correlations amongst the spins, which
may make classical simulation of large spin systems (e.g., hundreds of spins)
intractable [503, 504, 505, 500]. This is because the primary method by which
those classical simulations are done involves brute-force simulation of the
dynamics, which incurs an unfavorable exponential resource scaling. (Though
approximate methods may be applied.) Further, until recently, using quantum
computers to simulate spin systems was also restricted to relatively small
systems; namely, on the order of tens of spins [506, 507, 508, 509].

However, as the previous section noted, recent work has extended the frontier
of using quantum computing to simulate two-dimensional (2D) spin models [80].
This work shows that, for a quantum circuit inspired by a particular class of
spin models, it is possible to use error mitigation to estimate properties in
regimes where brute-force classical approximation methods break down. (That
said, it is possible to use other, non-brute-force methods to attain
comparable results, both amongst the classical methods and the quantum error-
mitigated ones [86, 510, 88, 83, 85]. As noted above, it is reasonable to
expect back-and-forth between advances in classical simulation methods and
quantum error mitigation advances. Hence, the results in [80] cannot be taken
as evidence of quantum advantage, per se, but they highlight how using
circuits which are tailored to the connectivity of the hardware, along with
quantum error mitigation techniques and improvements in the hardware itself,
could enable quantum computers to be useful in the near-term. In addition,
they exemplify how in the near-term, it may be possible to realize non-trivial
scientific applications of quantum computers. As such, there are grounds for a
cautious optimism that near-term quantum computers will be useful for
scientific exploration and research. Of course, whether and how the ideas
developed for those purposes can be re-used or adjusted for commercial
purposes remains to be seen, and is an active area of engagement between
quantum computing providers and end-users [511, 512, 447].

In sum, circuit knitting, variational algorithms, and error mitigation offer
new approaches for realizing near-term value from quantum computers. It is
possible to use these approaches for both current and future quantum
computers. The commercial sector has explored how to use quantum computers for
business benefit, especially the finance, aerospace/automotive, and high-
technology manufacturing industries. In parallel, the scientific community has
identified one particular class of scientifically-relevant problems
(simulating the behavior of spin systems) for which quantum computers would
enable marked advances in our understanding of the behavior of Nature. The
ideas and techniques being developed for tackling such problems at
classically-intractable scales should have relevance for unlocking value in a
commercial context, though translating them will require collaboration between
private sector end-users and commercial providers of access to quantum
computers.

This section primarily discussed the implications of quantum computing for
national prosperity. However, ever since the development of Shor’s algorithm
in 1994, it has been known that quantum computing poses a threat to
cybersecurity (and by extension, national security). Having a solid handle on
this threat is essential for informed discussion on the benefits and risks of
quantum computers. We turn to the topic of cybersecurity and quantum computing
in the next section.

##  4 Implications of Quantum Computing for National Security

Having discussed the implications of quantum computers for commerce and
science, we turn in this section to discussing the implications for
cybersecurity. We begin with a brief overview of public-key cryptosystems,
discuss common quantum algorithms for breaking those cryptosystems, and then
present conservative estimates (based on existing literature) on the typical
error rates a quantum computer would need to break cryptosystems with varying
numbers of bits of security. The reader is also invited to look at [513,
Section 4] and [514] for additional discussion on this topic.

###  4.1 An Overview of Public-Key Cryptosystems

Public-key cryptography involves techniques for encrypting (or signing) data
using pairs of related keys, consisting of a public key and a private key. As
its name indicates, the public key is assumed to be public information. In a
public-key encryption system, anybody with the public key can encrypt a
message to produce the ciphertext, while the recipient uses their private key
to decrypt it, recovering the original message. Similarly, in a public-key
signature system, the author of a document uses their private key to digitally
sign a message, which anybody with the public key can verify, providing
authentication. Public-key cryptography is also sometimes known as asymmetric
cryptography – the public and private keys are different – in contrast with
symmetric-key, involving a single secret key, which is used to both encrypt
and decrypt.

The primary threat quantum computers pose to existing cryptosystems is
attacking asymmetric cryptography. For symmetric-key cryptosystems, the
relevant quantum attack is Grover’s search algorithm [11], which would speed
up (by a quadratic factor) a brute-force search for the key. However, this
attack can be resolved by doubling the key length for the impacted algorithms.
In fact, there are mitigating factors suggesting Grover’s algorithm will not
speed up brute force key search as dramatically as one might suspect: it was
proven in 1997 [515] that in order to obtain the full quadratic speedup, all
the steps of Grover’s algorithm must be performed in series. In the real
world, where attacks on cryptography use massively parallel processing, the
practical advantage of using Grover’s algorithm for symmetric-key cryptography
will be substantial smaller [516]. While other attacks on symmetric-key
cryptosystems exist [517, 518, 519], the full ramifications of these attacks
are currently unknown.

In contrast, the ramifications of quantum computing for public-key
cryptosystems are much better understood, and hence, we focus on such
cryptosystems in this paper. Various public-key algorithms are widely used
today, including RSA [520], the Diffie-Hellman key agreement [521], the
digital signature algorithm (DSA) [522], and elliptic curve cryptography (ECC)
algorithms [523]. The mathematics underlying these cryptosystems is different,
which has implications for how quantum computers can break them:

  * •

RSA is based on arithmetic with integers, and its security is related to the
hardness of factoring large integers into their prime factors.

  * •

Both Diffie-Hellman and DSA are examples of finite field cryptography (FFC),
which is based on modular arithmetic in a finite field.

  * •

ECC is based on the elliptic curve discrete logarithm problems, and includes
the elliptic curve Diffie-Hellman (ECDH) key exchange [524], as well as the
elliptic curve digital signature algorithm (ECDSA) [525].

The way a quantum computer would break these cryptosystems is through the use
of Shor’s algorithm [9]. This algorithm has several variants: a _discrete
logarithm_ version, which can be used to break ECC and FCC cryptosystems, and
a _factoring_ version, which can be used to break RSA. As we’ll see below,
these variants require different quantum compute resources to break the
cryptosystem they attack. If a large-scale fault-tolerant quantum computer is
built, FFC, RSA, and ECC algorithms will all be vulnerable to attacks by
quantum computers.

Both the National Institute of Standards and Technology (NIST) and the
National Security Agency (NSA) have a long history in making and updating
recommendations for the various parameters of these cryptosystems to ensure an
overall appropriate level of security in light of advances (both classical and
quantum) for attacking them. The strength of a cryptographic algorithm is
often given in terms of “bits of security.” For example, common
implementations of the Advanced Encryption Standard (AES) [526] are AES-128 or
AES-256. The “-128” refers to AES at the 128-bit security level. Roughly
speaking, this means about $2^{128}$ operations are required for a brute-force
search for the secret key212121For AES, this key is 128 bits long. In public-
key cryptosystems, e.g., RSA, an RSA-X key is not necessarily X bits in
length.. For other cryptosystems, the number of bits of security provided by a
given key length is different; we provide formulae [Equations (1), (2), (3)]
in the next Section for them.

Since the first introduction of recommended key sizes by NIST and the NSA,
those recommendations have been updated in light of advances in classical
compute power and cryptanalysis. We now briefly recall the history of public-
key algorithms and their recommended security strengths. In the early 1990’s,
NIST proposed DSA as an approved digital signature algorithm. DSA had been
developed by the NSA, and was being adopted in part due to the high costs of
licensing RSA. Shortly afterwards, an analogous elliptic curve version (ECDSA)
was also developed. Real-world usage of ECC initially remained relatively low,
even though ECC has much smaller key sizes.

In the early 2000’s, adoption of RSA and ECC increased. In 2002, the broader
community recognized that RSA key lengths [527] should be at least 1024 bits
in length [528]222222In comparison, to provide the same level of 80-bit
security, ECC keys are only 160 bits.. In 2005, NIST recommended 80 bits of
security would be sufficient through 2010 [529]. It also suggested 112 bits of
security would be sufficient through 2030, corresponding to key lengths of
2048 bits (for RSA) and 224 bits (for ECC). Beyond 2030, the recommendation
was for 128 bits of security, corresponding to key lengths of 3072 bits (for
RSA) and 256 bits (for ECC). These general trends have been maintained in the
updates NIST has given in recent years [530, 531, 532].

In 2012, NIST deprecated the parameter sets for 80 bits of security [532],
where “deprecation” means these parameter sets were disallowed for use except
for legacy processing. NIST also recommended RSA sizes be doubled to 2048 bits
and ECC keys be increased to 224 bits, corresponding to 112 bits of security.
In subsequent revisions in 2016, NIST provided the same guidance, but with all
cryptosystem parameters of 80 bits of security dropped [533, 534].

In 2005, the NSA announced recommended algorithms for national security
systems, collectively known as “NSA Suite B” [535, 536]. NSA Suite B
cryptography required the use of 256-bit ECC up to the Secret level and 384
bits for the Top Secret level. Noticeably, it did not authorize the use of RSA
nor FFC. In 2010, the NSA provided updated guidance for Suite B cryptography,
and authorized “during the transition to the use of” ECC that 2048-bit RSA and
FFC to be used to protect information up to the Secret level. No change was
made for the Top Secret level. By mid-2014, NSA had updated its guidance to
clearly state the use of RSA and FFC would not be allowed after October 1,
2015, even at the Secret level.

In 2015, NSA released a memorandum which clearly stated it was focusing on the
effects of quantum computers and the need to shift to post-quantum (also known
as quantum-resistant or quantum-safe) cryptography in the near future [537,
538, 539]. Post-quantum cryptography (PQC) refers to algorithms which are
believed to provide protection against attacks from both classical and quantum
computers. The memorandum also stated NSA found it acceptable to continue to
use RSA and Diffie-Hellman if the key lengths were a minimum of 3072 bits. In
addition, ECC was allowed to continue to be used with a 384 bit key. (For an
excellent summary of the history and issues raised by this memo, see [540].)
The NSA later published more documents and guidance which led to the demise of
NSA Suite B, which was followed by the establishment of the Commercial
National Security Algorithm (CNSA) Suite [541, 542, 543, 544].

We postpone continuing the discussion of post-quantum cryptography to Section
5, and turn now to understanding the threat posed by quantum computers to the
public-key cryptosystems which are currently used today. As noted above, all
of the public-key cryptosystems used today to protect sensitive data are based
on hard problems which are susceptible to being broken using quantum
computers. Further, understanding this risk allows for a more thoughtful
balance on the matter of weighing the risk against the benefits and
opportunities previously discussed in Section 3.

###  4.2 Quantum Computing for Breaking Public-Key Cryptography

In this section, we discuss what is known about using quantum computers to
break public-key cryptosystems. We connect resource estimates for fault-
tolerant implementations of algorithms which are known to break existing
public-key cryptosystems to both the required capabilities a quantum computer
would need to run them as well as the number of bits of security provided by a
key of a given cryptosystem and length. Doing so provides a framework for
understanding the risks quantum computers pose to a given cryptosystem using
keys of a given level of security.

Our focus on fault-tolerant implementations is motivated by the fact that, to
date, no approach based on variational quantum algorithms has been discovered
for which a provable (or even plausible) threat exists for current public-key
cryptosystems. The variational approaches considered to date consist of 2
parts. First, map the task of attacking a cryptosystem onto a combinatorial
optimization problem (using some amount of classical pre-processing to
simplify it). Second, solve the resulting optimization problem with
variational algorithms. This approach has been used in [545, 546, 547, 548,
549, 550]. Although these approaches have made claims of feasibility (at least
in principle) for attacking public-key cryptosystems, implementations on
hardware have yielded no conclusive results on the feasibility of scaling them
to relevant key sizes [546, 547, 548, 551]. This is because scaling to such
key sizes would require circuits which are so large as to be impractical to be
run without error correction. In addition, the end-to-end analysis of such
approaches lacks the systematic analysis necessary to draw definitive
conclusions about their power [552, 553]. Other approaches have been pursued
[554, 555, 556], but again, there have been no definitive proofs of
feasibility for scaling such methods to relevant key sizes. What’s more, these
algorithms are not proven to be competitive with, e.g., Shor’s algorithm, even
if they were run in a fault-tolerant manner. Finally, it is currently unknown
as to whether these algorithms can offer any speedups in principle relative to
using a brute-force search via Grover’s algorithm. Hence, we focus here on
known fault-tolerant implementations.

Our analysis of these algorithms is based on the observation that while error
correction reduces to arbitrary levels the effect of noise, doing so requires
increasing the code distance $d_{C}$. Because error correction at finite code
distance $d_{C}$ simply suppresses the rate of errors, and does not eliminate
them entirely, there is the possibility an error-corrected quantum computer
could fail to successfully run the required circuit for the algorithm. Recall
that the relationship between the logical error rate $p_{\mathrm{L}}$, code
distance $d_{C}$, code threshold $p_{\mathrm{th}}$ and physical error rate
$p_{\mathrm{ph}}$ goes as
$p_{\mathrm{L}}\sim(p_{\mathrm{ph}}/p_{\mathrm{th}})^{\mathcal{O}(d_{C})}$.
Hence, for fixed code distance $d_{C}$, there is an associated non-zero
logical error rate – even when the physical error rate is below the code’s
threshold – implying that a fault-tolerant implementation of a given algorithm
using a given error-correcting code still has a non-zero probability of
failing.

The required logical error rate necessary to ensure, with high confidence, the
algorithm will succeed can be roughly upper-bounded using the framework for
analyzing the performance of variational algorithms discussed in Section 3.
Namely, if the algorithm requires circuits acting on $q$ qubits and having a
depth of $d$, we take $(q*d)^{-1}$ as a loose upper bound on the required
value of $p_{\mathrm{L}}$ needed in order to run the algorithm successfully.
In turn, this bound places fairly stringent requirements on the underlying
physical error rate $p_{\mathrm{ph}}$: it must be sufficiently small so that
$p_{\mathrm{L}}<(q*d)^{-1}$. Phrased another way, the physical error rate
needs to be small enough such that after error correction on the noisy
physical qubits is used, the resulting logical error rate is itself
sufficiently small as to enable the error-corrected quantum computer to run
the algorithm with a high probability of success.

Our analysis is primarily based on [181] which currently provides the most
efficient quantum algorithm for factoring RSA integers and computing discrete
logarithms over a finite field such as the Diffie-Hellman (DH) key agreement
and Diffie-Hellman digital signature algorithm (DHDSA). It builds on two
papers that provide the foundation for solving the discrete log problem with a
quantum computer [557, 558]. (Recall the security of ECC is based on the
hardness of solving the discrete log problem.) The former of these two papers
[557] effectively uses the techniques in [181] to further improve the latter
[558]. These resource estimates are summarized in Table 2. We note for
completeness the origin of each of these entries:

  * •

Row 1 (RSA - Gidney): See Table 1 of [181], with $q$ as “Abstract Qubits”, and
$d$ as “Measurement Depth”.

  * •

Row 2 (ECC - Häner): Formulae given in the final paragraph above Section 10 of
[558], with $q$ as the number of qubits, and $d$ as the $T$-depth.

  * •

Row 3 (ECC - Banegas): See [558], with $q$ given as the number of qubits
indicated just below Table 4, and $d$ is the number of Toffoli gates,
indicated just below Table 6. (From that self-same page, “…as such the depth
is of the same order as the number of TOF [Toffoli] gates.” )

We emphasize for the reader that the above references are by no means the last
and final say regarding resource estimates for cryptanalysis. In particular,
we note that just this year, an improved version of Shor’s factoring algorithm
was released [202], and already researchers have found ways to improve it
[559]. In addition, the algorithm of [202] has been extended to the problem of
computing discrete logarithms [560]. We do not include [202] in Table 2 and
Figure 2 because the resource analysis of this algorithm in terms of Toffoli
or $T$ gates has not yet been done. And from [202]: “ It therefore remains to
be seen whether the algorithm can lead to improved physical implementations in
practice.”. Similarly, [561] provides new architectural approaches to
implementing Shor’s algorithm for ECC, and provides new resource estimates for
ECC-256. That said, Table 2 does, as far as we authors are aware, provide the
state-of-the-art in terms of resource estimates (with analytic formulae) for
circuit width and depth for cryptanalysis.

Cryptographic Scheme | Paper |  Circuit Width ($q$) |  Required Depth ($d$)
---|---|---|---
RSA | Gidney [181] | $3n+.002n\log_{2}n$ | $n^{2}(\log_{2}n+500)$
ECC | Häner [557] | $8n+10.2\lfloor\log_{2}n\rfloor-1$ | $120n^{3}-1.67*2^{22}$
ECC | Banegas [558] | $7n+\lfloor\log_{2}n\rfloor+9$ | $48n^{3}+8n^{\log_{2}(3)+1}+n^{2}(352\log_{2}n+512)$
Table 2: State-of-the-art resource estimates for quantum computers to break
public-key cryptosystems. This table shows the resource estimates for fault-
tolerant quantum algorithms used to attack the RSA and ECC cryptosystems. $q$
refers to the circuit width, not the number of physical qubits required to run
such circuits. The depth $d$ gives the number of algorithmic time-steps
required, and does not refer to the amount of actual (“wall clock”) time
required.

We emphasize that in these resource estimates, $q$ refers to the number of
_logical_ qubits required by the circuit, and _does not_ refer to the number
of _actual_ or physical qubits a quantum computer would need to realize
running that circuit. Logical qubits must be _distilled_ using quantum error
correction (recall the end of Section 2). This distillation process introduces
additional overhead with respect to both the number of physical qubits
required, as well as the runtime of the algorithm, which is not accounted for
in the notion of circuit depth $d$ used here. And here, $d$ provides a measure
of the total program complexity (in terms of primitive timesteps required),
not the total (physical) runtime of the algorithm.

Also as an example of how the required resources will generally be greater
than the “bare” numbers, it should be noted that [181] provides a detailed
analysis of factoring RSA-2048 with a characteristic underlying gate error
rate of $10^{-3}$ using a surface code and an efficient implementation of
Shor’s algorithm. With this error rate, the final number of logical qubits was
estimated to be $q=14238$: more than a factor of 2 larger than plugging
$n=2048$ into the equation for $q$ in Table 1 (namely, $q=6190$). The reason
is that additional auxiliary qubits are needed to implement gate operations
and for data movement.

The input to these resource estimates is the key length $n$. Although it may
be intuitive to the reader that increasing $n$ increases the protection of the
information encrypted using a given cryptosystem, we make explicit the
relationship between $n$ and the number of bits of security the key provides.
This relationship is a necessary ingredient in what follows. Thankfully,
relating $n$ to number of bits of security is known!

For an $n$-bit RSA key, the approximate number of bits of security,
$x_{\mathrm{RSA}}$, is [562, Formula 1]

$x_{\mathrm{RSA}}(n)=\frac{1}{\ln 2}\left(\sqrt[3]{64/9}*\sqrt[3]{(n\ln
2)}*\sqrt[3]{[\ln(n\ln 2)]^{2}}-4.69\right).$ (1)

For FFCDH, if the length of the public and private keys are $n$ and $m$
respectively, then the corresponding number of bits of security is

$x_{\mathrm{FFCDH}}(n,m)=\min(x_{\mathrm{RSA}}(n),m/2).$ (2)

Hence, as long as $m>2x_{\mathrm{RSA}(n)}$, the security is limited by that of
the public key, and is equivalent to the security of an RSA key of length $n$.
We assume this in the analysis below.

For ECC, as mentioned previously, if the modulus of the prime number used to
generate finite field for the curve is $n$ bits, then the number of bits of
security is half that:

$x_{\mathrm{ECC}}(n)=n/2.$ (3)

With Table 2 and Equations (1), (2), and (3) in hand, we are now in a position
to reason about how increasing the number of bits of security changes both the
required quantum compute resources, and the upper bound on the required
logical error rate.

In the left side of Figure 6, we sweep across varying key lengths for RSA
(fixing the size of the key length for ECC to yield the same number of bits of
security) and trace out the circuit width $q$ and depth $d$ required to break
them with current implementations of Shor’s algorithm. The figure shows that,
as the number of bits of security increases, the resources required for
breaking RSA (both $q$ and $d$) increase more quickly than for ECC. This
implies that for a given amount of security, data encrypted using RSA will be
generally harder to decrypt using quantum computers than data encrypted using
ECC. Recent optimizations for factoring using Shor’s algorithm [202, 559] will
likely decrease the scaling of $d$ for RSA, but not decrease $q$.

Figure 6: Quantum Algorithms for Cryptanalysis. Left: Circuit-model-based
resource estimates for RSA and ECC. For a fixed number of bits of security, we
plot $q$ and $d$ from Table 2 based on current implementations of Shor’s
algorithm. Shading gets darker with increasing number of bits of security
(specified as “RSA key size (bits of security)” in the legend). Dashed lines
indicate constant values of the product $q*d$. Right: Error Opportunities
($q*d$) for RSA and ECC as a function of bits of security, $x$. As the number
of bits of security increases, the number of error opportunities for quantum
algorithms attacking the RSA cryptosystem grows more rapidly than those for
attacking ECC.

In the right side of Figure 6, we plot the number of error opportunities
$(q*d)$ as a function of the number of bits of security for current
implementations of Shor’s algorithm. Increasing the cryptographic key length
$n$ increases both the number of bits of security, as well as the quantum
compute resources required to break it. (Recall Table 2: both $q$ and $d$
increase with $n$.) Hence, the number of error opportunities increases with
the number of bits of security for the key. This is clearly seen in the
figure. A few specific RSA key sizes are labeled for the reader.

While the number of error opportunities grows with the number of bits of
security, the rate of growth depends on the cryptosystem. The right side of
Figure 6 shows that for a fixed number of bits of security, the number of
error opportunities is much lower for ECC than RSA. (This follows from the
previously-observed fact that $q$ and $d$ for ECC are less than RSA.) This
implies that, given current resource estimates, ECC is more vulnerable to a
successful quantum-based attack: the tolerable error rates for ECC are much
higher for a successful quantum-based attack. For example, RSA-1024 is five
times more difficult to crack as 160-bit or 163-bit ECC (as measured by the
number of error opportunities). We note however, that this assessment may
change in the future with algorithmic improvement, such as recent developments
for factoring that have not been fully assessed yet [202, 559].

Also indicated in the right side of Figure 6 is the evolution of the
recommended standards for public-key cryptography. By increasing the number of
bits of security from 80 (pre-2015 recommendation) to 128 (today), the number
of error opportunities for both RSA and ECC go up by almost an order of
magnitude. In turn, this means that by migrating from the old recommendation
to the new one, the information stored with those keys is more secure against
attacks by quantum computers. It should be noted that the largest RSA key
factored by purely-classical means is RSA-250 [563], which is labeled in the
figure.

Recall one of the observations made for Figure 2; namely, it is expected near-
future quantum computers should be able to run circuits with a width of $\sim
1000$ and between $\sim 1K$ and $\sim 10K$ $T$ gates. Assuming that a
comparable number of non-$T$ gates can be run as well, then the largest-
possible sized circuit which could be run reliably has a size on the order of
$10^{4}$. (It’s not $10^{7}=1000*10^{4}$ because the number of $T$ gates is
the _total_ number, not the number per qubit.) Looking at the right side of
Figure 6, being able to run circuits of such a size does not pose a threat to
cryptography.

Year | $N$ | $n=\lceil\log_{2}(N)\rceil$ | $x_{\mathrm{RSA}}(n)$ | Factors | Notes
---|---|---|---|---|---
2001 [28] | 15 | 4 | N/A | 3, 5 | NMR System
2011 [564] | 21 | 5 | N/A | 3, 7 | Photonic System
2019 [565] | 35 | 6 | N/A | 7, 5 | Superconducting System
2019 [566] | 961307 | 20 | 5.9 | 619, 1553 | Simulator
2023 [567, Table III] | 247 | 8 | 0.26 | 13,19 | Simulator
2023 [568] | 549755813701 | 39 | 11.7 | 712321, 771781 | Simulator; iterative algorithm
Table 3: State-of-the-art, non-trivial implementations of Shor’s algorithm for
factoring integers (by year). Here, we focus on works which use non-trivial
implementations of the algorithm, in which a minimal (or no) amount of prior
information about the solution is used to implement or compile the algorithm
prior to running it on hardware or a simulator. For some integers, the number
of bits of security they would provide if they were used as keys in an RSA
cryptosystem is negative, indicated as N/A.

Looking towards future quantum computers, estimating how much time remains
before RSA-2048 keys can be broken is quite difficult. To date, neither
experiments nor simulations thereof have tackled the problem of factoring
integers at scales close to the aforementioned 829-bit RSA-250 number, much
less RSA-2048 keys. Table 3 tabulates state-of-the-art implementations of
Shor’s algorithm (either on real quantum computing hardware, or simulators).
We note that some implementations leverage compilation techniques and
favorable parameter choices for the algorithm (as described in [569]) which
make the implementation trivial in nature. The results in Table 3 are non-
trivial implementations, and thus provide an accurate representation of where
the field currently stands in terms of using Shor’s algorithm to factor
integers. It is clear that both simulation and hardware experiments do not
come close to realizing credible attacks on cryptographically-relevant RSA key
sizes. In light of the prior paragraph, this is understandable: the hardware
simply cannot run large enough circuits to tackle cryptography.

Many analyses have been done to assess the risk quantum computers pose to
cybersecurity. One suggests RSA-2048 is unlikely to be factored ($<5\%$
confidence) before 2039, based on a statistical model extrapolating current
quantum computing hardware progress [570]. Another, via a survey of quantum
computing experts for the “2022 Quantum Threat Timeline Report”, gives a 50%
probability for the same problem by 2037 [571]. The 2023 version of the self-
same report, which comparing prior estimates for the likelihood RSA-2048 could
be broken within the next 5 years, shows expert assessments continue to assign
this occurrence as being “Extremely Unlikely ($<1\%$ chance)” [572, Figure
10]. An analysis of the energetic requirements needed to operate a
cryptographically-relevant quantum computer (CRQC) was performed in [159],
concluding “…Even if a CRQC is eventually built, merely operating it would
probably remain the domain of nation-states and large organizations for a
significant period of time”. Reference [181] gives a physical resource
estimate for using Shor’s algorithm on RSA-2048 integers of 20 million
physical qubits and 8 hours of runtime232323Note that many assumptions go into
deriving those numbers: changing them would generally change the required
number of physical qubits and/or runtime..

All of these analyses suggest that near-future quantum computers will not pose
a risk to cybersecurity. However, given the significance of the potential
threat, transitioning to new cryptographic primitives is necessary. This
significance is highlighted in part by the USG’s National Security Memorandum
10 (NSM-10) [573] of May 4, 2022 entitled National Security Memorandum on
Promoting United States Leadership in Quantum Computing While Mitigating Risks
to Vulnerable Cryptographic Systems. This memorandum directs USG to mitigate
“as much of the quantum risk as is feasible” by 2035. In addition, the NSA’s
Commercial National Security Algorithm (CNSA) Suite 2.0 [574] directs that by
2030, certain components of national security systems will need to use the
algorithms documented in CNSA 2.0.

In the next section, we briefly discuss how cryptography has been evolving in
light of the threat posed by quantum computers, and how organizations can
prepare now to transition their digital systems to such cryptosystems.

##  5 Evolving Cryptography for the Quantum Era

Given the threat of quantum computing to cryptography, identifying,
standardizing, and implementing new cryptographic systems which are believed
to be resistant to attacks from both classical and quantum computers is one of
the most pressing tasks in the cybersecurity community today. We briefly
review the three primary lines of work in doing so: quantum key distribution
(QKD), quantum random number generation (QRNG), and “post-quantum”
cryptography242424These techniques are often captured under the common
umbrella of “quantum-safe cryptography”, since they are designed to also be
safe against quantum-enabled attacks. In some of the literature the term
quantum-safe cryptography is equated with post-quantum cryptography only. In
this article we take the broader interpretation.. In doing so, we emphasize
the importance of considering the evolution of cryptography in light of
quantum computers as being about establishing “defense-in-depth” through a
judicious choice of relevant cryptographic methods. These methods must
consider the different ways that cryptography is used to protect computing,
for example, to protect the confidentiality of data when it is stored or
transmitted, to authenticate entities such as people and software updates, and
to provide repudiation in the case of digital signatures.

The reader may be wondering what urgency, if any, exists for evolving the use
of cryptography. In light of the analysis in the previous discussions, it
should be clear that near-term quantum computers should not be able to crack
currently-used public-key infrastructure, especially if the keys used conform
to the updated recommendations from NIST (namely, to use at least 112 bits of
security). So why worry about addressing what seems, at first glance, to be a
non-existent threat to currently-used cryptosystems?