A search for quantum coin-flipping protocols using optimization techniques (Q263220)

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.