Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise

• URL: http://arxiv.org/abs/1809.09748v5
• Date: Mon, 1 May 2023 18:12:06 GMT
• Title: Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
• Authors: Noah Shutty, Mary Wootters, Patrick Hayden
• Abstract summary: It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. We show that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. We provide evidence that the 0.91 result is the best possible using a large class of proof strategies.
• Score: 19.970633213740363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any nonlocal binary function could be evaluated with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement "communication complexity is nontrivial" has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We provide evidence that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from an upper bound on the threshold for reliable computation with formulas of noisy XOR and AND gates.

Related papers

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Coordinating Decisions via Quantum Telepathy [5.343878011292203]
  We present a conceptual framework for applying quantum telepathy to real-world problems. In general, the problems involve coordinating decisions given a set of observations without being able to communicate.
  arXiv  Detail & Related papers  (2024-07-31T16:18:15Z)
• Unbounded Quantum Advantage in One-Way Strong Communication Complexity of a Distributed Clique Labelling Relation [0.19090202146054183]
  We investigate the one-way zero-error classical and quantum communication complexities for a class of relations induced by a distributed clique labelling problem. We show that for the specific class of relations considered here when the players do not share any resources, there is no quantum advantage in the CCR task for any graph. We highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Topologically driven no-superposing theorem with a tight error bound [0.0]
  We study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. Our results exclude the superposition as an elementary gate for quantum computation.
  arXiv  Detail & Related papers  (2021-11-03T17:57:56Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• The Second Law of Quantum Complexity and the Entanglement Wormhole [0.0]
  Quantum complexity arises as an alternative measure to the Fubini metric between two quantum states. It is defined as the least complex unitary operator capable of transforming one state into the other.
  arXiv  Detail & Related papers  (2021-04-11T15:23:47Z)
• On Query-to-Communication Lifting for Adversary Bounds [14.567067583556714]
  We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree.
  arXiv  Detail & Related papers  (2020-12-07T02:10:37Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.