Work In Progress

This page has not been updated since the end of the project in 2005

We are a group of people working on a 2001 EPSRC MathFIT proposal, entitled

Quantum Computing and Algorithms in Group Theory

The abstract of the research proposal is "We propose 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 for 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 to 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."

So far, the work completed has been to understand the group-theoretic aspects of quantum computing such as the hidden subgroup problem, and work such as Watrous' algorithm to find the order of a finite solvable group. This has been written up as the survey article below. We have also done some theoretical work on generalising the Deutsch-Jozsa algorithm to the nonabelian case (see the third article below). On the computing side of things, we are writing a quantum simulator in GAP and it is being integrated with a web-based simulator which has been developed at Fraunhofer FIRST in Berlin. The idea is to allow quantum registers to be arbitrary finite groups, rather than just qubits. Eventually this facility will be available online to simulate group-theoretic quantum algorithms on our cluster at Newcastle.

People Involved With The Project

Michael Batty (Newcastle)

Sam Braunstein (York)

Andrew Duncan (Newcastle)

Mark Lawson (Heriot-Watt)

Steve Linton (St. Andrews)

Sarah Rees (Newcastle)

Helge Rose (Fraunhofer FIRST, Berlin)

Andreas Schramm (Fraunhofer FIRST, Berlin)

Publications and Preprints

Quantum Algorithms In Group Theory by Michael Batty, Sam Braunstein, Andrew Duncan and Sarah Rees.
Contemporary Mathematics Volume 349 (2004), 1-62. Also available as Newcastle Preprint PUR 03,2 (2003) and quant-ph/0310133.
A survey article in quantum computing which emphasizes the interplay with group theory. We cover basic quantum computing, the Deutsch-Jozsa algorithm, Shor's algorithm, Grover's algorithm and Watrous' algorithm for finding the order of a black box solvable group.

A Generalised Deutsch-Jozsa Algorithm by Michael Batty and Sam Braunstein.
Newcastle Preprint PUR 03,3 (May 2003)
We find promises under which it can be decided whether a given function from a set to itself is constant, bipartite (i.e takes two values only, both with the same number of preimages) or "generalised balanced" in a number of queries logarithmic in the size of the set.

Extending The Promise of the Deutsch-Jozsa-Hoyer Algorithm for Finite Groups (quant-ph/0412067) by Michael Batty, Sam Braunstein and Andrew Duncan (December 2004).
Submitted to LMS JCM.
We give a general form of the Deutsch-Jozsa algorithm for a finite group which uses the non-abelian Fourier transform. Many other quantum algorithms are a special case of this. A more general form of balanced and constant functions is defined in terms of matrix entries of irreducible representations. The paper also deals with alternative characterisations of these definitions of constant and balanced, especially in finite abelian groups where there are connections with minimal polynomials over the rationals of roots of unity.

Work in progress (limited access only)

Links to Literature on Quantum Computing and Related Areas

Scott Aaronson: Quantum Lower Bound for the Collision Problem

Andris Ambainis, Richard Bonner, Rusins Freivalds and Arnold Kikusts: Probabilities To Accept Languages By Quantum Finite Automata

Laszlo Babai: Trading Group Theory For Randomness Proceedings of the 17th ACM Symposium On The Theory Of Computing (1985), 421-429.

Laszlo Babai: Local Expansion Of Vertex-Transitive Graphs and Random Generation In Finite Groups Proceedings of the 23rd ACM Symposium On The Theory Of Computing (1991), 164-174.

Laszlo Babai and Shlomo Moran: Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes Journal of Computer and Systems Sciences 36 2 (1988), 254-276.

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf: Quantum Lower Bounds by Polynomials In Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS '98) (1998) 352-361.

Andre Berthiaume and Gilles Brassard: Oracle Quantum Computing (a.k.a. The Quantum Challenge To Structural Complexity Theory ) Proceedings of the 7th Annual IEEE Symposium on Structure in Complexity Theory, June 1992, pp 132-137.

Gilles Brassard, Peter Hoyer and Alain Tapp: Quantum Algorithm for the Collision Problem

Gilles Brassard, Peter Hoyer and Alain Tapp: Quantum Counting

Gilles Brassard, Peter Hoyer, Michele Mosca and Alain Tapp: Quantum Amplitude Amplification and Estimation

Artur Ekert and Richard Jozsa Quantum Computation and Shor's Factoring Algorithm Rev. Mod. Phys. 68 (3) (1996), 733-753.

Katalin Friedl, Gabor Ivanyos, Frederic Magniez, Miklos Santha and Pranab Sen: Hidden Translation and Orbit Coset in Quantum Computing

Lov K Grover: A Fast Quantum Mechanical Algorithm for Database Search Proceedings of the 28th ACM Symposium on the Theory of Computing, 212-219.

Gabor Ivanyos, Frederic Magniez and Miklos Santha: Efficient Quantum Algorithms for Some Instances of the Non-Abelian Hidden Subgroup Problem

Richard Jozsa: Quantum Factoring, Discrete Logarithms and the Hidden Subgroup Problem

Richard Jozsa: Characterising Classes Of Functions Computable By Quantum Parallelism Proceedings of the Royal Society of London Series A (1991) 435, 563-574.

Elham Kashefi, Adrian Kent, Vlatko Vedral and Konrad Banaszek: A Comparison of Quantum Oracles

Alexei Yu Kitaev: Quantum Computations: Algorithms and Error Correction Russian Mathematical Surveys, 52 6 (1997), 1191-1249.

Greg Kuperberg: A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Laszlo Lovasz (translation: P. Gacs): Computation Complexity Graduate Lecture Notes (1994) available here .

Jumpei Niwa, Keili Matsumoto and Hiroshi Imai General Purpose Parallel Simulator for Quantum Computing

Nicholas T Ouellette: Quantum Computation

Wolfgang Polak and Eleanor Rieffel: An Introduction To Quantum Computing For Non-Physicists Preprint (1998).

Yaoyun Shi: Quantum Lower Bounds for the Collision and Element Distinctness Problems

Peter W. Shor: Algorithms For Quantum Computation: Discrete Logs and Factoring Proceedings of the 35th Symposium on the Foundations of Computer Science (1994), 124-134.

Peter W. Shor: Polynomial-Time Algorithms for Prime Factorisation and Discrete Logarithms on a Quantum Computer SIAM Journal on Computing 26 5 (1997), 1484-1509.

Daniel R. Simon: On The Power Of Quantum Computation Proceedings of the 35th Annual Symposium on Foundations of Computer Science.

Julia Wallace: A Brief History Of Quantum Computation

John Watrous: Succinct Quantum Proofs For Properties Of Finite Groups Proceedings of the 41st Annual Symposium on Foundations of Computer Science (2000), 537-546.

John Watrous: Quantum Algorithms For Solvable Groups Proceedings of the 33rd ACM Symposium on Theory of Computing (2001), 60-67.

Quantum Computing and Algorithms in Group Theory

People Involved With The Project

Links to Literature on Quantum Computing and Related Areas

Other Links

Quantum Computing

Parallel Computing

Algorithms in Group Theory