Eric Chitambar

The no-cloning theorem leads to information-theoretic security in various quantum cryptographic protocols. However, this security typically derives from a possibly weaker property that classical information encoded in certain quantum states cannot be broadcast. To formally capture this property, we introduce the study of ``orthogonality broadcasting." When attempting to broadcast the orthogonality of two different qubit bases, we establish that the power of classical and quantum communication is equivalent. However, quantum communication is shown to be strictly more powerful for broadcasting orthogonality in higher dimensions. We then relate orthogonality broadcasting to quantum position verification and provide a new method for establishing error bounds in the no pre-shared entanglement model that can address protocols previous methods could not. Our key technical contribution is an uncertainty relation that uses the geometric relation of the states that undergo broadcasting rather than the non-commutative aspect of the final measurements.

Quantum teleportation is a quantum communication primitive that allows a long-distance quantum channel to be built using pre-shared entanglement and one-way classical communication. However, the quality of the established channel crucially depends on the quality of the pre-shared entanglement. In this work, we revisit the problem of using noisy entanglement for the task of teleportation. We first show how this problem can be rephrased as a state discrimination problem. In this picture, a quantitative duality between teleportation and dense coding emerges in which every Alice-to-Bob teleportation protocol can be repurposed as a Bob-to-Alice dense coding protocol, and the quality of each protocol can be measured by the success probability in the same state discrimination problem. One of our main results provides a complete characterization of the states that offer no advantage in one-way teleportation protocols over classical states, thereby offering a new and intriguing perspective on the long-standing open problem of identifying such states. This also yields a new proof of the known fact that bound entangled states cannot exceed the classical teleportation threshold. Moreover, our established duality between teleportation and dense coding can be used to show that the exact same states are unable to provide a non-classical advantage for dense coding as well. We also discuss the duality from a communication capacity point of view, deriving upper and lower bounds on the accessible information of a dense coding protocol in terms of the fidelity of its associated teleportation protocol. A corollary of this discussion is a simple proof of the previously established fact that bound entangled states do not provide any advantage in dense coding.

An efficient paradigm for multi-party computation (MPC) are protocols structured around access to shared pre-processed computational resources. In this model, distributed correlations are initially disseminated to participants in some form of shared randomness. This allows for a phase of computation, thereafter, built on information theoretic broadcasting primitives with efficient round complexity. While privacy against a malicious adversary is trivial in this phase, the same information theoretic guarantees cannot be met when distributing shared randomness classically, without strong setup assumptions, such as a trusted Dealer and private channels. We present a novel approach for generating these correlations from entangled quantum graph states, and yield information theoretic privacy guarantees that hold against a malicious adversary, with limited assumptions. Our primary contribution is a tripartite resource state and measurement-based protocol for extracting a binary \textit{multiplication triple}, a special form of shared randomness that enables the private multiplication of a bit conjunction. Here, we employ a third party as a Referee, and demand only an honest pair among the three parties. The role of this Referee is weaker than that of a Dealer, as the Referee learns nothings about the underlying shared randomness that is disseminated. We prove perfect privacy for our protocol, assuming access to an ideal copy of the resource state, an assumption that is based on the existence of graph state verification protocols. Finally, we demonstrate its application as a primitive for more complex Boolean functionalities such as 1-out-of-2 oblivious transfer (OT) and MPC for an arbitrary $N$-party Boolean function, assuming access to the proper broadcasting channel.