Quantum-generated probability distributions can be hard for classical machines to recreate
2 May 2014
Editor’s Suggestion - Physical Review Letters
Hussain Anwar, Naïri Usher and Dan Browne, together with collaborators at ICFO Barcelona and University of Sydney have discovered a new way in which quantum systems may exceed the capabilities of classical computing machines. In a quantum computer, information is processed by quantum logic gates, analogues of the NAND and XOR gates which power a classical computer, but which can generate intrinsically quantum phenomena such as superposition and entanglement. A quantum computer could solve certain problems (factorising numbers, simulating the properties of a material) much faster than the best classical algorithm for these tasks.
In their recent article , highlighted as an Editor’s suggestion in Physical Review Letters, they have found strong evidence of a behaviour that a classical computer would find hard to emulate in a much simpler setting. A simple quantum state over many qubits is prepared and then immediately measured. This process samples from a probability distribution. They show that such distributions, which can be generated by a simple quantum process, could only be generated efficiently by a classical machines if certain foundational principles of computer science were incorrect - i.e. if this were shown to be possible, the computer science textbooks would need to be rewritten. This indicates that some quantum properties can remain associated with a probability distribution, even though this concept stems from (non-quantum) classical probability theory.
 Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf, and Dan E. Browne Phys. Rev. Lett. 112, 140505 2014 (Editor’s Suggestion)
Journal Link: Physical Review Letters