rose.blog

… check out the whole series.

The first of a series of publications on solving artificial intelligence problems with quantum computers.

Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization

Abstract:

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.

Here are a couple of articles about D-Wave in MIT Technology Review magazine this month.

The first is by Seth Lloyd, the second is by Scott Aaronson.

The reason that Scott’s is so much shorter is that he is busy trying to solve the four problems I presented when I last visited MIT and working on being a professional shut-in.

I will be representing quantum computation, superconducting electronics and AI at Future in Review this year. This will be the biggest event I’ve gotten to present at since TED/03 and I’m pretty stoked. The time / date of my slot is May 23rd, 10:30am-11:00am PST.

I should start working on the presentation shortly… I think what I’m going to focus on is running our latest & greatest hardware on some pattern matching & machine learning type problems. Should be a lot of fun…

Anybody want to guess how this picture from the FIRe 2008 website is connected to D-Wave?

Anyone want to guess where this is?

The Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation

We numerically study the evolution of an adiabatic quantum computer in the presence of a Markovian ohmic environment. We consider Ising spin glass systems with up to 20 coupled qubits that are independently coupled to the environment via two conjugate degrees of freedom. We demonstrate that the required computation time in the presence of the environment is of the same order as that for an isolated system, and is not limited by the single qubit decoherence time T2*, even when the minimum gap is much smaller than temperature. We also show that the behavior of the system can be efficiently described by a two-state model with only longitudinal coupling to the environment.

The main result is summarized in the conclusions:

…we have explicitly demonstrated that the computation time in AQC can be much longer than single qubit decoherence time T2∗.

Here are some new job postings.

20080205_quantum_information_theory.pdf

20080205_condensed_matter_theory.pdf

20080205_computational_physicists.pdf

While I was watching my old buddy Dan Henderson get beat up last Saturday I got into a beer- and scotch-fueled argument with my boxing coach (who also happens to be a criminal defense lawyer for people with names like Lucky who have institution mandated “halos of security” that you have to stay out of) about gambling. Here is the scenario. Two people. Person A is The Buyer and person B is The Bank.

The Buyer agrees to pay a certain sum (to be determined) to The Bank to play the following game.

The Bank tosses a fair coin until it comes up tails. The number of heads before the first tails comes up we define to be N.

If N=0 (the first coin toss comes up tails) The Bank pays The Buyer nothing. If N>0 The Bank pays The Buyer 2^(N-1) dollars.

For example if The Bank throws {heads, heads, heads, tails} then N=3 and The Buyer gets paid 2^(3-1)=4 dollars.

The argument was about what price The Bank should charge to The Buyer to play this game to ensure a “house edge”. What do you think?

Does anyone know a way to reduce the space complexity of an AQC algorithm (ie number of qubits required) by increasing the time complexity? Are there any known tricks in AQC to trade off one vs. the other?

I am pleased to announce that we have closed a $17M financing round as of last week. These funds will be used primarily to push the level of integration of our chips into the low thousands of qubits by the end of the year. In parallel with this central effort we will be working on running experiments on smaller systems to map out features of these systems important to their operation as quantum computers. Stay tuned, it’s going to be an interesting year!