Introduction to Quantum Computing

SC24 Tutorial

Scott Pakin
Eleanor G. Rieffel
18 November 2024

Operated by Triad National Security, LLC for the U.S. Department of Energy's NNSA

LA-UR-19-31426
 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 2

 All of Quantum Computing on One Slide

• The good on that number, and writes a single 32-bit

number?
– 2n-way parallelism from n qubits
– Limited applicability—note the use of
– Possibility of exponential speedup for
“some problems” above
some problems
– Programming is extremely difficult:
– Some classically intractable problems
requires expertise in linear algebra,
can be made tractable
computer science, and quantum
– Some tractable problems can be physics as well as knowledge of prior
solved asymptotically faster algorithms and innate creativity
– Some problems can be solved exactly • The ugly
in the time it would take classically to
– Contemporary quantum computers
solve them only probabilistically
provide too few qubits even to
• The bad represent most interesting problems
– Quantum computation is extremely I/O – Current qubit quality is extremely low:
bottlenecked: only n bits of input and n unlikely to produce correct answers for
bits of output relative to 2n-way more than handful of qubits running for
parallelism more than a handful of time steps
• Can you think of a problem that reads a
single 32-bit number, performs sequences
of 4,294,967,296 concurrent operations

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3

 Introduction to Quantum Computing
Tutorial SC’24

Eleanor Rieffel, NASA Ames Research Center

Scott Pakin, Los Alamos National Laboratory

18-Nov-2024
Quantum-Computing Fundamentals

18-Nov-2024
 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3

 NASA’s Stake in Quantum Computing

Quantum Networks
NASA constantly confronting
massively challenging
computational problems Quantum-enhanced
• Computational capacity limits applications
mission scope and aims
Quantum, hybrid quantum-
classical, and physics-
inspired classical algorithms

QC programming
NASA’s Aitken
and Pleiades
Supercomputers Fundamental quantum
physics mechanisms
NASA QuAIL mandate:
Determine the potential for Simulation tools Analytical methods

quantum computation to enable

more ambitious and efficient
NASA missions in the future
NASA Ames QuAIL team
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 4
 Birth of Quantum Computing

• Feynman and Manin recognized in the early

1980s that certain quantum phenomena
could not be simulated efficiently by a
computer
– Phenomena related to quantum entanglement;
Bell’s inequality
• Perhaps these quantum phenomena could
be used to speed up more general
computation?

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 5

 Computers as Classical Mechanical Machines

• Babbage’s analytical engine was a

classical mechanical machine
• Turing machines
– The abstraction that underlies complexity
theory and universal computing machines
– Firmly rooted in classical mechanics
– Described in classical mechanical terms
• Abstraction allowed us ignore how
classical computers are implemented Babbage
physically engine
– When we program we don’t think about the (Computer
History
fundamental physics Museum)

• How do different models of physics

affect how quickly we can compute?

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 6

 Computers as Quantum Mechanical Machines?

Fundamental questions

• How do different models of physics affect how quickly we can

compute?
– Suggests new computation-based physics principles

• How would basing computation on a quantum mechanical model rather

than a classical mechanical model change our notions of computing?
– Quantum physics is the physics of our universe

• How quickly does nature allow us to compute?

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 7

 What a Quantum Computer is Not

• Just because a computer uses quantum effects, does not mean it is a

quantum computer
– All the computers in this building make use of quantum effects
– The fundamental unit of computation, the bit, and the algorithms we design for
computers did not change when quantum effects were used
• A quantum computer has a fundamentally different way of encoding and
processing information
– Quantum computers are quantum information processing devices
– They process qubits instead of bits
– They use quantum operations instead of logic gates
• Also, just because a piece of hardware has a certain number of qubits, it
isn’t necessarily a quantum computer
– A set of light switches, even a very large set, is not a classical computer

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 8

 Certainty and Randomness in Quantum Computation

• Any computation a classical computer can do, a quantum computer can

do with roughly the same efficiency
– With the same probability of the outcome
– If the classical computation is non-probabilistic, so is the quantum one
• Like classical algorithms, some quantum algorithms are inherently
probabilistic and others are not
– First quantum algorithms were not probabilistic
• E.g. Deutsch-Jozsa algorithm solves problem with certainty that classical algorithms, of
equivalent efficiency, could solve only with high probability
– Shor’s algorithms are probabilistic
– Grover’s is not intrinsically probabilistic
• initial search algorithm was probabilistic, but
• slight variants, which preserve the speed up, are non-probabilistic

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 9

 Current Status of Quantum Algorithms

Unknown quantum advantage

Quantum for everything else
computing can do Status of classical algorithms
everything a • Provable bounds hard to obtain
classical – Analysis is just too difficult A handful of
• Best classical algorithm not known for most proven
computer can do problems
and • Empirical evaluation required limitations
• Ongoing development of classical heuristic
Provable approaches on quantum
quantum – Analyzed empirically: ran and see what happens
advantage known
– E.g. SAT, planning, machine learning, etc.
competitions
computing
for a few dozen
quantum • NISQ era supports unprecedented means
for empirical analysis of quantum
algorithms algorithms
– Quantum heuristics come into their own

Conjecture: Quantum Heuristics will significantly broaden

applications of quantum computing
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 10
 Quantum Hardware

General Purpose: Superconducting quantum processors

Universal quantum processors Trapped ion quantum processors

Photonic quantum processors

Other approaches
Google Rigetti - Electron spins in silicon
- Neutral atom, cold atom
- Topological, anyon based quantum computing
Special Purpose: Noisy
Intermediate-
Number of qubits alone is not a good measure
E.g. Quantum - Analogy: billions of switches do not a classical
annealers Scale computer make
Quantum
(NISQ) Other key factors
devices - precision, speed, and generality of the control
- particularly operations involving multiple qubits
- how long quantum coherence can be maintained
D-Wave - stability over time
- speed with which processors can be calibrated

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 11

 Quantum Computing has Entered the NISQ Era

Quantum supremacy has been achieved! … but not useful quantum supremacy.
• Perform computations not possible • Currently too small to be useful for solving
on even the largest supercomputers practical problems
in a reasonable amount of time • Perhaps an early application to certified random
number generation, but other applications require
Cover article, larger, more capable devices
Nature, 24 Oct
2019 Uses of these still limited, quantum devices?

Google, NASA, (1) Unprecedented opportunity to explore and

ORNL collaboration evaluate algorithms, both quantum and hybrid
quantum-classical heuristic algorithms
(2) Investigate quantum mechanisms that may be
2023 Update harnessed for computational purposes

Insights gained feed into next generation

• quantum algorithms
• quantum hardware

A. Morvan, B. Villalonga, X. Mi, S. Mandrà, et al., One early target: Optimization

(2023) Phase transition in Random Circuit
Sampling, arXiv:2304.11119 Other early targets: ML, Chem & Materials Simulation

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 12

 Quantum Optimization Algs.: QA, AQO, QAOA

• Common elements:
– Cost function: C(z)
– Phase separation operator tied to the cost function,
• Usually based on , but often including “penalty terms” to enforce constraints
– Driver/Mixing operator
• Most frequently, though we will see reasons to use other mixers

AQO (Adiabatic Q Opt) QA (Q. Annealing) QAOA

• Evolution under • Evolution under • Alternate application
𝑯(𝒕) = 𝒂(𝒕)𝐻𝐶 + 𝒃(𝒕)𝐻𝑀 𝑯(𝒕) = 𝒂(𝒕)𝐻𝐶 + 𝒃(𝒕)𝐻𝑀 of and
• For p alterations, the
• Slowly enough to • Many quick runs, parameters are
stay in the ground thermal effect times/angles
subspace contribute
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 13
 Three Group Exercises

• Before going on to a more technical part introducing the fundamentals

of quantum computation

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 14

 Exercise 1

• Which of the following best describes the current status of quantum

algorithms?
a) Quantum algorithms can beat classical algorithms on every problem, we just need
to build quantum computers on which to run them!
b) While there are only a few dozen quantum algorithms known, quantum algorithms
continue to be discovered, with many more algorithms likely to be identified as
larger processors are built, enabling the evaluation of quantum heuristics.
c) Quantum algorithms have been studied since the early 1990s, and pretty much
everything is known by now.
d) Quantum mechanics is the physics of the universe. Every algorithm is a quantum
algorithm!

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 15

 Exercise 2

• Which statement best describes “quantum supremacy”?

a) “Quantum supremacy” was already achieved in the 1990s by Shor’s algorithm,
since it is a polynomial time algorithm whereas the best classical algorithms are
superpolynomial time algorithms.
b) It is well-known that quantum computers can beat classical computers, even
supercomputers, at everything. “Quantum supremacy” is just a quick way of saying
that.
c) “Quantum supremacy” will be achieved only when quantum computers can run
Shor’s algorithm on cryptographically relevant numbers.
d) A quantum processor demonstrating “Quantum supremacy” means it has been
able to perform, in a practical amount of time, a computation that could not be
performed on even the world’s largest supercomputers in a practical amount of
time. It would be achieved even if it was demonstrated for only one computation
and that computation was useless.

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 16

 Exercise 3

• Which statement best describes the relation between uncertainty and

quantum algorithms?
a) Quantum mechanics is by nature uncertain—think the quantum uncertainty
principle—so unlike classical algorithms, quantum algorithms are inherently
probabilistic
b) Classical algorithms can be translated to a form that can be run on quantum
computers, so translations of classical algorithms that answer with certainty, still
answer with certainty, but if an algorithm makes use of truly quantum effects, it
cannot provide an answer with certainty
c) Like classical algorithms, quantum algorithms fall in two categories, algorithms that
provide an answer with certainty and probabilistic algorithms
d) All algorithms, both quantum and classical, cannot provide a result with certainty—
life is inherently uncertain.

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 17

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 18

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 19

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 20

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 21

 Mathematically Representing Photon Polarization

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 22

 Measurement of Polarization

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 23

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 24

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 25

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 26

 Qubits (Quantum Bits)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 27

 Measurement of Single Qubits

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 28

 Multiple Qubits

• Qubits combine like quantum particles not classical objects

• Quantum states combine via tensor products not direct products
• The quantum state space, the space of possible states of n
quantum particles, is exponentially larger than that of n classical
objects
• 2n instead of 2n
• Entangled states make up the bulk of this space
• No classical analog: The state of entangled multiple particle systems
cannot be described in terms of the states of the individual particles

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 29

 High-level View of How State Spaces Combine

Scott will go over the mathematics and notation here in more detail in the next
segment of the tutorial.
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 30
 Exponential State Space

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 31

 Quantum vs. classical state spaces

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 32

 Measurement of Single Qubits

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 33

 Entangled States

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 34

 Entanglement, correlations, and communication

