A team in China claims to have made the first definitive demonstration of ‘Quantum Advantage’ by exploiting the counter-intuitive workings of quantum mechanics to perform computations that would be prohibitively slow on classical computers.
They have used beams of laser light to perform a computation which had been mathematically proven to be practically impossible on normal computers. The team achieved within a few minutes what would take half the age of Earth on the best existing supercomputers. Contrary to Google’s first demonstration of a quantum advantage, performed last year, their version is virtually unassailable by any classical computer.
The calculation that they carried out — called the boson-sampling problem — is not just a convenient vehicle for demonstrating quantum advantage, but has potential practical applications in graph theory, quantum chemistry and machine learning.
The boson-sampling problem was devised in 2011 by two computer scientists, Scott Aaronson and Alex Arkhipov, then at the Massachusetts Institute of Technology in Cambridge. It entails calculating the probability distribution of many bosons whose quantum waves interfere with one another in a way that essentially randomizes the position of the particles. The probability of detecting a boson at a given position can be calculated from an equation in many unknowns.
It is a ‘#P-hard problem’, which is even harder than notoriously tricky NP-hard problems, for which the number of solutions increases exponentially with the number of variables.
Starting from laser pulses, the researchers encoded the information in the spatial position and the polarization of particular photon states — the orientation of the photons’ electromagnetic fields. These states were then brought together to interfere with one another and generate the photon distribution that represents the output. The team used photodetectors capable of registering single photons to measure that distribution, which in effect encodes the calculations that are so hard to perform classically.
The Chinese team could find solutions to the boson-sampling problem in 200 seconds. They estimate these would take 2.5 billion years to calculate on China’s TaihuLight supercomputer — a quantum advantage of around 1014.
Nevertheless, the Chinese team’s photonic circuit is not programmable at the moment and have to evolve with programmable features to solve other computational problems. (Nature)
The paper has been published in Science.