How To Program Your Quantum Computer
Table of Contents
- 1. Intro
- 2. Background
- 3. Fundamentals
- 3.1. Qubits
- 3.2. NOT gate & observations
- 3.3. Possibilities & Amplitudes
- 3.4. Four Qubits
- 3.5. Measuring
- 3.6. Hadamard Gate
- 3.7. Hadamard gate definition
- 3.8. \(H^2\)
- 3.9. Analyzing the second H-gate
- 3.10. \(H\cdot Ob \cdot H\)
- 3.11. Partial Observations
- 3.12. Phase Gates
- 3.13. Phases Matter
- 3.14. Entanglement
- 3.15. Independent Qubits
- 3.16. Entangled Qubits
- 3.17. Entanglement & Modification
- 3.18. Fundamentals
- 4. Algorithms
- 5. Outro
- 6. Appendices
- 7. Export Metastuff
1 Intro
1.1 How To Program Your Quantum Computer text_centered
Gary Fredericks
November 18, 2014
Geekfest
1.2 Take 2 text_centered
September 18, 2012
1.3 Like, what even is a quantum computer?
1.4 Focus…
1.5 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.5.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.6 Roadmap
- Background
- Classical Circuits
- Probabilistic Circuits
- Complex Numbers
- Fundamentals
- Qubits
- Amplitudes & Possibilities
- Measurements
- Entanglement
- Algorithms & Things
- Deutsch Algorithm
- CHSH Game
2 Background
2.1 Background – 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 Background – 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 Background – 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 Fundamentals
3.1 Qubits
A qubit can be operated on like a classical bit, and can be queried to obtain its "value" which is always 0 or 1.
3.2 NOT gate & observations
[:circuit
{:wires 1 :gates [[:X 0] [:observe 0] [:X 0] [:observe 0]]}
{:scale 2}]
3.2.1 Notes notes
Here we're just showing how the circles and animated circuit work.
3.3 Possibilities & Amplitudes
A system has a complex amplitude for each set of possible values of all the qubits involved. The amplitude determines the probability of measuring that set of possible values.
3.4 Four Qubits
[:circuit
{:wires 4 :gates [[:X 2] [:X 3 2] [:parallel [:X 0] [:X 1]]]}
{:scale 2}]
3.5 Measuring
When we measure any of the qubits, the possibilities that are incompatible with the outcome vanish.
3.6 Hadamard Gate
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0]]}
{:scale 2}]
3.7 Hadamard gate definition
[:transition
2
[:H 0]]
[:transition
3
[:H 0]]
3.8 \(H^2\)
[:circuit
{:wires 1 :gates [[:H 0] [:H 0]]}
{:scale 2}]
3.8.1 Notes notes
Probabilistic computation is like making observations after each gate. Or something.
3.9 Analyzing the second H-gate
[:transition
2
[:H 0]
[:H 0]]
3.9.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.10 \(H\cdot Ob \cdot H\)
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]}
{:scale 2}]
3.10.1 Notes notes
Probabilistic computation is like making observations after each gate. Or something.
3.11 Partial Observations
[:circuit
{:wires 2 :gates [[:parallel [:H 0] [:H 1]] [:observe 0]]}
{:scale 2}]
3.11.1 Notes notes
This demonstrates that the wavefunction doesn't have to collapse completely.
3.12 Phase Gates
[:circuit
{:wires 1 :gates [[:Z 0] [:S 0] [:T 0] [0.33 0]]}
{:scale 2}]
3.12.1 Notes notes
Arbitrary phase gates are not necessarily efficiently implementable
3.13 Phases Matter
[:circuit
{:wires 1 :gates [[:H 0] [:noop] [:H 0]]}]
[:circuit
{:wires 1 :gates [[:H 0] [:S 0] [:H 0]]}]
3.14 Entanglement
When multiple qubits are operated on together, they can be "entangled" such that their values are correlated.
3.15 Independent Qubits
[:circuit
{:wires 2 :gates [[:H 1] [:X 0] [:S 1]]}
{:scale 2}]
3.16 Entangled Qubits
[:circuit
{:wires 2 :gates [[:H 0] [:X 1 0]
[:noop]
[:observe 0 1]]}]
3.17 Entanglement & Modification
[:circuit
{:wires 2 :gates [[:H 0] [:X 1 0]
[:noop] [:noop] [:noop]
[:X 1 0] [:H 0] [:observe 0]]}
{:scale 2}]
[:circuit
{:wires 2 :gates [[:H 0] [:X 1 0]
[:noop] [:Z 1] [:noop]
[:X 1 0] [:H 0] [:observe 0]]}
{:scale 2}]
3.18 Fundamentals
- A qubit can be operated on like a classical bit, and can be queried to obtain its "value" which is always 0 or 1.
- A system has a complex amplitude for each set of possible values of all the qubits involved. The amplitude determines the probability of measuring that set of possible values.
- When we measure any of the qubits, the possibilities that are incompatible with the outcome vanish.
- When multiple qubits are operated on together, they can be "entangled" such that their values are correlated.
4 Algorithms
- The Deutsch Algorithm
- The CHSH Game
4.1 The Deutsch Algorithm
4.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}]
4.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}]
|
4.1.3 The Deutsch Algorithm centered
- Classical algorithm calls \(f\) twice
- Deutsch algorithm calls \(f\) once
- But scalable!
4.2 The CHSH Game
4.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\)
4.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 Outro
5.1 PHEW
5.2 Okay so what can you actually do with qubits?
- certain things faster/better
- But only with extreme cleverness
- a few entirely new things
- key distribution w/ evesdropping detection
- teleportation
- something about randomness
5.3 Things I Didn't Talk About
Gee whiz.
- Quantum Key Distribution
- Factoring (!!)
- Quantum Teleportation
- Mixed States
- Bloch Sphere
- Grover's Quantum Search Algorithm
- Quantum Error Correction
- …
5.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
6 Appendices
6.1 Deutsch Explanation
6.1.1 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}]
6.1.2 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}]
6.1.3 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}]
6.2 Factoring
6.2.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\))
6.2.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 |
6.2.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"]}]
6.2.4 Quantum Fourier Transform
6.3 Quantum Teleportation
6.3.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}]
6.3.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}]
6.3.3 Notes notes
Mention the no-cloning theorem probably. Also entanglement-swapping (from wiki) is a fascinating corollary Why you can't
6.4 Quantum Key Distribution
6.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}] |
- |
6.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
6.4.2 Measuring the Sign
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0] [:H 0]
[:noop]
[:H 0] [:observe 0] [:H 0]
[:noop]
[:Z 0]
[:noop]
[:H 0] [:observe 0] [:H 0]]}
{}]
6.4.3 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 |
6.4.4 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 |
6.5 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 |
6.6 Independent Qubits Separability centered
6.7 Entanglement as Observation (Decoherence)
6.7.1 Double Hadamard (review)
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]}]
[:circuit
{:wires 1 :gates [[:H 0] [:noop] [:H 0]]}]
6.7.2 Double Hadamard observed by qubit
[:circuit
{:gates [[:H 0] [:X 1 0][:H 0]], :wires 2}
{:scale 2}]
6.7.2.1 Notes notes
Quantum Decoherence! This is why building quantum computers is hard.