Non-classical behavior
•Two people each see completely random results from
their coin tosses
•Completely correlated results!
•But no way to know this unless they communicate
•There is no way to use this to communicate
•Different relativistic frames disagree about who
flipped the coin first

Critically important also: the behavior when they

measure in different basis.

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 35

 Quantum Computer (Circuit Model)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 36

 Exercise

Which of the following states

1
a) 2
(|0⟩ + |1⟩)

b) |00101⟩
1
c) ++ = 2 00 + 01 + 10 + |11⟩
1
d) ( 01 + |10⟩)
2
1
e) 𝑤4 = 2 ( 0001 + 0010 + 0100 + |1000⟩)

i) are superpositions in the standard basis?

ii) are superpositions in the Hadamard basis { + , |−⟩}, where
1 1
+ = 2
( 0 + |1⟩) and − = 2
( 0 − |1⟩)
iii) are entangled?
• Bonus exercise: Prove the no cloning theorem
(Hint: follows from linearity of quantum operations)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 37

 Notation

Los Alamos National Laboratory and NASA Ames 18-Nov-2024

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 2

 Tensor Products

• The tensor product, ⊗, multiplies two vectors to produce a longer

vector or two matrices to produce a larger matrix
– Unlike dot products or matrix multiplication, the two arguments do not have to have
compatible dimensions
• Operational semantics (loosely specified)
– Multiply each scalar on the left-hand-side vector/matrix by the entire right-hand-side
vector/matrix
• Vector example
𝑎𝑐 1⋅3 3
𝑎 𝑐 𝑎𝑑 1 3 1⋅4 4
⊗ = , e.g., ⊗ = =
𝑏 𝑑 𝑏𝑐 2 4 2⋅3 6
𝑏𝑑 2⋅4 8
• Matrix example
𝑎𝑒 𝑎𝑓 𝑏𝑒 𝑏𝑓 3 1 6 2
𝑎 𝑏 𝑒 𝑓 𝑎𝑔 𝑎ℎ 𝑏𝑔 𝑏ℎ 1 2 3 1 1 4 2 8
⊗ = , e.g., ⊗ =
𝑐 𝑑 𝑔 ℎ 𝑐𝑒 𝑐𝑓 𝑑𝑒 𝑑𝑓 2 1 1 4 6 2 3 1
𝑐𝑔 𝑐ℎ 𝑑𝑔 𝑑ℎ 2 8 1 4

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3

 Basics of Dirac (a.k.a. Bra-Ket) Notation

• Two components: bras and kets

⟨𝜓| |𝜓⟩
“Bra” “Ket”

Row vector (adjoint) Column vector

• The label (e.g., “𝜓”) is merely a name and has no

Paul Dirac
inherent meaning 1902–1984
• However, some conventions exist:
1 0 1 1 1 1
0 ≡ 1 ≡ + ≡ − ≡
0 1 2 1 2 −1

• Bra times ket: ⟨𝝍|𝝓⟩ • Ket times bra: |𝝓⟩⟨𝝍| Hence, e.g.,
– Inner product – Outer product 1
⟨−| ≡ 1 −1
– Returns a scalar – Returns a matrix 2

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 4

 More on Dirac Notation

• Ket-kets and bra-bras

– 𝑎 |𝑏⟩ is an implicit tensor product: 𝑎 ⊗ |𝑏⟩
– We routinely simplify this even further to just |𝑎𝑏⟩

0
1 0 1
– Example: Given that 0 ≡ and 1 ≡ , then 01 = 0 ⊗ 1 =
0 1 0
0
• Simple cases
– Given two orthogonal kets ↑ and ↓ that are each normalized (this is typical),
– ↑ ↑⟩ = ⟨↓ ↓ = 1 and ↑ ↓ = ↓ ↑ = 0
• Convenient way to reason about linear transformations
– |out⟩⟨in| is an operator that maps |in⟩ to |out⟩ (i.e., by left multiplication) and anything
orthogonal to |in⟩ to a zero vector: out ⟨in|in⟩ = |out⟩; out ⟨in|out⟩ = 𝟎 (if in ⊥ |out⟩)
• Distributive properties
– Example: assuming 𝑥 ⊥ |𝑦⟩ and ∥ 𝑥 ∥ = ∥ 𝑦 ∥= 1,
– ( 𝑥 ⟨𝑦| − 𝑖|𝑦⟩⟨𝑥|) 𝑥 = 𝑥 ⟨𝑦|𝑥⟩ − 𝑖 𝑦 ⟨𝑥|𝑥⟩ = 𝑥 ⋅ 0 − 𝑖 𝑦 ⋅ 1 = −𝑖|𝑦⟩
– Also, |𝑎⟩⟨𝑏| ⊗ |𝑐⟩⟨𝑑| = 𝑎 ⊗ 𝑐 ⟨𝑏| ⊗ ⟨𝑑| = |𝑎𝑐⟩⟨𝑏𝑑|

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 5

 Notation Exercises

• For the following exercises,

1 3 7 3
– Define 𝑢 ≡ 0 + 1 and 𝑣 ≡ 0 − |1⟩
2 2 4 4
– Please work with Dirac notation—don’t convert to explicit
vectors/matrices
• Exercise 1: Evaluate 〈𝒖|𝒗〉
– Remember: This is an inner product so you should wind
up with a scalar value: 𝛼
• Exercise 2: Expand |𝒖〉〈𝒗|
– Remember: This is an outer product so you should wind
up with a matrix: 𝛼|0⟩⟨0| + 𝛽|0⟩⟨1| + 𝛾|1⟩⟨0| + 𝛿|1⟩⟨1|
• Exercise 3: Apply |𝒖〉〈𝒗| to |𝒗〉
– Remember: This is a matrix times a vector so you should Remember FOIL (first,
wind up with a vector: 𝛼 0 + 𝛽|1⟩ outer, inner, last):
• Exercise 4: Expand |𝒖𝒗〉 𝑎+𝑏 𝑐+𝑑 =
– Remember: |𝑢𝑣〉 ≡ |𝑢〉|𝑣〉 ≡ |𝑢〉 ⊗ |𝑣〉 so you should wind 𝑎𝑐 + 𝑎𝑑 + 𝑏𝑐 + 𝑏𝑑
up with a vector: 𝛼 00 + 𝛽 01 + 𝛾 10 + 𝛿|11⟩

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 6

 Notation Exercises: Solutions

• Exercise 1: Evaluate 〈𝒖|𝒗〉

1 3 7 3 1 7 1 3 3 7 3
– 𝑢|𝑣 = 〈0| + 〈1| |0〉 − |1〉 = ⋅ 00 − ⋅ 01 + ⋅ 10 − ⋅
2 2 4 4 2 4 2 4 2 4 2
3 7 3 21 3 3 7−3 3
11 = ⋅1− ⋅0+ ⋅0− ⋅1=
4 8 8 8 8 8
• Exercise 2: Expand |𝒖〉〈𝒗|
1 3 7 3 7 3 21 3 3
– |𝑢〉〈𝑣| = |0〉 + |1〉 ⟨0| − ⟨1| = |0⟩⟨0| − |0⟩⟨1| + |1⟩⟨0| − |1⟩⟨1|
2 2 4 4 8 8 8 8

• Exercise 3: Apply |𝒖〉〈𝒗| to |𝒗〉

7 3 21 3 3 7 3
– Hard way: |𝑢〉〈𝑣| |𝑣〉 = |0⟩⟨0| − |0⟩⟨1| + |1⟩⟨0| − |1⟩⟨1| |0〉 − |1〉 =
8 8 8 8 4 4
7 7 3 7 21 7 3 3 7 7 3 3
⋅ 0 00 − ⋅ 0 10 + ⋅ 1 00 − ⋅ 1 10 − ⋅ 0 01 + ⋅
8 4 8 4 8 4 8 4 8 4 8
3 21 3 3 3 3 7 147 9
0 11 − ⋅ 1 01 + ⋅ 1 11 = 0 −0+ 1 −0−0+ 0 −
4 8 4 8 4 32 32 32
9 3 1 3
0+ 1 = 0 + |1⟩
32 2 2
1 3
– Easy way: |𝑢〉 𝑣|𝑣 = |𝑢〉 ⋅ 1 = |𝑢〉 = |0〉 + |1〉
2 2
• Exercise 4: Expand |𝒖𝒗〉
1 3 7 3 7 3 21 3 3
– |𝑢𝑣〉 = |0〉 + |1〉 |0〉 − |1〉 = 00 − 01 + 10 + |11⟩
2 2 4 4 8 8 8 8

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 7

 The Circuit Model of Quantum Computing

Qubit number
|0⟩ H

|0⟩ Y

Time

• A labelled box represents single-qubit operators (2×2 matrix)

• Symbol–vertical line–symbol represents a two-qubit operator (4×4 matrix)
• A quantum circuit is really just a piecewise representation of an enormous
unitary matrix (2n×2n for an n-qubit system)
1 0 0 0 0 −𝑖 0 −𝑖
0 1 0 0 1 1 1 0 −𝑖 1 𝑖 0 𝑖 0
– Above: 𝐶𝑁𝑂𝑇 𝐻 ⊗ 𝑌 = ⊗ =
0 0 0 1 2 1 −1 𝑖 0 2 𝑖 0 −𝑖 0
0 0 1 0 0 −𝑖 0 𝑖
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 8
 Mathematical Forms Commonly Encountered in QC

• Magnitude of a complex number, | ⋅ |

– 𝑎 + 𝑏𝑖 ≡ 𝑎 2 + 𝑏 2
• Vector and matrix adjoint, 𝑨†
– Complex-conjugate transpose
†
𝑎 + 𝑏𝑖
– ≡ 𝑎 − 𝑏𝑖 𝑐 − 𝑑𝑖
𝑐 + 𝑑𝑖
†
𝑎 + 𝑏𝑖 𝑐 + 𝑑𝑖 𝑎 − 𝑏𝑖 𝑒 − 𝑓𝑖
– ≡
𝑒 + 𝑓𝑖 𝑔 + ℎ𝑖 𝑐 − 𝑑𝑖 𝑔 − ℎ𝑖
• Matrix types
– Hermitian: 𝐴 = 𝐴†
– Unitary: 𝐴† 𝐴 = 𝐴𝐴† = 𝐼
• Matrix exponentials
∞
1 𝑘
– For square matrix 𝐴, 𝑒 𝐴 = ෍ 𝐴
𝑘!
𝑘=0

– In the above, 𝐴0 ≡ 𝐼 for the 𝐼 with the same dimensions as 𝐴

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 9

 The Circuit Model

