How To Program Your Quantum Computer

Table of Contents

1 How To Program Your Quantum Computer    slide text_slide text_centered

Gary Fredericks

2 Quantum Computing    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!
  • 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    slide text_slide

  • Background
    • Classical Circuits
    • Probabilistic Circuits
    • Complex Numbers
  • Single-Qubit Circuits (superposition, observation)
  • Multi-Qubit Circuits (entanglement, decoherence, teleportation)
  • Factoring
  • Quantum Key Distribution?

4 Slides    slide text_slide text_centered

Posted at http://gfredericks.com/qc

5 Background

5.1 Classical Circuits    slide

5.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}]

5.1.2 Controlled NOT    slide centered_table th_borders

[:classical-circuit {:gates [[:X 1 0]], :wires 2} {:input-labels ["x" "y"] :output-labels ["x" "y'"] :scale 3}]
xyy'
000
011
101
110

5.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 ["x" "y"] :output-labels ["x" "x AND y"] :scale 3}]
xyx AND y
000
010
100
111

5.1.4 AND    slide

[: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    slide

[: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    slide

[: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    slide

5.2.1 Single-Wire Circuits    slide

[: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    slide

[: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    slide

[: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    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}]

5.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}]

5.3 Complex Numbers    slide

5.3.1 Complex Numbers: Polar vs Rectangular    slide

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    slide centered_tds th_borders centered

valuerepresentation
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    slide

6.1 NOT gate    slide

[: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)    slide

6.2.1 Hadamard gate definition    slide

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

6.2.2 Example HH    slide

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

6.2.3 The effect of the second H-gate    slide

[: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    slide

[: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!    slide

6.4 Phase Gates    slide

[: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    slide 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 050/50
[:state 1 [ [:H 0] [:Z 0] ] {:dim 100}]</div>
Always 150/50
[:state 1 [ [:H 0] [:S 0] ] {:dim 100}]</div>
50/50Always 1
[:state 1 [ [:H 0] [:S 0] [:Z 0] ] {:dim 100}]</div>
50/50Always 0

7 Multi-Qubit Circuits    slide

7.1 Independent Qubits    slide

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

7.2 Independent Qubits Separability    slide slide_123 centered

7.3 Entangled Qubits

7.3.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]]}]

7.4 Phases Are Weird    slide

[: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    slide

7.5.1 Partial Observations 1    slide

[: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    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]]}]
7.5.2.1 Notes    notes

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

7.6 Entanglement as Observation (Decoherence)    slide

7.6.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.6.2 Double Hadamard observed by qubit    slide

[: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    slide

7.7.1 The Deutsch Algorithm    slide centered slide_512 th_borders

namef(0)f(1)property
zero00constant
one11constant
identity01balanced
not10balanced
[: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    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}]

7.8 Quantum Teleportation    slide

7.8.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}]

7.8.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}]

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    slide

8.1 Factoring    slide text_slide

  • 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    slide centered_tds text_slide th_borders

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

x13x mod 15
113
24
37
41
513
64
77
81
913
104

8.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"]}]

8.4 Quantum Fourier Transform    slide slide_832

9 Quantum Key Distribution    slide

9.1 Value vs Sign    slide centered_tds th_borders centered

StateName
[: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)    slide centered th_borders

Alice's Bit ValueAlice's EncodingQubit StateBob MeasurementBob MeasuresBob's Bit Value
0value0value00
0sign+sign+0
0sign+sign+0
1value1sign+0
1sign-value00
1sign-value00
1sign-value00
0value0sign+0
1sign-sign-1
1value1sign+0
1value1sign+0
1sign-sign-1
0sign+value11
1value1value11
1sign-sign-1
0value0value00
1sign-value11
0sign+value11
0value0value00
0value0value00

9.3 Protocol (removed wrongly measurements)    slide centered th_borders

Alice's Bit ValueEncodingQubit StateBob's Bit Value
0value00
0sign+0
0sign+0
1sign-1
1sign-1
1value11
1sign-1
0value00
0value00
0value00

10 Moar Things!    slide text_slide

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

11 tl;dl    slide text_slide

  • 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?    slide

13 Export Metastuff

Author: Gary Fredericks <gary@gary-groupon>

Date: 2012-09-18 11:19:24 CDT

HTML generated by org-mode 6.33x in emacs 23