# Quantum Machine Learning

or

How I learned to stop worrying and love the Hamiltonian

# The Problem

• Global optimum is NP-Hard
• Lloyd's Algorithm offers a heuristic for solving it
• Three step process
• Assign
• Update
• Iterate

## 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
• n-1 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  NOT 0 = 1 NOT 1 = 0
• 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

• Classical Toffoli Gate

• 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
• Billiard-ball 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 3-sphere
• 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
• N-qubit states are created by tensor products of the basis vectors
• These are not diffeomorphic to a 3-sphere, but to a 15-sphere
• 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
• No-cloning 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