How To Program Your Quantum Computer
Table of Contents
- 1 How To Program Your Quantum Computer
- 2 Quantum Computing
- 3 Roadmap
- 4 Slides
- 5 Background
- 6 Single Qubit Circuits
- 7 Multi-Qubit Circuits
- 8 Factoring
- 9 Quantum Key Distribution
- 10 Moar Things!
- 11 tl;dl
- 12 Questions?
- 13 Export Metastuff
1 How To Program Your Quantum Computer text_centered
Gary Fredericks
2 Quantum Computing
-
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
-
2.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.
3 Roadmap
-
Background
- Classical Circuits
- Probabilistic Circuits
- Complex Numbers
- Single-Qubit Circuits (superposition, observation)
- Multi-Qubit Circuits (entanglement, decoherence, teleportation)
- Factoring
- Quantum Key Distribution?
4 Slides text_centered
Posted at http://gfredericks.com/qc
5 Background
5.1 Classical Circuits
5.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}]
5.1.2 Controlled NOT centered_table th_borders
[:classical-circuit
{:gates [[:X 1 0]], :wires 2}
{:input-labels ["x" "y"]
:output-labels ["x" "y'"]
:scale 3}]
| x | y | y' |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
5.1.3 Non-reversible AND centered_table centered_tds th_borders
[:classical-circuit-1
{:gates [["AND" 1 0]], :wires 2}
{:input-labels ["x" "y"]
:output-labels ["x" "x AND y"]
:scale 3}]
| x | y | x AND y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
5.1.4 AND
[:classical-circuit
{:gates [[:X 2 0 1]], :wires 3}
{:input-labels ["x" "y" "0"]
:output-labels ["x" "y" "x AND y"]
:scale 4}]
5.1.5 OR
[:classical-circuit
{:gates [[:parallel [:X 0] [:X 1]]
[:X 2 0 1]
[:parallel [:X 0] [:X 1]]], :wires 3}
{:input-labels ["x" "y" "0"]
:output-labels ["x" "y" "x OR y"]
:scale 4}]
5.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 ["x1" "x2" "y1" "y2" "0" "0" "0"]
:output-labels ["x1" "x2" "y1" "y2" "z1" "z2" "z3"]
:scale 2}]
5.2 Probabilistic Circuits
5.2.1 Single-Wire Circuits
[:prob-circuit
{:gates [[0.75 0] [0.5 0]], :wires 1}
{:input-labels ["0"]
:output-labels ["?"]}]
5.2.1.1 Notes notes
What's the probability that the bit is heads at the end of the circuit?
5.2.2 Single-Wire Circuit Calculations
[:prob-circuit
{:gates [[0.75 0] [0.5 0]], :wires 1}
{:input-labels ["0"]
:output-labels ["?"]}]
[:prob-circuit-trans
{:gates [[0.75 0] [0.5 0]], :wires 1}]
5.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 ["?" "?"]}]
5.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}]
5.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}]
5.3 Complex Numbers
5.3.1 Complex Numbers: Polar vs Rectangular
5.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
5.3.2 Complex Numbers: Visual Representation centered_tds th_borders centered
| value | representation |
|---|---|
| 1 | [:complex 1 0 {:dim 100}]</div> |
| 0 | [:complex 0 0 {:dim 100}]</div> |
| -½ | [:complex -0.5 0 {:dim 100}]</div> |
| i | [:complex 0 1 {:dim 100}]</div> |
| ½ - ½i | [:complex 0.5 -0.5 {:dim 100}]</div> |
6 Single Qubit Circuits
6.1 NOT gate
[:circuit
{:wires 1 :gates [[:X 0] [:X 0]]}
{:scale 2}]
6.1.1 Notes notes
Here we're just showing how the circles and animated circuit work.
6.2 Hadamard gate (superposition & observations)
6.2.1 Hadamard gate definition
[:transition
2
[:H 0]]
[:transition
3
[:H 0]]
6.2.2 Example HH
[:circuit
{:wires 1 :gates [[:H 0] [:H 0]]}
{:scale 2}]
6.2.3 The effect of the second H-gate
[:transition
2
[:H 0]
[:H 0]]
6.2.3.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.
6.2.4 Example H<ob>H
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]}
{:scale 2}]
6.2.4.1 Notes notes
Probabilistic computation is like making observations after each gate. Or something.
6.3 Phases!
6.4 Phase Gates
[:circuit
{:wires 1 :gates [[:Z 0] [:S 0] [:T 0]]}
{:scale 2}]
6.4.1 Notes notes
Arbitrary phase gates are not necessarily efficiently implementable
6.5 Phase Distinguishability centered
| State | [:circuit-drawing {:wires 1 :gates [[:H 0] [:observe 0]]}]</div> | [:circuit-drawing {:wires 1 :gates [[:S 0] [:H 0] [:observe 0]]}]</div> |
|---|---|---|
[:state 1 [ [:H 0] ] {:dim 100}]</div> | Always 0 | 50/50 |
[:state 1 [ [:H 0] [:Z 0] ] {:dim 100}]</div> | Always 1 | 50/50 |
[:state 1 [ [:H 0] [:S 0] ] {:dim 100}]</div> | 50/50 | Always 1 |
[:state 1 [ [:H 0] [:S 0] [:Z 0] ] {:dim 100}]</div> | 50/50 | Always 0 |
7 Multi-Qubit Circuits
7.1 Independent Qubits
[:circuit
{:wires 2 :gates [[:H 1] [:X 0] [:S 1]]}
{:scale 2}]
7.2 Independent Qubits Separability centered
7.3 Entangled Qubits
7.3.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]]}]
7.4 Phases Are Weird
[:circuit
{:wires 2 :gates [[:X 1]
[:parallel [:H 0] [:H 1]]
[:X 1 0]
[:parallel [:H 0] [:H 1]]]}
{:scale 2}]
7.5 Partial Observations
7.5.1 Partial Observations 1
[:circuit
{:wires 2 :gates [[:parallel [:H 0] [:H 1]] [:observe 0]]}
{:scale 2}]
7.5.1.1 Notes notes
This demonstrates that the wavefunction doesn't have to collapse completely.
7.5.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]]}]
7.5.2.1 Notes notes
This demonstrates that the wavefunction doesn't have to collapse completely.
7.6 Entanglement as Observation (Decoherence)
7.6.1 Double Hadamard (review)
[:circuit
{:wires 1 :gates [[:H 0] [:observe 0] [:H 0]]}]
[:circuit
{:wires 1 :gates [[:H 0] [:noop] [:H 0]]}]
7.6.2 Double Hadamard observed by qubit
[:circuit
{:gates [[:H 0] [:X 1 0][:H 0]], :wires 2}
{:scale 2}]
7.6.2.1 Notes notes
Quantum Decoherence! This is why building quantum computers is hard.
7.7 The Deutsch Algorithm
7.7.1 The Deutsch Algorithm centered th_borders
| 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}]
7.7.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}]
|
7.8 Quantum Teleportation
7.8.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}]
7.8.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}]
7.8.3 Notes notes
Mention the no-cloning theorem probably. Also entanglement-swapping (from wiki) is a fascinating corollary Why you can't
8 Factoring
8.1 Factoring
-
Factoring a number (
12 -> [2,2,3]) -
Finding a factor (
12 -> 3) - Order-Finding (for some a < N, find the smallest x such that ax mod N = 1)
8.2 Order Finding centered_tds th_borders
To factor N = 15, we choose a random a = 13
| x | 13x mod 15 |
|---|---|
| 1 | 13 |
| 2 | 4 |
| 3 | 7 |
| 4 | 1 |
| 5 | 13 |
| 6 | 4 |
| 7 | 7 |
| 8 | 1 |
| 9 | 13 |
| 10 | 4 |
8.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"]}]
8.4 Quantum Fourier Transform
9 Quantum Key Distribution
9.1 Value vs Sign centered_tds th_borders centered
| State | Name |
|---|---|
[:state 1 [ ] {:dim 100}]</div> | 0 |
[:state 1 [ [:X 0] ] {:dim 100}]</div> | 1 |
[:state 1 [ [:H 0] ] {:dim 100}]</div> | + |
[:state 1 [ [:X 0] [:H 0] ] {:dim 100}]</div> | - |
9.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
9.2 Protocol (Initial) 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 |
9.3 Protocol (removed wrongly measurements) 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 |
10 Moar Things!
- Mixed States
- Bloch Sphere
- Grover's Quantum Search Algorithm
- Quantum Error Correction
11 tl;dl
-
Quantum Computing is
- very very weird
- not obviously useful
- full of potential, but difficult to speculate about
-
Qubits are
- very very weird
- teleportable
- probably useful in crypto
12 Questions?
13 Export Metastuff
Date: 2012-09-18 11:19:24 CDT
HTML generated by org-mode 6.33x in emacs 23