A search for quantum coin-flipping protocols using optimization techniques

Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Semidefinite programming (90C22)

Abstract: 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. The probability of any outcome in these protocols is provably at most

1 / s q r t 2 + d e l t a

for any given

d e l t a > 0

. However, no explicit description of these protocols is known, and the number of rounds in the protocols tends to infinity as

d e l t a

goes to 0. In fact, the smallest bias achieved by known explicit protocols is

1 / 4

(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, 2003) restricting to commitment states used by Mochon (2005). An analysis of the resulting protocols via semidefinite programs (SDPs) unveils a simple structure. For example, we show that the SDPs reduce to second-order cone programs. We devise novel cheating strategies in the protocol by restricting the semidefinite programs and use the strategies to prune the search. The techniques we develop enable a computational search for protocols given by a mesh over the parameter space. The protocols have up to six rounds of communication, with messages of varying dimension and include the best known explicit protocol (with bias 1/4). We conduct two kinds of search: one for protocols with bias below 0.2499, and one for protocols in the neighbourhood of protocols with bias 1/4. Neither of these searches yields better bias. Based on the mathematical ideas behind the search algorithm, we prove a lower bound on the bias of a class of four-round protocols.

Review text

The article addresses a family of coin-flipping protocols based on bit-commitment so that a balance between the two parties is reached in order to minimize the bias one of the player's can achieve by cheating. The authors introduce cheating strategies as semidefinite programs (SDPs) and develop an algorithm for finding protocols with low bias, addressing approaches to make the search for protocols computationally more efficient. In terms of organization of the article, Section 1 introduces main concepts and notation relevant for the work, including: elements from linear algebra (Subsection 2.1), convex analysis (Subsection 2.2), semidefinite programming (Subsection 2.3) and quantum information (Subsection 2.4). Section 3 introduces the quantum coin-flipping problem and protocols, in particular: the concept of strong coin-flipping (Definition 1), bias (Definition 2) and a coin-flipping protocol based on bit-commitment (Definition 3). Section 4 addresses cheating strategies as semidefinite programs (SDPs) and Section 5 introduces heuristics used to speed up protocol search including protocol filter (Subsection 5.1) and taking advantage of protocol symmetry (see Subsection 5.2). Section 6 introduces the main algorithm and Section 7 presents main numerical results. Section 8 concludes the article with final remarks. The algorithm proposed by the authors involves a computational search for protocols with low bias given by a mesh over the parameter space, specified by a four-tuple of quantum states. The model iterates through a fine mesh of such four-tuples, computing the bias of the resulting protocols. The mesh is designed so that it makes it easier to exploit the protocol symmetry greatly reducing the number of protocols to be tested and making the problem computationally feasible. The protocol symmetry was one of the major factors in complexity reduction. This symmetry corresponds to an equivalence between the protocols due to symmetry in the states used in them, which allows the identification of states under which the bias remains unchanged, allowing the authors to prune the search space of parameters needed to specify a protocol in the family under scrutiny, reducing the time required for searching. For instance, as reported by the authors, in some cases only 1 in every 1,000,000 protocols needed to be checked due to symmetry-based pruning. The other heuristic, employed by the authors, used cheating strategies for filtering, namely, it uses sequences of cheating strategies for dishonest players that is given by a closed form expression determined by the four states, if the bias for any of these strategies is greater than \(1/4\) for any four-tuple, they rule out the protocol as a candidate for optimal control. The goal for the searches was therefore to find protocols within the mesh with bias of at most 1/4 minus a small constant. The filtering and symmetry pruning heuristics allowed, for instance, as reported by the authors, to check \(2.74\times 10^16\) protocols in a matter of days. The search algorithm and heuristics, thus, constitute one of the major methodological contributions of the article. The work is of primary interest for those working with quantum information theory, quantum communication and quantum cryptography, however the work is also of interest for researchers involved in optimization in the quantum setting. Optimization in the quantum setting is a relevant research field for quantum game theory and quantum technologies, with possible future applications in quantum artificial intelligence and machine learning. Even though the article is focused on the quantum coin-flipping problem, the wider area of optimization in the quantum setting may also benefit from this work.

Recommendations

Cites work

Cited in

(7)

Describes a project that uses

Uses Software

SeDuMi

This page was built for publication: A search for quantum coin-flipping protocols using optimization techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263220)