How To Program Your Quantum Computer

Table of Contents

1 Intro

1.1 How To Program Your Quantum Computer   slide text_centered

Gary Fredericks

November 18, 2014

Geekfest

1.2 Take 2   text_centered text_slide slide

September 18, 2012

1.3 Like, what even is a quantum computer?   slide

1.4 Focus…   slide

1.5 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!
  • 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   slide text_slide

  • Background
    • Classical Circuits
    • Probabilistic Circuits
    • Complex Numbers
  • Fundamentals
    • Qubits
    • Amplitudes & Possibilities
    • Measurements
    • Entanglement
  • Algorithms & Things
    • Deutsch Algorithm
    • CHSH Game

2 Background   slide

2.1 Background – 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}]

2.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 ["a1" "a2" "b1" "b2" "0" "0" "0"] :output-labels ["a1" "a2" "b1" "b2" "c1" "c2" "c3"] :scale 2}]

2.2 Background – 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 Background – 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 Fundamentals   slide

3.1 Qubits   text_slide slide

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   slide

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

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   slide

[:circuit {:wires 4 :gates [[:X 2] [:X 3 2] [:parallel [:X 0] [:X 1]]]} {:scale 2}]

3.5 Measuring   text_slide slide

When we measure any of the qubits, the possibilities that are incompatible with the outcome vanish.

3.6 Hadamard Gate   slide

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

3.7 Hadamard gate definition   slide

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

3.8 \(H^2\)   slide

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

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

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

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

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

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

3.14 Entanglement   text_slide slide

When multiple qubits are operated on together, they can be "entangled" such that their values are correlated.

3.15 Independent Qubits   slide

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

3.16 Entangled Qubits   slide

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

3.17 Entanglement & Modification   slide

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

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

  • The Deutsch Algorithm
  • The CHSH Game

4.1 The Deutsch Algorithm   slide

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

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

4.1.3 The Deutsch Algorithm   slide centered

  • Classical algorithm calls \(f\) twice
  • Deutsch algorithm calls \(f\) once
  • But scalable!

4.2 The CHSH Game   slide

4.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\)

4.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 Outro

5.1 PHEW   slide

5.2 Okay so what can you actually do with qubits?   text_slide slide

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

Gee whiz.

  • Quantum Key Distribution
  • Factoring (!!)
  • Quantum Teleportation
  • Mixed States
  • Bloch Sphere
  • Grover's Quantum Search Algorithm
  • Quantum Error Correction

5.4 Questions?   text_slide slide

Resources

6 Appendices   slide

6.1 Deutsch Explanation   slide

6.1.1 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}]

6.1.2 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}]

6.1.3 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}]

6.2 Factoring   slide

6.2.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\))

6.2.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

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

6.2.4 Quantum Fourier Transform   slide slide_832

6.3 Quantum Teleportation   slide

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

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

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   slide

6.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}]
-
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   slide

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

6.4.4 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

6.5 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

6.6 Independent Qubits Separability   slide slide_123 centered

6.7 Entanglement as Observation (Decoherence)   slide

6.7.1 Double Hadamard (review)   slide

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

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

7 Export Metastuff

Author: Gary Fredericks

Created: 2014-11-18 Tue 11:35

Emacs 24.3.1 (Org mode 8.2.7c)

Validate