Introduction to Quantum Computing

Scott Pakin, Los Alamos National Laboratory

Eleanor G. Rieffel, NASA Ames Research Center

13 November 2022

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
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 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 13-Nov-2022 3

 Quantum-Computing Fundamentals

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 5

 NASA’s Stake in Quantum Computing

NASA constantly confronting

massively challenging Quantum-enhanced
computational problems applications
• Computational capacity limits
mission scope and aims
Quantum, hybrid quantum-
classical, and physics-
NASA’s Pleiades inspired classical algorithms
One of the top 25 fastest
supercomputers in the
world QC programming

NASA QuAIL mandate: Fundamental quantum

Determine the potential for physics mechanisms
quantum computation to enable Simulation tools
more ambitious NASA missions Analytical methods

in the future
NASA Ames QuAIL team
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 6
 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 13-Nov-2022 7

 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 engine
physically (Computer History
Museum)
– When we program we don’t think about the
fundamental physics

• How do different models of physics

affect how quickly we can compute?

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 8

 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 13-Nov-2022 9

 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 13-Nov-2022 10

 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 13-Nov-2022 11

 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
computer can do • Best classical algorithm not known for most
problems proven
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 13-Nov-2022 12
 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
Number of qubits alone is not a good measure
E.g. Quantum Intermediate-
- 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 13-Nov-2022 13

 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
larger, more capable devices

Uses of these still limited, quantum devices?

(1) Unprecedented opportunity to explore and

evaluate algorithms, both quantum and hybrid
quantum-classical heuristic algorithms
Cover article, (2) Investigate quantum mechanisms that may be
Nature, 24 Oct harnessed for computational purposes
2019

Google, NASA, ORNL collaboration Insights gained feed into next generation
• quantum algorithms
[Link] • quantum hardware
6-019-1666-5
[Link] Early target: Optimization, Machine Learning, Chem &
antum-supremacy Materials Simulation

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 14

 Three Group Exercises

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

of quantum computation

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 15

 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 13-Nov-2022 16

 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) 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.
d) “Quantum supremacy” will be achieved only when quantum computers can run
Shor’s algorithm on cryptographically relevant numbers.

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 17

 Exercise 3

• Which statement best describes the relation between uncertainty and

quantum algorithms?
a) Like classical algorithms, quantum algorithms fall in two categories, algorithms that
provide an answer with certainty and probabilistic algorithms
b) Quantum mechanics is by nature uncertain—think the quantum uncertainty
principle—so unlike classical algorithms, quantum algorithms are inherently
probabilistic
c) 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
d) All algorithms, both quantum and classical, cannot provide a result with certainty—
life is inherently uncertain.

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

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 19

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 20

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 21

 A Simple Experiment: Photon Polarization

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 22

 Mathematically Representing Photon Polarization

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 23

 Measurement of Polarization

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 24

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 25

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 26

 The Photon Polarization Experiment Revisited

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 27

 Qubits (Quantum Bits)

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 28

 Measurement of Single Qubits

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 29

 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 13-Nov-2022 30

 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 13-Nov-2022 31
 Exponential State Space

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 32

 Quantum vs. classical state spaces

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 33

 Measurement of Single Qubits

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 34

 Entangled States

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 35

 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 13-Nov-2022 36

 Quantum Computer (Circuit Model)

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 37

 Exercise

Which of the following states

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

b) |00101⟩
1
c) ++ = 00 + 01 + 10 + |11⟩
2
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
+ = ( 0 + |1⟩) and − = ( 0 − |1⟩)
2 2
iii) are entangled?
• Bonus exercise: Prove the no cloning theorem
(Hint: follows from linearity of quantum operations)

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 38

 Notation

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 40

 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 13-Nov-2022 41

 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 13-Nov-2022 42

 More on Dirac Notation

• Ket-kets and bra-bras

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

