Quantum computing, quantum games and geometric algebra.

Abstract

Early researchers attempting to simulate complex quantum mechanical interactions on digital computers discovered that they very quickly consumed the computers’ available memory resources, because the state space of a quantum system typically grows exponentially with problem size. Consequently, Richard Feynman proposed in 1982 that perhaps the only way to simulate complex quantum mechanical situations was by simulating them on some quantum mechanical system. Quantum computers attempt to exploit this idea incorporating the special properties of quantum mechanics, such as the superposition of states and entanglement, into a computing device. Two key algorithms have been discovered which would run on this new type of computer, Shor’s factorization algorithm discovered in 1994, which provides an exponential speedup over classical algorithms and Grover’s search algorithm in 1996, which provides a quadratic speedup. Following this in 1999 Meyer initiated the field of quantum game theory by introducing quantum mechanical states into the framework of classical game theory. In this thesis, we firstly investigate the phase estimation procedure, due to its importance as the basis for Shor’s factorization algorithm, for which a new error formula is found using an improved symmetrical definition of the error. Unlike other existing error formulas which require approximations in their derivation, our result is obtained analytically. The work on the phase estimation procedure then motivates the development of computer software written in the Java programming language, which can simulate the common algorithms and visually display their behavior on a circuit board type layout. The software is found useful in verifying the new error formula described above and to test ideas for new algorithms. Being written in Java, it is envisaged that it could be placed online and used as a learning tool for new students to the field. We then investigate the second key algorithm of quantum computing, the Grover search algorithm. It is already known that the Grover search is an SU(2) rotation but the idea is extended by deriving the three generators in terms of the two non-orthogonal basis vectors, representing the solution and initial states. We then demonstrate that the Grover search is equivalent to the precession of the polarization axis of a spin- 1/2 particle in a magnetic field. At this point we introduce geometric algebra (GA), because of its efficient implementation of rotations and its associated visual representation, and hence ideal to describe the Grover search process. It was found to provide a simple algebraic solution to the exact Grover search problem as well providing a simple visual picture describing the general solution to Meyer’s quantum penny flip game, which is a simple two-player quantum game based on the manipulation of a single qubit and hence closely analogous to the Grover search process. We then extend the work on quantum games developing two-player, three-player and N player quantum games in the context of an EPR type experiment, which has the advantage of providing a sound physical basis to quantum games avoiding the common criticism of other quantum game frameworks regarding the proper embedding of the classical game. Using the algebraic approach of GA, we solve the general N player game, without requiring the use of matrices which become unworkable for large N. Games based on non-factorisable joint probabilities were then also developed which provided a more general framework for both classical and quantum games, and allows the field of quantum games to be accessible to nonphysicists, as it does not employ Dirac’s bra-ket notation. In summary, several new results in the field of Quantum computing were produced, including an improved error formula for phase estimation [JMCL11b], a general solution to Meyer’s quantum penny flip game [CILVS09] and a paper producing quantum games from non-factorisable joint probabilities [CIA10], as well as an EPR framework for quantum games [JMCL11a], refer attached papers.