# How To Program Your Quantum Computer

## 1 Intro

### 1.1 Quantum Computing   slide text_centered

Gary Fredericks

November 5, 2014

North Shore Fringe Coders

### 1.4 The Sweet Spot   slide text_slide

• In Science Journalism
• Run your program on all inputs at once!
• Exponential speedup!
• Qubits can be zero and one at the same time!
• High (but finite) dimensional complex Hilbert spaces
• Tensor products, hermitian/unitary matrices, projections

#### 1.4.1 Notes   notes

To learn about QC, 2 primary paths: journalism, where claims are easy to read but at best meaningless and at worse misleading or outright false, and academia where you can see the weirdness in vivid color but you have to hack through piles of linear algebra to do it. Today we will try to figure out if we can have the best of both worlds.

• Background
• Classical Circuits
• Probabilistic Circuits
• Complex Numbers
• Single-Qubit Circuits (superposition, observation)
• Multi-Qubit Circuits (entanglement, simple algorithms)
• Algorithms & Things
• Deutsch Algorithm
• CHSH Game
• Factoring
• Quantum Key Distribution
• Quantum Teleportation

## 2 Background

### 2.1 Classical Circuits   slide

#### 2.1.1 NOT   slide

[:classical-circuit {:gates [[:X 0]], :wires 1} {:input-labels ["0"] :output-labels ["1"] :scale 5}]

[:classical-circuit {:gates [[:X 0]], :wires 1} {:input-labels ["1"] :output-labels ["0"] :scale 5}]

#### 2.1.2 Controlled NOT   slide centered_table th_borders

[:classical-circuit {:gates [[:X 1 0]], :wires 2} {:input-labels ["a" "b"] :output-labels ["a" "b'"] :scale 3}]
a b b'
0 0 0
0 1 1
1 0 1
1 1 0

#### 2.1.3 Non-reversible AND   slide centered_table centered_tds th_borders slide_238

[:classical-circuit-1 {:gates [["AND" 1 0]], :wires 2} {:input-labels ["a" "b"] :output-labels ["a" "a AND b"] :scale 3}]
a b a AND b
0 0 0
0 1 0
1 0 0
1 1 1

#### 2.1.4 Reversible AND   slide

[:classical-circuit {:gates [[:X 2 0 1]], :wires 3} {:input-labels ["a" "b" "0"] :output-labels ["a" "b" "a AND b"] :scale 4}]

#### 2.1.5 OR   slide

[:classical-circuit {:gates [[:parallel [:X 0] [:X 1] [:X 2]] [:X 2 0 1] [:parallel [:X 0] [:X 1]]], :wires 3} {:input-labels ["a" "b" "0"] :output-labels ["a" "b" "a OR b"] :scale 4}]

[:classical-circuit {:gates [[:X 4 2] [:X 4 0] [:X 5 0 2] [:X 5 1] [:X 5 3] [:X 6 1 3 5] [:X 5] [:X 6 3 5] [:X 3] [:X 6 1 3 5] [:X 3] [:X 5]], :wires 7} {:input-labels ["a1" "a2" "b1" "b2" "0" "0" "0"] :output-labels ["a1" "a2" "b1" "b2" "c1" "c2" "c3"] :scale 2}]

### 2.2 Probabilistic Circuits   slide

#### 2.2.1 Single-Wire Circuits   slide

[:prob-circuit {:gates [[0.75 0] [0.4 0]], :wires 1} {:input-labels ["0"] :output-labels ["?"]}]
##### 2.2.1.1 Notes   notes

What's the probability that the bit is heads at the end of the circuit?

#### 2.2.2 Single-Wire Circuit Calculations   slide

[:prob-circuit {:gates [[0.75 0] [0.4 0]], :wires 1} {:input-labels ["0"] :output-labels ["?"]}]
[:prob-circuit-trans {:gates [[0.75 0] [0.4 0]], :wires 1}]

#### 2.2.3 Multi-Wire Circuits   slide

