A search for quantum coin-flipping protocols using optimization techniques

• 成果类型: Article
• 署名作者: Nayak, Ashwin; Sikora, Jamie; Tuncel, Levent
• 署名单位: University of Waterloo; University of Waterloo; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0909-y
• 发表日期: 2016
• 页码: 581-613
• 关键词: unconditional security; bit commitment

摘要

Coin-flipping is a cryptographic task in which two physically separated, mistrustful parties wish to generate a fair coin-flip by communicating with each other. Chailloux and Kerenidis (2009) designed quantum protocols that guarantee coin-flips with near optimal bias away from uniform, even when one party deviates arbitrarily from the protocol. The probability of any outcome in these protocols is provably at most for any given . However, no explicit description of these protocols is known; in fact, the smallest bias achieved by known explicit protocols is (Ambainis 2001). We take a computational optimization approach, based mostly on convex optimization, to the search for simple and explicit quantum strong coin-flipping protocols. We present a search algorithm to identify protocols with low bias within a natural class, protocols based on bit-commitment (Nayak and Shor in Phys Rev A 67(1):012304, 2003). The techniques we develop enable a computational search for protocols given by a mesh over the corresponding parameter space. We conduct searches for four-round and six-round protocols with bias below each of varying dimension which include the best known explicit protocol (with bias ). After checking over protocols, a task which would be infeasible using semidefinite programming alone, we conjecture that the smallest achievable bias within the family of protocols we consider is .