A search for quantum coin-flipping protocols using optimization techniques
type: Item
instance of: scholarly article
title: A search for quantum coin-flipping protocols using optimization techniques
zbMATH Open document ID: 1353.81040
author: Ashwin Nayak
author: Jamie Sikora
author: Levent Tunçel
published in: Mathematical Programming. Series A. Series B
publication date: 2016-04-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1403.0505
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, whic…
Mathematics Subject Classification ID: 81P94
Mathematics Subject Classification ID: 90-08
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 81P68
zbMATH DE Number: 6562701
zbMATH Keywords: semidefinite programming
zbMATH Keywords: quantum coin-flipping
zbMATH Keywords: computational optimization
reviewed by: Carlos Pedro Gonçalves
describes a project that uses: SeDuMi
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2126146705
arXiv ID: 1403.0505
cites work: A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias
cites work: Quantum bit escrow
cites work: A new protocol and lower bounds for quantum coin flipping
cites work: Quantum cryptography: public key distribution and coin tossing
cites work: Quantum Complexity Theory
cites work: Optimal Quantum Strong Coin Flipping
cites work: Optimal Bounds for Quantum Bit Commitment
cites work: Q3549656
cites work: Weak coin flipping with small bias
cites work: Unconditional security in quantum cryptography
cites work: Optimal Counterfeiting Attacks and Generalizations for Wiesner’s Quantum Money
cites work: Q2706552
cites work: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
cites work: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
cites work: Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
cites work: Strong duality and minimal representations for cone optimization
cites work: Q3671875
cites work: Handbook of semidefinite programming. Theory, algorithms, and applications
DOI: 10.1007/S10107-015-0909-Y
description: scientific article; zbMATH DE number 6562701