How To Program Your Quantum Computer
Table of Contents
- 1. Intro
- 2. Background
- 3. Single Qubit Circuits
- 4. Multi-Qubit Circuits
- 5. Algorithms & Things
- 5.1. The Deutsch Algorithm
- 5.1.1. The Deutsch Algorithm centered th_borders
- 5.1.2. The Deutsch Algorithm centered centered_tds
- 5.1.3. The Deutsch Algorithm, before applying \(f\) centered
- 5.1.4. The Deutsch Algorithm, after applying \(f\) centered
- 5.1.5. The Deutsch Algorithm, after applying \(H_0\) centered
- 5.1.6. The Deutsch Algorithm centered
- 5.2. The CHSH Game
- 5.3. Factoring
- 5.4. Quantum Key Distribution
- 5.5. Quantum Teleportation
- 5.1. The Deutsch Algorithm
- 6. Outro
- 7. Appendix
- 8. Export Metastuff
1 Intro
1.1 Quantum Computing text_centered
Gary Fredericks
November 5, 2014
North Shore Fringe Coders
1.2 What even is a quantum computer?
1.3 Focus…
1.4 The Sweet Spot
- In Science Journalism
- Run your program on all inputs at once!
- Exponential speedup!
- Qubits can be zero and one at the same time!
- In Academia
- 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.
1.5 Roadmap
- 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
2.1.1 NOT
[: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 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 centered_table centered_tds th_borders
[: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
[: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
[: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}]
2.1.6 Two-Bit-Adder
[: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
2.2.1 Single-Wire Circuits
[: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
[: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
[: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 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 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
2.3.1 Complex Numbers: Polar vs Rectangular
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 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
3.1 NOT gate & observations
[: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.
3.2 Hadamard Gate
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0]]}
{:scale 2}]
3.3 Hadamard gate definition
[:transition
2
[:H 0]]
[:transition
3
[:H 0]]
3.4 \(H^2\)
[: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
[: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\)
[: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
[: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
4.1 Independent Qubits
[:circuit
{:wires 2 :gates [[:H 1] [:X 0] [:S 1]]}
{:scale 2}]
4.2 Entangled Qubits
4.2.1 Entangled Qubits
[: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
4.3.1 Partial Observations 1
[: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
[: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
- The Deutsch Algorithm
- The CHSH Game
- Factoring
- Quantum Key Distribution
- Quantum Teleportation
5.1 The Deutsch Algorithm
5.1.1 The Deutsch Algorithm centered 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 centered 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\) 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\) 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\) 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 centered
- Classical algorithm calls \(f\) twice
- Deutsch algorithm calls \(f\) once
- But scalable!
5.2 The CHSH Game
5.2.1 The CHSH Game centered 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 centered 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
5.3.1 Factoring
- 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 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
[: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.3.4 Quantum Fourier Transform
5.4 Quantum Key Distribution
5.4.1 Value vs Sign 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 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 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
5.5.1 Quantum Teleportation (cheating)
[: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)
[: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.1 PHEW
6.2 Things I Didn't Talk About
- Mixed States
- Bloch Sphere
- Grover's Quantum Search Algorithm
- Quantum Error Correction
- …
6.3 And so
- 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
6.4 Questions?
Resources
- The circuit simulator used in these slides: http://gfredericks.com/things/qc
- A Clojure library that simulates qubits as individual objects: http://github.com/gfredericks/qubits
7 Appendix
7.1 Phase Distinguishability 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.2 Independent Qubits Separability centered
7.3 Entanglement as Observation (Decoherence)
7.3.1 Double Hadamard (review)
[: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
[: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.