0
1 0 1
– Example: Given that 0 ≡ and 1 ≡ , 01 = 0 |1⟩ = 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⟩ = 𝟎
• Distributive properties
– Example: assuming 𝑥 ⊥ |𝑦⟩ and ∥ 𝑥 ∥ = ∥ 𝑦 ∥= 1,
– ( 𝑥 ⟨𝑦| − 𝑖|𝑦⟩⟨𝑥|) 𝑥 = 𝑥 ⟨𝑦|𝑥⟩ − 𝑖 𝑦 ⟨𝑥|𝑥⟩ = 𝑥 ⋅ 0 − 𝑖 𝑦 ⋅ 1 = −𝑖|𝑦⟩
– Also, |𝑎⟩⟨𝑏| ⊗ |𝑐⟩⟨𝑑| = |𝑎𝑐⟩⟨𝑏𝑑|

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 43

 Examples of Working with Dirac Notation

1 3
• Let 𝑤 ≡ 0 + 1 in the following examples
2 2
• Example 1 (bra-ket): Evaluate 〈𝒘|𝒘〉
1 3 1 3 1 3 3 3 1
– 𝑤|𝑤 = 〈0| + 〈1| |0〉 + |1〉 = 0|0 + 0|1 + 1|0 + 1|1 = ⋅ 1 +
2 2 2 2 4 4 4 4 4
3 3 3
⋅ 0+ ⋅0+ ⋅1=1
4 4 4
• Example 2 (ket-bra): Expand |𝒘〉〈𝒘|
1 3 1 3 1 3 3 3
– |𝑤〉〈𝑤| = |0〉 + |1〉 〈0| + 〈1| = |0〉 0| + |0 1| + |1 0| + |1 〈1|
2 2 2 2 4 4 4 4
• Example 3 (operator-ket): Apply |𝒘〉〈𝒘| to |𝒘〉
1 3 3 3 1 3
– Hard way: |𝑤〉〈𝑤| |𝑤〉 = |0〉 0| + |0 1| + |1 0| + |1 〈1| |0〉 + |1〉 =
4 4 4 4 2 2
1 3 3 3 3 1 3
|0〉 +0+ |1〉 +0 + 0 + |0〉 + 0 + |1〉 = |0〉 + |1〉
8 8 8 8 2 2
1 3
– Easy way: |𝑤〉 𝑤|𝑤 = |𝑤〉 ⋅ 1 = |𝑤〉 = |0〉 + |1〉
2 2
• Example 4 (ket-ket): Expand |𝒘𝒘〉
1 3 1 3 1 3 3 3
– |𝑤𝑤〉 = 𝑤 𝑤 = |0〉 + |1〉 |0〉 + |1〉 = |00〉 + |01〉 + |10〉 + |11〉
2 2 2 2 4 4 4 4

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 44

 The Circuit Model of Quantum Computing

Qubit number
|0⟩

|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 13-Nov-2022 45
 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 13-Nov-2022 46

 The Circuit Model

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 48

 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 2n-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 13-Nov-2022 49

 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 13-Nov-2022 50
 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.
• Examples of single-qubit gates Pauli x gate
– 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 13-Nov-2022 51
 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⟩
1
0 0 0 1
• |0⟩ → (|0⟩ + |1⟩), a.k.a. |+⟩ – Swaps the values of the two qubits
2

• |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 – CNOT:
0 1 0 0
– 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 13-Nov-2022 52
 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 13-Nov-2022 53

 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 13-Nov-2022 54

 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 13-Nov-2022 55

 Let’s Create a Quantum Circuit

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

– Go to [Link] 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 13-Nov-2022 56

 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 13-Nov-2022 57

 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 13-Nov-2022 58

 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⟩
00⟩
𝐻0 + Input Output
|00⟩⟩ |01⟩
01⟩⟩
01 𝐶𝑁𝑂𝑇0→1
|00⟩ + + |00⟩ |00⟩ |0⟩ |+〉 = 0 + |1⟩
|01⟩ |00⟩
00⟩ |1⟩ |−〉 = 0 − |1⟩
+
−|01⟩
|01⟩
01⟩