[:prob-circuit {:gates [[0.5 0] [0.75 1 0] [0.25 1]], :wires 2} {:input-labels ["0" "0"] :output-labels ["?" "?"]}]

#### 2.2.4 Multi-Wire Circuits Calculations 1   slide centered_table

[:prob-circuit {:gates [[0.5 0] [0.75 1 0] [0.25 1]], :wires 2} {:input-labels ["0" "0"] :output-labels ["?" "?"]}]
[:prob-circuit-trans {:gates [[0.5 0] [0.75 1 0]], :wires 2}]

#### 2.2.5 Multi-Wire Circuits Calculations 2   slide centered_table

[:prob-circuit {:gates [[0.5 0] [0.75 1 0] [0.25 1]], :wires 2} {:input-labels ["0" "0"] :output-labels ["?" "?"]}]
[:prob-circuit-trans {:gates [[0.5 0] [0.75 1 0] [0.25 1]], :wires 2}]

### 2.3 Complex Numbers   slide

#### 2.3.1 Complex Numbers: Polar vs Rectangular   slide

##### 2.3.1.1 Notes   notes

The magnitude is the "size" of the number, and the phase is just a generalization of "sign" from real numbers

#### 2.3.2 Complex Numbers: Visual Representation   slide centered_tds th_borders centered

value representation
$$1$$
[:complex 1 0 {:dim 100}]
$$0$$
[:complex 0 0 {:dim 100}]
$$-\frac{1}{2}$$
[:complex -0.5 0 {:dim 100}]
$$i$$
[:complex 0 1 {:dim 100}]
$$\frac{1}{2} - \frac{1}{2}i$$
[:complex 0.5 -0.5 {:dim 100}]

## 3 Single Qubit Circuits   slide

### 3.1 NOT gate & observations   slide

[:circuit {:wires 1 :gates [[:X 0] [:observe 0] [:X 0] [:observe 0]]} {:scale 2}]

#### 3.1.1 Notes   notes

Here we're just showing how the circles and animated circuit work.

[:circuit {:wires 1 :gates [[:H 0] [:observe 0]]} {:scale 2}]

### 3.3 Hadamard gate definition   slide

[:transition 2 [:H 0]]
[:transition 3 [:H 0]]

### 3.4 $$H^2$$   slide

[:circuit {:wires 1 :gates [[:H 0] [:H 0]]} {:scale 2}]

#### 3.4.1 Notes   notes

Probabilistic computation is like making observations after each gate. Or something.

### 3.5 Analyzing the second H-gate   slide

[:transition 2 [:H 0] [:H 0]]

#### 3.5.1 Notes   notes

Note how the amplitudes add (0.5+0.5=1) but the probabilities don't (0.25 + 0.25 != 1). "If anybody here has intuition for why this can be the case and always work out consistently then I have a lot of respect for you.

### 3.6 $$H\cdot Ob \cdot H$$   slide

[:circuit {:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]} {:scale 2}]

#### 3.6.1 Notes   notes

Probabilistic computation is like making observations after each gate. Or something.

### 3.7 Phase Gates   slide

[:circuit {:wires 1 :gates [[:Z 0] [:S 0] [:T 0] [0.33 0]]} {:scale 2}]

#### 3.7.1 Notes   notes

Arbitrary phase gates are not necessarily efficiently implementable

## 4 Multi-Qubit Circuits   slide

### 4.1 Independent Qubits   slide

[:circuit {:wires 2 :gates [[:H 1] [:X 0] [:S 1]]} {:scale 2}]

### 4.2 Entangled Qubits

#### 4.2.1 Entangled Qubits   slide

[:circuit {:wires 2 :gates [[:H 0] [:X 1 0] [:noop] [:observe 0 1] [:noop] [:X 1 0] [:H 0]]}]
[:circuit {:wires 2 :gates [[:H 0] [:X 1 0] [:noop] [:noop] [:noop] [:X 1 0] [:H 0]]}]

### 4.3 Partial Observations   slide

#### 4.3.1 Partial Observations 1   slide

