Transcript Slides

Quantum Computing for Programmers
Paul E. Black
[email protected]
http://hissa.nist.gov/~black/
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
An Experience in Torpor

Steps in reading a computer chip design
– Add gates to “not done” list
– Process gates from top to bottom
– Remove gate from “not done” list

Big designs were very slow
Why???
Note: gates added to head of list
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
2
Computing the Execution
  
n
  
n-1
  
n-2
  
n-3
  
  
  
How long does it take to delete gates?
  

3
2
1

Total time is about n2/2
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
3
How Long to Search an Array?

Code for linear search:
while (a[++i].key != value …);

Average number of steps for
linear search is n/2
n
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
4
How Long for Random Search?

Code for random search:
while (a[rand(0,a.size)].key
!= value);

Expected number of steps for
random search is n
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
5
How Long for Binary Search?

Expected number of steps for
binary search is log2 n
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
6
Compare Performance

Type
#Loops
Time for n=1,000,000
Random:
n
Linear:
n/2
Binary: log2 n
1,000,000xcR
500,000xcL
~20xcB
where c is time for 1 loop

Ignoring constant multiples, we say
random search is O(n)
linear search is O(n)
binary search is O(log n)
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
7
Definition of O(m)


Informally, saying f(n) = O(g(n)) means
f(n) is less than a constant times g(n)
Formally: there exist positive constants c and k
such that 0  f(n)  cg(n) for all n  k.
cg(n)
f(n)
k

Big-O notation can also express memory use,
messages sent, average time, worst case, etc.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
8
Definition of θ(m)


Informally, saying f(n) = θ(g(n)) means
f(n) equals, or grows as fast as, g(n)
Formally: there exist positive constants c1, c2, k
such that c1g(n)  f(n)  c2g(n) for all n  k.
c2g(n)
f(n)
c1g(n)
k

There are also notations for “greater than”, “less
than or equal to”, etc.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
9
Example: Sort Algorithms

Comparison of some sort algorithms
Sort
Typical Worst Case
Bubble sort
Quicksort
Heap sort
Θ(n2)
O(n log n)
O(n log n)
same
O(n2)
same

Bubble sort: repeatedly pass through the
list swapping items until all are in order
 Improvements(?)
– Bidirectional bubble sort: go both directions
– Don’t go beyond last swap
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
10
Polynomial vs. Exponential

Traveling Salesman: find shortest route to
visit every city on a list and return home.
 Best exact algorithm is Θ(n!) ≈ Θ((n/e)n)
where n is the number of cities.

Algorithms tend to fall into two classes:
polynomial, Θ(np), and exponential, Θ(bn).
 These classes are distinct:
– Polynomials of polynomials are polynomials
– Any exponential eventually exceeds any
polynomial
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
11
Factoring, or
What good is a quantum computer?

RSA, a good encryption scheme, is secure
because factoring large numbers is hard
 After centuries of work, the best factoring
algorithm is the Number Field Sieve
D(log D)2
 Factor a D-digit number in e
steps
 A key 8 times longer
3
– Takes 64 times longer to multiply, but
– Squares the time to factor
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
12
Shor’s Quantum Algorithm

Using quantum computing, numbers can
be factored in D2 log D log log D steps

Classical factoring is exponential, but
quantum factoring is polynomial!
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
13
DEAD or ALIVE
Schrödinger’s cat
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
What Math Should We Use?

10 L
15 ºC
Water
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
=?
5L
21 ºC
Alcohol
Paul E. Black
15
Polarization is really a measurement

A filter yields only photons with the same alignment.

A second filter at right angles blocks all photons.

A third filter in between those two allows some photons to pass.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
16
What Really Happens?

Polarization is a vector.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
17
What Really Happens?

Polarization is a vector.

Measurement projects the
vector onto a new basis.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
18
What Really Happens?

Polarization is a vector.

Measurement projects the
vector onto a new basis.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
19
What Really Happens?

Polarization is a vector.

Measurement projects the
vector onto a new basis.

Polarizer passes one basis.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
20
What Really Happens?

Polarization is a vector.
Y

Measurement projects the
vector onto a new basis.

Polarizer passes one basis.

Next polarizer measures “back
into” original basis.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
X
21
What Really Happens?

Polarization is a vector.

Measurement projects the
vector onto a new basis.

Polarizer passes one basis.

Next polarizer measures “back
into” original basis.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
22
Superposition

Single slit makes a normal distribution
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
23
Superposition

Single slit makes a normal distribution
 Two slits make interference patterns, even
with only one photon at a time
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
24
Superposition

A quantum system’s state may be several
potential places, spins, etc. at once.

Quantum algorithms often start with
qubits in a superposition of 1s and 0s.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
25
Entanglement

