Quantum advantages of communication complexity from Bell nonlocality
- URL: http://arxiv.org/abs/2004.05098v3
- Date: Tue, 1 Jun 2021 19:16:06 GMT
- Title: Quantum advantages of communication complexity from Bell nonlocality
- Authors: Zhih-Ahn Jia, Lu Wei, Yu-Chun Wu, Guang-Can Guo
- Abstract summary: We present a method to construct CC problems from Bell tests in a graph-theoretic way.
By pre-sharing entangled states, the success probability will exceed that for arbitrary classical strategy.
The non-signaling protocol based on Popescu-Rohrlich box is also discussed.
- Score: 3.1113932875711305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Communication games are crucial tools for investigating the limitations of
physical theories. The communication complexity (CC) problem is a typical
example, for which several distributed parties attempt to jointly calculate a
given function with limited classical communications. In this work, we present
a method to construct CC problems from Bell tests in a graph-theoretic way.
Starting from an experimental compatibility graph and the corresponding Bell
test function, a target function which encodes the information of each edge can
be constructed, then using this target function we could construct an CC
function for which by pre-sharing entangled states, the success probability
will exceed that for arbitrary classical strategy. The non-signaling protocol
based on Popescu-Rohrlich box is also discussed, and the success probability in
this case would reach one.
Related papers
- Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
Quantum resources offer advantages over classical methods in addressing this challenge.
We show that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state, certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender.
We also show that the entanglement-based protocol exhibits significant robustness under white noise.
arXiv Detail & Related papers (2024-09-20T05:17:09Z) - Simple Information Processing Tasks with Unbounded Quantum Advantage [0.0]
We show that it is possible to detect a definite, unbounded advantage of quantum systems over classical systems.
No finite storage can be used to store all the coordinated actions needed to implement all the possible quantum communication tasks with classical systems.
arXiv Detail & Related papers (2023-08-15T12:07:31Z) - Entanglement and Causal Relation in distributed quantum computation [0.0]
We investigate two different aspects of entanglement and classical communication in distributed quantum computation (DQC)
In the first part, we analyze implementable computation over a given quantum network resource by introducing a new concept, quantum network coding for quantum computation.
In the second part, we show that entanglement required for local state discrimination can be substituted by less entanglement by increasing the rounds of classical communication.
arXiv Detail & Related papers (2022-02-14T07:23:17Z) - Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
"Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation.
We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
arXiv Detail & Related papers (2021-12-09T19:00:00Z) - 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) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations.
We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
arXiv Detail & Related papers (2021-03-12T20:58:41Z) - 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) - Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
A client remotely prepares a quantum state using a classical channel.
Privacy loss incurred by employing $RSP_CC$ as a sub-module is unclear.
We show that a specific $RSP_CC$ protocol can replace the quantum channel at least in some contexts.
arXiv Detail & Related papers (2020-07-03T13:15:13Z)
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.