Physics of Life: Flipping a Quantum Coin

Quantum computing (QC) is a radically new approach to computation. Classical computing is based on the idea of bits: strings of 1's and 0's on which we do arithmetic operations. QC, however, is based on quantum bits, qubits, and new physical operations. Despite the complexity of QC, we contend that it is an appropriate and useful topic for undergraduate physics students. In this talk, we present our results from three small QC projects relating to flipping coins. In the first, we investigate the results of a secret coin flip and use QC to guess whether the coin landed on heads or tails. In the second, we determine whether a given coin is fair or unfair using only a single qubit ( instead of multiple bits). In the third, we explore how quantum communication can alleviate dishonest player biases in coin flipping cryptographic primitives.Quantum computing (QC) is a radically new approach to computation. Classical computing is based on the idea of bits: strings of 1's and 0's on which we do arithmetic operations. QC, however, is based on quantum bits, qubits, and new physical operations. Despite the complexity of QC, we contend that it is an appropriate and useful topic for undergraduate physics students. In this talk, we present our results from three small QC projects relating to flipping coins. In the first, we investigate the results of a secret coin flip and use QC to guess whether the coin landed on heads or tails. In the second, we determine whether a given coin is fair or unfair using only a single qubit ( instead of multiple bits). In the third, we explore how quantum communication can alleviate dishonest player biases in coin flipping cryptographic primitives.

Jan 1, 20199 citations

Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment

André Chailloux, Iordanis Kerenidis

Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the $30$ th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than $1/\sqrt{2}$ [A. Kitaev, Presentation at the $6$ th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to $1/\sqrt{2}$ . More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2+\varepsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\varepsilon)$ . The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately $\gamma \approx 0.739$ , improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to $\gamma$ . More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2 + \varepsilon$ in order to achieve a quantum bit commitment protocol with cheating probability $\gamma + O(\varepsilon)$ . To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.Coin flipping and bit commitment are two fundamental cryptographic primitives with numerous applications. Quantum information allows for such protocols in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum coin flipping and bit commitment protocol by Ambainis achieved a cheating probability of at most 3/4 [A. Ambainis, Proceedings of the $30$th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than $1/\sqrt{2}$ [A. Kitaev, Presentation at the $6$th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to $1/\sqrt{2}$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2+\varepsilon$ in order to achieve a strong coin flipping protocol with cheating probability $1/\sqrt{2}+O(\varepsilon)$. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately $\gamma \approx 0.739$, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to $\gamma$. More precisely, we show how to use any weak coin flipping protocol with cheating probability $1/2 + \varepsilon$ in order to achieve a quantum bit commitment protocol with cheating probability $\gamma + O(\varepsilon)$. To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

SIAM Journal on ComputingJan 1, 20172 citations

Quantum Physics and Life

Ingemar T. Ernberg, Göran Johansson, Tomas Lindblad +2 more

Oct 31, 20228 citations

Physics and the Riddle of Life

Max Ferdinand Perutz

Comprehensive biochemistryJan 1, 19901 citation

Quantum Coin Flipping: and Circuit Design Problems in Distributed Quantum Computing

Roy van Houte

Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a complex semidefinite optimization problem. In this master thesis we show new explicit bounds in multiparty quantum coin flipping, we investigate how to explicitly formulate these problem in a standard form, we show that a fair coin flip results in the lowest possible bias and we determine more measures of the quality of a protocol. Furthermore, this master thesis presents a rigorous and detailed mathematical description of semidefinite optimization, quantum information theory and quantum coin flipping. This thesis also includes an article written together with J. Mulderij, T. Attema, I. Chiscop and F. Phillipson on distributed quantum computing. In this article, we pose new questions and formulate integer linear programs that solve to find optimal assignment of qubits to computers for a given network of quantum computers and quantum algorithm.Quantum coin flipping is a cryptographic primitive in which two or more parties that do not trust each other want establish a fair coin flip. These parties are not physically near each other and use quantum communication channels to interact. A quality of protocols is measured by the best possible cheating strategy, which is the solution of a complex semidefinite optimization problem. In this master thesis we show new explicit bounds in multiparty quantum coin flipping, we investigate how to explicitly formulate these problem in a standard form, we show that a fair coin flip results in the lowest possible bias and we determine more measures of the quality of a protocol. Furthermore, this master thesis presents a rigorous and detailed mathematical description of semidefinite optimization, quantum information theory and quantum coin flipping. This thesis also includes an article written together with J. Mulderij, T. Attema, I. Chiscop and F. Phillipson on distributed quantum computing. In this article, we pose new questions and formulate integer linear programs that solve to find optimal assignment of qubits to computers for a given network of quantum computers and quantum algorithm.

Jan 1, 20201 citation

30

th Annual ACM Symposium on Theory of Computing, Washington, DC, IEEE Computer Society, 2001]. On the other hand, Kitaev showed that no quantum coin flipping or bit commitment protocol can have cheating probability less than

1/\sqrt{2}

[A. Kitaev, Presentation at the

6

th Workshop on Quantum Information Processing (QIP), 2003]. Closing these gaps has been one of the important open questions in quantum cryptography. In this paper, we resolve both questions. First, we present a quantum strong coin flipping protocol with cheating probability arbitrarily close to

1/\sqrt{2}

. More precisely, we show how to use any weak coin flipping protocol with cheating probability

1/2+\varepsilon

in order to achieve a strong coin flipping protocol with cheating probability

1/\sqrt{2}+O(\varepsilon)

. The optimal quantum strong coin flipping protocol follows from our construction and the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Second, we provide the optimal bound for quantum bit commitment. On the one hand, we show a lower bound of approximately

\gamma \approx 0.739

, improving Kitaev's lower bound. On the other hand, we present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to

\gamma

. More precisely, we show how to use any weak coin flipping protocol with cheating probability

1/2 + \varepsilon

in order to achieve a quantum bit commitment protocol with cheating probability

\gamma + O(\varepsilon)

. To obtain the final protocol, we then use the optimal quantum weak coin flipping protocol described by [C. Mochon, arXiv:0711.4114, 2007]. Unlike the previous protocol for coin flipping, our protocol uses quantum effects beyond the weak coin flip. To stress this fact, we additionally show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.