Los Alamos National Laboratory and NASA Ames 18-Nov-2024

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 2

 Reminders
Either How much
0 or 1 “0-ness”
• Unit of information α
𝑏 vs.
β
– Classical: Single bit, 𝑏 How much
𝛼 bit qubit “1-ness”
– Quantum: Complex 2-vector, 𝜓 = 𝛽
(𝑏 ∈ 𝔹) (𝛼, 𝛽 ∈ ℂ)
• Measurement
– Measuring a qubit forces it to either 0 or 1
• Superposition
𝛼 1 0
– If qubit 𝜓 = 𝛽 = 𝛼 +𝛽 = 𝛼 0 + 𝛽|1⟩, then it will be measured as 0 with
0 1
probability 𝛼 2 and as 1 with probability 𝛽 2 00
• Multiple-qubit representation 𝛼
𝛽 01
– A two-qubit state is a complex 4-vector 𝛼 00 + 𝛽 01 + 𝛾 10 + 𝛿|11⟩ =
𝛾 10
– An n-qubit state is a complex 2 n-vector 𝛿
• Entanglement 11
– The qubits in a two-qubit state are entangled if they can’t be factored into 𝑝 ⊗ |𝑞⟩
1 1 1 1 1
– Example: 1 −1 1 −1 ⊤ can be factored into ⊗ (∴ not
2 2 1 2 −1
1
entangled), but 0 1 1 0 ⊤ cannot be factored (∴ entangled)
2

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3

 Basic Circuit-Model Concepts

• Analogy to classical, digital circuits

Qubits
Bits

T† S
T H T†

Time Time

• Differences
– Quantum circuits must be reversible (implication: same number of inputs
and outputs for each gate and for the circuit as a whole)
– Only combinational, not sequential, logic
• Key point
– Abstract model of the operators to be applied—software not hardware
• A qubit’s state can be considered a point on the unit sphere
• Programmers explicitly control quantum effects
– Superposition: This qubit should be rotated by this amount in this direction
– Entanglement (loosely): This qubit should conditionally rotate that qubit
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 4
 Manipulating Quantum States

• Apply operators (a.k.a. quantum gates)

– Unitary matrices (corollary: all operations are 0 1
reversible) 1 0
– 2×2 for single-qubit gates, 4×4 for double-,
8×8 for triple-, etc.
Pauli x gate
• Examples of single-qubit gates
– X, a.k.a. Pauli x, a.k.a. σx, a.k.a. NOT rotates
by π radians around the x axis; it flips 0 |1⟩
– Y, a.k.a. Pauli y, a.k.a. σy rotates by π radians 0 −𝑖
around the y axis 𝑖 0
– Z, a.k.a. Pauli z, a.k.a. σz rotates by π radians
around the z axis
Pauli y gate
– Note that 𝑋𝑋 = 𝑌𝑌 = 𝑍𝑍 = 𝐼
• A rotation in any direction by any
amount is a gate
1 0
– Example: NOT rotates by π/2 radians around 0 −1
the x axis

Pauli z gate
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 5
 Manipulating Quantum States (cont.)

• An important single-qubit gate • Examples of two-qubit gates

– H, a.k.a. Hadamard rotates by π radians
1 0 0 0
around the diagonal pointing towards
0 0 1 0
(+x, +z); it puts each of |0⟩ and |1⟩ into a – SWAP:
0 1 0 0
perfect superposition of |0⟩ and |1⟩
0 0 0 1
1
• |0⟩ → 2
(|0⟩ + |1⟩), a.k.a. |+⟩ – Swaps the values of the two qubits
• |1⟩ →
1
(|0⟩ − |1⟩), a.k.a. |−⟩ (i.e., maps ab → ba )
2
– Measurement of perfect superposition 1 0 0 0
returns 0 and 1 with equal probability 0 1 0 0
– CNOT:
– Surprise: applying a Hadamard gate to a 0 0 0 1
perfect superposition returns 0 or 1 with 0 0 1 0
certainty (because 𝐻𝐻 = 𝐼) – Flips the second qubit if and only if the
first qubit is 1 [“if a then b ← ¬b”]
(essentially an XOR: 𝑎𝑏 → 𝑎 |𝑎 ⊕ 𝑏⟩)
– Side effect of entangling the two
1 1 1 qubits
2 1 −1

Hadamard gate H
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 6
 A Useful Three-Qubit Gate

• Toffoli gate
Input Output
– A.k.a. controlled-controlled-not or CCNOT
|000⟩ |000⟩
1 0 0 0 0 0 0 0 |001⟩ |001⟩
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 |010⟩ |010⟩
0 0 0 1 0 0 0 0
– CCNOT: |011⟩ |011⟩
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 |100⟩ |100⟩
0 0 0 0 0 0 0 1
|101⟩ |101⟩
0 0 0 0 0 0 1 0
– Flips the third qubit if and only if both of the first two qubits are 1 |110⟩ |111⟩
– Maps 𝑎𝑏𝑐 → 𝑎 𝑏 |𝑐 ⊕ 𝑎𝑏⟩ |111⟩ |110⟩
• Universal gate
– Can implement any classical Boolean function using only CCNOTs
– AND: CCNOT(x, y, 0) → (x, y, x∧y)
– NOT: CCNOT(1, 1, x) → (1, 1, ¬x)
– OR: CCNOT(1, 1, CCNOT(CCNOT(1, 1, x), CCNOT(1, 1, y), 0)) → (1, 1, ¬x, ¬y, x∨y)
– NAND: CCNOT(x, y, 1) → (x, y, ¬(x∧y))

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 7

 Constructing a Gate from First Principles

• What matrix implements a Pauli X (NOT) gate?

1 0
– We assume the standard basis, 0 ≡ and 1 ≡
0 1
• Start with a truth table mapping inputs to outputs
Input Output
|0⟩ |1⟩
|1⟩ |0⟩
• Define a corresponding operator
– One term per row, which maps input to output and all else to the zero vector
– 𝑋 = |1⟩⟨0| + |0⟩⟨1|
0 1 0 1
– In matrix form, this would be 𝑋 = 1 0 + 0 1 =
1 0 1 0
• Although defined using basis vectors, this works on superpositions, too
1 3 3 1
– Example: If 𝜓 ≡ 0 − |1⟩, then 𝑋 𝜓 = − 0 + |1⟩
4 4 4 4

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 8

 Constructing a Larger Gate from First Principles

• What operator/matrix implements a SWAP gate? Input Output

– This is a two-qubit gate with the semantics 𝑎𝑏 → |𝑏𝑎⟩ |00⟩ |00⟩
• The corresponding truth table is shown at right
|01⟩ |10⟩
• Construct an operator (same process as before but
with more terms) |10⟩ |01⟩
– 𝑆𝑊𝐴𝑃 = |00⟩⟨00| + |10⟩⟨01| + |01⟩⟨10| + |11⟩⟨11| |11⟩ |11⟩
1 0 0 0
0 0 1 0
= 1 0 0 0 + 0 1 0 0 + 0 0 1 0 + 0 0 0 1
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
=
0 1 0 0
0 0 0 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 9

 Let’s Create a Quantum Circuit

• We’ll use the Quirk gate-model simulator for this task

– Go to https://algassert.com/quirk and click Edit Circuit
– Easy to use; lots of features; runs entirely within a Web browser

For now, we’ll

focus on just the
most basic gates

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 10

 Let’s Create a Quantum Circuit (cont.)

• What state are we in initially?

– The |00⟩ state
– Place a Chance display on qubit 0 then
extend it downwards to cover qubit 1, which
shows all two-qubit probabilities

• What if we add a CNOT from 0 to 1?

– So far, nothing happens ( 00 → |00⟩)

• What if we put an X before the control?

– The state changes from |00⟩ to |11⟩

• What if change the X to an H?

– We’re now in the state 00 + |11⟩
– Because qubit 0 is now equally |0⟩ and |1⟩, it
both flips and doesn’t flip qubit 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 11

 Let’s Create a Quantum Circuit (cont.)

• What if we double the H?

– We’re back in the |00⟩ state
– H-H = I so qubit 0 is 0 and we therefore don’t flip
qubit 1

• What if we move one of the Hs after the

CNOT control?
– We’re in the 00 + 01 + 10 − |11⟩ state

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 12

 Whoa! What Just Happened?

• Why does H-H-CNOT produce such a different result from H-CNOT-H?

– Let’s step through the two cases slowly to see what each circuit does…
• The H-H-CNOT case
– Timeline illustration (unnormalized): The H gate
𝐻0 (unnormalized)
|00⟩
𝐻0 + Input Output
|00⟩ |01⟩ 𝐶𝑁𝑂𝑇0→1
|00⟩ + + |00⟩ |00⟩ |0⟩ |+〉 = 0 + |1⟩
|01⟩ |00⟩ |1⟩ |−〉 = 0 − |1⟩
+
−|01⟩

• The H-CNOT-H case

– Timeline illustration (unnormalized):
𝐻0 |00⟩
𝐻0 𝐶𝑁𝑂𝑇0→1 +
|00⟩ |00⟩ |01⟩
|00⟩ + + +
|01⟩ |11⟩ |10⟩
+
−|11⟩
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 13
 Whoa! What Just Happened? (cont.)

• Formal explanation of the H-CNOT-H case

– Our circuit represents 𝐼 ⊗ 𝐻 𝐶𝑁𝑂𝑇 𝐼 ⊗ 𝐻 applied to the input |00⟩
1 1
– 𝐼 ⊗ 𝐻 = |0⟩⟨0| + 1 ⟨1| ⊗ |0⟩⟨0| + |1⟩⟨0| + |0⟩⟨1| − |1⟩⟨1| = (|00⟩⟨00| +
2 2
|01⟩⟨00| + |00⟩⟨01| − |01⟩⟨01| + |10⟩⟨10| + |11⟩⟨10| + |10⟩⟨11| − |11⟩⟨11|)
– 𝐶𝑁𝑂𝑇 = |00⟩⟨00| + |11⟩⟨01| + |10⟩⟨10| + |01⟩⟨11|
1
– ∴ 𝐼 ⊗ 𝐻 00 = 00 + |01⟩
2
1 Different from what we
– ∴ (𝐶𝑁𝑂𝑇) 𝐼 ⊗ 𝐻 00 = 00 + |11⟩ showed on an earlier
2
1 slide because we
– ∴ (𝐼 ⊗ 𝐻)(𝐶𝑁𝑂𝑇) 𝐼 ⊗ 𝐻 00 = 00 + 01 + 10 − |11⟩
2 swapped the order of the
• Or, if you prefer a matrix formulation, control and target qubits

