Ed Farhi Google Tech Talk on AQC

Here is Ed Farhi from MIT at Google talking about physics-based approaches to quantum computing and specifically AQC. Introduced by Hartmut Neven.

7 thoughts on “Ed Farhi Google Tech Talk on AQC

  1. This guy gives a lecture like he’s speaking to undergrads rather than Google engineers.

    Hey Geordie,
    Are you blowing classical systems out of the water yet? I asked a while back and I think you gave me an estimate for out-of-water-devastation to be sometime around now =D

  2. Yo Geordie. Farhi gave basically the same talk at a review I was just at. Great stuff. Speaking of obliteration, what is the Kimbo Slice interpretation of the adiabatic factoring algorithm that just appeared on the arXiv?

  3. Is there an adiabatic version of Grover’s algorithm ?
    If there was would the current Dwave system be able to run it ?

    What are the known adiabatic QC algorithms that should have an advantage over classical systems ?

    A superior quantum chemistry simulator was still needing the 2010 version of the system right ?

  4. Ash & Sam: The idea of casting factoring as a global optimization problem isn’t new, it was tried classically and the approach doesn’t work well (see http://research.microsoft.com/~cburges/tech_reports/tr-2002-83.pdf for a good review of this). Many years ago we ran through the entire machinery of how to do this on our hardware, but ended up putting it on the shelf because it seemed highly unlikely that the quantum adiabatic algorithms for solving these types of optimization problems should perform well. I can guarantee we could use the “factoring as optimization” approach and factor a much bigger number than 21. It’s dead simple–you can for example just use the unconstrained optimization problems as generated in the above document and solve them as quadratic integer programs in hardware. But I have trouble seeing why this is a good idea. So my response to this work is the same as my response to a lot of QC research: What next? Where does it lead? Is it really a good idea or just a dead end?

  5. Brian: Yes there is an adiabatic Grover search but it is not a useful quantum adiabatic algorithm for two reasons: (1) it has the same computational scaling as conventional unsorted database search and (2) it requires highly unnatural Hamiltonians. It is an “artificial” algorithm for AQC. All of the realistic (ie those you’d actually want to implement in a real AQC) adiabatic quantum algorithms are variants of the basic algorithm Ed Farhi, Seth Lloyd, etc. proposed in 1999-2000 and are designed to solve (either in the heuristic or complete sense depending on how they are operated) discrete optimization problems. As far as I know no-one has a useful prescription for doing generic quantum simulation with a quantum adiabatic algorithm yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s