AQIS’10: Day 1 liveish blogging

Well, I’m looking at everything through bleary eyes this morning after yesterday lasted for about 36 hours, but I’m pretty sure I’m in Tokyo and today is the first day of AQIS’10.

Today’s agenda is a series of Tutorials being given by some of the fancier names in this Quantum Information/Computation business. I’m a big fan of this trend of having a warm-up/tutorial day at the beginning of a workshop where a lot of technical ground will be covered. Good for the newbies and good for us older folk who need an extra day or so to rebound from the jet-lag!

Hopefully I’ll be able to liveblog a bit today, not sure how much wifi we’ll have…

Update: Well, it seems that we do have wifi here!

Intro talk: Charlie Bennett

Charlie is giving a nice talk giving the motivation for considering information quantumly.

Quantum nonlocality tutorial: Harry Buhrman


New paper: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Yes, I am still alive. I hope the 3 of you that still subscribe to my RSS feed weren’t too shocked this morning when you saw “Brissie to Brizzle” highlighted in Google Reader.

Why have I come out of hibernation? Well, it’s because today I have a new paper together with Dan Shepherd and Richard Jozsa out on the arXiv (SciRate link):

Title: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Abstract: We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, even up to 41% multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy, would collapse to its third level. We mention some further results on the classical  simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may in fact, be classically efficiently sampled.

This paper is a sequel  to a paper that Dan Shepherd and I wrote back in 2008, Instantaneous Quantum Computation.

For those of you that attended QIP in Zurich this year you might have seen our poster on these results (which was very kindly advertised by Scott Aaronson during one of his talks).

Those of you that are really keen will notice in the references of this paper that there is another related paper by Dan Shepherd that will appear imminently… It’s well worth a read if you are interested in the classical simulation of quantum systems!

Oh, and while I’m at it Dan’s PhD thesis (SciRate link) is available on the arXiv today as well!

Lies, damned lies and …

SciRate stats.

A few days back Dave did some analysis on papers that were highly scited on SciRate in the past 12 months. He examined papers that had more than 10 scitations and tried to group them by region.

Papers that had multiple co-authors were split between regions and if an author had multiple affiliations between different regions it was split again. He found, somewhat interestingly, that the US beat out Europe and Canada for the number of highly scited papers. This is interesting mostly because the US spends comparatively less than Canada and Europe on Quantum Information theory research.

Somewhat foolishly I decided that it would be interesting to see what the outcome of a similar calculation would be if we did the same analysis by institution instead of geographic region. Well, after an hour or so of downloading papers and checking affiliations I cobbled together the calculation.

I decided to basically use the same scoring mechanism as Dave. Each paper with more than 10 scitations, ie 11 or more, was worth 1 point. If there were multiple co-authors they each received a fraction of that point. Again, if an author had more than 1 affiliation I split their allocation accordingly.

Oh, and I did the calculation taking into account papers from 365 days prior to the 3rd of November. Clearly, the choice of time-period over which this calculation is done makes a big difference.

Now, before presenting a summary of these results I should point out that this was all done on the back of an envelope (actually, the reverse side of a printout of a paper) and isn’t necessarily accurate. While I was happy to waste my time to do this once, it wasn’t really worth checking the stats too thoroughly. Mostly, I was only interested in the broad trends that emerged and I think I counted accurately enough to establish those. But, please, don’t take any of this too seriously. I’m only publishing these stats as a discussion starter!!!

Of the 46 papers that I counted, 37 separate institutions were listed by authors as affiliations. Only 10 of those institutions received a score of 1 or more papers (remember if there were multiple co-authors the score for a paper would be fractional). The top 10 institutions were:

Continue reading

The Tricki looks awesome

I just had a look at the Tricki that Tim Gowers has set up, it looks like it is going to be an incredibly useful resource for solving mathsish problems!

I walked past Royal Albert Hall on my way to work this mornin

This week I’m attending the IMA conference on quantum computing and the complexity of quantum simulation.

Looks like it’s going to be a good conference. Daniel Gottesman is kicking off with a review(ish) talk on “Computationally hard problems in spin systems”…

Yay! I’ve now been published in a Royal Society journal

Yay! My paper with Dan Shepherd that was previously titled Instantaneous Quantum Computation has been appeared online in the Proceedings of the Royal Society A with the title Temporally Unstructured Quantum Computation.

I wonder if any royals read the Proceedings A?

Update: I forgot to add that the published version is roughly 100 bazillion times easier to read than the version that appeared originally on the arXiv. So if anyone out there was wanting to dive in and learn this material they should start with the published paper or possibly the latest arXiv version.

Matt Hastings is guest posting over at Tobias’ place

For those who are into the adiabatic model of quantum computation I suggest going here and having a read.