1 1 0 0 1 0 0 0 1
1 1 −1 0 0 0 0 0 1 0
𝐼⊗𝐻 = ; CNOT = ; and 00 =
2 0 0 1 1 0 0 1 0 0
0 0 1 −1 0 1 0 0 0
1 1 0 0 1 0 0 0 1 1 0 0 1 1
1 1 −1 0 0 0 0 0 1 1 1 −1 0 0 0 1 1
– So we get =
2 0 0 1 1 0 0 1 0 2 0 0 1 1 0 2 1
0 0 1 −1 0 1 0 0 0 0 1 −1 0 −1
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 14
 Hands-On Exercise: Construct a 4-Qubit GHZ State

• Greenberger–Horne–Zeilinger (GHZ) state

– Entangled state, equally likely to be all zeros or all ones but never anything else
• For this exercise, we’ll construct a 4-qubit GHZ state in Quirk
1
– That is, we want to create a circuit that produces 0000 + |1111⟩
2
– Here’s what your solution should look like (and note that we extended the Chance
display to cover four qubits):

?
• We’ll provide hints every few minutes to help you keep making progress

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 15

 Difficult Hands-On Exercise: a 2-bit Adder

• Skip this exercise unless you’ve already completed the previous

exercise and want a bigger challenge
• With only 4 qubits, implement a 2-bit adder modulo 4
– 𝑐1 𝑐0 ← 𝑎1 𝑎0 + 𝑏1 𝑏0 mod 4
– Input {𝑎1 , 𝑎0 , 𝑏1 , 𝑏0 } and output {𝑐1 , 𝑐0 , 𝑥, 𝑦} (where 𝑥 and 𝑦 are “don’t cares”)

• Hint #1
– This can be implemented with exactly two CNOTs plus one Toffoli (CCNOT) gate
• Hint #2
– CNOT flips the target bit iff the control bit is 1 (i.e., 𝑐𝑡 → 𝑐 |𝑐 ⊕ 𝑡⟩)
– CCNOT flips the target bit iff both control bits are 1 (i.e., 𝑐1 𝑐0 𝑡 → 𝑐1 𝑐0 |𝑐1 𝑐0 ⊕ 𝑡⟩)
• Hint #3
– From Digital Circuits 101,
𝑎1 𝑎0
+ 𝑏1 𝑏0
𝑎1 ⊕ 𝑏1 ⊕ 𝑎0 𝑏0 𝑎0 ⊕ 𝑏0

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 16

 4-Qubit GHZ State: Hint #1

• How would you create a 1-qubit GHZ state?

1
– That is, 0 + |1⟩ (a.k.a. |+〉), a state that’s equally likely to be |0⟩ or |1⟩
2
– What gate have we seen that does this?
• Solution format

– Quirk requires a minimum of two qubits so just leave qubit 1 alone

1
– Technically, the above represents 00 + |01⟩
2

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 17

 4-Qubit GHZ State: Hint #2

• Solution to Hint #1: Creating a 1-qubit GHZ state

1
– All we need is an H gate to transform state |00⟩ into state 00 + |01⟩
2

• Hint #2: How would you create a 2-qubit GHZ state?

1
– That is, 00 + |11⟩ , a state that’s equally likely to be |00⟩ or |11⟩
2
1
– Start from the Hint #1 state, 00 + |01⟩
2
– How can we leave |00⟩ alone but replace |01⟩ with |11⟩?
• Solution format

?
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 18
 4-Qubit GHZ State: Hint #2′

• Hint #2: How would you create a 2-qubit GHZ state?

1
– That is, 00 + |11⟩ , a state that’s equally likely to be |00⟩ or |11⟩
2
1
– Start from the Hint #1 state, 00 + |01⟩
2
– How can we leave |00⟩ alone but replace |01⟩ with |11⟩?
• Hint #2′: What single 2-qubit gate performs the preceding mapping?
– Given 𝑎𝑏 , negate 𝑎 if and only if 𝑏 is 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 19

 4-Qubit GHZ State: Hint #3

• Solution to Hint #2: Creating a 2-qubit GHZ state

1 1
– A CNOT gate performs the requisite mapping from 00 + |01⟩ to 00 + |11⟩
2 2
– “If qubit 0 is 1, flip qubit 1” (from 0 to 1 in this case)

• Hint #3: How would you create a 3-qubit GHZ state?

1 1
– Extend the above to 3 qubits: Given 000 + |011⟩ , produce 000 + |111⟩
2 2

• Solution format

?
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 20
 4-Qubit GHZ State: Hint #4

• Solution to Hint #3: Creating a 3-qubit GHZ state

– We simply repeat what we did for Hint #2
– A CNOT from qubit 0 to qubit 2 implements “If qubit 0 is 1, flip qubit 2”
1 1
– Maps 000 + |011⟩ to 000 + |111⟩
2 2

• Hint #4: What’s the pattern? How can we scale up from a 3-qubit GHZ
state to to a 4-qubit GHZ state?

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 21

 4-Qubit GHZ State: Solution

• Solution to Hint #4: Scaling up

– We can keep applying CNOTs to copy qubit 0 to each subsequent qubit in turn to
produce a circuit for the desired 4-qubit GHZ state

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 22

 4-Qubit GHZ State: Solution (cont.)

• Note how much easier it is to specify a quantum circuit gate-by-gate

than to specify the complete unitary matrix to which it corresponds:

• Such matrices grow large quickly

– The above is a 16×16 matrix; producing a 5-qubit GHZ would require a 32×32 matrix

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 23

 2-bit Adder: Solution

• Problem
– With only 4 qubits, implement a 2-bit adder modulo 4: 𝑐1 𝑐0 ← 𝑎1 𝑎0 + 𝑏1 𝑏0 mod 4
• Solution (explained by time step)
1. 𝑎1 , 𝑎0 , 𝑏1 , 𝑏0
2. 𝑎1 ⊕ 𝑏1 , 𝑎0 , 𝑏1 , 𝑏0
3. 𝑎1 ⊕ 𝑏1 ⊕ 𝑎0 𝑏0 , 𝑎0 , 𝑏1 , 𝑏0
4. 𝑎1 ⊕ 𝑏1 ⊕ 𝑎0 𝑏0 , 𝑎0 ⊕ 𝑏0 , 𝑏1 , 𝑏0
–= 𝑐1 , 𝑐0 , 𝑏1 , 𝑏0
𝑏0 𝑏0
𝑏1 𝑏1
𝑎0 𝑐0
𝑎1 𝑐1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 24

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 25

 Grover’s Algorithm

• Which box contains the prize?

0 1 2 3 4 5 6 7

– Classically, must open all 8 boxes in the worst case

• Let’s see how we can use quantum effects to do better than that…
• Given
– A power-of-two number of boxes
– A guarantee that exactly one box contains the prize
– An operator 𝑈𝜔 that, given a box number |𝑥⟩, negates the probability amplitude iff the
box contains the prize (i.e., 𝑈𝜔 𝑥 = −|𝑥⟩ for 𝑥 = 𝜔 and 𝑈𝜔 𝑥 = |𝑥⟩ for 𝑥 ≠ 𝜔)
• Define the Grover diffusion operator as follows
1
– 𝑠 ≡ σ𝑁−1
𝑥=0 |𝑥⟩ (i.e., the equal superposition of all states)
𝑁
– 𝑈𝑠 ≡ 2|𝑠⟩⟨𝑠| − 𝐼 (the Grover diffusion operator)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 26

 Grover’s Algorithm (cont.)

• The basic algorithm is fairly straightforward to apply:

– Put each of the n qubits in a superposition of |0⟩ and |1⟩
𝜋
– For 2𝑛 iterations
4
• Apply 𝑈𝜔 to the state
• Apply 𝑈𝑠 to the state
• How does that work?
– Gradually shifts the probability amplitude to state |𝜔⟩ from all the other states
– When we measure, we’ll get a result of |𝜔⟩ with near certainty
Probability
amplitude

Mean

000 001 010 011 100 101 110 111

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 27

 Implementing Grover’s Algorithm

• Let’s solve the following circuit-satisfiability problem:

– For what 0/1 inputs {𝑥1 , 𝑥2 , 𝑥3 } does the following circuit return 𝑥10 = 1?

𝑥1 𝑥5
𝑥2 OR
𝑥8
OR
𝑥6
NOT

𝑥9
OR AND 𝑥10
𝑥7
𝑥3 NOT AND
𝑥4

• Classically, this requires 𝟐𝟑 = 𝟖 circuit evaluations in the worst case

– Half that in the average case
𝜋
• Grover’s algorithm performs exactly 𝟐𝟑 = 𝟐 circuit evaluations
𝟒
– But on a superposition of all possible inputs

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 28

 Approach

1. Express the digital circuit as a 4. Apply the Grover diffusion

quantum circuit (an “oracle”) operator
– Operates on qubits {𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥10 } – Apply Hadamard gates to 𝑥1 , 𝑥2 , and
– 𝑥1 , 𝑥2 , and 𝑥3 are the circuit inputs 𝑥3 to amplify |000 ⋯ ⟩
– 𝑥4 through 𝑥9 are scratch qubits – Use 𝑥10 ’s negative phase to swap the
assumed to be 0 on input phases of |000 ⋯ 0⟩ and |000 ⋯ 1⟩.
– 𝑥10 is the circuit output, which can be This is implemented with a cccNOT,
either 0 or 1 on input which negates 𝑥10 if and only if 𝑥1 =
𝑥2 = 𝑥3 = 0 (as opposed to a
– For a given 𝑥1 , 𝑥2 , and 𝑥3 , the CCCNOT, which negates 𝑥10 if and
quantum circuit negates 𝑥10 iff only if 𝑥1 = 𝑥2 = 𝑥3 = 1).
𝑓 𝑥1 , 𝑥2 , 𝑥3 = 1
– Apply Hadamard gates to 𝑥1 , 𝑥2 , and
2. Initialize Grover’s algorithm 𝑥3 to transfer |000 ⋯ ⟩’s amplitude to
– Apply Hadamard gates to 𝑥1 , 𝑥2 , and the basis vector corresponding to the
𝑥3 to work with all 8 combinations in solution
parallel 5. Repeat steps 3 and 4
– Apply an X and an H to 𝑥10 to put it in
6. Finalize Grover’s algorithm
the state 0 − |1⟩, thereby providing
both a positive and a negative phase – Apply an H to 𝑥10 to retain only basis
states of the form |𝑥1 𝑥2 𝑥3 0000000⟩
3. Apply the oracle
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 29
 Toolbox

