It has been a while (almost a semester) since I last attended the excellent quantum computing group meetings organized by Eddie Farhi. Many people from the Boston Area interested in quantum computing meet weekly at the institute for theoretical physics at MIT. These meetings have been important for my lab to remain connected with the quantum information community. There, I met Stephen Jordan and Seth Lloyd, who are now collaborators and co-authors on a few papers. I plan to attend as many meetings as I can from now on, when I am not on travel (next Monday, I will be in Urbana-Champaign). This semester, my laboratory took off with even more momentum, and I have been busy with in-house things, which has forced me to miss these meetings at MIT for one reason or other. Most often, it has been because we had been meeting with the DARPA SERS team (Ken Crozier and Eric Mazur).

Yesterday, Peter Young, from UC Santa Cruz’s Physics department gave a talk about the complexity of the adiabatic quantum algorithm (<- click to download his slides). The quantum Monte Carlo (QMC) algorithm allowed him to test the gap for typical instances of the exact cover NP-hard problem for up to 128 spins. Peter Young and his co-authors found that up to 128 spins, the scaling is still polynomial. For classical algorithms like WALKSAT, he found a crossover from polynomial to exponential. The open question, of course, is if the adiabatic algorithm will have a cross over at a certain size. He is working on extending his QMC calculations to 256 spins. Hopefully, it still has an advantage for that size.

This talk connects two of my interests: quantum information and quantum Monte Carlo.

More QMC news: Sangwoo Shim, a graduate student in my laboratory, is gearing up to become our local Harvard Chemistry QMC expert, and he is attending The Towler Institute Summer School of Quantum Monte Carlo, organized by Mike Towler. Mike’s conferences are excellent. I had great fun at the TTI conference last year (as for example, this photo or this one attest), and plan to attend it bi-yearly to stay abreast with the field. Also, I saw the source code of what will soon become Zori 2.0. Brian Austin did an excellent job and I am excited of trying it out. We are using Assembla.com for most of our projects, and we love it. Zori 2.0 will be hosted using that service.

Link: Mark Dewing’s Quantum Monte Carlo blog.