Boson Sampling Tests Quantum Computing

### New Book Reviews!

 Boson Sampling Tests Quantum Computing
Written by Mike James
Wednesday, 02 January 2013

Despite all the hype, we still don't know if we can build a quantum computer that is worth anything. Now we have something that might provide a shortcut to the test of a full machine - boson sampling.

We have made a lot of progress with quantum computing, but there is still the nagging doubt at the back of every researchers mind that there might be a "no-go" principle in operation. The problem with building a quantum computer is keeping the quantum effects operating properly as the device grows larger. Roughly speaking you can build a quantum computer that works with a few bits, but extending things to enough bits to do some thing that goes beyond what can be achieved using a classical computer is a tough practical problem.

This is fine as long as it is a tough practical problem and there is no basic theoretical result which limits what a quantum computer can do. If it is just practical then we need to push on and refine our technology until we reach the point where a quantum computer can beat a classical computer. If there is a "no-go" theorem then we might as well give up.

To be clear about this - no quantum computer to date has computed anything that isn't well within the ability of a classical computer.

The quantum computers of today have done things like factoring two-digit numbers in a time that can be easily beaten by a classical computer.

If you can increase the number of bits that the quantum computer works with then they could in the same time factor numbers that would take a classical computer the rest of the life of the universe to factor.

You can see that it would not be unreasonable for there to be a deep principle that says something like - "no quantum computer can ever compute something that is beyond the reach of a classical computer".