Measuring the polarization of A changes
the result of measuring B and vice versa.
A
A
Entangle
B
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
B
Paul Black
26
Fakey Entanglement Demonstration
We get an even number of heads from any
number of coin tosses.
How?
?
Heads are “entangled”: there is a 100% correlation
between getting one head and getting the other.
We don’t know when we will get heads, but we know we
will always get them together.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
27
How Do We Represent a State?
Classical (binary)
1
Example for 2 variables:
a = {00, 01, 10, 11}
Use 1 bit per variable
0
Limitation:
Can’t represent superposition or entanglement
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
28
Dirac or “ket” notation

Quantum bit or qubit:
… a quantum system with two discrete states.1

States are expressed in ket notation:
0

1

Multiple states are combined using a
tensor product in some fixed order:
P1  P2
PB  PA
 Tensor
productmay be implicit and is
associative, but not commutative:

P1P2P3
P PP

National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
PP P
Paul Black
PPP
29
What is a Tensor Product?
 1
2
2 5 1 2  
0


 
 1
4 3 0 3 
40
 
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
2 1 2 2 4
 5
 
3 0 3 0 6

2 1 2 4 8
 3
 
3 0 3 0 12
Paul Black
5 10

0 15
3 6 

0 9 
30
How do kets represent superposition?


Superpositions are sums of states, each
with “amplitude”: a complex number
1
2
0 
1
2
1
Probability is norm squared amplitude,
e.g. above is found in state |0> with
probability 1/2
– Complex numbers needed for interference
A general 2 qubit system is in state

a 00 b 01 c 10 d 11
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
31
Can We Copy an Unknown State?

We might measure exactly by copying an
unknown state onto many other particles.
 Formally, assume there is U such that
U 0   

Is there a consistent definition for U? In
other words, what is the value of
U a 0 b 1  0


National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
32
Proof of the No-Cloning Theorem
U a 0  b 1  0 U a 0 0  b 1 0

Ua 0 0  Ub1 0
 a 0 a 0 b 1 b 1
 a 00 b 11
2
2
U a 0  b 1  0  a 0  b 1 a 0  b 1 
 a 0 a 0  a 0 b 1  b 1 a 0 b 1 b 1
 a 00  ab 01  ab 10  b 11
2
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
2
Paul Black
33
Quantum Gates
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
34
Basic Gate: Controlled-Not (CNOT)


If control qubit ψ is 1, data qubit φ is flipped.
| 
| 
| 
| 
Here is CNOT in ket notation



CNOT 0 0  
0 0
CNOT 0 1  01
CNOT 1 0  11
CNOT 1 1  1 0
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
35
CNOT if input is in superposition


If control qubit ψ is 1, data qubit φ is flipped.
| 
| 
| 
| 
What happens if input is a superposition?


CNOT

1
2
0 
1
2
 CNOT


1
2

1
2

1  0


1
2
0 0 

1
2
1 0

CNOT 0 0  CNOT 1 0 
0 0  1 1 




The output is entangled!
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
36
CCNOT: A More Useful Gate

Controlled-Controlled Not or Toffolli
 If both control qubits ψ1 and ψ2 are 1, the
data qubit φ is flipped.

1
1
2
2



This
is the quantum computing
version of

AND gate


National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
37
Basic Gate: Hadamard

Rotate 90° or “square root of not”


H
1
1
0 1

2
1

H |1 
0  1  

2
1
1

H H 1   H
0  1 
H 0 H1 


0
2
2


1  1
1

0  1 
  0  1 


2  2
2
1
1
  0  1  0  1   2 0   0
2
2
H |0
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
38
Dirac or “ket” Notation

Equivalent to a
vector on the
surface of a
3-dimensional
Bloch sphere
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
39
BB84: Detectable
Eavesdropping
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
40
Basic BB84
•Alice and Bob wish to generate a shared secure private key
•Alice chooses random bases and polarizations to send photons
Alice’s Basis:
Alice Sends:
•Bob then chooses random bases to measure the photons
Bob’s Basis:
Bob Receives:
•If Bases differ, Bob measures randomly polarized photon
•If Bases match, Bob measures same polarization as Alice sent
•Photons are discarded when Alice and Bob choose a different basis.
Key Value:
0
1
1
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
41
BB84 With Eavesdropping
•An eavesdropper (Eve) measures the photons sent by Alice in her
own random basis and then forwards them to Bob:
Alice’s Basis:
Alice Sends:
Eve’s Basis:
=
Eve Sends:
Bob’s Basis:
Bob Receives:
Key Value:
-
0
-
1
Error!
•Eve’s measurement creates a 25% error rate in the key generation
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
42
The Quantum Processor Checklist

Well-defined quantum states for qubits
 State preparation or initialization
 Scalable
– Pure states
– High-fidelity operations “on demand”

Entangling operations and quantum gates
– Controlled-Not Gate
– Phase Gate

Efficient readout
 Little “noise” (decoherence) per operation
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
43
More information

Paul E. Black, D. Richard Kuhn, and Carl J.
Williams, “Quantum Computing and
Communication”, Advances in Computers,
Marvin Zelkowitz, ed., vol 56, pp 189-244.
http://hissa.nist.gov/~black/Papers/quantumCom.html

