In this note we consider optimised circuits for implementing Shor's quantum factoring algorithm. First I give a circuit for which none of the about 2n qubits need to be initialised (though we still have to make the usual 2n measurements later on). Then I show how the modular additions in the algorithm can be carried out with a superposition of an arithmetic sequence. This makes parallelisation of Shor's algorithm easier. Finally I show how one can factor with only about 1.5n qubits, and maybe even fewer.
Also I understand that John Watrous @cite_4 has been using uniform superpositions of subgroups (and cosets) in his work on quantum algorithms for solvable groups. Thus he also used coset superpositions to represent elements of the factor group (and probably also to carry out factor group operations on them). In our case the overall group are the integers, the (normal) subgroup are the multiples of @math . The factor group who's elements we want to represent is @math . We now represent these elements by superpositions over the cosets of the form @math . A problem in our case is that we can do things only approximatively as the integers and the cosets are infinite sets.
@cite_4
1967088292
In this paper we give a polynomial-time quantum algorithm for computing orders of solvable groups. Several other problems, such as testing membership in solvable groups, testing equality of subgroups in a given solvable group, and testing normality of a subgroup in a given solvable group, reduce to computing orders of solvable groups and therefore admit polynomial-time quantum algorithms as well. Our algorithm works in the setting of black-box groups, wherein none of these problems have polynomial-time classical algorithms. As an important byproduct, our algorithm is able to produce a pure quantum state that is uniform over the elements in any chosen subgroup of a solvable group, which yields a natural way to apply existing quantum algorithms to factor groups of solvable groups.