Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography.[1]Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols,[2] e.g. Quantum Byzantine agreement.
Unlike other types of quantum cryptography (in particular, quantum key distribution), quantum coin flipping is a protocol used between two users who do not trust each other.[3] Consequently, both users (or players) want to win the coin toss and will attempt to cheat in various ways.[3]
It is known that if the communication between the players is over a classical channel, i.e. a channel over which quantum information cannot be communicated, then one player can (in principle) always cheat regardless of which protocol is used.[4] We say in principle because it might be that cheating requires an unfeasible amount of computational resource. Under standard computational assumptions, coin flipping can be achieved with classical communication.
The most basic figure of merit for a coin-flipping protocol is given by its bias, a number between and . The bias of a protocol captures the success probability of an all-powerful cheating player who uses the best conceivable strategy. A protocol with bias means that no player can cheat. A protocol with bias means that at least one player can always succeed at cheating. Obviously, the smaller the bias better the protocol.
When the communication is over a quantum channel, it has been shown that even the best conceivable protocol can not have a bias less than .[5][6]
Consider the case where each player knows the preferred bit of the other. A coin flipping problem which makes this additional assumption constitutes the weaker variant thereof called weak coin flipping (WCF). In the case of classical channels this extra assumption yields no improvement. On the other hand, it has been proven that WCF protocols with arbitrarily small biases do exist.[7][8] However, the best known explicit WCF protocol has bias .[9]
Although quantum coin flipping offers clear advantages over its classical counterpart in theory, accomplishing it in practice has proven difficult.[3][10]
^Blum, Manuel (1983-01-01). "Coin flipping by telephone a protocol for solving impossible problems". ACM SIGACT News. 15 (1): 23–27. doi:10.1145/1008908.1008911. ISSN 0163-5700. S2CID 19928725.
^Oded., Goldreich (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. ISBN 9780521791724. OCLC 45093786.
^ abcStuart Mason Dambort, "Heads or tails: Experimental quantum coin flipping cryptography performs better than classical protocols", Phys.org, March 26, 2014
^Cleve, R. (1986-11-01). "Limits on the security of coin flips when half the processors are faulty". Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. ACM. pp. 364–369. doi:10.1145/12130.12168. ISBN 0897911938. S2CID 17394663.
^A. Kitaev, Quantum Coin Flipping, Quantum Information Processing Workshop, Mathematical Sciences Research Institute, University of California, Berkeley, 2003.
^Ambainis, A.; Buhrman, H.; Dodis, Y.; Rohrig, H. (2004). "Multiparty quantum coin flipping". Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004. IEEE. pp. 250–259. arXiv:quant-ph/0304112. doi:10.1109/ccc.2004.1313848. ISBN 0769521207. S2CID 3261413.
^C. Mochon, Quantum Weak Coin Flipping with Arbitrarily Small Bias, preprint, arXiv:0711.4114, 2007.
^Aharonov, Dorit; Chailloux, André; Ganz, Maor; Kerenidis, Iordanis; Magnin, Loïck (January 2016). "A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias". SIAM Journal on Computing. 45 (3): 633–679. arXiv:1402.7166. doi:10.1137/14096387x. ISSN 0097-5397. S2CID 7519640.
^Mochon, Carlos (2005). "Large family of quantum weak coin-flipping protocols". Physical Review A. 72 (2): 022341. arXiv:quant-ph/0502068. Bibcode:2005PhRvA..72b2341M. doi:10.1103/PhysRevA.72.022341. S2CID 46533337.
^Vivek R and Dr. J. Roopchand, “Emerging Trends in Quantum Cryptography – A Survey", International Journal of Computer Technology and Applications, August 2012
and 27 Related for: Quantum coin flipping information
trusted third party, is called the coinflipping problem in cryptography. Quantumcoinflipping uses the principles of quantum mechanics to encrypt messages...
relativistic protocols for coinflipping and bit-commitment have been shown by Kent. Unlike quantum key distribution, quantumcoinflipping is a protocol that...
Quantum optics is a branch of atomic, molecular, and optical physics dealing with how individual quanta of light, known as photons, interact with atoms...
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence...
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the...
Quantum information science is a field that combines the principles of quantum mechanics with information theory to study the processing, analysis, and...
In quantum information theory, a quantum channel is a communication channel which can transmit quantum information, as well as classical information....
Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum...
A quantum computer is a computer that takes advantage of quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles...
In quantum computing, the threshold theorem (or quantum fault-tolerance theorem) states that a quantum computer with a physical error rate below a certain...
Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation...
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier...
Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions...
The term was coined by John Preskill in 2012, but the concept dates to Yuri Manin's 1980 and Richard Feynman's 1981 proposals of quantum computing. Conceptually...
In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit...
Quantum programming is the process of designing or assembling sequences of instructions, called quantum circuits, using gates, switches, and operators...
This list contains quantum processors, also known as quantum processing units (QPUs). Some devices listed below have only been announced at press conferences...
Quantum machine learning is the integration of quantum algorithms within machine learning programs. The most common use of the term refers to machine learning...
Quantum information is the information of the state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated...
Quantum simulators permit the study of a quantum system in a programmable fashion. In this instance, simulators are special purpose devices designed to...
substructure. The electron's mass is approximately 1/1836 that of the proton. Quantum mechanical properties of the electron include an intrinsic angular momentum...
Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational...
A quantum machine is a human-made device whose collective motion follows the laws of quantum mechanics. The idea that macroscopic objects may follow the...
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple...
Gilles (1984). "Quantum cryptography: Public key distribution and coin tossing". Theoretical Computer Science. Theoretical Aspects of Quantum Cryptography...
simultaneously, a property that is fundamental to quantum mechanics and quantum computing. The coining of the term qubit is attributed to Benjamin Schumacher. In the...
Quantum key distribution (QKD) is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. It...
Global Information
