China Makes Quantum Leap In Developing Quantum Computer (scmp.com)

hackingbear writes: Researchers at the University of Science and Technology of China created a quantum device, called a boson sampling machine, that can now carry out calculations for five photons, but at a speed 24,000 times faster than previous experiments. Pan Jianwei, the lead scientist on the project, said that though their device was already (only) 10 to 11 times faster at carrying out the calculations than the first electronic digital computer, ENIAC, and the first transistor computer, TRADIC, in running the classical algorithm, their machine would eclipse all of the world's supercomputers in a few years. "Our architecture is feasible to be scaled up to a larger number of photons and with a higher rate to race against increasingly advanced classical computers," they said in the research paper published in Nature Photonics. This device is said to be the first quantum computer beating a real electronic classical computer in practice. Scientists estimate that the current faster supercomputers would struggle to estimate the behavior of 20 photons.

Comments

Re:What about link to an actual article?

[PaulBu]

Nope, I mean to the scientific paper in Nature Photonics, not press-release...

Like this: http://www.nature.com/nphoton/...

Paul B.

Here's a few more links...

[slew]

Paper preprint...
Wikipage about boson sampling...

In principle, a large-scale boson-sampling machine would constitute an effective disproof against a foundational tenet in computer science: the Extended Church-Turing Thesis, which postulates that all realistic physical systems can be efficiently simulated with a (classical) probabilistic Turing machine.

The machine may not have any practical use, but it still is an interesting theoretical advance that might serve to challenge our understanding of computablity... Part of the theoretical importance of this area of research is the understanding of #P-complete problems.

The wikipedia articlenotes the theoretical significance of this...

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP, and thus P = PH. No such algorithm is currently known.

Re: Here's a few more links...

[Anonymous Coward]

Researcher in computational complexity here. No one believes this machine (or any quantum machine, at that) will be able to solve #P-complete problems in full generality. There's strong evidence that even NP complete problems are out of reach for quantum algorithms, and #P is (seemingly) way, way, way above NP in terms of computational difficulty.

Re:Not general purpose?

[JoshuaZ]

Summary is accurate in that regard. The idea of using Boson sampling to do this came from a paper http://www.scottaaronson.com/papers/optics.pdf by Scott Aaronson and Alex Arkhipov which showed that if a classical computer can do Boson sampling efficiently then certain widely believed conjectures in classical computational complexity would need to be false. In particular, the polynomial hierarchy would collapse https://en.wikipedia.org/wiki/Polynomial_hierarchy.