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 2032980094 2015253075 1980351200
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. Recently, Frumkin (9) pointed out that none of the well-known algorithms that transform an integer matrix into Smith (16) or Hermite (12) normal form is known to be polynomially bounded in its running time. In fact, Blankinship (3) noticed--as an empirical fact--that intermediate numbersmaybecome quite large during standard calculations Of these canonical forms. Here we present new algorithms in which both the number of algebraic operations and the number of (binary) digits of all intermediate numbers are bounded by polynomials in the length of the input data (assumed to be encoded in binary). These algorithms also find the multiplier-matrices K, U' and K' such thatAK and U'AK' are the Hermite and Smith normal forms of the given matrix A. This provides the first proof that multipliers with small enough entries exist. 1. Introduction. Every nonsingular integer matrix can be transformed into a lower triangular integer matrix using elementary column operations. This was shown by Hermite ((12), Theorem 1 below). Smith ((16), Theorem 3 below) proved that any integer matrix can be diagonalized using elementary row and column operations. The Smith and Hermite normal forms play an important role in the study of rational matrices (calculating their characteristic equations), polynomial matrices (determining the latent roots), algebraic group theory (Newman 15)), system theory (Heymann and Thorpe (13)) and integer programming (Garfi!akel and Nemhauser (10)). Algorithms that compute Smith andHermite normal forms of an integer matrix are given (among others) by Barnette and Pace (1), Bodewig (5), Bradley (7), Frumkin (9) and Hu (14). The methods of Hu, Bodewig and Bradley are based on the explicit calculation of the greatestcommon divisor (GCD) and a set of multiplierswhereas other algorithms ((1)) perform GCD calculations implicitly. As Frumkin (9) pointed out, none of these algorithms is known to be polynomial. In transforming an integer matrix into Smith or Hermite normal form using known techniques, the number of digits of intermediate numbers does not appear to be bounded by a polynomial in the length of the input data as was pointed out by Blankinship (3), (4-1 and Frumkin (9). In this paper we prove the results announced in [13]. Let G be a semi- simple, simply connected algebraic group defined over an algebraically closed field k. Let T be a maximal torus, B a Bore1 subgroup, B 3 T. Let W be the Weyl group of G. Let R (resp. R+ ) be the set of roots (resp. positive roots) relative to T (resp. B). Let S be the set of simple roots in R+. Let P be a maximal parabolic subgroup in G with associated fundamental weight w. Let W, be the Weyl group of P, and Wp be the set of minimal representatives of W W,. For w E Wp, let e(w) be the point and X(w) the Schubert variety in G P associated to w. In this paper we deter- mine the multiplicity m,(w) of X(w) at e(z), where e(z) E X(w), for all minuscule P’s and also for P = Pgn, G being of type C, (here Pun denotes the maximal parabolic subgroup obtained by omitting a,). The determina- tion of m,(w) is done as follows. Let L be the ample generator of Pic(G P). A basis has been constructed for @(X(w), L”) in terms of standard monomials on X(w) (cf. [ 16, 11 I). Let U; be the unipotent subgroup of G generated by U-,, ?ET(R+ - Rp+) (here R, denotes the set of roots of P and U, denotes the unipotent subgroup of G, associated to tl E R). Then U; e(r) gives an affme neighborhood of e(z) in G P. Let A, be the affine algebra of U, e(z) and A,.. = A, &, where & is the ideal of elements of A, that vanish on X(w) n U; e(z). Let M,,, be the maximal ideal in A, H, corresponding to e(r). Then using the results of [ 16, 111, we obtain a basis of M;, &f:,+,,’ . This enables us to obtain an inductive formula for F,,,, the Hilbert polynomial of X(w) at e(T) (cf. Corollaries 3.8 and 4.11), and also express m, (w) in terms of m, (w’)‘s, X(w’)‘s being the Schubert divisors in X(w) such that e(T)E X(w’) (cf. Theorems 3.7 and 4.10). Using this we We build a theory of black box groups, and apply it to matrix groups over finite fields. Elements of a black box group are encoded by strings of uniform length and group operations are performd by an oracle. Subgroups are given by a list of generators. We prove that for such subgroups, membership and divisor of the order are in NPB. (B is the group box oracle.) Under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be in NPB and thus in NPB ∩ NPB.