Untitled Flashcards Set

While today’s computing machines leverage exquisite control over

nature to create designs of immense complexity, the representation and

logical processing of information in these machines can be explained

using the laws of classical physics.2 These classical descriptions of electro

magnetism and Newtonian physics provide an intuitive and deterministic

explanation of the physical universe, but they fail to predict all observable

phenomena. This realization, made around the turn of the 20th century,

led to the most important transformation in physics: the discovery of

the principles of quantum mechanics. Quantum mechanics (or quantum

physics) is a theory of the physical world that is not deterministic, but

probabilistic, with inherent uncertainty. While the dynamics it describes

at a small scale are exotic and counterintuitive, it accurately predicts a

wide range of observable phenomena that classical physics could not, and

replicates correct classical results for larger systems. The development

of this field has transformed the way scientists understand nature. Very

small systems whose behavior cannot be adequately approximated by the

equations of classical physics are often referred to as “quantum systems.”

While classical physics is often a good approximation for observable

phenomena, all matter is fundamentally quantum mechanical—including

the materials from which today’s computers are built. However, even as

the design of their hardware components is increasingly informed by the

quantum properties of materials, and as the ever-shrinking size of these

components means that quantum phenomena introduce more constraints

2

While the laws of quantum mechanics must be invoked to design or explain the operation

of semiconductor materials whose bandgaps enable the implementation of today’s widely

deployed conventional computer logic gates, the nature of the logical information processing

itself is based upon the flow of a classical model of a charged particle.

Quantum Computing : Progress and Prospects, edited by Mark Horowitz, and Emily Grumbling, National Academies Press, 2019.

ProQuest Ebook Central, http://ebookcentral.proquest.com/lib/westminster/detail.action?docID=5742474.

Created from westminster on 2025-02-10 15:48:05.

Copyright © 2019. National Academies Press. All rights reserved.Quantum Computing: Progress and Prospects

Copyright National Academy of Sciences. All rights reserved.

PROGRESS IN COMPUTING

15

on their design, the principles and operations that these computers imple

ment have remained classical.

Despite the extraordinary power of today’s computers, there are

applications that are difficult for them to compute but seem to be easily

“computed” by the quantum world: estimating the properties and behav

ior of quantum systems. While today’s classical computers can simulate

simple quantum systems, and often find useful approximate solutions for

more complicated ones, for many such problems the amount of memory

needed for the simulation grows exponentially with the size of the system

simulated.

In 1982, physicist Richard Feynman suggested that quantum mechan

ical phenomena could themselves be used to simulate a quantum system

more efficiently than a naïve simulation on a classical computer [2,3]. In

1993, Bernstein and Vazirani showed [4] that quantum computers could

violate the extended Church-Turing thesis—a foundational principle of

computer science that said that the performance of all computers was only

polynomially faster than a probabilistic Turing machine [5,6]. Their quan

tum algorithm offered an exponential speedup over any classical algo

rithm for a certain computational task called recursive Fourier sampling.

Another example of a quantum algorithm demonstrating exponential

speedup for a different computational problem was provided in 1994 by

Dan Simon [7]. Quantum computation is the only model of computation

to date to violate the extended Church-Turing thesis, and therefore only

quantum computers are capable of exponential speedups over classical

computers.

In 1994, Peter Shor showed that several important computational

problems could, in principle, be solved significantly more efficiently using

a quantum computer—if such a machine could be built. Specifically, he

derived algorithms for factoring large integers and solving discrete loga

rithms rapidly—problems that could take even the largest computer today

thousands or millions of years—or even the lifetime of the universe—to

compute. This was a striking discovery because it also suggested that any

one with a real-world quantum computer could break the cryptographic

codes that make use of these problems, compromising the security of

encrypted communications and encrypted stored data, and potentially

uncovering protected secrets or private information. These results cata

lyzed interest among researchers in developing other quantum algorithms

with exponentially better performance than classical algorithms, and try

ing to create the basic quantum building blocks from which a quantum

computer could be built.

During the past few decades, this research has progressed to the point

where very simple quantum computers have been built, and a positive

outlook is emerging based upon the assumption that the complexity

Quantum Computing : Progress and Prospects, edited by Mark Horowitz, and Emily Grumbling, National Academies Press, 2019.

ProQuest Ebook Central, http://ebookcentral.proquest.com/lib/westminster/detail.action?docID=5742474.

Created from westminster on 2025-02-10 15:48:05.

Copyright © 2019. National Academies Press. All rights reserved.Quantum Computing: Progress and Prospects

Copyright National Academy of Sciences. All rights reserved.

16

QUANTUM COMPUTING

of these machines will grow exponentially with time, analogous to the

growth that has been achieved in performance of classical computers.

Given the importance of this scaling assumption to the future of quantum

computing, understanding the factors that drive scaling is critical.