Statisfaction

Quantum Monte Carlo

Posted in Uncategorized by Pierre Jacob on 19 November 2010

Hi again!

In Vancouver, there is (weak beer, seafood, good weed and) the first and only company in the world that aims at building a real quantum computer. By real I mean that they want to solve real-world problems using quantum computers, and eventually become leader in deploying such devices. It’s called D-Wave Systems. I have had the opportunity to visit their building this week, thanks to one of their employees that I’ve met through a professor of Computer Science at UBC. Many thanks to him and his colleagues for having shown me around and having taken the time to discuss Monte Carlo with me!

D-Wave has built a quantum computer of the type “Adiabatic Quantum Computer”. There is a controversy now in the physics community, whether they managed to observe quantum effects (superposition for instance) or not. Of course I know nothing about that, but they seemed really convinced and convincing to me! Overall these people are really passionate about their work and talking to them was really exciting. Usually, when talking to statisticians working in finance, insurance or pharmaceutics, my impression is that private companies provide better salaries but less interesting topics than the University; but in this case they really are pioneering a new field of computer science… it’s pretty ambitious to say the least!

To summarize why quantum computer woulds be so great, consider that our “classic” computers work with “bits”, taking value in $\{0,1\}$. A sequence of e.g. 3 bits can then take value in $\{000, 001, 010, 011, 100, 101, 110, 111\}$, that is $2^3 = 8$ possible values. A quantum computer works with qubits instead of bits. Due to a quantum phenomenom called superposition, a qubit can take all its possible values at the same time, and is roughly modeled by a probability distribution: a sequence of three qubits takes value $000$ with some probability $a_1$, $001$ with some probability $a_2$, etc. The goal of quantum computing is to take advantage of this superposition, in order to process as many calculations at the same time as possible. D-Wave is now operating with systems equipped with 128 qubits, so the sequence can take $2^{128}$ possible values at the same time, theoretically.

Of course it’s a long shot until standard algorithms are actually $2^{128}$ faster, but they already have results for some Quantum Monte Carlo algorithms. Since qubits are modeled with the theory of probability, it is not surprising that Monte Carlo algorithms might become handy in this context. So a bunch of guys at D-Wave work on Monte Carlo algorithms that they already implement on their quantum devices. These algorithms are linked with simulated annealing techniques, parallel tempering and so on, and they aim at solving complex optimization and sampling problems, escaping local modes as much as possible.

It’s also much more complicated than that. I was hoping that quantum computers were just super fast computers, but it actually behaves differently; and most likely it’ll never be just a fast computer, at least for the next decades. Quantum algorithms allow techniques that wouldn’t make sense in the classical equivalent. For instance, a phenomenon called Quantum Tunnelling can provide a huge benefit in optimization problems, but is not translatable in classical Monte Carlo. On the other hand, to my question “can a quantum computer compute 2+2 ?”, the answer was not as short as expected! I don’t even remember exactly what it was. Something like “it depends what you mean by 2 + 2 but yes it’s likely to answer “4”, 99.99% of the time”. Pros and cons!

You can browse their publications’ list to see what they’ve been working on. In terms of Monte Carlo, there are interesting stuff about Parallel Tempering and GPGPU. Have a look at the preprints as well. I hope to see the day when Quantum Monte Carlo will be all over the place! And congrats to D-Wave for taking risks in a whole new field!