[:circuit {:wires 2 :gates [[:parallel [:H 0] [:H 1]] [:observe 0]]} {:scale 2}]
##### 4.3.1.1 Notes   notes

This demonstrates that the wavefunction doesn't have to collapse completely.

#### 4.3.2 Partial Observations 2   slide

[:circuit {:wires 4 :gates [[:parallel [:H 0] [:H 1] [:H 2]] [:X 3 0] [:X 0] [:X 3 2 1 0] [:X 0] [:observe 3]]}]
##### 4.3.2.1 Notes   notes

This demonstrates that the wavefunction doesn't have to collapse completely.

## 5 Algorithms & Things   text_slide slide

• The Deutsch Algorithm
• The CHSH Game
• Factoring
• Quantum Key Distribution
• Quantum Teleportation

### 5.1 The Deutsch Algorithm   slide

#### 5.1.1 The Deutsch Algorithm   slide centered slide_512 th_borders

We have a 1-bit function $$f$$ and we want to know if $$f(0) = f(1)$$

name $$f(0)$$ $$f(1)$$ property
zero 0 0 constant
one 1 1 constant
identity 0 1 balanced
not 1 0 balanced
[:circuit-drawing {:wires 2 :gates [[:f 1 0]]} {:input-labels ["x" "0"] :output-labels ["x" "f(x)"] :scale 3 :gate-names true}]

#### 5.1.2 The Deutsch Algorithm   slide centered slide_672 centered_tds

 Zero [:static-circuit {:gates [[:X 1] [:H 1] [:H 0] [:noop] [:noop] [:noop] [:noop] [:H 0] [:observe 0]], :wires 2} {:complex-size 100}] One [:static-circuit {:gates [[:X 1] [:H 1] [:H 0] [:noop] [:X 1] [:noop] [:noop] [:H 0] [:observe 0]], :wires 2} {:complex-size 100}] Identity [:static-circuit {:gates [[:X 1] [:H 1] [:H 0] [:noop] [:X 1 0] [:noop] [:noop] [:H 0] [:observe 0]], :wires 2} {:complex-size 100}] Not [:static-circuit {:gates [[:X 1] [:H 1] [:H 0] [:noop] [:X 1 0] [:X 1] [:noop] [:H 0] [:observe 0]], :wires 2} {:complex-size 100}]

#### 5.1.3 The Deutsch Algorithm, before applying $$f$$   slide centered

$$x=0$$

[:complex 0.5 0 {:label "00", :dim 175}]
[:complex -0.5 0 {:label "01", :dim 175}]

$$x=1$$

[:complex 0.5 0 {:label "10", :dim 175}]
[:complex -0.5 0 {:label "11", :dim 175}]

#### 5.1.4 The Deutsch Algorithm, after applying $$f$$   slide centered

$$x=0$$, phases flipped when $$f(0)=1$$

[:complex 0.5 0 {:label "00", :dim 175}]
[:complex -0.5 0 {:label "01", :dim 175}]

$$x=1$$, phases flipped when $$f(1)=1$$

[:complex 0.5 0 {:label "10", :dim 175}]
[:complex -0.5 0 {:label "11", :dim 175}]

#### 5.1.5 The Deutsch Algorithm, after applying $$H_0$$   slide centered

$$x=0$$, phases flipped when $$f(0)=1$$

[:complex 0.3536 0 {:label "00", :dim 175}]
[:complex -0.3536 0 {:label "01", :dim 175}]
[:complex 0.3536 0 {:label "10", :dim 175}]
[:complex -0.3536 0 {:label "11", :dim 175}]

$$x=1$$, phases flipped when $$f(1)=1$$

[:complex 0.3536 0 {:label "00", :dim 175}]
[:complex -0.3536 0 {:label "01", :dim 175}]
[:complex -0.3536 0 {:label "10", :dim 175}]
[:complex 0.3536 0 {:label "11", :dim 175}]

#### 5.1.6 The Deutsch Algorithm   slide centered

• Classical algorithm calls $$f$$ twice
• Deutsch algorithm calls $$f$$ once
• But scalable!

### 5.2 The CHSH Game   slide

