** 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

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.

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)

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.

Extended references on quantum computing

Research In Quantum Computing and Information

Work Done in Parallel Algorithms and Complexity

Parallel Random Access Machine (PRAM) Model Emulator Home Page

Gene Cooperman:
*Towards a practical, theoretically sound algorithm for random generation in finite groups*

Groups and Computation Conference, Columbus, Ohio

Permutation group algorithms via black box recognition algorithms

Back to Newcastle University School of Mathematics and Statistics