QCSim quantum simulator available at
http://hissa.nist.gov/~black/Source/qcsim.tar.gz
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
44
More resources

Complexity – Big O notation
http://en.wikipedia.org/wiki/Big_O_notation

Summary of quantum algorithms
http://www.its.caltech.edu/~sjordan/zoo.html
– Known quantum algorithms offering speedup
over the best known classical algorithms. It
has links to pedagogical (noncomprehensive)
surveys of quantum algorithms and an
overview at a semipopular level.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
45
Density Matrix
10 April
2016
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
46
What is a Density Matrix?


Sum of probability of pure states
2
a
rSi pi |ii|
a
b
*
*
*
*
|abba| a b g d 
g
d
-
Diagonals are probabilities
 Off-diagonals are correlations
 Operations are “two-sided”:
-
-
b2
-
-
-
g2
-
-
-
d2
r’ |i’i’| U|iU|i†  U|ii|U† UrU†
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
47
Density Matrix

Equivalent to a Vector within the Body of a
3-dimensional Bloch Sphere
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
48
QCSIM
10 April
2016
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
49
Simulation Taxonomy

Detail
– Classical
– Dirac ket (pure states)
– Density matrix (mixed states)
Time
– Discrete
– Continuous

Mixed
State
Detail

State
– Discrete (n-level)
– Continuous (finite)
– Infinite
QCSim
Pure
State
Classical
Discrete
Continuous
Time
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
50
Simulation Taxonomy (cont.)

Values
– Concrete (e.g., .4i 10 )
– Symbolic (e.g., a 00  b 01  d 11 )

Simulation

– Randomized (Monte Carlo or quantum
trajectories)
– Branching (one run; explore all choices)
– Complete state (one run)
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
51
How Should We Represent States?

Direct Simulator
– Concrete input state; noise operator
Xe
.707|00.707|10

.62 -
-
-
-
.2
-
-
-
-
-
-
.15 - .03
Must compute error model operators
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
52
QCSim




4481 lines of C++, plus 205k of tests & demos
State is density matrix
Simulates up to 13 qubits
Operations
–
–
–
–
–
–
–
–
Hadamard, X (bit flip), CNOT, Toffoli (CCNOT)
Controlled Z (Phase), H
Measure (collapse to classical binary)
Trace Over (remove from state)
Initialize and print density matrix
Probabilistic XYZ
Generalized Amplitude Damping
BSW Depolarizing CPhase
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
53
Input: subset of QHDL


Reference qubits by name
Initialize state
– ket notation
– normalized


Gates and commands
Example
variable qubit0, anc: qubit;
= .25|00> + .75i|11>;
cnot(qubit0, anc);
hadamard(anc);
print_state();
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
54
Computation is via Superoperators

Typically written as two-sided operations
a
U
g

QCSim uses the equivalent superoperator


b  †
U
d 
a 
 
b 
US  
g
 
d 
Zeroes and identities are optimized out
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
55
CNOT


Standard
1 0 0 0
a2
-
-
-
1 0 0 0
0 1 0 0
-
b2
-
-
0 1 0 0
0 0 0 1
-
-
g2
-
0 0 0 1
0 0 1 0
-
-
-
d2
0 0 1 0
QCSim code
// swap appropriate rows
for (int row = 0; row < mat->size(); row++) {
if ((mask & row) == mask) {
int otherrow = row ^ target;
for (int col = 0; col < mat->size(); col++) {
temp = mat->get_state(row, col);
mat->set_state(row, col, mat->get_state(otherrow, col));
mat->set_state(otherrow, col, temp);
}
}
}
// swap appropriate columns
. . .
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
56
QCSim Results (BB84 NoEve)
current state:
0.5
0
0
0
EqBases, Error
0
0
0
0
0
0.5
0
0
0
0
0
0
•Alice and Bob select different bases 50% of the time.
•The other half of the time, Alice and Bob select the same basis. An error never
occurs because Bob’s info qubit is always copied directly from Alice.
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
57
QCSim Results for BB84
•We simulate the circuit and display the “Equal Bases” qubit
and the “Error” qubit.
BasesEq=0,
Error=0
current state:
0.5
0
0
0
BasesEq, Error
0
0
0
0
0
0
0
0.375
0
0
0
0.125
BasesEq=1,
Error=0
BasesEq=1,
Error=1
•Alice and Bob choose a different basis 50% of the time, so it is
ignored
•When they choose the same basis, Eve’s measurement creates
an error on 1 of every 4 photons (.125/.5 = ¼)
•QCSim validates the 25% error rate
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
58
Teleportation
National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
59
Two More “Gates”

Measure – convert to a classical bit


b
Pauli Z or phase change
gate




Z
Z a 0  b 1   a 0  b 1



National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
60
Copy a state to another particle

0

Input
H
H
0
Z
is a state and zeros

National Institute of Standards and Technology
Technology Administration, U.S. Department of Commerce
Paul Black
61