• The H-CNOT-H case

– Timeline illustration (unnormalized):
𝐻0 |00⟩
00⟩
𝐻0 𝐶𝑁𝑂𝑇0→1 +
|00⟩⟩ ||00⟩⟩ |01⟩
01⟩
|00⟩ + + +
|01⟩ ||11⟩⟩ |10⟩
10⟩
+
−|11⟩
11⟩
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 59
 Hands-On Exercise: Construct a 3-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 3-qubit GHZ state in Quirk
1
– That is, we want to create a circuit that produces 000 + |111⟩
2
– Here’s what your solution should look like (and note that we extended the Chance
display to cover three qubits):

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

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 60

 3-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 13-Nov-2022 61

 3-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 13-Nov-2022 62
 3-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 13-Nov-2022 63

 3-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 13-Nov-2022 64
 3-Qubit GHZ State: Solution

• 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

• Continuing the pattern

– For a 4-qubit GHZ state, add a CNOT from qubit 0 to qubit 3
– For a 5-qubit GHZ state, add a CNOT from qubit 0 to qubit 4
– For a 6-qubit GHZ state, add a CNOT from qubit 0 to qubit 5

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 65

 Comparing Circuit and Matrix Formulations

• 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:

1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 −1
0 0 1 1 0 0 0 0
1 0 0 0 0 1 −1 0 0
vs.
2 0 0 0 0 1 1 0 0
0 0 1 −1 0 0 0 0
0 0 0 0 0 0 1 1
1 −1 0 0 0 0 0 0

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 66

 Comparing Circuit and Matrix Formulations (cont.)

• Let’s extend the 3-qubit GHZ state to a 4-qubit GHZ state

– Add one more CNOT to the circuit or double each matrix dimension

vs.

• Very quickly grows out of hand

– A 10-qubit GHZ state could be expressed with either an H and 10 CNOTs or a
million-element unitary matrix

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 67

 Basic Quantum Algorithms

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 69

 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 |𝑥⟩ (i.e., the equal superposition of all states)
𝑁 𝑥=0
– 𝑈𝑠 ≡ 2|𝑠⟩⟨𝑠| − 𝐼 (the Grover diffusion operator)

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 70

 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 13-Nov-2022 71

 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 ax 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 13-Nov-2022 72

 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 ax 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 13-Nov-2022 73
 Further Quantum Algorithms and Tools

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 75

 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 13-Nov-2022 76

 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 13-Nov-2022 77

 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 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 13-Nov-2022 78

 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
• Many problems can be mapped to extended QAOA formalism
– Initial paper focused on scheduling and network problems

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 13-Nov-2022 79

 Summary and Open Questions

Unclear as of yet as to whether QA or QAOA provides a quantum advantage

beyond a few examples
– True for any NISQ quantum optimization algorithm!

Parameter setting is challenging

– Active area of research
– relation between parameter setting in QAOA and annealing schedule choice in quantum
annealing
– Only requires satisficing, not optimizing

Exploration of variants of QAOA and QA may be promising

Empirical evaluation of QAOA as a quantum heuristic critical for

understanding its potential impact
Tie between quantum hardware and quantum algorithms research
– Role of special purpose quantum hardware
– Possibility of quantum hardware between quantum annealers and gate model, pulsing
global Hamiltonians
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 80
 Connecting QA schedules and QAOA parameter setting

Yang, Rahmani, Shabani, H Neven, C Chamon, Optimizing variational quantum algorithms using pontryagin's minimum
principle, PRX 2017
- Pontryagin’s minimum principle implies optimal evolution schedules must be bang-bang, up to some caveats

Zhou, Wang, Choi, Pichler, Lukin, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and
Implementation on Near-Term Devices, arXiv:1812.01041
• Learned optimal parameters
• Identified regular subfamily of optimal parameters, resembling digitized smooth evolution
– For easy problems, resembled adiabatic schedules
– For hard problems, resembled diabatic schedules

