Provable quantum advantage in randomness processing

Howard Dale, David Jennings and Terry Rudolph ()
Additional contact information
Howard Dale: Imperial College London Prince Consort Road
David Jennings: Imperial College London Prince Consort Road
Terry Rudolph: Imperial College London Prince Consort Road

Nature Communications, 2015, vol. 6, issue 1, 1-4

Abstract: Abstract Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics exactly coincides with the class computable quantum mechanically. It is strongly believed, but not proven, that quantum computing provides exponential speed-up for a range of problems, such as factoring. Here we address a computational scenario of randomness processing in which quantum theory provably yields, not only resource reduction over classical stochastic physics, but a strictly larger class of problems which can be solved. Beyond new foundational insights into the nature and malleability of randomness, and the distinction between quantum and classical information, these results also offer the potential of developing classically intractable simulations with currently accessible quantum technologies.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/ncomms9203 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:6:y:2015:i:1:d:10.1038_ncomms9203

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms9203

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().