Abstract. We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an [Formula: see text]-player predicate [Formula: see text]. In particular, we show that for a distribution [Formula: see text] that is product across the input sets of the [Formula: see text] players, the success probability of any entanglement-assisted quantum communication protocol for computing [Formula: see text] copies of [Formula: see text], whose communication is [Formula: see text], goes down exponentially in [Formula: see text]. Here [Formula: see text] is a distributional version of the quantum efficiency or partition bound introduced in [S. Laplante, V. Lerays, and J. Roland, Classical and quantum partition bound and detector inefficiency, in Automata, Languages, and Programming, Springer, Berlin, Heidelberg, 2012, pp. 617–628], which is a lower bound on the distributional quantum communication complexity of computing a single copy of [Formula: see text] with respect to [Formula: see text]. Applying our direct product theorem for small communication, and techniques related to [Formula: see text], we show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information. We analyze parallel and sequential versions of the DI quantum key distribution protocol given in [R. Jain, C. A. Miller, and Y. Shi [ IEEE Trans. Inform. Theory, 66 (2020), pp. 5567–5584], and show that it is possible to extract [Formula: see text] bits of key from it, even in the presence of [Formula: see text] bits of leakage. Finally, we show that proofs of quantumness with two entangled provers are resistant to leakage, i.e., classical players who communicate [Formula: see text] bits with each other cannot convince the verifier that they share entanglement.Abstract. We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an [Formula: see text]-player predicate [Formula: see text]. In particular, we show that for a distribution [Formula: see text] that is product across the input sets of the [Formula: see text] players, the success probability of any entanglement-assisted quantum communication protocol for computing [Formula: see text] copies of [Formula: see text], whose communication is [Formula: see text], goes down exponentially in [Formula: see text]. Here [Formula: see text] is a distributional version of the quantum efficiency or partition bound introduced in [S. Laplante, V. Lerays, and J. Roland, Classical and quantum partition bound and detector inefficiency, in Automata, Languages, and Programming, Springer, Berlin, Heidelberg, 2012, pp. 617–628], which is a lower bound on the distributional quantum communication complexity of computing a single copy of [Formula: see text] with respect to [Formula: see text]. Applying our direct product theorem for small communication, and techniques related to [Formula: see text], we show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information. We analyze parallel and sequential versions of the DI quantum key distribution protocol given in [R. Jain, C. A. Miller, and Y. Shi [ IEEE Trans. Inform. Theory, 66 (2020), pp. 5567–5584], and show that it is possible to extract [Formula: see text] bits of key from it, even in the presence of [Formula: see text] bits of leakage. Finally, we show that proofs of quantumness with two entangled provers are resistant to leakage, i.e., classical players who communicate [Formula: see text] bits with each other cannot convince the verifier that they share entanglement.

arXiv:2106.04299SIAM Journal on ComputingAug 7, 20253 citations

Building multiparticle states with teleportation

Ernesto F. Galvão, Lucién Hardy

We describe a protocol which can be used to generate any N-partite pure quantum state using Einstein-Podolsky-Rosen pairs. This protocol employs only local operations and classical communication between the N parties $(N$ -LOCC). In particular, we rely on quantum data compression and teleportation to create the desired state. The protocol can be used to obtain upper bounds for the bipartite entanglement of formation of an arbitrary N-partite pure state, in the asymptotic limit of many copies. We apply it to a few multipartite states of interest, showing that in some cases it is not optimal. Generalizations of the protocol are developed which are optimal for some of the examples we consider, but which may still be inefficient for arbitrary states.We describe a protocol which can be used to generate any N-partite pure quantum state using Einstein-Podolsky-Rosen pairs. This protocol employs only local operations and classical communication between the N parties $(N$-LOCC). In particular, we rely on quantum data compression and teleportation to create the desired state. The protocol can be used to obtain upper bounds for the bipartite entanglement of formation of an arbitrary N-partite pure state, in the asymptotic limit of many copies. We apply it to a few multipartite states of interest, showing that in some cases it is not optimal. Generalizations of the protocol are developed which are optimal for some of the examples we consider, but which may still be inefficient for arbitrary states.

arXiv:quant-ph/9906080Physical Review AJun 15, 200018 citations

The Quantum Detection Problem: A Survey

Sara Botelho-Andrade, Peter G. Casazza, Desai Cheng +2 more

Springer proceedings in mathematics & statisticsJan 1, 20187 citations

Bell’s inequality and detector inefficiency

Jan-Åke Larsson

In this paper, a method of generalizing the Bell inequality is presented that makes it possible to include detector inefficiency directly in the original Bell inequality. To enable this, the concept of ``change of ensemble'' will be presented, providing both qualitative and quantitative information on the nature of the ``loophole'' in the proof of the original Bell inequality. In a local hidden-variable model lacking change of ensemble, the generalized inequality reduces to an inequality that quantum mechanics violates as strongly as the original Bell inequality, irrespective of the level of efficiency of the detectors. A model that contains change of ensemble lowers the violation, and a bound for the level of change is obtained. The derivation of the bound in this paper is not dependent upon any symmetry assumptions such as constant efficiency, or even the assumption of independent errors.In this paper, a method of generalizing the Bell inequality is presented that makes it possible to include detector inefficiency directly in the original Bell inequality. To enable this, the concept of ``change of ensemble'' will be presented, providing both qualitative and quantitative information on the nature of the ``loophole'' in the proof of the original Bell inequality. In a local hidden-variable model lacking change of ensemble, the generalized inequality reduces to an inequality that quantum mechanics violates as strongly as the original Bell inequality, irrespective of the level of efficiency of the detectors. A model that contains change of ensemble lowers the violation, and a bound for the level of change is obtained. The derivation of the bound in this paper is not dependent upon any symmetry assumptions such as constant efficiency, or even the assumption of independent errors.

Physical Review AMay 1, 199897 citations

The set partitioning problem in a quantum context

Rafael Cação, Lucas R. C. T. Cortez, Jackson Forner +3 more

Optimization LettersJun 23, 20233 citations

(N

-LOCC). In particular, we rely on quantum data compression and teleportation to create the desired state. The protocol can be used to obtain upper bounds for the bipartite entanglement of formation of an arbitrary N-partite pure state, in the asymptotic limit of many copies. We apply it to a few multipartite states of interest, showing that in some cases it is not optimal. Generalizations of the protocol are developed which are optimal for some of the examples we consider, but which may still be inefficient for arbitrary states.