Demonstrating quantum communication complexity superiority non-trivially with currently available experimental systems is of utmost importance in quantum information science. Here, we propose a generalized entanglement-assisted communication complexity reduction protocol and analyze the robustness of its quantum superiority against the measurement imperfections, such as measurement basis deviation and choice probability bias, a common problem rarely studied before. We find that the quantum superiority can be obtained in a specific entangled state in a suitable range of measurement basis and basis choice parameters. And the quantum superiority strengthens with the increase of the entanglement degree of quantum states. By using the maximum entangled state and its corresponding optimal measurement, the result we obtained violated the optimal classical bound by 239 standard deviations. Besides, the robustness of effective measurement basis in dephasing and depolarizing quantum channels is also investigated. These results not only make a step forward in investigating sufficient experimental conditions to unambiguously demonstrate the superiority of quantum communication complexity but also help to develop relevant practical applications.
Demonstrating quantum communication complexity superiority non-trivially with currently available experimental systems is of utmost importance in quantum information science. Here, we propose a generalized entanglement-assisted communication complexity reduction protocol and analyze the robustness of its quantum superiority against the measurement imperfections, such as measurement basis deviation and choice probability bias, a common problem rarely studied before. We find that the quantum superiority can be obtained in a specific entangled state in a suitable range of measurement basis and basis choice parameters. And the quantum superiority strengthens with the increase of the entanglement degree of quantum states. By using the maximum entangled state and its corresponding optimal measurement, the result we obtained violated the optimal classical bound by 239 standard deviations. Besides, the robustness of effective measurement basis in dephasing and depolarizing quantum channels is also investigated. These results not only make a step forward in investigating sufficient experimental conditions to unambiguously demonstrate the superiority of quantum communication complexity but also help to develop relevant practical applications.
Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In this paper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., where the inputs are mixed states and/or prepared adversarially. We consider three models of imperfect entanglement, namely, the bounded measurement model, the depolarization model, and the fidelity model. We describe these models as well as the motivations for studying them. For the bounded measurement model and the depolarization model, we prove tight and almost-tight bounds on the output quality of non-interactive protocols. For the fidelity model, we prove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes communication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality of the BB84 protocol in terms of communication complexity. We emphasize that although some of the results appear intuitively straightforward, their proofs are not. In fact, two novel techniques are developed for proving these results. We believe that these techniques are of independent interests, too.
Abstract Entanglement is an essential resource for quantum com-munication and quantum computation, similar to shared random bits in the classical world. Entanglement distil-lation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity ofthese protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In thispaper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., wherethe inputs are mixed states and/or prepared adversarially. We consider three models of imperfect entanglement,namely, the bounded measurement model, the depolarization model, and the fidelity model. We describe there mod-els as well as the motivations for studying them. For the bounded measurement model and the depolarization model,we prove tight and almost-tight bounds on the output quality of non-interactive protocols. For the fidelity model weprove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes commu-nication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality ofthe BB84 protocol in terms of communication complexity. We emphasize that although some of the results appearintuitively straightforward, their proofs are not. In fact, two novel techniques are developed for proving these results.We believe that these techniques are of independent interests, too.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.
Abstract In this article, we investigate classical simulations of quantum-type probabilities and correlations that defy Boole’s conditions of possible experience, specifically the Clauser-Horne-Shimony-Holt inequality, and even surpass the Tsirelson bound. We demonstrate that such violations can be achieved by encoding a single bit to communicate the measurement context. Our findings highlight the crucial role of context communication in reproducing quantum correlations that are stronger than classical limits, providing insights into the fundamental principles underlying entangled systems.