From Non-Abelian Anyons to Quantum Computation to Coin-Flipping by Telephone

Citation

Mochon, Carlos (2005) From Non-Abelian Anyons to Quantum Computation to Coin-Flipping by Telephone. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/7JS5-VE50. https://resolver.caltech.edu/CaltechETD:etd-05112005-132038

Abstract

Following their divorce, Alice and Bob would like to split some of their possessions by flipping a coin. Unwilling to meet in person, and without a trusted third party, they must figure out a scheme to flip the coin over a telephone that guarantees that neither party can cheat.

The preceding scenario is the traditional definition of two-party coin-flipping. In a classical setting, without limits on the available computational power, one player can always guarantee a coin-flipping victory by cheating. However, by employing quantum communication it is possible to guarantee, with only information-theoretic assumptions, that neither party can win by cheating, with a probability greater than two thirds. Along with the description of such a protocol, this thesis derives a tight lower bound on the bias for a large family of quantum weak coin-flipping protocols, proving such a protocol optimal within the family. The protocol described herein is an improvement and generalization of one examined by Spekkens and Rudolph. The key steps of the analysis involve Kitaev's description of quantum coin-flipping as a semidefinite program whose dual problem provides a certificate that upper bounds the amount of cheating for each party.

In order for such quantum protocols to be viable, though, a number of practical obstacles involving the communication and processing of quantum information must be resolved. In the second half of this thesis, a scheme for processing quantum information is presented, which uses non-abelian anyons that are the magnetic and electric excitations of a discrete-group quantum gauge theory. In particular, the connections between group structure and computational power are examined, generalizing previous work by Kitaev, Ogburn and Preskill. Anyon based computation has the advantage of being topological, which exponentially suppresses the rate of decoherence and the errors associated with the elementary quantum gates. Though no physical systems with such excitations are currently known to exist, it remains an exciting open possibility that such particles could be either engineered or discovered in exotic two-dimensional systems.

Thesis Files