#### 5.2.1 The CHSH Game   slide centered slide_512 th_borders

Alice and Bob are separated; they each receive a single bit, and must respond with a single bit, without communicating.

• Alice receives $$x$$ and responds with $$a$$
• Bob receives $$y$$ and responds with $$b$$
• They win if $$x \land y = a \oplus b$$

#### 5.2.2 The CHSH Game   slide centered slide_673 centered_tds

 $$x=0,\hspace{10pt} y=0,\hspace{10pt} x \land y=0$$ [:static-circuit {:gates [[:H 0] [:X 1 0] [:noop] [:parallel [:S 0] [:S 1]] [:parallel [:H 0] [:H 1]] [:noop] [0.25 1] [:noop] [:parallel [:H 0] [:H 1]] [:parallel [:S 0] [:S 1]]], :wires 2} {:complex-size 100}] $$x=0,\hspace{10pt} y=1,\hspace{10pt} x \land y=0$$ [:static-circuit {:gates [[:H 0] [:X 1 0] [:noop] [:parallel [:S 0] [:S 1]] [:parallel [:H 0] [:H 1]] [:noop] [-0.25 1] [:noop] [:parallel [:H 0] [:H 1]] [:parallel [:S 0] [:S 1]]], :wires 2} {:complex-size 100}] $$x=1,\hspace{10pt} y=0,\hspace{10pt} x \land y=0$$ [:static-circuit {:gates [[:H 0] [:X 1 0] [:noop] [:parallel [:S 0] [:S 1]] [:parallel [:H 0] [:H 1]] [:noop] [:parallel [0.25 1] [:S 0]] [:noop] [:parallel [:H 0] [:H 1]] [:parallel [:S 0] [:S 1]]], :wires 2} {:complex-size 100}] $$x=1,\hspace{10pt} y=1,\hspace{10pt} x \land y=1$$ [:static-circuit {:gates [[:H 0] [:X 1 0] [:noop] [:parallel [:S 0] [:S 1]] [:parallel [:H 0] [:H 1]] [:noop] [:parallel [-0.25 1] [:S 0]] [:noop] [:parallel [:H 0] [:H 1]] [:parallel [:S 0] [:S 1]]], :wires 2} {:complex-size 100}]

### 5.3 Factoring   slide

#### 5.3.1 Factoring   slide text_slide

• Factoring a number ($$12 \mapsto [2,2,3]$$)
• Finding a divisor ($$12 \mapsto 6$$)
• Order-Finding (for some $$a < N$$, find the smallest $$x$$ such that $$a^x \equiv 1 \mod N$$)

#### 5.3.2 Order Finding   slide small_text_slide centered_tds th_borders

To factor $$N = 15$$, we choose a random $$a = 13$$

$$x$$ $$13^x \mod 15$$ $$\hspace{10pt}$$ $$x$$ $$13^x \mod 15$$ $$\hspace{10pt}$$ $$x$$ $$13^x \mod 15$$
1 13   11 7   21 13
2 4   12 1   22 4
3 7   13 13   23 7
4 1   14 4   24 1
5 13   15 7   25 13
6 4   16 1   26 4
7 7   17 13   27 7
8 1   18 4   28 1
9 13   19 7   29 13
10 4   20 1   30 4

#### 5.3.3 Order Finding Circuit   slide slide_724

[:circuit-drawing {:wires 12 :gates [[:parallel [:H 0] [:H 1] [:H 2] [:H 3] [:H 4] [:H 5] [:H 6] [:H 7]] [:noop] [:noop] [:noop] [:noop] [:noop] [:noop] [:noop] [:noop] [:observe 8 9 10 11]]} {:input-labels ["x1" "x2" "x3" "x4" "x5" "x6" "x7" "x8"]}]

### 5.4 Quantum Key Distribution   slide

#### 5.4.1 Value vs Sign   slide centered centered_tds th_borders centered vmiddle_tds

