People often ask me how long it will be before we have an optical quantum computer with post-classical capabilities. My answer, until recently, was that it will be a very, very long time. However, a recent landmark theoretical study by Aaronson & Arkhipov (here) suggests that the timeline could be much shorter than previously expected. They presented a model for optical quantum computing called ‘Boson-sampling’, which significantly relaxes the requirements for optical quantum computing, yet nonetheless likely implements an algorithm which cannot be efficiently classically simulated. From a quantum computing perspective this is exactly what we want – a computer that no classical computer in the world can efficiently simulate.
The model is very simple. We prepare a bunch of single photons, pass them through a passive linear optics network (i.e beamsplitters and phase shifters – no feedforward, no quantum memory, no post-selection), and then measure the photo-statistics at the end. Importantly, while implementing a classically hard problem, the model is (strongly) not believed to be universal for quantum computing.
Recently, numerous experimental groups have begun implementing elementary demonstrations of Boson-sampling. In the last few weeks there have been no less than four experimental demonstrations of three photon Boson-sampling (here, here, here and here). The demonstration by Broome et al. (here) was recently published in Science.
Since full blown optical quantum computing is a very long term goal, here’s my prediction for the next ten years.
In 2014 we’ll see another Science paper demonstrating four photon Boson-sampling. In 2015 there will be another Science paper with five photons. The following year we’ll see – here’s a scoop – a six photon Boson-sampling paper, published in Science of course. And this will continue, on and on, until the experimentalists run out of single photon sources and photo-detectors. Then, in ten years time, we’ll have a device with post-classical capabilities and everyone will rejoice.
Here’s the catch. First, unlike many other computational problems, the output to Boson-sampling cannot even be efficiently verified (unlike, say, Shor’s algorithm which resides in NP). That is, if I tell you the output statistics that I measured, there is no way of determining whether the output was correct. So how will we ever know that our computer is working correctly? One approach (the one used by Broome et al.) is, instead of verifying the output to the computer, we characterise the unitary network defining the transformation. This can be implemented efficiently (see work by Rahimi-Keshari et al. here), but works off the assumption that the network is purely unitary, which, in general, is not the case (e.g. as a result of effects like mode-mismatch and higher order photon number terms). Second, there are no known algorithmic applications for Boson-sampling. Aaronson & Arkhipov present a strong computational complexity argument that Boson-sampling is classically hard to simulate, but, at this stage, no one has actually mapped it to solving a problem of interest. This is in distinction to universal quantum computation whereby a plethora of algorithms, most famously Shor’s integer factorisation algorithm, are known.
Nonetheless, I fully expect that this is the direction optical quantum computing will (and should) follow in the near future – one Science paper after another, each adding a few more photons and a bunch more modes.
It’s exciting, but, based on present understanding, completely and utterly useless. Nonetheless, I look forward to seeing how far this concept can be pushed, and I hope that in the meantime the theorists will come up with a killer application for these devices (I personally don’t know how to do this – I’m not sure that anyone does).
On a positive note, my recent work suggests that Boson-sampling may still implement a hard algorithm even in the presence of very high loss rates (here) and very low photon fidelities and spectral purities (here). This is in contrast to universal optical quantum computing schemes, which place very stringent requirements on these effects (the best known fault tolerant algorithms still require error rates below 1%). This means that Boson-sampling may be much more viable with present-day technology than other optical quantum computing schemes.
I look forward to future demonstrations with a couple of dozen photons, at which point a reasonable claim can be made that we have a device with post-classical capabilities (albeit still not very useful).