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.
quant-ph Preprint Server
Quantum computing links
Home Page of John Watrous
Extended references on quantum computing
Journal of Quantum Computing
Research In Quantum Computing and Information
References for Richard Jozsa
Peter Shor - Home Page
Louis H. Kauffman
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
Home Page of Persi Diaconis
Groups and Computation Conference, Columbus, Ohio
Permutation group algorithms via black box recognition algorithms
Back to my home page
Back to Newcastle University School of Mathematics and Statistics