State Name
[:state 1 [ ] {:dim 100}]
0
[:state 1 [ [:X 0] ] {:dim 100}]
1
[:state 1 [ [:H 0] ] {:dim 100}]
+
[:state 1 [ [:X 0] [:H 0] ] {:dim 100}]
-
##### 5.4.1.1 Notes   notes

At most 0/1 or +/- can have a determined value at any time.

Compare to particle's position/momentum and HUP

#### 5.4.2 Protocol (Initial)   centered_tds slide centered th_borders

Alice's Bit Value Alice's Encoding Qubit State Bob Measurement Bob Measures Bob's Bit Value
0 value 0 value 0 0
0 sign + sign + 0
0 sign + sign + 0
1 value 1 sign + 0
1 sign - value 0 0
1 sign - value 0 0
1 sign - value 0 0
0 value 0 sign + 0
1 sign - sign - 1
1 value 1 sign + 0
1 value 1 sign + 0
1 sign - sign - 1
0 sign + value 1 1
1 value 1 value 1 1
1 sign - sign - 1
0 value 0 value 0 0
1 sign - value 1 1
0 sign + value 1 1
0 value 0 value 0 0
0 value 0 value 0 0

#### 5.4.3 Protocol (removed wrongly measurements)   centered_tds slide centered th_borders

Alice's Bit Value Encoding Qubit State Bob's Bit Value
0 value 0 0
0 sign + 0
0 sign + 0
1 sign - 1
1 sign - 1
1 value 1 1
1 sign - 1
0 value 0 0
0 value 0 0
0 value 0 0

### 5.5 Quantum Teleportation   slide

#### 5.5.1 Quantum Teleportation (cheating)   slide

[:circuit {:gates [[:H 0] [:T 0] [:H 0] [:noop] [:X 1 0] [:H 0] [:observe 0] [:Z 1 0]], :wires 2} {:scale 2}]

#### 5.5.2 Quantum Teleportation (legit)   slide

[:circuit {:gates [[:H 0] [:T 0] [:H 0] [:noop] [:H 1] [:X 2 1] [:noop] [:X 1 0] [:H 0] [:observe 0 1] [:X 2 1] [:Z 2 0]], :wires 3} {:scale 1.4}]

#### 5.5.3 Notes   notes

Mention the no-cloning theorem probably. Also entanglement-swapping (from wiki) is a fascinating corollary Why you can't

## 6 Outro

### 6.2 Things I Didn't Talk About   slide text_slide

• Mixed States
• Bloch Sphere
• Grover's Quantum Search Algorithm
• Quantum Error Correction

### 6.3 And so   slide text_slide

• Quantum computers have the potential to do things faster than classical computers
• …but exploiting quantum parallelism is quite tricky
• I think this stuff is fun

Resources

## 7 Appendix   slide

### 7.1 Phase Distinguishability   slide centered

State
[:circuit-drawing {:wires 1 :gates [[:H 0] [:observe 0]]}]
[:circuit-drawing {:wires 1 :gates [[:S 0] [:H 0] [:observe 0]]}]
[:state 1 [ [:H 0] ] {:dim 100}]
Always 0 50/50
[:state 1 [ [:H 0] [:Z 0] ] {:dim 100}]
Always 1 50/50
[:state 1 [ [:H 0] [:S 0] ] {:dim 100}]
50/50 Always 1
[:state 1 [ [:H 0] [:S 0] [:Z 0] ] {:dim 100}]
50/50 Always 0

### 7.3 Entanglement as Observation (Decoherence)   slide

#### 7.3.1 Double Hadamard (review)   slide

[:circuit {:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]}]
[:circuit {:wires 1 :gates [[:H 0] [:noop] [:H 0]]}]

#### 7.3.2 Double Hadamard observed by qubit   slide

[:circuit {:gates [[:H 0] [:X 1 0][:H 0]], :wires 2} {:scale 2}]
##### 7.3.2.1 Notes   notes

Quantum Decoherence! This is why building quantum computers is hard.

## 8 Export Metastuff

Created: 2014-11-15 Sat 19:49

Emacs 24.3.1 (Org mode 8.2.7c)

Validate