• 𝒚 ← ¬𝒂 • 𝒚 ← 𝒂 ∨ 𝒃 (expressed as
𝒚 ← ¬(¬𝒂 ∧ ¬𝒃))
|𝑎⟩ |𝑎⟩
|0⟩ X |𝑦⟩ |𝑎⟩ X X |𝑎⟩

|𝑏⟩ X X |𝑏⟩
• 𝒚←𝒂∧𝒃
|0⟩ X |𝑦⟩
|𝑎⟩ |𝑎⟩
|𝑏⟩ |𝑏⟩
• Grover diffusion operator
|0⟩ |𝑦⟩
|𝑎⟩ H H |𝑎⟩

|𝑏⟩ H H |𝑏⟩

|0⟩ |𝑦⟩

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 30

 Toolbox

• 𝒚 ← ¬𝒂 • 𝒚 ← 𝒂 ∨ 𝒃 (expressed as
𝒚 ← ¬(¬𝒂 ∧ ¬𝒃))
|𝑎⟩ |𝑎⟩
|0⟩ |𝑦⟩ |𝑎⟩ |𝑎⟩

|𝑏⟩ |𝑏⟩
• 𝒚←𝒂∧𝒃
|0⟩ X |𝑦⟩
|𝑎⟩ |𝑎⟩
|𝑏⟩ |𝑏⟩
• Grover diffusion operator
|0⟩ |𝑦⟩
|𝑎⟩ H H |𝑎⟩

|𝑏⟩ H H |𝑏⟩

|0⟩ |𝑦⟩

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 31

 Defining the Oracle

𝑥1
𝑥2
𝑥3
𝑥4
𝑥5
𝑥6
𝑥7
𝑥8
𝑥9
𝑥10

Quirk version of this circuit: “Uncompute”—undo modifications to

https://tinyurl.com/m6wf6r 𝑥4, 𝑥5 , 𝑥6 , 𝑥7, 𝑥8, and 𝑥9 in preparation
for subsequent iterations

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 32

 The Complete Grover’s Algorithm

Init. Iter. 1 Iter. 2 Final.

Solution (read right
to left) is 110
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 33
 Shor’s Algorithm

• Factor 1,274,093,332,123,426,680,869 into a product of two primes

– Okay, it’s 135,763,451,261×9,384,656,329
• Observations
– Given that N is the product of two primes, p and q
– Given some a that is not divisible by either p or q
– Then the sequence {a1 mod N, a2 mod N, a3 mod N, a4 mod N, a5 mod N, …} will
repeat every r elements (the sequence’s period)
– As Euler discovered (ca. 1760), r always divides (p−1) (q−1)
• Example
– Let a be 2 and N be 15 (=3×5)
– Then ak mod N = {2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1 …} so r is 4
– Lo and behold, 4 divides (3−1) (5−1)=8
• Approach
– Once we know the period, r, it’s not too hard to find N’s prime factors, p and q
– Unfortunately, finding r is extremely time-consuming…for a classical computer

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 34

 Shor’s Algorithm (cont.)

• Use an inverse quantum Fourier N is the number

transform (QFT) to find the period to factor
• All else is classical
• Randomized algorithm with proof Choose a
of timely termination random a < N

Y N
gcd(a, N)=1?

Find r, the period of ak mod N

a and N/a are
factors of N
Y
r odd?
N
Y
ar/2 ≡ 0 mod N?
N
gcd(ar/2+1, N) and gcd(ar/2−1, N) are factors of N
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 35
 Other Models of Quantum Computing

Los Alamos National Laboratory and NASA Ames 18-Nov-2024

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 2

 Measurement-Based Quantum Computing (MBQC)

Outline of measurement-based quantum computation

– Start in a highly entangled state that serves as the quantum resource
• Cluster states, graph states, …
– Make series of single-qubit measurements that can depend on previous
– Interpret results of the measurements to obtain a final answer
Properties
– Computational power equivalent to standard quantum computation
– Separation between classical and quantum aspects of the computation
– Entanglement decreases; also called one-way quantum computing
Resource states for MBQC
– Some states too entangled to serve as a resource!
– Classically hard to sample from output distributions of non-adaptive MBQC!
– Natural setting for “blind” quantum computing, with ties delegated and
verifiable quantum computation
– Elegant setting for proving certain results in quantum computation, e.g.
Gottesman-Knill Theorem
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3
 Graph States

Two (equivalent) ways of Graph state

defining graph states
• Ctrl-Z on all edges, or
• Stabilizers 𝑋𝑣 ⊗ ໆ 𝑍𝑤
𝑤∈nbhd(𝑣)

Specific types of graph

states on (subgraph of) 2D Cluster state
lattice
• Cluster states
• Brickwork states Brickwork state

Computation goes from left

to right
• Measuring column by
column
• Rows correspond to
logical qubits
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 4
 Key Primitive: “One-Bit Teleportation”

Measurement is in the standard

basis
• Corresponds to Hermitian
operator Z

State is transferred, up to action of

a Hadamard gate and possible X
operator, from the input qubit to
the output qubit

The measurement outcome m is

known, so we know where an X
was applied or not

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 5

 Key Primitive: One-Bit Teleportation with Phase Shift

• An arbitrary phase gate Z𝜃 can

incorporated
• We can think of the H Z𝜃 followed
by the standard basis
measurement as a single qubit
measurement in a different basis,
the basis B𝜃
• The first operator, the Ctrl-Z
operator, has already taken place
m when forming a graph state

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 6

 Chaining to Enable Single-Qubit Operations

• We can chain two 1-bit

teleportation circuits together
Chaining of two 1-bit
teleportation circuits • We can then write this operation
more succinctly, just labeling the
qubits with the measurement
that will be done
3-qubit cluster state

B(𝜃0) B(𝜃1)

Cluster state diagram equivalent to above

circuit diagram
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 7
 Universal Gate Set for MBQC

Three gates on
a brickwork state

Hadamard gate CNOT gate

π/4 π/4 π/4 0 0 0 π/4 0

0 0 0 0 0 π/4 0 π/4

T gate MBQC can implement gate model QC

π/8 0 0 0 using these primitives

0 0 0 0 Supports blind quantum computation

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 8

 Can Any Entangled State be Used?

• Can all entangled states be used as resource states for measurement-

based quantum computation?
• Is more entanglement better?

• No!
• Gross, Flammia and Eisert, and independently, Bremner, Mora, and
Winter showed that if states are too highly entangled they cannot be
used for measurement-based quantum computation.
• Low showed that there are efficiently constructable states that are too
entangled to be used for measurement-based quantum computation.

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 9

 Measurement-Based Quantum Computation and
Optical Implementations of Quantum Computers
• Prior to 2001, optical approaches to quantum computation were viewed
as unpromising
– Photons do not interact much with anything
– Good for communication but not computation

• In 2001, Knill, Laflamme and Milburn (KLM) pioneered approach that

makes use of measurement to achieve CNOT gates, but with significant
overhead

• In 2004, Nielsen showed how to reduce this overhead by combining the

KLM approach and measurement-based quantum computation

• Optical approaches are now viewed as reasonable candidates for

implementation of quantum computers

• In 2021, Bartolucci et al. introduced Fusion-Based Quantum

Computation
– Uses two-qubit entangling measurements

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 10

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 11

 Analog Rydberg Atom Arrays

