Quantum Computation: Foundations, Security, Cryptography and Group Theory

Lead Research Organisation: Newcastle University
Department Name: Mathematics and Statistics


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.


10 25 50
publication icon
Blok R (2012) Expander graphs from Curtis-Tits groups in Journal of Combinatorial Theory, Series A

publication icon
Carbone L (2012) Groups acting simply transitively on vertex sets of hyperbolic triangular buildings in LMS Journal of Computation and Mathematics

publication icon
CIOBANU L (2013) RAPID DECAY IS PRESERVED BY GRAPH PRODUCTS in Journal of Topology and Analysis

publication icon
Diekert V (2012) Cyclic rewriting and conjugacy problems in Groups - Complexity - Cryptology

publication icon

publication icon
Duncan A (2010) Automorphisms of partially commutative groups I: Linear subgroups in Groups, Geometry, and Dynamics

publication icon

publication icon
Lawson M (2010) A NONCOMMUTATIVE GENERALIZATION OF STONE DUALITY in Journal of the Australian Mathematical Society

Description 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)