Noise Thresholds for Amplification: Quantum Foundations From Classical Fault-Tolerant Computation

09/25/2018
by   Noah Shutty, et al.
0

It has long been known that certain superquantum nonlocal correlations collapse communication complexity, and it is conjectured that a statement like "communication complexity is not trivial" may provide an intuitive information-theoretic axiom for quantum mechanics. With the goal of addressing this conjecture, we take aim at collapsing communication complexity using weaker nonlocal correlations, and present a no-go theorem for a broad class of approaches. To achieve this, we investigate fault-tolerant computation by noisy circuits in a new light. Our main technical result is that, perhaps surprisingly, noiseless XOR gates are not more helpful than noisy ones in read-once formulas that have noisy AND gates for the task of building amplifiers. We also formalize a connection between fault-tolerant computation and amplification, and highlight new directions and open questions in fault-tolerant computation with noisy circuits. Our results inform the relationship between superquantum nonlocality and the collapse of communication complexity.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset