Impossibility of coin flipping in generalized probabilistic theories via discretizations of semi-infinite programs

Simple item page
dc.contributor.authorSikora, Jamieen
dc.contributor.authorSelby, John H.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2021-02-15T20:03:29Zen
dc.date.available2021-02-15T20:03:29Zen
dc.date.issued2020-10-23en
dc.description.abstractCoin flipping is a fundamental cryptographic task where 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 formalism which may be of independent interest to the quantum community.en
dc.description.notesWe thank M. Plavala, G. Chiribella, and H. Barnum for helpful discussions. This research was supported in part by Perimeter Institute for Theoretical Physics. Research at Perimeter Institute is supported by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Research, Innovation, and Science. This research was also supported in part by the Foundation for Polish Science through IRAP project cofinanced by EU within Smart Growth Operational Programme (Contract No. 2018/MAB/5).en
dc.description.sponsorshipPerimeter Institute for Theoretical Physics; Government of Canada through the Department of Innovation, Science and Economic Development Canada; Province of Ontario through the Ministry of Research, Innovation, and ScienceMinistry of Research and Technology of the Republic of Indonesia (RISTEK); Foundation for Polish Science through IRAP project - EU within Smart Growth Operational Programme [2018/MAB/5]en
dc.format.mimetypeapplication/pdfen
dc.identifier.doihttps://doi.org/10.1103/PhysRevResearch.2.043128en
dc.identifier.eissn2643-1564en
dc.identifier.issue4en
dc.identifier.other43128en
dc.identifier.urihttp://hdl.handle.net/10919/102374en
dc.identifier.volume2en
dc.language.isoenen
dc.rightsCreative Commons Attribution 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.titleImpossibility of coin flipping in generalized probabilistic theories via discretizations of semi-infinite programsen
dc.title.serialPhysical Review Researchen
dc.typeArticle - Refereeden
dc.type.dcmitypeTexten
dc.type.dcmitypeStillImageen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
PhysRevResearch.2.043128.pdf
Size:
261.04 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Scholarly Works, Computer Science