Details of Grant 

EPSRC Reference:	GR/R87406/01
Title:	Quantum Computing and Algorithms in Group Theory
Principal Investigator:	Duncan, Dr A
Other Investigators:	Braunstein, Professor SL Rees, Professor SE
Researcher Co-Investigators:
Project Partners:
Department:	Mathematics and Statistics
Organisation:	Newcastle University
Scheme:	Standard Research (Pre-FEC)
Starts:	01 April 2002	Ends:	31 July 2005	Value (£):	201,457
EPSRC Research Topic Classifications:	Algebra & Geometry New & Emerging Comp. Paradigms
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:
Summary on Grant Application Form
We proposed to develop quantum algorithms in the setting of computational group theory. We shall survey existing quantum algorithms (based mostly on Shor's and Grover's algorithms) to see how these may be applied to problems in computational group theory. We shall go on to develop new quantum models to address problems of group theory. We shall consider in particular algorithms for the word problem in free groups, where previous results suggest we should expect advances. This should lead to consideration of algorithms for other problems in finitely presented groups: for example the conjugacy or power problem. The eventual aim is an efficient quantum version of Makanin's algorithm ffor equations in a free group (or semigroup). Routines for integer matrix manipulation, which play a large part in computational group theory as well as having many other applications, will also be considered. Once we have developed new quantum algorithms we shall compare their complexity to traditional procedures. This is of particular interest where random or parallel algorithms address the problem in question. We shall develop computer simulations for quantum algorithms and use these compare them experimentally to traditional methods. Once we have established a reasonable library of quantum algorithms we shall try to understand how to transform standard algorithms into corresponding fast quantum algorithms.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.ncl.ac.uk