• Underlying physics
– Focusing a laser on a rubidium atom can
send its outer electron from the fifth orbital to
a high-numbered orbital (∼60th–80th)
– This excited state is called the “Rydberg ground state Rydberg state
state”
– Atoms can be moved precisely around the 0 1
plane using optical tweezers
– Quantum effect: Atoms nearer than some
threshold distance cannot both be in the
Rydberg state (the “Rydberg blockade”
effect)
• Computational model
– Label ground state |0⟩ and Rydberg state |1⟩
– Place atoms in problem-specific locations
and excite all of them simultaneously
– The system will maximize the number of |1⟩
atoms subject to not violating any Rydberg
blockades

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 12

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
• Suffices for solving satisfiability problems
– OR + NOT is classically universal (but other gates
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 13

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
A = FALSE
• Suffices for solving satisfiability problems B = FALSE
– OR + NOT is classically universal (but other gates Y = FALSE
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 14

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
A = FALSE
• Suffices for solving satisfiability problems B = TRUE
– OR + NOT is classically universal (but other gates Y = TRUE
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 15

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
A = TRUE
• Suffices for solving satisfiability problems B = FALSE
– OR + NOT is classically universal (but other gates Y = TRUE
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 16

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
A = TRUE
• Suffices for solving satisfiability problems B = TRUE
– OR + NOT is classically universal (but other gates Y = TRUE
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 17

 Example: A Logical OR Relation

• Goal is to construct a state representing

𝒀=𝑨∨𝑩
1
– That is, 𝐴𝐵𝑌 = 000 + 011 + 101 + |111⟩
2
• One solution is shown to the right
• Treat as a game with the following rules: B
– Place exactly 3 coins on the figure
– Place 0 or 1 coin in each single circle
– Place 0 or 2 coins in the double circle A
– If a coin is placed in a circle, a coin cannot be
placed in any overlapping circle Y
• No matter how you place the 3 coins, Y will
have a coin if and only if A or B (or both)
contains a coin
• Suffices for solving satisfiability problems
– OR + NOT is classically universal (but other gates P ¬P
can be created for convenience)
– Weighting the circuit output biases it to TRUE

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 18

 Native Problem for Analog Rydberg Atom Arrays

• Maximum weighted independent set on

unit-disk graphs (MWIS-UDG)
– NP-hard problem
• Independent set
– Marking of graph vertices such that no two
connected vertices are both marked
• Maximal independent set
– Independent set such that no more vertices
can be marked
• Maximum independent set
– Largest possible maximal independent set
• Maximum weighted independent set
– Vertices can have different weights
– Maximum total weight is marked
• MWIS-UDG
– Vertices represented by diameter-1 disks laid
out on a plane
– Edge exists iff two disks overlap
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 19
 Native Problem for Analog Rydberg Atom Arrays

• Maximum weighted independent set on

unit-disk graphs (MWIS-UDG)
– NP-hard problem
• Independent set
– Marking of graph vertices such that no two
connected vertices are both marked
• Maximal independent set
– Independent set such that no more vertices
can be marked
• Maximum independent set
– Largest possible maximal independent set
• Maximum weighted independent set
– Vertices can have different weights
– Maximum total weight is marked
• MWIS-UDG
– Vertices represented by diameter-1 disks laid
out on a plane
– Edge exists iff two disks overlap
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 20
 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 21

 Quantum Annealing

• Underlying physics
– Hamiltonian function (ℋ) ≡ a mapping from a (Hamiltonian-
specific) orthogonal basis vector to a real-valued energy
– The system relaxes a given Hamiltonian function to a low—
not necessarily the lowest—energy level
– Measurement returns the associated basis vector
– Increasing the likelihood of finding the lowest energy:
• Start with the variables (qubits) initialized to the solution to a
known, trivial problem (the initial Hamiltonian)
• Gradually transition the problem from the trivial problem to the
problem you want to solve (the problem Hamiltonian)
• Premise (adiabatic theorem): Sufficiently gradual transition →
qubits remain in the solution state
• Computational model
– Encode a problem as a Hamiltonian function ℋ ∶ 𝔹𝑁 → ℝ
such that the solution corresponds to the inputs producing
the smallest output:
𝑁 𝑁−1 𝑁
arg min ෍ 𝑎𝑖 𝑥𝑖 + ෍ ෍ 𝑏𝑖,𝑗 𝑥𝑖 𝑥𝑗 , 𝑎𝑖 , 𝑏𝑖,𝑗 ∈ ℝ, 𝑥𝑖 ∈ 𝔹 (an NP-hard problem)
𝒙
𝑖=1 𝑖=1 𝑗=𝑖+1
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 22
 Example: A Logical OR Relation

• Goal is to construct a state representing 1 1

𝒀=𝑨∨𝑩
1
1
– That is, 𝐴𝐵𝑌 =
2
000 + 011 + 101 + |111⟩ A B
• One solution is shown to the right
• Treat as a game with the following rules:
– Place 0–3 coins on the figure
−2 −2
– For each covered circle, gain the number of points
associated with that circle
– For each 2 covered circles connected by an edge, Y
gain the # of points associated with that edge
– Golf-style scoring: Aim for the lowest score
• The lowest score is achieved when Y has a 1
coin if and only if A or B (or both) contains
a coin arg min 𝐴 + 𝐵 + 𝑌 + 𝐴𝐵 − 2𝐴𝑌 − 2𝐵𝑌
𝐴,𝐵,𝑌
• Suffices for solving satisfiability problems
– OR + NOT is classically universal (but other gates
can be created for convenience)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 23

 Example: A Logical OR Relation

1 1

1
A B Y Score A B
0 0 0 0
0 0 1 1
0 1 0 1 −2 −2
0 1 1
1 0 0 1 Y
1 0 1
1 1 0 1
1 1 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 24

 Example: A Logical OR Relation

1 1

1
A B Y Score A B
0 0 0 0
0 0 1 1
0 1 0 1 −2 −2
0 1 1 1+1−2 = 0
1 0 0 1 Y
1 0 1 1+1−2 = 0
1 1 0 1
1 1 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 25

 Example: A Logical OR Relation

1 1

1
A B Y Score A B
0 0 0 0
0 0 1 1
0 1 0 1 −2 −2
0 1 1 1+1−2 = 0
1 0 0 1 Y
1 0 1 1+1−2 = 0
1 1 0 1+1+1 = 3 1
1 1 1

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 26

 Example: A Logical OR Relation

1 1

1
A B Y Score A B
0 0 0 0
0 0 1 1
0 1 0 1 −2 −2
0 1 1 1+1−2 = 0
1 0 0 1 Y
1 0 1 1+1−2 = 0
1 1 0 1+1+1 = 3 1
1 1 1 1+1+1+1−2−2 = 0

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 27

 Example: A Logical OR Relation

1 1

1
A B Y Score A B
0 0 0 0
0 0 1 1
0 1 0 1 −2 −2
0 1 1 1+1−2 = 0
1 0 0 1 Y
1 0 1 1+1−2 = 0
1 1 0 1+1+1 = 3 1
1 1 1 1+1+1+1−2−2 = 0

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 28

 Example: A Logical OR Relation

• Goal is to construct a state representing 1 1

𝒀=𝑨∨𝑩
1
1
– That is, 𝐴𝐵𝑌 =
2
000 + 011 + 101 + |111⟩ A B
• One solution is shown to the right
• Treat as a game with the following rules:
– Place 0–3 coins on the figure
−2 −2
– For each covered circle, gain the number of points
associated with that circle
– For each 2 covered circles connected by an edge, Y
gain the # of points associated with that edge
– Golf-style scoring: Aim for the lowest score
• The lowest score is achieved when Y has a 1
coin if and only if A or B (or both) contains
a coin 2
• Suffices for solving satisfiability problems P ¬P
– OR + NOT is classically universal (but other gates
can be created for convenience)
−1 −1
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 29
 Example: A Logical OR Relation

• Goal is to construct a state representing 1 1

𝒀=𝑨∨𝑩
1
1
– That is, 𝐴𝐵𝑌 =
2
000 + 011 + 101 + |111⟩ A B
• One solution is shown to the right
• Treat as a game with the following rules:
– Place 0–3 coins on the figure
−2 −2
– For each covered circle, gain the number of points
associated with that circle
– For each 2 covered circles connected by an edge, Y
P
gain the # of points associated with that edge
– Golf-style scoring: Aim for the lowest score
• The lowest score is achieved when Y has a 1 −1 = 0
coin if and only if A or B (or both) contains
a coin 2
• Suffices for solving satisfiability problems ¬P
– OR + NOT is classically universal (but other gates
can be created for convenience)
−1
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 30
 Native Problem for Quantum Annealing

• Quadratic unconstrained binary optimization (QUBO) problems

– Also known as unconstrained binary quadratic programming (UBQP) problems
– Quadratic: 𝑥𝑖 and 𝑥𝑖 𝑥𝑗 terms are allowed but not 𝑥𝑖 𝑥𝑗 𝑥𝑘 terms
– Unconstrained: no direct ability to specify, for example, 𝑥𝑖 + 𝑥𝑗 + 𝑥𝑘 ≤ 2
– Binary: 𝑥𝑖 ∈ [0,1] or, in the “Ising-model Hamlitonian” variation, 𝑥𝑖 ∈ [−1, +1]
– Optimization: goal is to find the 𝒙 values that minimize the target expression
– That is, arg min σ𝑁 𝑁−1 𝑁
𝑖=1 𝑎𝑖 𝑥𝑖 + σ𝑖=1 σ𝑗=𝑖+1 𝑏𝑖,𝑗 𝑥𝑖 𝑥𝑗 , 𝑎𝑖 , 𝑏𝑖,𝑗 ∈ ℝ, 𝑥𝑖 ∈ 𝔹
𝒙
• Surprisingly general formulation
– Any polynomial cost function over discrete variables with polynomial constraints can
be mapped to this form
– Many examples exist; see Andrew Lucas’s, “Ising formulations of many NP
problems”, DOI: 10.3389/fphy.2014.00005
• Robustly handles frustrated systems 2
P Q
– Recall from the previous slide that 𝑃 ≠ 𝑄 can be expressed as
ℋ≠ 𝑃, 𝑄 = −𝑃 − 𝑄 + 2𝑃𝑄 and that Hamiltonians are additive −1 −1
– How is ℋ≠ 𝐴, 𝐵 + ℋ≠ 𝐵, 𝐶 + ℋ≠ (𝐶, 𝐴) minimized? That’s 𝐴 ≠ 𝐵, 𝐵 ≠ 𝐶, 𝐶 ≠ 𝐴
– A quantum annealer always returns a value because it’s minimizing, not solving

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 31

 Exploiting Frustration

• Example: Find the maximum cut of a graph

– Goal is to divide the vertices of an undirected graph into two partitions to maximize
the number of edges that must be cut to separate the partitions
– This is an NP-hard problem

A A A

B C B C B C

D E D E D E

A example graph Partitioning leading to Partitioning leading to a

a cut of size 3 (not cut of size 5 (maximal)
maximal)
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 32
 Maximum Cut on a Quantum Annealer

• Maximizing the number of edges

that span partitions = maximizing Given ℋ≠ 𝑃, 𝑄 = −𝑃 − 𝑄 + 2𝑃𝑄,
the number of adjacent vertices
with different colors let ℋ𝑀𝐶 𝐴, 𝐵, 𝐶, 𝐷, 𝐸
= ℋ≠ 𝐴, 𝐵 + ℋ≠ 𝐴, 𝐶 + ℋ≠ 𝐵, 𝐶 +
• Approach: Specify 𝒖 ≠ 𝒗 for all ℋ≠ 𝐵, 𝐷 + ℋ≠ 𝐶, 𝐸 + ℋ≠ 𝐷, 𝐸
adjacent vertices 𝒖 and 𝒗
• These may not all be satisfiable, but = −2𝐴 − 3𝐵 − 3𝐶 − 2𝐷 − 2𝐸 + 2𝐴𝐵 +
the quantum annealer will satisfy as 2𝐴𝐶 + 2𝐵𝐶 + 2𝐵𝐷 + 2𝐶𝐸 + 2𝐷𝐸
many as possible as this is what
minimizes ℋ𝑴𝑪 A
– For example, the optimal partitioning
shown to the right yields
ℋMC 0,0,1,1,0 = −5 B C
– The suboptimal partitioning from the
previous slide yields ℋ𝑀𝐶 0,0,1,0,1 = −3
– An example of a very poor partitioning is
ℋ𝑀𝐶 1,1,1,1,1 = 0
D E

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 33

 Further Quantum Algorithms

Los Alamos National Laboratory and NASA Ames 18-Nov-2024

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 2

 Target for NISQ Evaluation: Quantum Optimization
Heuristics
• Instances of combinatorial optimization problems
– Current approach: classical heuristics algorithms
– NISQ hardware provides means to evaluate quantum heuristic algorithms

One strategy: Try the simplest algorithm that might work!

• Quantum heuristics
– Combine cost-function-based operator with a mixing operator
– AQO, QA, QAOA
– Other ideas welcome!

• Evaluation techniques
– Analytic, numerical, experimenting on NISQ hardware

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 3

 Target for NISQ Evaluation: Quantum Optimization
Heuristics
• Diverse optimization goals
– Exact optimization with guarantees
– Approximate opt. with guarantees
– Good heuristic, without guarantees
– Fair sampling; portfolio sampling

• Sampling goals, e.g. for machine learning (ML)

– Sampling thermal distribution corresponding to cost function (sampling from
Boltzmann distributions used in ML)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 4

 Quantum Optimization Algorithms: AQO, QA, QAOA

Common elements: Given cost function C(z),

• Phase separation operator based on the cost function,
– Usually based on 𝐻𝑃 = −𝐶 𝑧 |𝑧⟩⟨𝑧|, often including additional “penalty terms” to
enforce constraints
• Driver/Mixing operator
– Most frequently 𝐻𝑀 = ∑𝑋𝑗, though we will shortly see other mixers
𝑗

(AQO is a special case of Adiabatic Quantum Computing (AQC))

AQO QA QAOA
• Alternate
• Evolution under • Evolution under application of 𝐻𝑃
𝑯(𝒕) = 𝒂(𝒕)𝐻𝑃 + 𝒃(𝒕)𝐻𝑀 𝑯(𝒕) = 𝒂(𝒕)𝐻𝑃 + 𝒃(𝒕)𝐻𝑀 and 𝐻𝑀
• For p alterations, the
• Slowly enough to • Many quick runs, parameters are 𝟐𝒑
stay in the ground thermal effect times/angles
subspace 𝜸𝟏 , 𝜷𝟏 , … 𝜸𝑷 , 𝜷 𝒑
contribute
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 5
 Quantum Optimization Algorithms: AQO, QA, QAOA

Common elements: Given cost function C(z),

• Phase separation operator based on the cost function,
– Usually based on 𝐻𝑃 = −𝐶 𝑧 |𝑧⟩⟨𝑧|, often including additional “penalty terms” to
enforce constraints
• Driver/Mixing operator
– Most frequently 𝐻𝑀 = ∑𝑋𝑗, though we will shortly see other mixers
𝑗

(AQO is a special case of Adiabatic Quantum Computing (AQC))

AQO QA QAOA
• Alternate
• Evolution under • Evolution under application of 𝐻𝑃
𝑯(𝒕) = 𝒂(𝒕)𝐻𝑃 + 𝒃(𝒕)𝐻𝑀 𝑯(𝒕) = 𝒂(𝒕)𝐻𝑃 + 𝒃(𝒕)𝐻𝑀 and 𝐻𝑀
• For p alterations, the
• Slowly enough to • Many quick runs, parameters are 𝟐𝒑
stay in the ground thermal effect times/angles
subspace 𝜸𝟏 , 𝜷𝟏 , … 𝜸𝑷 , 𝜷 𝒑
contribute
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 6
 Quantum Alternating Operator Ansatz

Based on the Quantum Approximate Optimization Algorithm

• A gate model algorithm due to Farhi et al.
• Iterates between two Hamiltonians, p times
– Phase separation (cost function dep.)
– Mixing
Early results by Farhi and co-authors
• p → ∞: from AQO
– Converges to optimum for p → ∞
• p = 1: proofs modified from proofs for IQP circuits
– Provably hard to sample output efficiently classically (up to standard
complexity theory conjectures)
– Beat existing classical approx. ratio on MaxE3Lin2, but inspired better
classical algorithm
Later results
Z. Jiang et al., Near-optimal quantum
• New algorithm for Grover’s unstructured search problem circuit for Grover's unstructured search
– achieves √N query complexity by different means using a transverse field, PRA 95 (6),
062317, 2017.

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 7

 Quantum Alternating Operator Ansatz

• Advantages
– Supports more general mixing operators, providing massive improvements in
implementability
– Incorporates hard constraints into mixer instead of as a penalty term; algorithm
explores only feasible subspace, often exponentially smaller, so more efficient
search
– Reworked QAOA acronym to support applications to exact optimization and
sampling as well as approximate optimization
• We have mapped many problems to extended QAOA formalism
– Focused on scheduling and network problems
– Including Max-k-colorable subgraph

S. Hadfield et al., From the Quantum Approximate Optimization Algorithm to a

Quantum Alternating Operator Ansatz, Algorithms 12 (2), 34 2019, arXiv:1709.03489

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 8

 Gate-model quantum optimization heuristic:
Quantum Alternating Operator Ansatz
•.
Generalization of Quantum Approximation Optimization algorithm

ෑ 𝑒 −𝑖𝛽𝑘𝐻𝑗
𝑗

Phase separator: unitary Mixer: unitary which: Initial state |s> which:
for which • Preserves the feasible • is a superposition of one or
• The energy spectrum of subspace more solutions in the feasible
HP encodes the • Provides nonzero transitions subspace
problem’s objective between all feasible states • can be prepared efficiently
function • Not necessarily time
evolution of a single local
• 𝐻𝑃 = −∑𝐶 𝑧 |𝑧⟩⟨𝑧|
Hamiltonian
• 𝛽k depends on the level 1 ≦ S. Hadfield et al., From the Quantum
k ≦ p, but independent of Hj Approximate Optimization Algorithm to
a Quantum Alternating Operator Ansatz,
Algorithms 12 (2), 34, 2019

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 9

 Example: QAOA for Max-κ-Colorable Subgraph

•Problem: Given a graph 𝑮 = 𝑽, 𝑬 ,

and 𝒌 colors 𝟏, … , 𝒌, find a color
assignment maximizing the # of
properly colored edges
Properly colored edge means endpoint
vertices have been assigned different
colors

“One-hot” Encoding: 𝒏𝒌 variables

• 𝒙𝒖𝒋 = 𝟏 iff vertex u is colored Must avoid invalid colorings
color j e.g. if a vertex is labeled as both red and
blue, or not colored at all
Requires n constraints: one for each
• Optimization: Write cost function as vertex u
• 𝑪 𝒙 = 𝒎 − ∑𝒎𝒖𝒗 ∈𝑬 ∑𝒌𝒋=𝟏 𝒙𝒖𝒋𝒙𝒗𝒋
∑𝒌𝒋=𝟏 𝒙𝒖𝒋 = 𝟏

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 10

 Example: QAOA for Max-κ-Colorable Subgraph

Could add constraints to the cost function Use a swap or XY-mixer (XX+YY) on the
to enforce penalties colors rather than bit flip mixer:
- standard approach in quantum instead of ∑𝑋𝑗, use sum of swap operators,
annealing 𝑗
𝟎𝟎 >< 𝟎𝟎 + 𝟏𝟎 >< 𝟎𝟏 +
Better: design mixer to keep evolution in
feasible subspace (constant Hamming |𝟎𝟏 >< 𝟏𝟎| + |𝟏𝟏 >< 𝟏𝟏|
weight in colors for each vertex) between colors at a vertex
Feasible subspace is exponentially smaller Ring mixer:
search space than entire Hilbert space order the colors, and apply swaps to
While still exponentially large adjacent colors only
Initial state choice Complete mixer:
Any classical feasible state swap for every pair of colors
e.g. all colored red Complete mixer mixes more quickly, but
Any superposition of feasible states has higher circuit depth, especially
when compiled to realistic hardware
e.g. superposition of all colors (W state)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 11

 Partitioned Mixer Example: Max-κ-Colorable Subgraph

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 12

 Numerical Results: Advantage of XY-mixer

Ring vs. complete mixer

Numerical obtained approximation ratio for 3-coloring

of a triangle graph. (Left) QAOA with standard X- Approximation ratio on all 4-colorable,
mixer. (Right) QAOA with XY-mixer. connected graphs with 7 vertices
Confirmed advantage of mixers that Trade off in depth between initial state
maintain evolution within feasible generation and QAOA iterations
subspace • W state vs single classical state
Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, Eleanor G. Rieffel,
Ratio of dimension of feasible subspace to full XY-mixers: analytical and numerical results for QAOA, PRA 101 (1),
012320, 2020
Hilbert space of shrinks exponentially with n:
XY-mixer retains advantage under noise
M Streif, M Leib, F Wudarski, E Rieffel, Z Wang, Quantum algorithms with local
particle number conservation: noise effects and errorcorrection, Physical
Review A 103 (4), 042412, 2021

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 13

 Status of QAOA

Unclear as of yet as to whether QAOA provides a speed up beyond a few

examples
– that is true for any NISQ quantum optimization algorithm!
– Alternative to Grover’s algorithm for unstructured search (not NISQ)
Parameter setting is challenging
– But only requires satisficing, not optimizing
– relation between parameter setting in QAOA and annealing schedule choice in
quantum annealing
Many variants of QAOA have been developed
– Iterative Quantum algorithms
– Build on classical optimization algorithms
– Ties with machine learning

Brady, Baldwin, Bapat, Kharkov, V. Gorshkov, Optimal protocols in quantum annealing and quantum approximate optimization
algorithm problems, PRL 2021

Stuart Hadfield, Tad Hogg, Eleanor G. Rieffel, Analytical Framework for Quantum Alternating Operator Ansätze, Quantum Science
and Technology, 2022

Lucas Brady, Stuart Hadfield, Iterative quantum algorithms for maximum independent set: a tale of low-depth quantum algorithms
arXiv:2309.13110, 2023

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 14

 Challenge Exercise: Map Independent Set to QAOA

• MIS (Map Independent Set) Problem: Given a graph 𝑮, find largest

mutually disjoint subset of vertices 𝑺 ⊂ 𝑽, where 𝑽 = 𝒏

• Specify
– Representation (meaning of binary variables)
– Cost function
– Mixing operator
– Initial state

• Feel free to express in terms of classical operations, including

controlled-NOTs, even multiply controlled-NOTs
– Then convert to Hamiltonian or unitary

• Bonus exercise: Map Max-3-Colorable-Induced Subgraph to QAOA

– Problem statement: Given a graph 𝑮, find largest subset of vertices 𝑺 ⊂ 𝑽, such that
all edges between s ∈ S are properly colored (endpoints have different colors)
– Hint: Use concepts from both Max-Colorable-Subgraph and MIS mappings

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 15

 A Solution: One Possible MIS to QAOA Mapping

• Representation
– Use n binary variables 𝒙𝒖 , one for each vertex in the graph. These variables will be
mapped to n qubits. Variable 𝒙𝒖 = 𝟏 indicates vertex 𝒖 ∈ 𝑺
• Initial State: Empty set: |𝟎𝟎…𝟎⟩

• Cost function
– cost function to maximize 𝒄 𝑺 = |𝑺| = ∑𝒖∈𝑽 𝒙𝒖
𝟏
– maps to Hamiltonian 𝑪 = ∑𝒖∈𝑽(𝑰 − 𝒁𝒋 )
𝟐

• Mixer
– Can add (or remove) a vertex 𝒖 to 𝑺 if none of 𝒖’s neighbors are already in 𝑺
– For each vertex, construct the partial mixer (a controlled X-rotation)
𝒆𝒙𝒑 −𝒊𝜷𝑩𝒖 = 𝚲𝒙𝒗 𝒙 …𝒙𝒗ℓ 𝐞𝐱𝐩(−𝐢𝜷𝑿𝒖)
𝟏 𝒗𝟐
For more explanation, and answer
where 𝒏𝒅𝒉𝒅 𝒖 = {𝒗𝟏 , … 𝒗ℓ }
to bonus exercise, see
– Total mixer: 𝑼𝑴 𝜷 = ς𝒖∈𝑽 𝒆𝒙𝒑(−𝒊𝜷𝑩𝒖 ) Hadfield et al. From the Quantum Approximate
where we must choose a product order Optimization Algorithm to a Quantum Alternating
Operator Ansatz. arXiv:1709.03489 (2017)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 16

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 17

 Example: Hardware-Alg. Co-Design: Q. Annealing

The power of pausing: additional control of anneal Standard D-

schedule, increases performance by orders of Wave 2000Q
magnitude schedule

Heat map of probability

of solution, depending Example
on pause location and pause
pause length schedule

An appropriately placed
pause can improve TTS as
well as the probability of
Anneal time regions. success
Purple region is where - on embedded instances of
pause is expected to be application interest
effective. - consistent region in which
pausing helps
J. Marshall et al. (2019), Power of pausing: Advancing understanding of thermalization in experimental quantum annealers, Phys. Rev.
Applied 11, 044083
Z. Izquierdo et al. (2021), Ferromagnetically shifting the power of pausing, Phys. Rev. Applied 15, 044013
Z. Izquierdo et al. (2022), Advantage of pausing: Parameter Setting for Quantum Annealers, Phys. Rev. Applied 18 (5), 054056

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 18

 Example: Hardware-Algorithm Co-Design, Gate-Model

Quantum Alternating Operator Ansatz Problem instance:

introduced more general “mixing Max-K-Colorable
operators” subgraph
inspired native implementations of
these general mixing operators on
Rigetti hardware

Rigetti developed novel calibration

techniques for this family of gates

Collaboration with Rigetti under Approximation ratio for 3-coloring a

DARPA ONISQ project to evaluate triangle: QAOA with standard X-mixer
QAOA on their gate-model processors (left) and with XY-mixer (right)

S. Hadfield et al. (2019), From the quantum approximate optimization algorithm to a quantum alternating operator Ansatz, Algorithms 12, 34
Z. Wang et al. (2020), XY-mixers: analytical and numerical results for QAOA pausing, Phys. Rev. A 101, 012320
M. Streif el al. (2021), Quantum algorithms with local particle number conservation: Noise effects and error correction, PRA

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 19

 Status of Quantum Algorithms

• Anything a classical computer can

do, a quantum computer can do
• Provable quantum advantage known Conjecture: Quantum
for a few dozen quantum algorithms heuristics will significantly
• Data from Quantum Algorithms Zoo: broaden of applications of
speed up over classical quantum computing
– Exponential: 2
– Superpolynomial: 29
– Polynomial: 28 What is the chance that the
– Constant: 1 only cases in which
– Varies: 4 quantum computing
– Total: 64 provides a speed up is in
– https://quantumalgorithmzoo.org/ cases when we can prove
• Rapidly expanding opportunity for it does?
empirical testing on emerging
quantum hardware

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 20

 Verification of quantum advantage

• How do you verify a

computation that no
other hardware can
do?
– check smaller version
– check pieces Example random quantum circuit. Every cycle includes
a layer of single- and two-qubit gates. The single-qubit
– check variants that are gates are chosen randomly from a set of three gates. The
simpler to simulate sequence of two-qubit gates follow a tiling pattern,
• Entering an era of coupling each qubit sequentially to its four neighbors.
unprecedented 24 Oct 2019
ways to explore
quantum
algorithms
• Era of quantum
heuristics.
• These explorations
will broaden the
known application
of quantum
computing

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 21

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
Break
• Part II: Circuit-model quantum computing
– Review of notation
– Quantum gates and quantum circuits
Lunch
– Basic quantum algorithms
• Part III: Other models of quantum computing
– Measurement-based quantum computing
– Analog Rydberg atom arrays
– Quantum annealing
Break
• Part IV: Further quantum algorithms
– Quantum Alternating Operator Ansatz (QAOA)
– Advances in quantum algorithms
– Concluding remarks

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 22

One Area of Quantum Computing
is Underhyped
They are applications of quantum
computing but not of quantum
computers
One Area of Quantum Computing
is Underhyped
 Impact of Quantum Information Processing Viewpoint
on Classical Computer Science
Example of quantum-inspired classical algorithms
• Quantum Monte Carlo
• Improved classical techniques for simulating quantum systems
• De-quantized quantum algorithms
• e.g. for E3Lin2
• e.g. certain sampling and quantum ML algorithms

Analogies
– Complex analysis enables computation of real integrals
– Probabilistic algorithms inform analysis of deterministic algorithms

Quantum-inspired, dequantized, quantum-spurred algorithms

– Drucker & de Wolf (2009) survey “Quantum proofs for classical theorems”
– Arrazola et al. (2019), “Quantum-Inspired Algorithms in Practice”
– Huynh et al. (2023), “Quantum-Inspired Machine Learning: a Survey”

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 26

 Quantum Error Mitigation

• Error suppression: Inhibits transitions out of the ground

subspace
• Error correction: Counteracts transitions that have
happened
• Quantum error correction initially thought impossible!
– No cloning principle: an unknown quantum state cannot be copied reliably without
destroying the original
• Quantum information theory was just too interesting
– Steane and Shor & Calderbank saw a way to finesse what had seemed
insurmountable barriers to quantum error correction
• Now quantum error correction is one of the most developed areas
– beautiful, almost magical, effects!
– uses properties of quantum measurement and entanglement to its advantage
• Stabilizer code formulation most common
– Surface code
• Remains active area of research
– Subsystem codes; dynamical/Floquet codes
– Decoders, …
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 27
 Fault Tolerance

• Error suppression and correction mechanisms cannot be done perfectly

• Fault tolerance: Ensures error suppression/correction do not introduce
more problems than they solve

• Imprecise implementation of mechanisms may cause errors

• Even accurate implementation may magnify errors
– can take correctable errors to uncorrectable ones

• Threshold theorems: There exists an error rate threshold rth below

which indefinitely long quantum computations can be carried out
robustly
• In the gate model, a number of different threshold theorems are known.
– Specific theorems involve precise statements of error model, precision of
implementation, resource quantification, distance measure
• How to establish a threshold theorem for adiabatic quantum computing
remains a major open question

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 28

 Utility-scale quantum computers

Utility-scale quantum computers May have 2D local structures,

will resemble supercomputers higher dimensional comm at larger
– Many quantum processing units scales
(QPUs), and classical processing
units (CPUs) Algorithm/QEC/hardware codesign
– Quantum and classical
communication Much of the processing will be for
Potentially heterogeneous quantum error correction
quantum components Surface code is not the end of the
– Memory story
– Magic state factories Many breakthroughs in QEC in the
past few years
– Special purpose components
New code types
targeted at common quantum
subroutines Better decoders
New types of codes:
Compilation and resource
estimation on future QC Dynamical/Floquet codes
architectures good quantum LDPC codes
Los Alamos National Laboratory and NASA Ames 18-Nov-2024
 Compiling quantum circuits to quantum hardware

Compilation of an algorithms to Qubit routing can be

a NISQ processor requires phrased as a temporal
• Decomposition into native planning problem
gates • minimize makespan
• Qubit routing Can incorporate
– nearest-neighbor h/w
constraints
Qubit routing moves qubit – varying quantum gate
states to locations where the times
required gates can act on them – crosstalk
• Can be done by inserting
SWAPs into a circuit
composed of native
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 30
 A Historical Perspective

• Illiac IV—first massively parallel

computer
– 64 64-bit FPUs and a single CPU
– 50 MFLOP peak, fastest computer at
the time

• Finding good problems and

algorithms was challenging

• Questions at the time

– How broad will the applications be of
massively parallel computing?
– Will computers ever be able to compete
with wind tunnels?

NASA Ames director Hans Mark brought

Illiac IV to NASA Ames in 1972

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 31

 Take Away Points

• Next year will be even more exciting!

– Emerging quantum hardware performing
computations beyond the reach of even the largest
supercomputers Quantum-
enhanced
• Many open questions remain: applications
– When will scalable quantum computers be built, and
how?
• How quickly can special purpose quantum computing
devices be built? QC programming
– How broad will the impact of quantum computation Novel classical
be? What will the ultimate impact of quantum solvers
heuristics be?
– How best to harness quantum effects for
computational purposes? Physics Insights

• Deep connection between physics and Simulation Analytical

tools methods
computer science
– How fast does nature let us compute?

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 32

 Further Reading

Eleanor Rieffel and Wolfgang Polak

Quantum Computing: A Gentle Introduction
MIT Press, March 2011

And references therein

Overviews of NASA QuAIL team work

Eleanor G Rieffel, Ata Akbari Asanjan, M Sohaib Alam, Namit Anand, David E Bernal Neira, Sophie Block, Lucas T
Brady, Steve Cotton, Zoe Gonzalez Izquierdo, Shon Grabbe, Erik Gustafson, Stuart Hadfield, P Aaron Lott, Filip B
Maciejewski, Salvatore Mandrà, Jeffrey Marshall, Gianni Mossi, Humberto Munoz Bauza, Jason Saied, Nishchay
Suri, Davide Venturelli, Zhihui Wang, Rupak Biswas, Assessing and advancing the potential of quantum
computing: A NASA case study, Future Generation Computer Systems (2024)

Eleanor G. Rieffel, et al, From Ansätze to Z-gates: a NASA View of Quantum Computing, , Adv. in Parallel
Computing 34, 133–160 (2019)

Los Alamos National Laboratory and NASA Ames 18-Nov-2024 33

 Additional Resources

• Free access to real quantum computers

– IBM Quantum Experience (circuit model): https://quantum-computing.ibm.com/
– D-Wave Leap (annealing model): https://cloud.dwavesys.com/
• Software for high-level programming of quantum computers
– Constraint programming (both circuit and annealing models): NchooseK
(https://github.com/lanl/NchooseK)
– Prolog (annealing model): QA Prolog (https://github.com/lanl/QA-Prolog)
– C (annealing model): C to D-Wave (https://github.com/lanl/c2dwave)
– Verilog (annealing model): edif2qmasm (https://github.com/lanl/edif2qmasm)
• HPC quantum-circuit simulator
– HybridQ (https://github.com/nasa/hybrid)
• Optimized physics-based classical codes for optimization and
benchmarking
– PySA (https://github.com/nasa/pysa)
• Student internships available
– NASA QuAIL at NASA Ames Research Center (https://www.nasa.gov/intelligent-
systems-division/discovery-and-systems-health/nasa-quail/)
– LANL Quantum Computing Summer School Fellowship:
https://quantumcomputing.lanl.gov/
Los Alamos National Laboratory and NASA Ames 18-Nov-2024 34