Mbeng, Fazio, Santoro, Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational
schemes, arXiv:1906.08948
- Connects adiabatic adiabatic schedules with optimal QAOA parameters for the easy problem of MaxCut on a Ring

Brady, Baldwin, Bapat, Kharkov, V. Gorshkov, Optimal protocols in quantum annealing and quantum approximate
optimization algorithm problems, arXiv:2003.08952
- generically, for a fixed amount of time, optimal procedure has bang-bang structure of QAOA at the beginning and end, but
a smooth annealing structure in between

LT Brady, L Kocia, P Bienias, A Bapat, Y Kharkov, AV Gorshkov, Behavior of analog quantum algorithms, arXiv:2107.01218
- optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern
- QAOA emulates this optimal procedure
- new algorithm that better approximates the optimal protocol

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 81

 Qubit Routing on NISQ Processors

Compilation of an algorithms to
a NISQ processor requires
• Decomposition into native
gates
• Qubit routing

Qubit routing moves qubit

states to locations where the
required gates can act on them
• Can be done by inserting
SWAPs into a circuit From Minh Do, Zhihui Wang, Bryan O'Gorman,
Davide Venturelli, Eleanor Rieffel, Jeremy Frank,

composed of native Planning for Compilation of a Quantum Algorithm

for Graph Coloring, ECAI 2020, arXiv:2002.10917

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 82

 Temporal Planning for Qubit Routing

• Qubit routing can be phrased as a • Mapped circuit compilation problem

temporal planning problem to a temporal planning problem,
• minimize makespan compared state-of-the-art temporal
• Can incorporate planners
– nearest-neighbor h/w constraints • Demonstrated temporal planning is a
– varying quantum gate times viable approach to circuit compilation
– crosstalk
• Initial experiments focused on • More recently, combined temporal
• QAOA circuits for Maxcut because of planning with constrained
their high number of commuting gates programming
• Rigetti hardware proposal with varying
gates between neighboring qubits
• Expressive framework can
incorporate further hardware
requirements, incl. noise tradeoffs, as
we learn them

D. Venturelli et al., Compiling quantum circuits to realistic

hardware architectures using temporal planners, Quantum
Science and Technology (2018)
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 83
 Classical HPC Simulation of Quantum Circuits

Advanced the state-of-the-art

- simulates larger quantum circuits than
previous approaches
- judicious use of cuts within a tensor
network contraction
- HPC memory tricks and trade-offs Computed exact amplitudes for 72 qubit
- can flexibly incorporate fidelity goal Bristlecone random circuit, depth 1+32+1
Largest computation run on NASA HPC clusters
- 60-qubit subgraph, depth 1+32+1
- 116,611 processes on 13,059 nodes, peak
of 20 PFLOPS, 64% of max
- across Pleiades, Electra, Hyperwall Villalonga et al., A flexible high-performance simulator for the
verification and benchmarking of quantum circuits implemented
Applications on real hardware. arXiv:1811.09599
Villalonga et al., Establishing the Quantum Supremacy Frontier
- quantum supremacy experiments with a 281 Pflop/s Simulation, arXiv:1905.00444

- benchmark emerging quantum hardware Open source qFlex code:

- empirically explore quantum algorithms [Link]

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 84

 HybridQ: A Hybrid Quantum Simulator
for Large Scale Simulations
Hardware agnostic quantum simulator, designed to simulate large scale quantum circuits.
Can run tensor contraction simulations, direct evolution simulation and Clifford+T
simulations using the same syntax
Features:
Fully compatible with Python (3.8+)
Low-level optimization achieved by using C++ and Just-In-Time (JIT) compilation with JAX and Numba,
It can run seamlessly on CPU/GPU and TPU, either on single or multiple nodes (MPI) for large scale
simulations, using the exact same syntax
User-friendly interface with an advanced language to describe circuits and gates, including tools to
manipulate/simplify circuits.

