On the impossibility of coin-flipping in generalized probabilistic theories via discretizations of semi-infinite programs

Abstract

Coin-flipping is a fundamental cryptographic task where a spatially separated Alice and Bob wish to generate a fair coin-flip over a communication channel. It is known that ideal coin-flipping is impossible in both classical and quantum theory. In this work, we give a short proof that it is also impossible in generalized probabilistic theories under the Generalized No-Restriction Hypothesis. Our proof relies crucially on a formulation of cheating strategies as semi-infinite programs, i.e., cone programs with infinitely many constraints. This introduces a new formalism which may be of independent interest to the quantum community.

References in corpus (21)

• No Signalling and Quantum Key Distribution
• Probabilistic theories with purification
• Why Quantum Bit Commitment And Ideal Quantum Coin Tossing Are Impossible
• Limitations on separable measurements by convex optimization
• On bit-commitment based quantum coin flipping
• Generalised phase kick-back: the structure of computational algorithms from physical principles
• Ultimate data hiding in quantum mechanics and beyond
• Higher-order interference in extensions of quantum theory
• Deriving Grover's lower bound from simple physical principles
• Computation in generalised probabilistic theories
• The computational landscape of general physical theories
• Conditions on the existence of maximally incompatible two-outcome measurements in General Probabilistic Theory
• Quantum computation is the unique reversible circuit model for which bits are balls
• Oracles and query lower bounds in generalised probabilistic theories
• Structure of Optimal State Discrimination in Generalized Probabilistic Theories
• Bounds on the power of proofs and advice in general physical theories
• Simple proof of the impossibility of bit-commitment in generalised probabilistic theories using cone programming
• How to make unforgeable money in generalised probabilistic theories
• Linear conic formulations for two-party correlations and values of nonlocal games
• A search for quantum coin-flipping protocols using optimization techniques
• Interferometric computation beyond quantum theory

Cited by in corpus (9)

• General probabilistic theories: An introduction
• A no-go theorem on the nature of the gravitational field beyond quantum theory
• Accessible fragments of generalized probabilistic theories, cone equivalence, and applications to witnessing nonclassicality
• Post-quantum steering is a stronger-than-quantum resource for information processing
• Correlations constrained by composite measurements
• Generalized dynamical theories in phase space and the hydrogen atom
• Complete extension: the non-signaling analog of quantum purification
• Breaking barriers in two-party quantum cryptography via stochastic semidefinite programming
• Spacetime symmetries and the qubit Bloch ball: a physical derivation of finite dimensional quantum theory and the number of spatial dimensions