Meeting notes 11 06 01

From Quantum Computing Theory Group
Jump to: navigation, search
Greg thesis defense
  • Weapons of Mass Simulation: Smashing down the barriers to building a quantum computer!
  • Friday, June 10, 2pm. P&A Room C520.
The "Kill D-Wave" project

Drag s from 0 to 1. As you do, set your Hamiltonian to <math>H(s) = (1-s)H_x + s H_f</math> where <math>H_x= -\sum_i X_i, H_f = \sum_{y\in\{0,1\}^n} f(y) |y\rangle\langle y|</math>.

Goal: If adiabatic evolution takes time T, then find a classical simulation that runs in time poly(T).

Why this should be possible: If this were a general 2-local Hamiltonian, we'd be cooked. But this Hamiltonian is stoquastic (see also quant-ph/0611021), meaning its off-diagonal elements are non-positive.

Assume <math>f\leq 0</math> and define <math>M(\beta)=I-(I + \frac{1}{n}H_x)e^{\beta H_f}</math>. This is stochastic, and its stationary state is <math>|\pi(\beta)\rangle = \sum_x \frac{e^{-\beta f(x)}}{Z} |x\rangle</math>

But what is the gap of <math>M(\beta)</math> and how does it relate to the gap of <math>H(s)</math>?

We can also consider this to be a classical Ising model in one extra dimension, and instead of considering Markov moves, we can make more general moves that will be able to handle critical points.