Quantum Machine Learning
or
How I learned to stop worrying and love the Hamiltonian
The Problem
 Global optimum is NPHard
 Lloyd's Algorithm offers a heuristic for solving it
 Three step process
Complexity
 Assignment
 Update
 Distance calculation is slow
Can we go faster?
Sure, let's build an ASIC!
 Distance calculation is slowest part
 We need
 n subtraction operations
 n squaring operations
 n1 sums
 a square root
 This can be done with adders and registers
Boolean Algebra
 AND
0 AND 0 = 0 
0 AND 1 = 0 
1 AND 0 = 0 
1 AND 1 = 1 
 OR
0 OR 0 = 0 
0 OR 1 = 1 
1 OR 0 = 1 
1 OR 1 = 1 
 NOT
 NODE
NODE 0 = {0, 0} 
NODE 1 = {1, 1} 
 Implement using NAND, XOR, and registers
Can we go faster?
Let's see what the physics says
Classical Hamiltonian Mechanics
 Time evolution is linear and bijective
 NODE is OK
 NOT meets this criterion
 AND and OR do not
 We must modify our algebra
 Total Energy is in Hamiltonian
 Differentation of Hamiltonian gives time evolution
Solution: Add More Bits
 Takes in three inputs and returns three outputs
Truth Table
 By picking which bits to read, we can emulate a Boolean Algebra
 Input A, B, C=0 => C = AND (A,B)
 Input A=1, B=1 => C = NOT C
 Input A, B, C=1 => C = XOR(A,B)
 By adding garbage data, we can compute reversibly
 Billiardball computing
 Each billiard ball is single (classical) atom
 Whether vibrating or not gives classical 0 and 1
 Vibration coupling produces our gates
Can we go faster?
Can we go quantum?
Quantum computing
 Instead of bits, we have qubits
 Can be 0, 1, or a superposition of the two
 The 0 and 1 states still behave like classical bits
 Measuring a qubit collapses it into a 0 or 1 state
 Instead of a Boolean Algebra, we have a Lie algebra
 The SU(2) Lie group is diffeomorphic to a 3sphere
 The surface of this sphere shows all accessible states
 A point on the surface of the sphere is a valid quantum state
 Measurement projects the vector onto one of the three axes
 Magnitude of projected vector = square root of probability of outcome
 Nqubit states are created by tensor products of the basis vectors
 These are not diffeomorphic to a 3sphere, but to a 15sphere
 We can flatten their dimensionality into a 4 x 4 matrix without loss of generality
 Instead of four diads, we have four orthogonal basis vectors
 Nocloning theorem prevents copying of quantum state. NODE is out
 N classical bits can be encoded in log(N) qubits in superposition
The Quantum Toolbox

Phase gates

 Hadamard Gate is a special case of phase gate
 Square root of NOT

Controlled Not (CNOT)
 We can build a Toffoli gate out of binary quantum gates
 Differentiation of Hamiltonian gives time evolution, as in classical HM
Centroid Calculation
 To compare two vectors, we do a SWAP test

Controlled SWAP gate
 If control bit is 0, swaps the two qubits, else does nothing
 Prbability of state is 1/2 + 1/2 * (\bra{a}\ket{b}^2)
 If this value is 1/2, vectors are orthogonal. If it's 1, they're parallel
 N qubits encode 2^N classical states, therefore logarithmic distance measurement
Open Problems in QML
 Quantum Neural Networks
 Quantum Decision Trees
 Quantum versions of Hidden Markov Models
Challenges in General QC
 Efficient State Preparation
 QRAM
 Decoherence