# Quantum Computation: Foundations, Security, Cryptography and Group Theory

Lead Research Organisation:
Newcastle University

Department Name: Mathematics and Statistics

### Abstract

Quantum computation is based on computers which operate on the level of quantum mechanics rather than classical electronics. The advantage of this is that in quantum mechanics entities can be simultaneously in many different positions at once: and this allows states of a quantum computer to behave in some ways like a stack of parallel states. This parallel stack does not unfortunately come without strings and, because of the physics of quantum mechanics, it is very difficult to find out what is in any such stack at a particular time: so reading the output of a quantum computer is not easy. Some powerful quantum algorithms have been developed: for example by Shor to factor integers much faster than convential algorithms can. However the number of such algorithms that we know is not growing very rapidly. One reason for this is that we do not have a systematic understanding of how to build up quantum computing algorithms and indeed do not have a comprehensive library of algorithms for very basic functions and procedures for building from them. The main aims of this project are to construct such a systematic foundation for quantum computation and to establish procedures for basic processes.We shall test our success in these objectives by attempting to construct algorithms for problems which arise in group theory. This area of mathematics provides an endless array of algorithmic problems at all levels of difficulty, so is a good test bed for a potential computation system. We shall also consider how to extend the analysis of cryptographic systems from classical schemes to quantum schemes. In particular this is expected to allow us to build an automated voting process which cannot be tampered with or broken into, by the people who run it.

### Organisations

### Publications

Blok R
(2012)

*Expander graphs from Curtis-Tits groups*in Journal of Combinatorial Theory, Series A
Carbone L
(2012)

*Groups acting simply transitively on vertex sets of hyperbolic triangular buildings*in LMS Journal of Computation and Mathematics
CIOBANU L
(2013)

*RAPID DECAY IS PRESERVED BY GRAPH PRODUCTS*in Journal of Topology and Analysis
Diekert V
(2012)

*Cyclic rewriting and conjugacy problems*in Groups - Complexity - Cryptology
DUNCAN A
(2012)

*AUTOMORPHISMS OF PARTIALLY COMMUTATIVE GROUPS II: COMBINATORIAL SUBGROUPS*in International Journal of Algebra and Computation
Duncan A
(2010)

*Automorphisms of partially commutative groups I: Linear subgroups*in Groups, Geometry, and Dynamics
Gray R
(2014)

*A strong geometric hyperbolicity property for directed graphs and monoids*in Journal of Algebra
GRAY R
(2013)

*QUASI-ISOMETRY AND FINITE PRESENTATIONS OF LEFT CANCELLATIVE MONOIDS*in International Journal of Algebra and Computation
Holt D
(2012)

*Generalising some results about right-angled Artin groups to graph products of groups*in Journal of Algebra
Lawson M
(2010)

*A NONCOMMUTATIVE GENERALIZATION OF STONE DUALITY*in Journal of the Australian Mathematical SocietyDescription | Many questions which arise from scientific or technological problems involve solving systems of equations. Algorithms for solving systems of equations sample or describe elements of the set of all solutions, and this involves determining which sequences of symbols in some alphabet give solutions and which do not. In this sense the solutions of a system of equations may be regarded as a language, in the given alphabet. Lawson (Heriot-Watt) and co-workers have associated to certain algebras, naturally occurring in many problems, mathematical structures called Cunz C*-algebras. These algebras are important in the theory of quantum mechanics and this opens one possible way to the development of a theory of languages in quantum computation. In Newcastle, Duncan and Rees and Vdovina investigated properties of partially commutative structures. In classical computation partially commutative monoids are used to model concurrent processes, and the parallel nature of quantum computation makes this a natural starting point in the search for models of quantum processing. Rees and colleagues developed combinatorial mechanisms to derive the rapid decay (a property related to the algorithmic properties of a group) of certain groups with a partially commutative structure. From the point of view of concurrent processing it is thus important to understand the automorphisms of partially commutative structures. Duncan and collaborators gave a description of the structure of the automorphism group of a partially commutative group in terms of certain substructures related to the graph. Automorphism groups describe the possible structure preserving maps between groups and are therefore useful in the understanding of concurrent processes described in terms of partially commutative groups. Vdovina and others gave polynomial estimates for solutions of equations in free groups. Such estimates are important in the proof of the NP-hardness of algorithms solving these equations. |

Exploitation Route | We believe that further progress in understanding quantum computation will arise from a deeper understanding of the physical basis of computing. This has to be rooted in quantum mechanics and, mathematically, our work suggests that C*-algebras provide the most natural framework for achieving this. One fundamental question is how to quantize correctly the classical theory of automata. Our research has uncovered some of the key issues involved in answering this question which we plan to develop more fully in subsequent work. |

Sectors | Digital/Communication/Information Technologies (including Software) |