Paper Info
Title
Noise Thresholds for Amplification: From Quantum Foundations to Classical Fault-Tolerant Computation.
Abstract
It has long been known that certain superquantum nonlocal correlations collapse 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 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 complexity.
Year
Venue
Field
2018
arXiv: Information Theory
Quantum,Topology,Computer science,Fault tolerant computation
DocType
Volume
Citations 
Journal
abs/1809.09748
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Noah Shutty101.35
Mary Wootters217225.99
Patrick Hayden321620.98