Quantum Machine Learning

or

How I learned to stop worrying and love the Hamiltonian

About me

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

IBM Quantum Computer