Recent Improvements:
Commutations rules are used to simplify circuits (useful for QAOA)
Expansion of density matrices as superpositions of Pauli strings accepts arbitrary non-Clifford gates,
Open-source (soon!) project with continuous-integration, multiple tests and easy installation using either
pip or conda

Open source code available at [Link]

S. Mandrà, J. Marshall, E. G. Rieffel, R. Biswas, HybridQ: A Hybrid Simulator for Quantum Circuits, arXiv:2111.06868
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 85
 Concluding Remarks

Los Alamos National Laboratory and NASA Ames 13-Nov-2022

 Agenda

• Part I: Quantum-computing fundamentals

– High-level motivation, history, and status
– Qubits, multi-qubit states, and quantum measurement
– Review of notation
– Quantum gates and quantum circuits
Break
• Part II: Circuit-model quantum computing
– Quantum gates and quantum circuits (cont.)
– Basic quantum algorithms
– Further quantum algorithms and tools
– Concluding remarks
Adjourn

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 87

 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
• Subsystem codes; Dynamical Logical Qubits; LDPC codes; …

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 88

 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 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 13-Nov-2022 89

 Measurement-Based Quantum Computing (MBQC)

• High-level description of “one-way” 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
measurement results
– Interpret the 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!

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 90

 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
– [Link] cases when we can prove
• Rapidly expanding opportunity for it does?
empirical testing on emerging
quantum hardware

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 91

 Impact of Quantum Information Processing Viewpoint
on Classical Computer Science

• Analogies
– Complex analysis enables computation of real integrals
– Probabilistic algorithms inform analysis of deterministic algorithms
• Quantum computational security reductions for purely classical
encryption schemes
– Regev’s lattice-based encryption scheme
– One of the security reductions for Gentry’s fully homomorphic encryption scheme
• Improved classical simulations of quantum systems

• Insights into classical complexity theory

– Aaronson found a short, almost trivial, proof of a property of the complexity class PP
by showing that it is the same as the quantum complexity class PostBQP
• Drucker & de Wolf (2009) survey “Quantum proofs for classical
theorems”

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 92

 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 13-Nov-2022 93

 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 13-Nov-2022 94

 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, Stuart Hadfield, Tad Hogg, Salvatore Mandrà, Jeffrey Marshall, Gianni Mossi, Bryan O'Gorman,
Eugeniu Plamadeala, Norm M. Tubman, Davide Venturelli, Walter Vinci, Zhihui Wang, Max Wilson, Filip Wudarski,
Rupak Biswas, From Ansätze to Z-gates: a NASA View of Quantum Computing, arXiv:1905.02860

Rupak Biswas, Zhang Jiang, Kostya Kechezhi, Sergey Knysh, Salvatore Mandrà, Bryan O'Gorman, Alejandro
Perdomo-Ortiz, Andre Petukhov, John Realpe-Gómez, Eleanor Rieffel, Davide Venturelli, Fedir Vasko, Zhihui Wang,
A NASA Perspective on Quantum Computing: Opportunities and Challenges, arXiv:1704.04836

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 95

 Additional Resources

• Free access to physical quantum processors

– IBM Quantum Experience (circuit model): [Link]
– D-Wave Leap (annealing model): [Link]
• Additional software for high-level programming of D-Wave systems
– Prolog: QA Prolog ([Link]
– C: C to D-Wave ([Link]
– Verilog: edif2qmasm ([Link]
– Macro assembly language: QMASM ([Link]
– QUBO/Ising Google Sheet ([Link] File→Make a copy
to store an editable version in Google Drive or File→Download as to save locally
• HPC quantum-circuit simulator
– qFlex ([Link]

• Student internships available

– NASA QuAIL at NASA Ames Research Center
([Link]
– LANL Quantum Computing Summer School Fellowship:
[Link]
Los Alamos National Laboratory and NASA Ames 13-Nov-2022 96
 Funding Acknowledgements

NASA QuAIL LANL

Los Alamos National Laboratory and NASA Ames 13-Nov-2022 97