Provable Quantum Advantage in Randomness Processing

Abstract

Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics actually 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.

A much improved version of the paper is available in Nature Communications. (10.1038/ncomms9203)

References in corpus (4)

• Quantum algorithm for solving linear systems of equations
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Creating superpositions that correspond to efficiently integrable probability distributions
• Fast simulation of new coins from old

Cited by in corpus (16)

• A perspective on protein structure prediction using quantum computers
• Using quantum theory to reduce the complexity of input-output processes
• Experimental Quantum Randomness Processing
• Toward Automatic Verification of Quantum Programs
• Efficient demultiplexed single-photon source with a quantum dot coupled to a nanophotonic waveguide
• Demultiplexed Single-Photon Source with a Quantum Dot Coupled to Microresonator
• Quantum-to-Quantum Bernoulli Factory
• An Experimental Quantum Bernoulli Factory
• Modular Quantum-to-Quantum Bernoulli Factory in an Integrated Photonic Processor
• Advantage of Quantum Theory Over Non-classical Models of Communication
• Polarization-encoded photonic quantum-to-quantum Bernoulli factory based on a quantum dot source
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• General Quantum Bernoulli Factory: Framework Analysis and Experiments
• Extreme Quantum Advantage when Simulating Strongly Coupled Classical Systems
• Complexity and multi-functional variants of the Quantum-to-Quantum Bernoulli Factories
• Reasoning about Recursive Quantum Programs