Contemporary Mathematics

Quantum Hidden Subgroup Algorithms: A Mathematical Perspective

Samuel J. Lomonaco, Jr. and Louis H. Kauffman

Abstract. The ultimate objective of this paper is to create a stepping stone to the development of new quantum algorithms. The strategy chosen is to begin by focusing on the class of abelian quantum hidden subgroup algorithms, i.e., the class of abelian algorithms of the Shor/Simon genre. Our strategy is to make this class of algorithms as mathematically transparent as possible. By the phrase “mathematically transparent” we mean to expose, to bring to the surface, and to make explicit the concealed mathematical structures that are inherently and fundamentally a part of such algorithms. In so doing, we create symbolic abelian quantum hidden subgroup algorithms that are analogous to the those symbolic algorithms found within such software packages as Axiom, Cayley, Maple, Mathematica, and Magma.

As a spin-off of this effort, we create three different generalizations of Shor’s quantum factoring algorithm to free abelian groups of finite rank. We refer to these algorithms as wandering (or vintage ℤ_{Q}) Shor algorithms. They are essentially quantum algorithms on free abelian groups A of finite rank n which, with each iteration, first select a random cyclic direct summand ℤ of the group A and then apply one iteration of the standard Shor algorithm to produce a random character of the “approximating” finite group Ã = ℤ_{Q}, called the group probe. These characters are then in turn used to find either the order P of a maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}, or the entire hidden quotient group H_{φ}. An integral part of these wandering quantum algorithms is the selection of a very special random transversal ι_{μ} : Ã ⟶ A, which we refer to as a Shor transversal. The algorithmic time complexity of the first of these wandering Shor algorithms is found to be O (n^{2} (lg Q)^{3} (lg lg Q)^{n+1}).

2000 Mathematics Subject Classification. Primary 81-01, 81P68. Key words and phrases. Shor’s algorithm, hidden subgroup algorithms, quantum computa-

tion, quantum algorithms.

This effort partially supported by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-01-2-0522, the National Institute for Standards and Technology (NIST), and by L-O-O-P Fund Grant WADC2000. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright annotations thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Defense Advanced Research Projects Agency, the Air Force Research Laboratory, or the U.S. Government. (Copyright 2002 by authors. Reproduction of this article, in its entirety, is permitted for noncommercial purposes.)

\begin{matrix}c \\ ◯ \end{matrix}2002 by authors. Reproduction of this article, in its entirety, is permitted for non-commertial purposes.

Contents

Part 1. Preamble

1. Introduction

2. An example of Shor’s quantum factoring algorithm

3. Definition of the hidden subgroup problem (HSP) and hidden subgroup algorithms (HSAs)

Part 2. Algebraic Preliminaries

4. The Character Group

5. Fourier analysis on a finite abelian group

6. Implementation issues: Group algebras as Hilbert spaces

Part 3. QRand_{φ}(): The Progenitor of All QHSAs

7. Implementing P rob_{φ} (χ) with quantum subroutine QRand_{φ}()

Part 4. Vintage Simon Algorithms

8. Properties of the probability distribution P rob_{φ} (χ) when φ has a hidden subgroup

9. A Markov process M_{φ} induced by P rob_{φ}

10. Vintage Simon quantum hidden subgroup algorithms (QHSAs)

Part 5. Vintage Shor Algorithms

11. Vintage Shor quantum hidden subgroup algorithms(QHSAs)

12. Direct summand structure

13. Vintage Shor QHSAs with group probe Ã = ℤ_{Q}.

14. Finding Shor transversals for vintage ℤ_{Q} Shor algorithms

15. Maximal Shor transversals

16. Identifying characters of cyclic groups with points on the unit circle 𝕊^{1} in the complex plane ℂ.

17. Group norms

18. Vintage ℤ_{Q} Shor QHSAs (Cont.)

19. When are characters of Ã = ℤ_{Q} close to some character of a maximal cyclic subgroup ℤ_{P} of H_{φ}?

20. Summary of Vintage ℤ_{Q} Shor QHSAs

21. A cursory analysis of complexity

22. Two alternative vintage ℤ_{Q} Shor algorithms

Part 6. Epilogue

23. Conclusion

24. Acknowledgement

25. Appendix A. Continued fractions

26. Appendix B. Probability Distributions on Integers

References

Part 1. Preamble

1. Introduction

The ultimate objective of this paper is to create a stepping stone to the development of new quantum algorithms. The strategy chosen is to begin by focusing on the class of abelian quantum hidden subgroup algorithms (QHSAs), i.e., the class of abelian algorithms of the Shor/Simon genre. Our strategy is to make this class of algorithms as mathematically transparent as possible. By the phrase “mathematically transparent,” we mean to expose, to bring to the surface, and to make explicit the concealed mathematical structures that are inherently and fundamentally a part of such algorithms. In so doing, we create a class of symbolic abelian QHSAs that are analogous to those symbolic algorithms found within such software packages as Axiom, Cayley, Magma, Maple, and Mathematica.

During this mathematical analysis, the differences between the Simon and Shor quantum algorithms become dramatically apparent. This is in spite of the fact that these two share a common ancestor, namely, the quantum random group character generator QRand, described herein. While the Simon algorithm is a QHSA on finite abelian groups which produces random characters of the hidden quotient group, the Shor algorithm is a QHSA on free abelian finite rank groups which produces random characters of a group which “approximate” the hidden quotient group. It is misleading, and a frequent cause of much confusion in the open literature, to call them both essentially the same QHSA.

Surprisingly, these two very different algorithms touch an amazing array of different mathematical disciplines, from the obvious to the not-so-obvious, requiring the integration of many diverse fields of mathematics. Shor’s quantum factoring algorithm, for example, depends heavily on the interplay of two metrics on the unit circle 𝕊^{1}, namely the arclength metric Arc_{2π} and the chordal metric Chord_{2π}. This observation greatly simplifies the analysis of the Shor factoring algorithm, while at the same time revealing more of the structure concealed within the algorithm.

As a spin-off of this effort, we create three different generalizations of Shor’s quantum factoring algorithm to free abelian groups of finite rank, found in sections 20 and 22. We refer to these algorithms as wandering (or vintage ℤ_{Q}) Shor algorithms. They are essentially QHSAs on free abelian finite rank n groups A which, with each iteration, first select a random cyclic direct summand ℤ of the group A and then apply one iteration of the standard Shor algorithm to produce a random character of the “approximating” finite group Ã, called a group probe. These algorithms find either the order P of a maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}, or the entire hidden quotient group H_{φ}. An integral part of these wandering algorithms is the selection of a very special random transversal ι_{μ} : Ã ⟶ A, which we refer to as a Shor transversal. The algorithmic time complexity of the first of these wandering (or vintage ℤ_{Q}) algorithms is found in theorem 11 of section 21 to be O (n^{2} (lg Q)^{3} (lg lg Q)^{n+1}), where n denotes the fixed finite rank of the free abelian group A. Theorem 11 is based on the assumptions also found in section 21. This asymptotic bound is by no means the tightest possible.

Throughout this paper, it is assumed that the reader is familiar with the class of quantum hidden subgroup algorithms. For an introductions to this subject, please refer, for example, to any one of the references [8], [25], [26], [29], [33], [36], [43], [44]. This paper focuses, in particular, on the abelian hidden subgroup problem (HSP), with eye toward future work by the authors on the non-abelian HSP. There is a great deal of literature on the abelian HSP, for example, [5], [14], [25], [26], [27], [29], [35], [36], [43], [44], [45]. For literature on the non-abelian hidden subgroup problem, see for example, [16], [24], [14], [26], [33], [36], [38], [39], [41], [48].

2. An example of Shor’s quantum factoring algorithm

As an example of what we would like to make mathematically transparent, consider the following instance of Peter Shor’s quantum factoring algorithm. A great part of this paper is devoted to exposing and bringing to the surface the many concealed mathematical structures that are inherently and fundamentally part of this example.

Perhaps you see them? Perhaps you find them to be self evident? If you do, then you need read no more of this paper, although you are most certainly welcome to read on. If, on the other hand, the following example leaves you with a restless, uneasy feeling of not fully understanding what is really going on (i.e., of not fully understanding what concealed mathematical structures are lurking underneath these calculations), then you are invited to read the remainder of this paper.

Peter Shor’s quantum factoring algorithm reduces the task of factoring a positive integer N to first finding a random integer a relatively prime to N, and then next to determining the period P of the following function

\begin{matrix}ℤ & ⟶^{φ} & ℤ mod N \\ x & ⟼ & a^{x} mod N , \end{matrix}

where ℤ denotes the additive group of integers, and where ℤ mod N denotes the integers mod N under multiplication^{1}.

Since ℤ is an infinite group, Shor chooses to work instead with the finite additive cyclic group ℤ_{Q} of order Q = 2^{m}, where N^{2} ≤ Q < 2N^{2}, and with the “approximating” map

1A random integer a with gcd (a, N) = 1 is found by selecting a random integer, and then applying the Euclidean algorithm to determine whether or not it is relatively prime to N. If not, then the gcd is a non-trivial factor of N, and there is no need to proceed futher. However, this possibility is highly unlikely if N is large.

\begin{matrix}ℤ_{Q} & \underrightarrow{φ̃} & ℤ mod N \\ x & ⟼ & a^{x} mod N , & 0 ≤ x < Q \end{matrix}

Shor begins by constructing a quantum system with two quantum registers

|Left Register⟩ |Right Register⟩ ,

the left intended to hold the arguments x of φ̃, the right to hold the corresponding values of φ̃. This quantum system has been constructed with a unitary transformation

Uφ̃ : |x⟩ |1⟩ ⟼ |x⟩ |φ̃ (x)⟩

implementing the “approximating” map φ̃.

As an example, let us use Shor’s algorithm to factor the enormous integer

N = 21, assuming that a = 2 has been randomly chosen. Thus, Q = 2^{9} = 512.

Unknown to Peter Shor, the period is P = 6, and hence, Q = 6 · 85 + 2.

Shor proceeds by executing the following steps:

𝕊𝕋𝔼ℙ 0 Initialize

|ψ_{0}⟩ = |0⟩ |1⟩

𝕊𝕋𝔼ℙ 1 Apply the Fourier transform

F : |u⟩ ⟼ \frac{1}{\sqrt{512}} ∑_{x=0}^{511} ω^{ux} |x⟩

to the left register, where ω = exp(2πi/512) is a primitive 512-th root of unity, to obtain

|ψ_{1}⟩ = \frac{1}{\sqrt{512}} ∑_{x=0}^{511} |x⟩ |1⟩

𝕊𝕋𝔼ℙ 2 Apply the unitary transformation

Uφ̃ : |x⟩ |1⟩ ⟼ |x⟩ |2^{x} mod 21⟩

to obtain

|ψ_{2}⟩ = \frac{1}{\sqrt{512}} ∑_{x=0}^{511} |x⟩ |2^{x} mod 21⟩

𝕊𝕋𝔼ℙ 3 Once again apply the Fourier transform

F : |x⟩ ⟼ \frac{1}{\sqrt{512}} ∑_{y=0}^{511} ω^{xy} |y⟩

to the left register to obtain

|ψ_{3}⟩ = \frac{1}{512} ∑_{x=0}^{511} ∑_{y=0}^{511} ω^{xy} |y⟩ |2^{x} mod 21⟩ = \frac{1}{512} ∑_{y=0}^{511} |y⟩ (∑_{x=0}^{511} ω^{xy} |2^{x} mod 21⟩)

= \frac{1}{512} ∑_{y=0}^{511} |y⟩ |Υ (y)⟩

where

|Υ (y)⟩ = ∑_{x=0}^{511} ω^{xy} |2^{x} mod 21⟩

𝕊𝕋𝔼ℙ 4 Measure the left register. Then with Probability

P robφ̃ (y) = \frac{⟨ Υ (y) | Υ (y) ⟩}{(512)^{2}}

the state will “collapse” to |y⟩ with the value measured being the integer y, where 0 ≤ y < Q.

Let us digress for a moment to find a more usable expression for the probability distribution P robφ̃ (y).

|Υ (y)⟩ = ∑_{x=0}^{511} ω^{xy} |2^{x} mod 21⟩

= ∑_{x_{1}=0}^{85−1} ∑_{x_{0}=0}^{6−1} ω^{(6x_{1}+x_{0})y} |2^{6x_{1}+x_{0}} mod 21⟩ + ∑_{x_{0}=0}^{2−1} ω^{(6·85+x_{0})y} |2^{6·85+x_{0}} mod 21⟩

But the order of a = 2 modulo 21 is P = 6, i.e., P = 6 is the smallest positive integer such that 2^{6} = 1 mod 21. Hence, the above expression becomes

|Υ (y)⟩ = ( ∑_{x_{1}=0}^{84} ω^{6x_{1}y}) ∑_{x_{0}=0}^{5} ω^{x_{0}y} |2^{x_{0}} mod 21⟩ + ω^{6·85y} ∑_{x_{0}=0}^{1} ω^{x_{0}y} |2^{x_{0}} mod 21⟩

= ( ∑_{x_{1}=0}^{85} ω^{6x_{1}y}) ∑_{x_{0}=0}^{1} ω^{x_{0}y} |2^{x_{0}} mod 21⟩ + ( ∑_{x_{1}=0}^{84} ω^{6x_{1}y}) ∑_{x_{0}=2}^{5} ω^{x_{0}y} |2^{x_{0}} mod 21⟩

Since the kets { |2^{x_{0}} mod 21⟩ | 0 ≤ x_{0} < 6 } are all distinct, we have

⟨ Υ (y) | Υ (y) ⟩ = 2 | ∑_{x_{1}=0}^{85} ω^{6x_{1}y}|^{2} + 4 | ∑_{x_{1}=0}^{84} ω^{6x_{1}y}|^{2} .

After a little algebraic manipulation, we finally have the following expression for P robφ̃ (y):

P rob_{φ} (y) = \frac{⟨ Υ (y) | Υ (y) ⟩}{(512)^{2}} = \{ \begin{matrix}\frac{sin^{2}(\frac{πy}{128})+2 sin^{2}(\frac{πy}{256})}{(131072) sin^{2}(\frac{3πy}{256} )} & if y ≠ 0 or 256 \\ \frac{10923}{65536} & if y = 0 or 256 \end{matrix}

A plot of P robφ̃ (y) is shown in Figure 1.

Figure 1. A plot of Probφ̃(y).

The peaks in the above plot of P robφ̃ (y) occur at the integers

y = 0, 85, 171, 256, 341, 427.

The probability that at least one of these six integers will occur is quite high. It is actually 0.78^{+}. Indeed, the probability distribution has been intentionally engineered to make the probability of these particular integers as high as possible. And there is a good reason for doing so.

The above six integers are those for which the corresponding rational y/Q is “closest” to a rational of the form d/P. By “closest” we mean that

|\frac{y}{Q} − \frac{d}{P} | < \frac{1}{2Q} < \frac{1}{2P^{2}} .

In particular,

\frac{0}{512}, \frac{85}{512}, \frac{171}{512}, \frac{256}{512}, \frac{341}{512}, \frac{427}{512}

are rationals respectively “closest” to the rationals

\frac{0}{6}, \frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6} .

So by theorem 12 of Appendix A, the six rational numbers 0/6, 1/6, …, 5/6 are convergents of the continued fraction expansions of 0/512, 85/512, …, 427/512, respectively. Hence, each of the six rationals 0/6, 1/6, …, 5/6 can be found with the recursion given in Appendix A.

But ... , we are not searching for rationals of the form d/P. Instead, we seek only the denominator P = 6.

Unfortunately, the denominator P = 6 can only be gotten from the continued fraction recursion when the numerator and denominator of d/P are relatively prime. Given that the algorithm has selected one of the random integers 0, 85, …, 427, the probability that the corresponding rational d/P has relatively prime numerator and denominator is ϕ (6) /6 = 1/3, where ϕ (−) denotes the Euler totient function. So the probability of finding P = 6 is actually not 0.78^{+}, but is instead 0.23^{−}.

From Peter Shor’s perspective, the expression for the probability distribution is not known, since the period P is not known. All that Peter sees is a random integer y produced by the probability distribution P robφ̃. However, he does know an approximate lower bound for the probability that the random y produced by P robφ̃ is a “closest” one, namely the approximate lower bound 4/π^{2} = 0.41^{−}. Also, because^{2}

lim inf \frac{ϕ(N) ln ln N}{N} = e^{−γ} ,

where γ = 0.5772 ⋯ denotes Euler’s constant, he knows that

\frac{ϕ (P)}{P} = Ω (\frac{1}{lg lg N} ) .

Hence, if he repeats the algorithm O (lg lg N) times^{3}, he will obtain one of the desired integers y with probability bounded below by approximately 4/π^{2}.

However, once he has in his possession a candidate P′ for the actual period P = 6, the only way he can be sure he has the correct period P is to test P′ by computing 2^{P′} mod 21. If the result is 1, he is certain he has found the correct period P. This last part of the computation is done by the repeated squaring algorithm^{4}.

a^{P′} = ∏_{j} (a^{2^{j}} )^{P′_{j}} ,

2Please refer to reference [21, Theorem 328, Section 18.4].

3For even tighter asymptotic bounds, please refer to [9] and [37].

4By the repeated squaring algorithm, we mean the algorithm which computes a^{P′} mod N via the expression where P′ = ∑_{j} P′_{j}2^{j} is the radix 2 expansion of P′.

3. Definition of the hidden subgroup problem (HSP) and hidden subgroup algorithms (HSAs)

We now proceed by defining what is meant by a hidden subgroup problem (HSP) and a corresponding hidden subgroup algorithm. For other perspectives on HSPs, please refer to [29], [27], [35].

Definition 1. A map φ : A ⟶ S from a group A into a set S is said to have hidden subgroup structure if there exists a subgroup K_{φ} of A, called a hidden subgroup, and an injection ι_{φ} : A/K_{φ} ⟶ S, called a hidden injection, such that the diagram

A  ⟶^{φ}  S
ν ↘  ↗ ι_{φ}
A/K_{φ}

is commutative, where A/K_{φ} denotes the collection of right cosets of K_{φ} in A, and where ν : A ⟶ A/K_{φ} is the natural map of A onto A/K_{φ}. We refer to the group A as the ambient group and to the set S as the target set. If K_{φ} is a normal subgroup of A, then H_{φ} = A/K_{φ} is a group, called the hidden quotient group, and ν : A ⟶ A/K_{φ} is an epimorphism, called the hidden epimorphism.

The hidden subgroup problem can be expressed as follows:

Problem 1 (Hidden Subgroup Problem (HSP)). Given a map with hidden subgroup structure

φ : A ⟶ S ,

determine a hidden subgroup K_{φ} of A. An algorithm solving this problem is called a hidden subgroup algorithm (HSA).

The corresponding quantum form of this HSP is stated as follows:

Problem 2 (Hidden Subgroup Problem: Quantum Version). Let

φ : A ⟶ S

be a map with hidden subgroup structure. Construct a quantum implementation of the map φ as follows:

Let H_{A} and H_{S} be Hilbert spaces defined respectively by the orthonormal bases

{ |a⟩ | a ∈ A } and { |s⟩ | s ∈ S } ,

and let s_{0} = φ (0), where 0 denotes the identity of the ambient group A. Finally, let U_{φ} be the unitary transformation

\begin{matrix}U_{φ} : H_{A} ⊗ H_{S} & ⟶ & H_{A} ⊗ H_{S} \\ |a⟩ |s_{0}⟩ & ⟼ & |a⟩ |φ (a)⟩ \end{matrix} ,

Determine the hidden subgroup K_{φ} with bounded probability of error by making as few queries as possible of the blackbox U_{φ}. A quantum algorithm solving this problem is called a quantum hidden subgroup algorithm (QHSA).

In this paper, we focus on the abelian hidden subgroup problem (AHSP), i.e., the HSP with the ambient group A assumed to be a finitely generated abelian group, and where the image of the hidden morphism φ is a finite subset of S. (We will also on occasion assume that the entire set S is finite.)

In this paper we focus on the following two classes of abelian hidden subgroup problems:^{5}

• Vintage Simon AHSP. The ambient group A is finite and abelian.

• Vintage Shor AHSP. The ambient group A is free abelian of finite rank.

Notation Convention For notational simplicity, throughout this paper we will use additive notation for both the ambient group A and the hidden subgroup K_{φ}, and multiplicative notation for the hidden quotient group H_{φ} = A/K_{φ}.^{6}

Part 2. Algebraic Preliminaries

4. The Character Group

Let G be an abelian group. Then the character group (or, dual group) Ĝ of G is defined as the group of all morphisms of G into the group 𝕊^{1}, i.e.,

Ĝ = Hom (G, 𝕊^{1})

where 𝕊^{1} denotes the group of orientation preserving symmetries of the standard circle, and where multiplication on Ĝ is defined as:

(f_{1}f_{2}) (g) = f_{1} (g) f_{2} (g) for all f_{1}, f_{2} ∈ Ĝ

The elements of Ĝ are called characters.^{7}

Remark 1. The group 𝕊^{1} can be identified with

1) The multiplicative group U(1) = { e^{2πix} | x ∈ ℝ }, i.e., with multiplication defined by e^{2πiα} · e^{2πiβ} = e^{2πi(α+β)}

2) The additive group 2πℝ/2πℤ, i.e., the reals modulo 2π under addition, i.e., with addition defined as

2πα + 2πβ mod 2π = 2π (α + β mod 1)

5For the general abelian HSP, please refer to [8] and [29].

6This follows the notational convention found in [43].

7More generally, for non-abelian groups, a character is defined as the trace of a representation of the group.

Remark 2. Please note that the 1-sphere 𝕊^{1} can be thought of as a ℤ-module under the action

(n, 2πα) ⟼ 2π (nα mod 1)

Theorem 1. Every finite abelian group G is isomorphic to the direct product of cyclic groups, i.e.,

G ≅ ℤ_{m_{1}}×ℤ_{m_{2}}× … × ℤ_{m_{ℓ}} ,

where ℤ_{m_{j}} denotes the cyclic group of order m_{j}.

Theorem 2. Let G be a finite abelian group. If G = G_{1} × G_{2}, then Ĝ = Ĝ_{1} × Ĝ_{2}.

Theorem 3. ℤ̂_{m} ≅ ℤ_{m}

Corollary 1. If G is a finite abelian group, then G ≅ Ĝ.

Remark 3. The isomorphism G ≅ Ĝ can be expressed more explicitly as follows:

Let G ≅ ℤ_{m_{1}}×ℤ_{m_{2}}× … × ℤ_{m_{ℓ}}, and let g_{1}, g_{2}, …, g_{ℓ} denote generators of ℤ_{m_{1}}, ℤ_{m_{2}}, …, ℤ_{m_{ℓ}} respectively. Moreover, let ω_{1}, ω_{2}, …, ω_{ℓ} be m_{1}-th, m_{2}-th, ... , m_{ℓ}-th primitive roots of unity, respectively. Then the character χ̃_{j} of ℤ_{m_{j}} defined by

χ̃_{j}(g_{j}) = ω_{j}

generates ℤ̂_{m_{j}} as a cyclic group, i.e., the powers \binom{}{χ_{j}}^{k} generate ℤ̂_{m_{j}}. Moreover, the characters χ_{j} of G defined by

χ_{j} = (∏_{i=0}^{j−1} χ_{i}^{0}) χ̃_{j} ( ∏_{i=j+1}^{ℓ} χ_{i}^{0})

generate Ĝ. It follows that an isomorphism G ≅ Ĝ is given by

g_{j} ⟷ χ_{j}

Notation Convention In general, we will not need to represent the isomorphism G ≅ Ĝ as explicitly as stated above. We will use the following convention. Let {g_{1}, g_{2}, …, g_{ℓ}} and {χ_{1}, χ_{2}, …, χ_{ℓ}, } denote respectively the set of elements of G and Ĝ indexed in such a way that

g_{j} ⟷ χ_{j}

is the chosen isomorphism of G and Ĝ. We will at times use the notation

\{ \begin{matrix}g ⟷ χ_{g} \\ χ ⟷ g_{χ} \end{matrix}

5. Fourier analysis on a finite abelian group

As in the previous section, let G be a finite abelian group^{8} and let Ĝ denote is character group. Let g and χ denote respectively elements of the groups G and Ĝ.

Let ℂG and ℂĜ denote the corresponding group algebras of G and Ĝ over the complex numbers ℂ. Hence, ℂG consists of all maps f : G ⟶ ℂ. Addition ‘+’, multiplication ‘•’, and scalar multiplication are defined as:

(f_{1} + f_{2}) (g) = f_{1}(g) + f_{2}(g)  ∀g ∈ G
(f_{1} • f_{2}) (g) = ∑_{h∈G}f_{1}(h)f_{2}(h^{−1}g) ∀g ∈ G  (Convolution)

(λf) (g)  = λf(g)  ∀λ ∈ ℂ and ∀g ∈ G

Caveat. Please note that the symbol g has at least three different meanings: ♦ Interpretation 1. The symbol g denotes an element of the group G

♦ Interpretation 2. The symbol g denotes a pointwise map

g : G ⟶ ℂ

defined by

g(g′) = \{ \begin{matrix}1 & if g = g′ \\ 0 & otherwise \end{matrix}

Thus,

f = ∑_{g∈G}f(g)g denotes g ⟼ f(g)

Hence, g ∈ ℂG. Since G is isomorphic as a group to the set of pointwise maps {g : G ⟶ ℂ | g ∈ G} under convolution, we can and do identify the group elements of G with the pointwise maps g ∈ ℂG. Thus, interpretations 1 and 2 lead to no ambiguity at the algebraic level.

♦ Interpretation 3. The symbol g denotes a character of Ĝ defined by

g (χ) = χ (g)

Thus, with this interpretation, g ∈ ˆ Ĝ ⊂ ℂˆĜ. This third interpretation can, in some instances, lead to some unnecessary confusion. When this intended interpretation is possibly not clear from context, we will resort to the notation

g^{•}

8If G is infinite, then ring multiplication ‘•’ is not always well defined. So ℂG is not a ring, but a ℤ-module, with a group of operators. One way of of making ℂG into a ring, is to restrict the maps on G, e.g., to maps with compact support, to maps with L^{2} norm, etc.

for interpretation 3 of the symbol g. Thus, for example,

f^{•} = ∑_{g∈G}f(g)g^{•} denotes the map χ ⟼ ∑_{g∈G}f(g)χ (g)

In like manner, the symbol χ has at least three different meanings:

• Interpretation ˆ1. The symbol χ denotes an element of the group Ĝ

♦ Interpretation ˆ2. The symbol χ denotes a pointwise map

χ : Ĝ ⟶ ℂ

defined by

χ(χ′) = \{ \begin{matrix}1 & if χ = χ′ \\ 0 & otherwise \end{matrix}

Thus,

f̂ = ∑_{χ∈Ĝ}f̂(χ)χ denotes χ ⟼ f̂(χ)

Hence, χ ∈ ℂĜ. Since Ĝ is isomorphic as a group to the set of pointwise maps {χ : Ĝ ⟶ ℂ | χ ∈ Ĝ} under convolution, we can and do identify the

group elements of Ĝ with the pointwise maps χ ∈ ℂĜ. Thus, interpretations ˆ1 and ˆ2 lead to no ambiguity at the algebraic level.

♦ Interpretation ˆ3. The symbol χ denotes a character map of G onto ℂ defined by

g ⟼ χ (g)

Thus, with this interpretation, χ ∈ ℂG. This third interpretation can, in some instances, also lead to some unnecessary confusion. When this intended interpretation is possibly not clear from context, we will resort to the notation

χ^{•}

for interpretation ˆ3 of the symbol χ. Thus, for example,

f̂^{•} = ∑_{χ∈Ĝ}f̂(χ)χ^{•} denotes the map g ⟼ ∑_{χ∈Ĝ}f̂(χ)χ (g)

We define complex inner products on the group algebras ℂG and ℂĜ as follows:

\{ \begin{matrix}(f_{1}, f_{2}) & = & \frac{1}{|G|} ∑_{g∈G}f_{1}(g)\overline{f_{2}(g)} & ∀f_{1}, f_{2} ∈ ℂG \\ (f̂_{1}, f̂_{2}) & = & \frac{1}{|G|} ∑_{χ∈Ĝ}f̂_{1}(χ)\overline{f̂_{2}(χ)} & ∀f̂_{1}, f̂_{2} ∈ ℂĜ \end{matrix}

where \overline{f_{2}(g)} and \overline{f̂_{2}(χ)} denote respectively the complex conjugates of f_{2}(g) and f̂_{2}(χ).

14 SAMUEL J. LOMONACO, JR. AND LOUIS H. KAUFFMAN

The corresponding norms are defined as

\{ \begin{matrix}∥f∥ & = & \sqrt{(f, f)} & ∀f ∈ ℂG \\ ∥f̂∥ & = & \sqrt{(f̂, f̂)} & ∀f̂ ∈ ℂĜ \end{matrix}

As an immediate consequence of the above definitions, we have:

(g_{1}, g_{2}) = \{ \begin{matrix}1 & if g_{1} = g_{2} \\ 0 & otherwise \end{matrix} and (χ_{1}, χ_{2}) = \{ \begin{matrix}1 & if χ_{1} = χ_{2} \\ 0 & otherwise \end{matrix}

It also follows from the standard character identities that

(g_{1}^{•}, g_{2}^{•}) = \{ \begin{matrix}1 & if g_{1}^{•} = g_{2}^{•} \\ 0 & otherwise \end{matrix}  and  (χ_{1}^{•}, χ_{2}^{•}) = \{ \begin{matrix}1 & if χ_{1}^{•} = χ_{2}^{•} \\ 0 & otherwise \end{matrix}

We are now in a position to define the Fourier transform on a finite abelian group G.

Definition 2. The Fourier transform F for a finite abelian group G is defined as

\begin{matrix}ℂG & ⟶^{F} & ℂĜ \\ f & ⟼ & f̂ = \frac{1}{\sqrt{|G|}} ∑_{g∈G}f(g)\overline{g^{•}} = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ} (∑_{g∈G}f(g)\overline{χ} (g)) χ \end{matrix}

Hence,

f̂(χ) = \sqrt{|G|} (f, χ^{•}) = \frac{1}{\sqrt{|G|}} ∑_{g∈G}f(g)\overline{χ (g)}

Proposition 1.

f = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ}f̂(χ)χ^{•}

Proof.

\frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ}f̂(χ)χ(g_{0}) = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ} \frac{1}{\sqrt{|G|}} ∑_{g∈G}f(g)\overline{χ (g)}χ(g_{0})

= \frac{1}{|G|} ∑_{g∈G}f(g)∑_{χ∈Ĝ}\overline{χ (g)}χ(g_{0}) = f(g_{0})

We define the inverse Fourier transform as follows:

Definition 3. The inverse Fourier transform F^{−1} is defined as

\begin{matrix}ℂĜ & ⟶^{F^{−1}} & ℂG \\ f̂ & ⟼ & f = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ}f̂(χ)χ^{•} \end{matrix}

Hence,

f (g) = \sqrt{|G|} (f̂, \overline{g^{•}}) = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ}f̂(χ)χ (g)

Theorem 4 (Plancherel identity).

∥f∥ = ∥f̂∥

Proof.

∥f∥^{2} = (f, f) = \frac{1}{|G|} ∑_{g∈G} |f(g)|^{2}

= \frac{1}{|G|} ∑_{g∈G} \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ}f̂(χ)χ (g) \overline{(\frac{1}{\sqrt{|G|}} ∑_{χ′∈Ĝ}f̂(χ′)χ′ (g))}

= \frac{1}{|G|^{2}} ∑_{g∈G}∑_{χ∈Ĝ} ∑_{χ′∈Ĝ}f̂(χ)\overline{f̂(χ′)}χ (g) \overline{χ′} (g)

= \frac{1}{|G|^{2}} ∑_{χ∈Ĝ} ∑_{χ′∈Ĝ}f̂(χ)\overline{f̂(χ′)} (∑_{g∈G}χ (g) \overline{χ′} (g))

= \frac{1}{|G|} ∑_{χ∈Ĝ} |f̂(χ)|^{2} = ∥f̂∥^{2}

6. Implementation issues: Group algebras as Hilbert spaces

For implementation purposes, we will need to view group algebras also as Hilbert spaces.^{9}

In particular, ℂG and ℂĜ can be respectively viewed as the Hilbert spaces H_{G} and HĜ defined by the respective orthonormal bases

{|g⟩ | g ∈ G} and {|χ⟩ | χ ∈ Ĝ}.

9Category theorists will recognize this as a forgetful functor.

In this context, the Fourier transform F becomes

\begin{matrix}H_{G} & ⟶^{F} & HĜ \\ |f⟩ = ∑_{g∈G}f(g) |g⟩ & ⟼ & |f̂⟩ = \frac{1}{\sqrt{|G|}} ∑_{χ∈Ĝ} (∑_{g∈G}f(g)\overline{χ} (g)) |χ⟩ \end{matrix}

and the inverse Fourier transform F^{−1} becomes

\begin{matrix}HĜ & ⟶^{F^{−1}} & H_{G} \\ |f̂⟩ & ⟼ & |f⟩ = \frac{1}{\sqrt{|G|}} ∑_{g∈G} (∑_{χ∈Ĝ}f̂(χ)χ (g)) |g⟩ \end{matrix}

One important and useful identification is to use the Hilbert space isomorphism

\begin{aligned}H_{G} & ⟷ & HĜ \\ |g⟩ & ⟷ & |χ_{g}⟩ \\ |g_{χ}⟩ & ⟷ & |χ⟩ \end{aligned}

to identify the two Hilbert spaces H_{G} and HĜ. As a result, the Fourier transform F and it’s inverse F^{−1} can both be viewed as transforms taking the Hilbert space H_{G} to itself, i.e.,

H_{G} ⟶^{F} ; ⟵_{F^{−1}} H_{G}

Remark 4. This last identification is crucial for the implementation of hidden subgroup algorithms.

Part 3. QRand_{φ}(): The Progenitor of All QHSAs

7. Implementing P rob_{φ} (χ) with quantum subroutine QRand_{φ}()

Let

φ : A ⟶ S

be a map from a finite abelian group A into a finite set S.

We use additive notation for the group A; and let s_{0} = φ (0) denote the image of the identity 0 of A under the map φ.

Let H_{A}, HÂ, and H_{S} denote the Hilbert spaces respectively defined by the orthonormal bases

{ |a⟩ | a ∈ A }, { |χ⟩ | χ ∈ Â }, and { |s⟩ | s ∈ S } .

We assume that we are given a quantum system which implements the unitary transformation U_{φ} defined by

\begin{matrix}H_{A} ⊗ H_{S} & ⟶^{U_{φ}} & H_{A} ⊗ H_{S} \\ |a⟩ |s_{0}⟩ & ⟼ & |a⟩ |φ (a)⟩ \end{matrix}

We will use the above implementation to construct a quantum subroutine QRand_{φ} () which produces a probability distribution

P rob_{φ} : Â ⟶ [0, 1]

on the character group Â of the group A.

Before doing so, we will, as explained in the previous section, make use of various identifications, such as respectively identifying the Fourier and inverse Fourier transforms F_{A} and F_{A}^{−1} on the group A

ℂA = H_{A} ⟶^{F_{A}} ; ⟵_{F_{A}^{−1}} HÂ = ℂÂ

with

ℂA = H_{A} ⟶^{F_{A}} ; ⟵_{F_{A}^{−1}} H_{A} = ℂA

Quantum Subroutine QRand_{φ}()

Step 0. Initialization

|ψ_{0}⟩ = |0⟩ |s_{0}⟩

Step 1. Application of the inverse Fourier transform F_{A}^{−1} of A

|ψ_{1}⟩ = (F_{A}^{−1} ⊗ 1_{S}) |ψ_{0}⟩ = \frac{1}{\sqrt{|A|}} ∑_{a∈A} |a⟩ |s_{0}⟩

where |A| denotes the cardinality of the group A.

Step 2. Application of the unitary transformation U_{φ}

|ψ_{2}⟩ = U_{φ} |ψ_{1}⟩ = \frac{1}{\sqrt{|A|}} ∑_{a∈A} |a⟩ |φ (a)⟩

Step 3. Application of the Fourier transform F_{A} of A

|ψ_{3}⟩ = (F_{A}^{−1} ⊗ 1_{S}) |ψ_{2}⟩ = \frac{1}{|A|} ∑_{a∈A}∑_{χ∈Â}χ (a) |χ⟩ |φ (a)⟩

= ∑_{χ∈Â}\frac{∥|φ (χ^{•})⟩∥}{|A|} |χ⟩ \frac{|φ (χ^{•})⟩}{∥|φ (χ^{•})⟩∥}

where

|φ (χ^{•})⟩ = ∑_{a∈A}χ (a) |φ(a)⟩

Remark 5. This notation is meant to be suggestive, since under the identification H_{A} = ℂA we have

|φ (χ^{•})⟩ = ∑_{a∈A}χ (a) φ (a) = φ (∑_{a∈A}χ (a) a) = φ (χ^{•})

Step 4. Measurement of the left quantum register. Thus, with probability

P rob_{φ} (χ) = \begin{matrix}∥φ (χ^{•})∥ & 2 \\ |A| & 2 \end{matrix}

the character χ is the resulting measured value, and the quantum system “collapses” to the state

|ψ_{4}⟩ = |χ⟩ \frac{|φ (χ^{•})⟩}{∥φ (χ^{•})∥}

Step 5. Output the character χ, and stop.

Remark 6. The quantum subroutine QRand_{φ}() can also be viewed as a subroutine with the state |χ⟩ |φ (χ^{•})⟩ as a side effect.

As a result of the above description of QRand_{φ}(), we have the following theorem:

Theorem 5. Let

φ : A ⟶ S

be a map from a finite abelian group A into a finite set S. Then the quantum subroutine QRand_{φ}() is an implementation of the probability distribution P rob_{φ} (χ) on the group Â of characters of A given by

P rob_{φ} (χ) = \begin{matrix}∥φ (χ^{•})∥ & 2 \\ |A| & 2 \end{matrix} ,

for all χ ∈ Â, where χ^{•} denotes

χ^{•} = ∑_{a∈A}χ (a) a ∈ ℂA

Remark 7. Please note that the above theorem is true whether or not the map φ : A ⟶ S has a hidden subgroup.

We will, on occasion, refer to the probability distribution

P rob_{φ} : Â ⟶ [0, 1]

on the character group Â as the stochastic source S_{φ} (χ) which produces a symbol χ ∈ Â with probability P rob_{φ} (χ). (See [32].) Thus, QRand_{φ} (χ) is an algorithmic implementation of the stochastic source S_{φ} (χ).

Part 4. Vintage Simon Algorithms

We now begin the development of the class of vintage Simon QHSAs. These are QHSAs for which the ambient group A is finite abelian.

8. Properties of the probability distribution P rob_{φ} (χ) when φ has a hidden subgroup

Let

φ : A ⟶ S

be a map from a finite abelian group A to a set S. We now assume that φ has a hidden subgroup K_{φ}, and hence, a hidden quotient group H_{φ} = A/K_{φ}.

Let

ν : A ⟶ H_{φ} = A/K_{φ}

denote the corresponding natural epimorphism respectively. Then since Hom_{ℤ} (−, 2πℝ/2πℤ) is a left exact contravariant functor, the map

\begin{matrix}ν̂ : Ĥ_{φ} & ⟶ & Â \\ η & ⟼ & η ∘ ν \end{matrix}

is a monomorphism^{10}.

Since ν̂ is a monomorphism, each character η of the hidden quotient group H_{φ} can be identified with a character χ of A for which χ (k) = 1 for every element of K_{φ}. In other words, Ĥ_{φ} can be identified with all characters of A which are trivial on K_{φ}.

10See [7].

Theorem 6. Let

φ : A ⟶ S

be a map from a finite abelian group A into a finite set S. If there exists a hidden subgroup K_{φ} of φ, and hence a hidden quotient group H_{φ} = A/K_{φ} of φ, then the probability distribution P rob_{φ} (χ) on Â implemented by the quantum subroutine QRand_{φ}() is given by

P rob_{φ} (χ) = \{ \begin{matrix}\frac{1}{|H_{φ}|} & if χ ∈ Ĥ_{φ} \\ 0 & otherwise \end{matrix}

In other words, in this particular case, P rob_{φ} (χ) is nothing more than the uniform probability distribution on the character group Ĥ_{φ} of the hidden quotient group H_{φ}.

Proof. Since φ has a hidden subgroup K_{φ}, there exists a hidden injection

ι_{φ} : H_{φ} ⟶ S

from the hidden quotient group H_{φ} = A/K_{φ} to the set S such that the diagram

A ⟶^{φ} S
ν ↓ ↗ ι_{φ}
H_{φ}

is commutative, where ν : A ⟶ H_{φ} denotes the hidden natural epimorphism of A onto the quotient group H_{φ} = A/K_{φ}.

Next let

ι_{ν} : H_{φ} ⟶ A

be a transversal map of the subgroup K_{φ} in A, i.e., a map such that

ν ∘ ι_{ν} = id_{H_{φ}} .

In other words, ι_{ν} sends each element h of H_{φ} to a unique element of the coset φ^{−1} (h).

Recalling that

φ (χ^{•}) = ∑_{a∈A}χ (a) φ (a) ,

we have

φ (χ^{•}) = ∑_{a∈A}χ (a) ι_{φ}νa = ∑_{h∈H_{φ}} ( ∑_{k∈K_{φ}}χ (ι_{v}h + k)) ι_{φ}h

= ∑_{h∈H_{φ}}χ (ι_{v}h) ( ∑_{k∈K_{φ}}χ (k)) ι_{φ}h = ( ∑_{k∈K_{φ}}χ (k)) ( ∑_{h∈H_{φ}}χ (ι_{v}h) ι_{φ}h)

Thus,

∥φ (χ^{•})∥^{2} = | ∑_{k∈K_{φ}}χ (k)|^{2} ∥ ∑_{h∈H_{φ}}χ (ι_{v}h) ι_{φ}h∥^{2}

= | ∑_{k∈K_{φ}}χ (k)|^{2} ∑_{h∈H_{φ}} |χ (ι_{v}h)|^{2} = | ∑_{k∈K_{φ}}χ (k)|^{2} |H_{φ}|

But by a standard character identity^{11}, we have

∑_{k∈K_{φ}}χ (k) = \{ \begin{matrix}|K_{φ}| = |A| / |H_{φ}| & if χ ∈ Ĥ_{φ} \\ 0 & otherwise \end{matrix}

Hence, it follows that

P rob_{φ} (χ) = \begin{matrix}∥φ (χ^{•})∥ & 2 \\ |A| & 2 \end{matrix} = \{ \begin{matrix}\frac{1}{|H_{φ}|} & if χ ∈ Ĥ_{φ} \\ 0 & otherwise \end{matrix}

9. A Markov process M_{φ} induced by P rob_{φ}

Before we can discuss the class of vintage Simon quantum hidden subgroup algorithms, we need to develop the mathematical machinery to deal with the following question:

Question. Let φ : A ⟶ S be a map from a finite abelian group A to a finite set S. Assume that the map φ has a hidden group K_{φ}, and hence a hidden quotient group H_{φ}. From theorem 6 of the previous section, we know that the probability distribution

P rob_{φ} : Â ⟶ [0, 1]

is effectively the uniform probability distribution on the character group Ĥ_{φ} of the hidden quotient group H_{φ}. How many times do we need to query the probability distribution P rob_{φ} to obtain enough characters of H_{φ} to generate the entire character group Ĥ_{φ}?

We begin with a definition:

Definition 4. Let

P rob_{G} : G ⟶ [0, 1]

be a probability distribution on a finite abelian group G, and let G_{+} denote the subgroup of G generated by all elements g of G such that P rob_{G} (g) > 0. The Markov process M_{G} associated with a probability distribution P rob_{G} is the Markov process with the subgroups G_{α} of G_{+} as states, and with transition probabilities given by

11See [17].

P rob (G_{a} ⇝ G_{β}) = P rob_{G} {g ∈ G_{+} | G_{β} is generated by g and the elements of G_{α}} ,

where G_{a} ⇝ G_{β} denotes the transition from state G_{α} to state G_{β}. The initial state of the Markov process M_{G} is the trivial subgroup G_{0}. The subgroup G_{+} is called the absorbing subgroup of G. The transition matrix T of the Markov process is the matrix indexed on the states according to some chosen fixed linear ordering with (G_{α}, G_{β})-th entry T_{αβ} given by P rob (G_{a} ⇝ G_{β}).

The following two propositions are immediate consequences of the above definition:

Proposition 2. Let

P rob_{G} : G ⟶ [0, 1]

be a probability distribution on a finite abelian group G. Then the Markov process M_{G} is an absorbing Markov process with sole absorbing state G_{+}, a state which once entered can never be left. The remaining states are transient states, i.e., states once left can never again be entered. Hence,

lim_{n→∞} P rob_{G} (G_{0} ⇝_{n} G_{α}) = \{ \begin{matrix}1 & if & G_{α} = G_{+} \\ 0 & if & G_{α} ≠ G_{+} \end{matrix}

In other words, if the Markov process M_{G} starts in state G_{0}, it will eventually end up permanently in the absorbing state G_{+}.

Proposition 3. Let T be the transition matrix of the Markov process associated with the probability distribution

P rob_{G} : G ⟶ [0, 1]

Then the probability P rob (G_{α} ⇝_{n} G_{β}) that the Markov process M_{G} starting in state G_{α} is in state G_{β} after n transitions is equal to the (G_{α}, G_{β})-th entry of the matrix T^{n}, i.e.,

P rob (G_{α} ⇝_{n} G_{β}) = (T^{n})_{αβ}

Under certain circumstances, we can work with a much simpler Markov process.

Proposition 4. Let G be a finite abelian group with probability distribution

P rob_{G} : G ⟶ [0, 1]

such that P rob_{G} is the uniform probability distribution on the absorbing group G_{+}. Partition the states of the associated Markov process M_{G} into the collection of sets

{G_{j} | j divides |G_{+}|} ,

where G_{j} is the set of all states G_{α} of M_{G} of group order j.

If

P rob (G_{i} ⇝ G_{j}) = ∑_{G_{j}∈G_{j}}P rob (G_{i} ⇝ G_{j})

has the same value for all G_{i} ∈ G_{i}, then the states of M_{G} can be combined (lumped) to form a Markov process M_{G}^{Lumped} with states {G_{j} | j divides |G_{+}|}, and with transition probabilities given by

P rob^{Lumped} (G_{i} ⇝ G_{j}) = P rob (G_{i} ⇝ G_{j}) ,

where G_{i} is an arbitrarily chosen element of G_{i}, and with initial state G_{1} = {G_{0}}.

Moreover, the resulting M_{G}^{Lumped} is also an absorbing Markov process with sole absorbing state G_{|G_{+}|} = {G_{+}}, with all other states transient, and such that

P rob (G_{0} ⇝_{k} G_{+}) = P rob (G_{1} ⇝_{k} G_{|G_{+}|})

As a consequence of the above proposition and theorem 6, we have:

Corollary 2. Let φ : A ⟶ S be a map from a finite abelian group A to a finite set S, which has a hidden subgroup K_{φ}, and hence a hidden quotient group H_{φ}. Moreover, let the ambient group A be the direct sum of cyclic groups of the same prime order p, i.e., let

A = ⊕^{n}_{1}ℤ_{p} .

Then the combined (lumped) process MLumped ; Â is a Markov process such that

P rob (Â_{0} ⇝_{k} Ĥ_{φ}) = P rob (G_{1} ⇝_{k} G_{\left|{ \atop H_{φ}}\right|})

Moreover, if the states of MLumped ; Â are linearly ordered as

G_{i} < G_{j} if and only if i divides j ,

then the transition matrix T of MLumped ; Â is given by

T = ( \begin{matrix}1 & 0 & 0 & 0 & ⋯ & 0 & 0 \\ 1 − \frac{1}{p} & \frac{1}{p} & 0 & 0 & ⋯ & 0 & 0 \\ 0 & 1 − \frac{1}{p^{2}} & \frac{1}{p^{2}} & 0 & ⋯ & 0 & 0 \\ 0 & 0 & 1 − \frac{1}{p^{3}} & \frac{1}{p^{3}} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ⋯ & \frac{1}{p^{n−1}} & 0 \\ 0 & 0 & 0 & 0 & ⋯ & 1 − \frac{1}{p^{n}} & \frac{1}{p^{n}} \end{matrix} )

Hence,

P rob (Â_{0} ⇝_{k} Ĥ_{φ}) = (T^{k})_{n1} ,

from which it easily follows that

P rob (Â_{0} ⇝_{k} Ĥ_{φ}) > 1 − \frac{1}{p − 1} (\frac{1}{p})^{k−n} S ≥ 1 − \frac{1}{(p − 1) p^{2}}

for k ≥ n + 2.

10. Vintage Simon quantum hidden subgroup algorithms (QHSAs)

We are now prepared to extend Simon’s quantum algorithm to an entire class of QHSAs on finite abelian groups.

Let

φ : A ⟶ S

be a map from a finite abelian group A to a finite set S for which there exists a hidden subgroup K_{φ}, and hence, a hidden quotient group H_{φ} = A/K_{φ}.

Following our usual convention, we use additive notation for the ambient group A and multiplicative notation for the hidden quotient group H_{φ}.

As mentioned in section 2 of this paper, it follows from the standard theory of abelian groups (i.e., Theorem 1) that the ambient group A can be decomposed into the finite direct sum of cyclic groups ℤ_{m_{0}}, ℤ_{m_{1}}, …, ℤ_{m_{ℓ−1}}, i.e.,

A = ℤ_{m_{0}} ⊕ ℤ_{m_{1}} ⊕ … ⊕ ℤ_{m_{ℓ−1}} ,

We denote respective generators of the above cyclic groups by

a_{0}, a_{1}, …, a_{ℓ−1} .

Consequently, each character χ of the ambient group A can be uniquely expressed as

χ : ∑_{j=0}^{ℓ−1}α_{j}a_{j} ⟼ exp (2πi∑_{j=0}^{ℓ−1}α_{j} \frac{y_{j}}{m_{j}} ) ,

where 0 ≤ y_{j} < m_{j} for j = 0, 1, …, ℓ − 1. Thus, we have a one-to-one correspondence between the characters χ of A and ℓ-tuples of rationals (modulo 1) of the form

(\frac{y_{0}}{m_{0}} , \frac{y_{1}}{m_{1}} , …, \frac{y_{ℓ−1}}{m_{ℓ−1}} ) ,

where

0 ≤ y_{j} < m_{j}, j = 0, 1, …, ℓ − 1 .

As a result, we can and do use the following notation to refer uniquely to each and every character χ of A

χ = χ_{( \frac{y_{0}}{m_{0}} , \frac{y_{1}}{m_{1}} ,... , \frac{y_{ℓ−1}}{m_{ℓ−1}} )} .

Definition 5. Let

A = ℤ_{m_{0}} ⊕ ℤ_{m_{1}} ⊕ ⋯ ⊕ ℤ_{m_{ℓ−1}}

be a direct sum decomposition of a finite abelian group A into finite cyclic groups. Let

a_{0}, a_{1}, …, a_{n−1}

denote respective generators of the cyclic groups in this direct sum decomposition.

Then an integer matrix

𝔊 = [α_{ij}]_{k×n} mod (m_{0}, m_{1}, …, m_{n−1})

is said to be a generator matrix of a subgroup K of A provided

{∑_{j=0}^{n−1}α_{ij}a_{j} | 0 ≤ i < k}

is a complete set of generators of the subgroup K.

A matrix of rationals mod 1

ℌ = [\frac{y_{ij}}{m_{j}} ]_{ℓ×n} mod 1

is said to be a dual generator matrix of a subgroup K of A provided

\{χ_{( \frac{y_{i0}}{m_{0}} , \frac{y_{i1}}{m_{1}} ,... \frac{y_{i(n−1)}}{m_{n−1}} )} | 0 ≤ i < ℓ\}

is a complete set of generators of the character group Ĥ of the quotient group H = A/K.

Let M_{φ} be the Markov process associated with the probability distribution

P rob_{φ} : Â ⟶ [0, 1]

on the character group Â of the ambient group A.

Let 0 ≤ ϵ ≪ 1 be a chosen threshold.

Then a vintage Simon algorithm is given below:

Vintage Simon(φ, ϵ)

Step 1. Select a positive integer ℓ such that

P robÂ (Â_{0} ⇝_{ℓ} Ĥ_{φ}) < 1 − ϵ

Step 2. Initialize running dual generator matrix

ℌ = [ ]

Step 3. Query the probability distribution P rob_{φ} ℓ times to obtain ℓ characters (not necessarily distinct) of the hidden quotient group H_{φ}, while incrementing the running dual generator matrix ℌ.

Loop i From 0 To ℓ − 1 Do

χ_{( \frac{y_{i0}}{m_{0}} , \frac{y_{i1}}{m_{1}} ,... \frac{y_{i(n−1)}}{m_{n−1}} )} = QRand_{φ}()

ℌ  = [ \begin{matrix}\frac{y_{i0}}{m_{0}} & \frac{y_{i1}}{m_{1}} & … & \frac{y_{i(n−1)}}{m_{n−1}} \\ − − − − − − − − − − −− \\ ℌ \end{matrix} ]

Loop Lower Boundary;

Step 4. Compute the generator matrix 𝔊 from the dual generator matrix ℌ by using Gaussian elimination to solve the system of equations

∑_{j=0}^{n−1} \frac{y_{ij}}{m_{j}} x_{j} = 0 mod 1 0 ≤ i < N_{0}

for unknown x_{j} mod m_{j}.

Step 5. Output 𝔊 and Stop.

Part 5. Vintage Shor Algorithms

11. Vintage Shor quantum hidden subgroup algorithms(QHSAs)

Let φ : A ⟶ S be a map with hidden subgroup structure. We now consider QHSPs for which the ambient group A is free abelian of finite rank n.

Since the ambient group A is infinite, at least two difficulties naturally arise. One is that the associated complex vector space H_{A} is now infinite dimensional, thereby causing some implementation problems. The other is that the Fourier transform of a periodic function on A does not exist as a function^{12}, but as a generalized function!

Following Shor’s lead, we side-step these annoying obstacles by choosing not to work with the ambient group A and the map φ at all. Instead, we work with a group Ã and a map φ̃: Ã ⟶ S which are “approximations” of A and φ : A ⟶ S, respectively.

The group Ã and the approximating map φ̃ are constructed as follows:

12As a clarifying note, let f : ℤ ⟶ ℂ be a period P function on ℤ. Then f on ℤ is neither of compact support, nor of bounded L^{2} or L^{1} norm. So the Fourier transform of f does not exist as a function, but as a generalized function, i.e., as a distribution. However, the function f does induce a function f̃ : ℤ_{P} ⟶ ℂ which does have a Fourier transform on ℤ_{P} which exists as a function. The problem is that we do not know the period of φ, and as a consequence, cannot do Fourier analysis on the corresponding unknown finite cyclic group.

Choose an epimorphism

μ : A ⟶ Ã

of the ambient group A onto a chosen finite group Ã, called a group probe. Next, select a transversal

ι_{μ} : Ã ⟶ A

of μ, i.e., a map such that

μ ∘ ι_{μ} = idÃ ,

where idÃ, denotes the identity map on the group probe Ã. [Consequently, ι_{μ} is an injection, and in most cases not a morphism at all.]

Having chosen μ and ι_{μ}, the approximating map φ̃ is defined as

φ̃ = φ ∘ ι_{μ} : Ã ⟶ S

Although the map φ̃ is not usually a morphism, the quantum subroutine QRandφ̃() is still a well defined quantum procedure which produces a well defined

probability distribution P robφ̃ (χ) on the character group ˆ Ã of the group probe Ã. As we shall see, if the the map φ̃ is a “reasonably good approximation” to the original map φ, then QRandφ̃() will with high probability produce characters χ of the probe group Ã which are “sufficiently close” to corresponding characters η of the hidden quotient group H_{φ}.

Following this basic strategy, we will now use the quantum subroutine QRandφ̃() to build three classes of vintage Shor QHSAs, where the probe group Ã is a finite cyclic group ℤ_{Q} of order Q. In this way, we will create three classes of quantum algorithms which form natural extensions of Shor’s original quantum factoring algorithm.

12. Direct summand structure

We digress momentarily to discuss the direct sum structure of the ambient group A when it is free abelian of finite rank n.

Since the ambient group A is free abelian of finite rank n, the hidden subgroup K_{φ} is also free abelian of finite rank. Moreover, there exist compatible direct sum decompositions of A and K_{φ} into free cyclic groups

\{ \begin{matrix}K_{φ} & = & P_{1}ℤ ⊕ ⋯ ⊕ P_{n}ℤ \\ A & = & \underbrace{ℤ ⊕ ⋯ ⊕ ℤ}_{n direct summands} \end{matrix} ,

where P_{1}, ..., P_{n} are non-negative integers, and where the inclusion morphism

K_{φ} = P_{1}ℤ ⊕ ⋯ ⊕ P_{n}ℤ ↪ \underbrace{ℤ ⊕ ⋯ ⊕ ℤ}_{n} = A

is the direct sum of the inclusion morphisms

P_{j}ℤ ↪ ℤ

It should be mentioned that, since the group K_{φ} is hidden, the above direct sum decompositions are also hidden. Moreover, the selection of a direct sum decomposition of the ambient group A is operationally equivalent to a selection a basis of A. This leads to the following definition:

Definition 6. A basis

{a_{1}, a_{2}, …, a_{n}}

of the ambient group A corresponding to the above hidden direct sum decomposition of A is called a hidden basis of A.

Question. How is the hidden basis {a_{1}, a_{2}, …, a_{n}} of A related to any “visible” basis {a′_{1}, a′_{2}, …, a′_{n}} of A that we might choose to work with?

The group of automorphisms of the free abelian group A of rank n is isomorphic to the group

SL_{±} (n, ℤ)

of n × n invertible integer matrices. This is the same as the group of n × n integer matrices of determinant ±1.

Proposition 5. Let {a_{1}, a_{2}, …, a_{n}} be a hidden basis of A, and let {a′_{1}, a′_{2}, …, a′_{n}} be any other basis of A. Then there exists a unique element M ∈ SL_{±} (n, ℤ) which carries the basis {a′_{1}, a′_{2}, …, a′_{n}} into the hidden basis {a_{1}, a_{2}, …, a_{n}}.

Since the image of φ is finite, we know that P_{j} > 0, for all j. Thus, the direct sum decomposition of the inclusion morphism becomes

\overbrace{(P_{1}ℤ ⊕ ⋯ ⊕ P\overline{n}ℤ) ⊕ \underbrace{(ℤ ⊕ ⋯ ⊕ ℤ)}_{n−\overline{n}}}^{K_{φ}} ↪ \overbrace{\underbrace{(ℤ ⊕ ⋯ ⊕ ℤ)}_{\overline{n}} ⊕ \underbrace{(ℤ ⊕ ⋯ ⊕ ℤ)}_{n−\overline{n}}}^{A}

As a consequence, the hidden quotient group H_{φ} is the corresponding direct sum of finite cyclic groups

H_{φ} = (ℤ_{P_{1}} ⊕ ⋯ ⊕ ℤ_{P\overline{n}}) ⊕ \underbrace{(0 ⊕ ⋯ ⊕ 0)}_{n−\overline{n}} ,

and the hidden epimorphism

ν : (P_{1}ℤ ⊕ ⋯ ⊕ P\overline{n}ℤ) ⊕ \underbrace{(ℤ ⊕ ⋯ ⊕ ℤ)}_{n−\overline{n}} ⟶ ℤ_{P_{1}} ⊕ ⋯ ⊕ ℤ_{P\overline{n}}

is the direct sum of of the epimorphisms

\{ \begin{matrix}ℤ ⟶ ℤ_{P_{j}} \\ ℤ ⟶ 0 \end{matrix}

As a consequence of the above, we have:

Definition 7. Let

{a_{1}, a_{2}, …, a_{n}}

be a hidden basis of A. Then a corresponding induced hidden basis of the hidden quotient group H_{φ} is defined as

\{b_{1} = ν (a_{1}) , b_{2} = ν (a_{2}) , …, b\overline{n} = ν (a\overline{n})\} ,

where ν : A ⟶ H_{φ} denotes the hidden epimorphism.^{13}

The above direct sum decompositions are summarized in the following diagram:

\overbrace{(⨁_{j=1}^{\overline{n}}P_{j}ℤ) ⊕ ( ⨁_{j=\overline{n}+1}^{n}ℤ)}^{K_{φ}} ↪ \overbrace{(⨁_{j=1}^{\overline{n}}ℤ) ⊕ ( ⨁_{j=\overline{n}+1}^{n}ℤ)}^{A}  ⟶^{φ}  S
ν ↘  ↗ ι_{φ}

\underbrace{⨁_{j=1}^{\overline{n}}ℤ_{P_{j}}}_{H_{φ}}

Definition 8. Let H be a finite abelian group. Then a maximal cyclic subgroup of H is a cyclic subgroup of H of highest possible order.

Proposition 6. Let b_{1}, b_{2}, …, b\overline{n} be the above defined induced hidden basis of the hidden quotient group H\overline{n} = ℤ_{P_{1}} ⊕ ℤ_{P_{2}} ⊕ ⋯ ⊕ ℤ_{P\overline{n}}. Then a maximal cyclic subgroup of H_{φ} is generated by

b_{1} ⊕ b_{2} ⊕ ⋯ ⊕ b\overline{n} ,

and is isomorphic to the finite cyclic group ℤ_{P} of order

P = lcm (P_{1}, P_{2}, …, P\overline{n}) .

b_{1}^{k_{1}}b_{2}^{k_{2}} ⋯ bk\overline{n} ; \overline{n} = 1

b_{j}^{k_{j}} = 1

13Please note that the hidden basis {a_{1}, a_{2}, …, a_{n}} of A is free in the abelian category. However, the induced basis \{b_{1}, b_{2}, …, b\overline{n}\} of H_{φ} is not because H_{φ} is a torsion group. \{b_{1}, b_{2}, …, b\overline{n}\} is a basis in the sense that it is a set of generators of H_{φ} such that implies that for every j. (For more information, please refer to [20].)

13. Vintage Shor QHSAs with group probe Ã = ℤ_{Q}.

Choose a positive integer Q and an epimorphism

μ : A ⟶ ℤ_{Q}

of the free abelian group A onto the finite cyclic group Ã = ℤ_{Q} of order Q.

Next we wish to select a transversal ι_{μ} of the epimorphism μ.

However, at this juncture we must take care. For, not every choice of the transversal ι_{μ} will produce an efficient vintage Shor algorithm. In fact, most choices probably will produce highly inefficient algorithms^{14}. We emphasize that the efficiency of the class of algorithms we are about to define depends heavily on the choice of the transversal ι_{μ}.

Following Shor’s lead once again, we select a very special transversal ι_{μ}.

Definition 9. Let μ : A ⟶ ℤ_{Q} be an epimorphism from a free abelian group A of finite rank n onto a finite cyclic group ℤ_{Q} of order Q, and let ã be a chosen generator of the cyclic group ℤ_{Q}.

A transversal

ι_{μ} : ℤ_{Q} ⟶ A

is said to be a Shor transversal provided

1) ι_{μ} (kã) ⟼ kι_{μ} \binom{}{a} , for all 0 ≤ k < Q, and

2) There exists a basis \{a′_{1}, a′_{2}, …, a′_{n}\} of A such that, when ι_{μ} \binom{}{a} is expressed in this basis, i.e., when

ι_{μ} \binom{}{a} = ∑_{j=1}^{n} λ′_{j}a′_{j} ,

it follows that

gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1

Proposition 7. Let λ′_{1}, λ′_{2}, …, λ′_{n} be n integers, and let M be a non-singular n × n integral matrix, i.e., an element of SL_{±} (n, ℤ). If λ_{1}, λ_{2}, …, λ_{n} are n integers defined by

(λ_{1}, λ_{2}, …, λ_{n}) = (λ′_{1}, λ′_{2}, …, λ′_{n}) M ,

then

gcd (λ_{1}, λ_{2}, …, λ_{n}) = gcd (λ′_{1}, λ′_{2}, …, λ′_{n})

As a corollary, we have

14For example, consider A = ℤ, P = 6, Q = 64, and the transversal defined by ι_{μ} : 6n+k ⟼ 6n + k + 64 ⌊k/2⌋ for 0 ≤ n ≤ 10, where \{ \begin{matrix}0 ≤ k < 6 & if & 0 ≤ n < 10 \\ 0 ≤ k < 4 & if & n = 10 \end{matrix} . One reason this is a poor choice of transversal is that the image of ι_{μ} does not contain a representative of every coset of the hidden subgroup ℤ_{P} of the ambient group A.

Proposition 8. If condition 2) is true with respect to one basis, then it is true with respect to every basis.

An another immediate consequence of the definition of a Shor traversal, we have the following lemma:

Lemma 1. If a Shor transversal

ι_{μ} : ℤ_{Q} ⟶ A ,

is used to construct the the approximating map

φ̃ = φ ∘ ι_{μ} : ℤ_{Q} ⟶ S ,

then the approximating map φ̃ has the following property

φ̃ (kã) = [φ̃ \binom{}{a}]^{k} ,

for all 0 ≤ k < Q, where we have used the hidden injection ι_{φ} : H_{φ} ⟶ S to identify the elements φ̃ (kã) of the set S with corresponding elements of the hidden quotient group H_{φ}.

14. Finding Shor transversals for vintage ℤ_{Q} Shor algorithms

Surprisingly enough, it is algorithmically simpler to find a Shor transversal ι_{μ} : ℤ_{Q} ⟶ A first, and then, as an after thought, to construct a corresponding epimorphism μ : A ⟶ ℤ_{Q}.

Definition 10. Let A be an ambient group, and let ℤ_{Q} be a finite cyclic group of order Q with a selected generator ã. Then an injection

ι : ℤ_{Q} ⟶ A

is called a Shor injection provided 1) ι (kã) = kι \binom{}{a} , for all 0 ≤ k < Q, and

2) There exists a basis {a′_{1}, a′_{2}, …, a′_{n}} of the ambient group A such that

gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1 ,

where

ι \binom{}{a} = ∑_{j=1}^{n}λ′_{j}a′_{j} .

Proposition 9. If condition 2) is true with respect to one basis, it is true with respect to all.

Next, we need to construct an epimorphism μ : A ⟶ ℤ_{Q} for which ι : ℤ_{Q} ⟶ A is a Shor transversal.

Proposition 10. Let A be an ambient group, and let ℤ_{Q} be a finite cyclic group of order Q with a selected generator ã. Given a Shor injection

ι : ℤ_{Q} ⟶ A ,

there exists an epimorphism

μ_{ι} : A ⟶ ℤ_{Q}

such that ι is a Shor transversal for μ_{ι}, i.e., such that

μ_{ι} ∘ ι = id_{ℤ_{Q}} ,

where id_{ℤ_{Q}} denotes the identity morphism on ℤ_{Q}.

Proof. Select an arbitrary basis {a′_{1}, a′_{2}, …, a′_{n}} of A. Then

ι \binom{}{a} = ∑_{j=1}^{n}λ′_{j}a′_{j} ,

where

gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1 .

Hence, from the extended Euclidean algorithm, we can find integers

α_{1}, α_{2}, …, α_{n}

for which

∑_{j=1}^{n}α_{j}λ′_{j} = 1 .

Define

μ : {a′_{1}, a′_{2}, …, a′_{n}} ⟶ ℤ_{Q}

by

μ (a′_{j}) = α_{j}ã , j = 1, 2, …, n.

Since a′_{1}, a′_{2}, …, a′_{n} is a free abelian basis of the ambient group A, it uniquely extends to a morphism

μ : A ⟶ ℤ_{Q} .

It immediately follows that μ is an epimorphism because

μ (∑_{j=1}^{n}λ′_{j}a′_{j}) = ∑_{j=1}^{n}α_{j}λ′_{j}ã = ã .

Thus the task of finding an epimorphism μ : A ⟶ ℤ_{Q} and a corresponding Shor transversal reduces to the task of finding n integers λ′_{1}, λ′_{2}, …, λ′_{n} such that

gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1 .

This leads of to the following probabilistic subroutine which finds a random Shor traversal:

Random Shor transversal( {a′_{1}, a′_{2}, …, a′_{n}} , Q, ã, n )

# Input: A basis {a′_{1}, a′_{2}, …, a′_{n}} of A, a positive integer Q, # a selected generator ã of A, and the rank n of A # Output: Shor transversal ι_{μ} : ℤ_{Q} ⟶ A # Side Effect: Epimorphism μ : A ⟶ ℤ_{Q} # Side Effect: Random integers λ′_{1}, λ′_{2}, …, λ′_{n}

Global: μ : A ⟶ ℤ_{Q} Global: λ′_{1}, λ′_{2}, …, λ′_{n}

Step 0 If n = 1 Then (Set λ′_{1} = 1 And Goto Step 4 )

Step 1 Select with replacement n random λ′_{1}, λ′_{2}, …, λ′_{n} from {1, 2, …, Q}.

Step 2 Use the extended Euclidean algorithm to determine

d = gcd (λ′_{1}, λ′_{2}, …, λ′_{n})

and integers α_{1}, α_{2}, …, α_{n} such that ∑_{j=1}^{n} α_{j}λ′_{j} = d

Step 3 If d ≠ 1 Then Goto Step 1 Else Goto Step 4

Step 4 Construct Shor transversal ι_{μ} : ℤ_{Q} ⟶ A as ι_{μ} (kã) = k ∑_{j=1}^{n} λ′_{j}a′_{j}, for 0 ≤ k < Q

Step 5 Construct epimorphism μ : A ⟶ ℤ_{Q} as

μ (a′_{j}) = α_{j}ã for all j = 1, 2, …, n

Step 6 Output transversal ι_{μ} : ℤ_{Q} ⟶ A and Stop

Theorem 7. For n > 1, the average case complexity of the Random Shor transversal subroutine is

O (n (lg Q)^{3}) .

Proof. The computationally dominant part of this subroutine is the main loop Steps 1 through 3.

Each iteration of the main loop executes the extended Euclidean algorithm n times to find the gcd d. Since the computational complexity of the extended Euclidean algorithm^{15} is O ((lg Q)^{3}), it follows that the computational cost of one iteration of steps 1 through 3 is

O (n (lg Q)^{3}) .

But by Corollary 7 of Appendix B,

P rob_{Q} (gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1) = Ω (1) .

15See [11, Chap. 31].

Thus, the average number of iterations before a successful exit to Step 4 is O (1). Hence, the average case complexity of steps 1 through 4 is

O (n (lg Q)^{3}) .

Remark 8. Our objective in this paper is to find reasonable asymptotic bounds, not the tightest possible bounds. For example, the above bound is by no means the tightest possible. For a tighter bound for the Euclidean algorithm is O ((lg Q)^{2}) which can be found in [11]. Thus, the bound found in the above theorem can be tightened to at least O (n (lg Q)^{2}).

15. Maximal Shor transversals

Unfortunately, the definition of a Shor transversal is in some instances not strong enough to extend Shor’s quantum factoring algorithm to ambient groups which are free abelian groups of finite rank. From necessity, we are forced to make the following definition.

Definition 11. Let a_{1}, a_{2}, …, a_{n} be a hidden basis of the ambient group A, let ã be a chosen generator the cyclic group probe ℤ_{Q}, and let H_{φ} = ℤ_{P_{1}} ⊕ ℤ_{P_{2}} ⊕ ⋯⊕ℤ_{P_{n}} be the corresponding hidden direct sum decomposition. A maximal Shor transversal is a Shor transversal ι_{μ} : ℤ_{Q} ⟶ A such that

gcd(λ_{j}, P_{j}) = 1, for 0 ≤ j < n ,

where the integers λ_{1}, λ_{2}, …, λ_{n} are defined by

ι_{μ} \binom{}{a} = λ_{1}a_{1} + λ_{2}a_{2} + …, +λ_{n}a_{n}

Remark 9. Thus, for maximal Shor traversals, ι_{μ} \binom{}{a} maps via the hidden epimorphism ν : A ⟶ A/K_{φ} to a maximum order element of the hidden quotient group H_{φ}.

One of the difficulties of the above definition is that it does not appear to be possible to determine whether or not a Shor transversal is maximal without first knowing the hidden direct sum decomposition of the hidden quotient group H_{φ}. We address this important issue in the following corollary, which is an immediate consequence of corollary 8 (found in Appendix B):

Corollary 3. Let

P_{1}, P_{2}, …, P_{n}

be n fixed positive integers, and let Q be an integer such that

Q ≥ lcm (P_{1}, P_{2}, …, P_{n}) ,

where n > 1.

If Conjecture 1 (found in Appendix B) is true, then the probability that the subroutine Random Shor transversal produces a maximal Shor transversal is

Ω (\frac{1}{∏_{j=1}^{n} lg lg P_{j}} ) = Ω (\frac{1}{(lg lg Q)^{n}} ) .

16. Identifying characters of cyclic groups with points on the unit circle 𝕊^{1} in the complex plane ℂ.

We will now begin to develop an answer to the following question:

Question. 1. Are the characters of the group probe ℤ_{Q} produced by the quantum subroutine QRandφ̃() “close enough” to the characters of a maximal cyclic subgroup of the hidden quotient group H_{φ}?

If QRandφ̃() produces a character χ of ℤ_{Q} which is “close enough” to some character η of a maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}, then the character χ can be used to find the corresponding closest character η of ℤ_{P}. Each time such a character η is found, something more is known about the hidden quotient group H_{φ} and the hidden subgroup K_{φ}. In this way, we have the conceptual genesis of a class of vintage ℤ_{Q} Shor algorithms.

But before we can answer the above question, we need to answer a more fundamental question, namely:

Question. 2. What do we mean by “close enough”? I.e, what do we mean by saying that a character χ of Ã = ℤ_{Q} is “close enough” to some character η of ℤ_{P}?

To answer this last question, we need to introduce two additional concepts:

1) The concept of a common domain for the characters χ of ℤ_{Q} and the characters η of ℤ_{P}.

2) The concept of a group norm which is to be used to define when two characters are “close.”

In this section, we address item 1). In the next, item 2).

We begin by noting that the character group ℤ̂ of the infinite cyclic group ℤ is simply the group 𝕊^{1}, i.e.,

ℤ̂ = 𝕊^{1} = {χ_{θ} : n ⟼ e^{2πiθn} | 0 ≤ θ < 1}

In other words, the characters of ℤ can be identified with the points on the unit radius circle in the complex plane ℂ.

Moreover, given an arbitrary epimorphism

τ : ℤ ⟶ ℤ_{m}

of the infinite cyclic group ℤ onto a finite cyclic group ℤ_{m}, the left exact contravariant functor^{16}

Hom_{ℤ} (−, 2πℝ/2πℤ)

transforms τ into the monomorphism

\begin{matrix}τ̂: ℤ̂_{m} & ⟶ & ℤ̂ \\ η & ⟼ & η ∘ τ \end{matrix}

In this way the characters of ℤ_{m} can be identified with the points of ℤ̂ = 𝕊^{1}.

Thus, to find a common domain 𝕊^{1} for the characters of the group probe ℤ_{Q} and the maximal cyclic group ℤ_{P}, all that need be done is to find epimorphisms μ̃ : ℤ ⟶ ℤ_{Q} and τ̃: ℤ ⟶ ℤ_{P}. This is accomplished as follows:

Let a be a generator of the infinite cyclic group ℤ, and let a_{1}, a_{2}, …, a_{n} be a hidden basis of the ambient group A. Then the epimorphisms μ̃ and τ̃ are defined as

\begin{matrix}μ̃ : ℤ & ⟶ & ℤ_{Q} \\ ka & ⟼ & kã \end{matrix} and \begin{matrix}τ̃: ℤ & ⟶ & ℤ_{P} \\ ka & ⟼ & ν [k (a_{1} + a_{2} + … + a_{n})] \end{matrix} ,

where ã is the selected generator of the group probe ℤ_{Q}, and where ν : A ⟶ H_{φ} is the hidden epimorphism.

Thus, as a partial answer to Question 2 of Section 16, a character χ of the probe group Ã = ℤ_{Q} is “close” to some character η of the maximal cyclic subgroup ℤ_{P} H_{φ} = ⨁\overline{n} ; j=1ℤ_{P_{j}} if the corresponding points ˆ μ̃ (χ) and ˆ τ̃ (η) on the circle 𝕊^{1} are “close.”

But precisely what do we mean by two points of 𝕊^{1} being “close” to one another? To answer this question, we need to observe that Shor’s algorithm uses, in addition to the group structure of 𝕊^{1}, also the metric structure of 𝕊^{1}.

17. Group norms

We proceed to define a metric structure on the circle group 𝕊^{1}. To do so, we need to define what is meant by a group norm.

Definition 12. A (group theoretic) norm on a group G is a map

|∥−∥| : G ⟶ ℝ

such that

1) |∥x∥| ≥ 0, for all x, and |∥x∥| = 0 if and only if x is the group identity (which is 1 if we think of G as a multiplicative group, or 0 if we think of G as an additive group).

16For the definition of a left exact contravariant functor, please refer to, for example, [7].

2) |∥x · y∥| ≤ |∥x∥| + |∥y∥| or |∥x + y∥| ≤ |∥x∥| + |∥y∥| , depending respectively on whether we think of G as a multiplicative or as an additive group.

Caveat. The group norms defined in this section are different from the group algebra norms defined in Section 5.

Remark 10. Such a norm induces a metric

G × G ⟶ ℝ
(x, y) ⟼ |∥x · y^{−1}∥| or |∥x − y∥|

depending on whether multiplicative or additive notation is used.

As mentioned in Section 4, we think of the 1-sphere 𝕊^{1} interchangeably as the multiplicative group

𝕊^{1} = {e^{2πiα} | 0 ≤ α < 1} ⊂ ℂ

with multiplication defined as

e^{2πiα} · e^{2πiβ} = e^{2πi(α+β)}

or as the additive group of reals ℝ modulo 2π, i.e., as

𝕊^{1} = 2πℝ/2πℤ = {2πα | 0 ≤ α < 1}

with addition defined as

2πα + 2πβ = (2πα + 2πβ) mod 2π = 2π (α + β mod 1)

It should be clear from context which of the two representation of the group 𝕊^{1} is being used.

Figure 2. Two metrics on the unit circle 𝕊^{1}, Arc_{2π} and Chord_{2π}.

There are two different norms on the 1-sphere 𝕊^{1} that we will be of use to us. The first is the arclength norm, written Arc_{2π}, defined by

Arc_{2π} (α) = 2π min { |α| − ⌊|α|⌋ , ⌈|α|⌉ − |α| } ,

which is simply the length of the shortest arc in the 1-sphere 𝕊^{1} connecting the point e^{2πiα} to the point 1.

The second norm is the chordal length norm, written Chord_{2π}, defined by

Chord_{2π} (α) = 2 |sin (πα)| ,

which is simply the length of the chord in the complex plane connecting the point e^{2πiα} to the point 1.

Shor’s algorithm depends heavily on the interrelationship of these two norms. We summarize these interrelationships in the following proposition:

Proposition 11. The the norms Arc_{2π} and Chord_{2π} satisfy the following conditions:

1) Chord_{2π} (α) = 2 sin (\frac{1}{2}Arc_{2π} (α))

2) \frac{2}{π} Arc_{2π} (α) ≤Chord_{2π} (α) ≤Arc_{2π} (α)

We need the following property of the arclength norm Arc_{2π}:

Proposition 12. Let n be a nonzero integer. If Arc_{2π} (α) ≤ \frac{π}{|n|}, then Arc_{2π} (nα) = |n|Arc_{2π} (α)

18. Vintage ℤ_{Q} Shor QHSAs (Cont.)

Our next step is to look more closely at the probability distribution

P robφ̃ : ˆ Ã ⟶ [0, 1] .

We seek first to use this probability distribution to determine the maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}. However, as indicated by the following lemma, there are a number of obstacles to finding the subgroup ℤ_{P}.

Lemma 2. Let a_{1}, ... , a_{n} denote a hidden basis of the ambient group A = ⨁_{j=1}^{n}ℤ, and let P_{1}, P_{2}, …, P\overline{n} denote the respective orders of the corresponding cyclic direct summands of the hidden quotient group H_{φ} = ⨁\overline{n} ; j=1ℤ_{P_{j}}.

Let ã denote a chosen generator of the group probe Ã = ℤ_{Q}, and let λ_{1}, λ_{2}, …, λ_{n} denote the unknown integers such that

ι_{μ}(ã) = ∑_{j=1}^{n}λ_{j}a_{j} ∈ A.

Finally, use the hidden injection ι_{φ} : H_{φ} ⟶ S to identify the elements of the hidden quotient group H_{φ} with the corresponding elements of the set S.

If the approximating map φ̃ is constructed from a Shor transversal, then the order of φ̃ \binom{}{a} ∈ H_{φ} is \overline{P}, i.e.,

order (φ̃ \binom{}{a}) = \overline{P} ,

where \overline{P} = lcm (\overline{P}_{1}, \overline{P}_{2}, …, \overline{P}_{n}), and where \overline{P}_{j} = P_{j}/ gcd (λ_{j}, P_{j}) for j = 1, 2, …, n. Hence,

\{φ̃ (kã) = φ̃ \binom{}{a}^{k} | 0 ≤ k < \overline{P} \}

are all distinct elements of S.

Moreover, if the approximating map φ̃ is constructed from a maximal Shor transversal, \overline{P} = P = lcm (P_{1}, P_{2}, …, P_{n}).

Proof.

φ̃ \binom{}{a} = φ ∘ ι_{μ} \binom{}{a} = φ (∑_{j} λ_{j}a_{j}) = ∏_{j} φ (a_{j})^{λ_{j}} = ∏_{j} b_{j}^{λ_{j}} ,

where we have used the hidden injection ι_{φ} : H_{φ} ⟶ S to identify the hidden basis element b_{j} of H_{φ} with the element φ(a_{j}) of the set S.

Since the order of each b_{j} is P_{j}, it follows from elementary group theory that the order of ∏_{j} b_{j}^{λ_{j}} must be \overline{P}.

Lemma 3. Let a_{1}, ... , a_{n} be a hidden basis of the ambient group A = ⨁_{j=1}^{n}ℤ, and let P_{1}, P_{2}, …, P_{n} denote the respective orders of the corresponding cyclic direct summands of the hidden quotient group H_{φ} = ⨁\overline{n} ; j=1ℤ_{P_{j}}.

Let ã denote a chosen generator of the group probe Ã = ℤ_{Q}, let λ_{1}, λ_{2}, …, λ_{n} denote the unknown integers such that

ι_{μ}(ã) = ∑_{j=1}^{n}λ_{j}a_{j} ∈ A ,

and let χ_{\frac{y}{Q}} be a character of ℤ_{Q}.

Finally, identify the elements of the hidden quotient group H_{φ} with the corresponding elements of the set S via the hidden injection ι_{φ} : H_{φ} ⟶ S.

If the approximating map φ̃ is constructed from a Shor transversal, then

• When \overline{P} y ≠ 0 mod Q, we have

φ̃ (χ•_{\frac{y}{Q}} ) = ±e^{iπ \frac{\overline{P} y}{Q} q} Chord_{2π} (\frac{\overline{P} y}{Q} (q + 1)) ; Chord_{2π} (\frac{\overline{P} y}{Q} ) ∑_{k_{0}=0}^{r−1} χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

± e^{iπ \frac{\overline{P} y}{Q} (q−1)} Chord_{2π} (\frac{\overline{P} y}{Q} q) ; Chord_{2π} (\frac{\overline{P} y}{Q} ) ∑_{k_{0}=r}^{\overline{P} −1} χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

where \overline{P} = lcm (\overline{P}_{1}, \overline{P}_{2}, …, \overline{P}_{n}), where \overline{P}_{j} = P_{j}/ gcd (λ_{j}, P_{j}) for j = 1, 2, …, n, and where

Q = q\overline{P} + r, with 0 ≤ r < \overline{P}.

• And when \overline{P} y = 0 mod Q, we have

φ̃ (χ•_{\frac{y}{Q}} ) = (q + 1) ∑_{k_{0}=0}^{r−1} χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã) + q ∑_{k_{0}=r}^{\overline{P} −1} χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

Moreover, if the approximating map φ̃ is constructed from a maximal Shor transversal, then \overline{P} = P = lcm (P_{1}, P_{2}, …, P_{n}).

Proof. We begin by identifying the elements of the hidden quotient group H_{φ} with the corresponding elements of the set S via injection ι_{φ} : H_{φ} ⟶ S.

We first consider the case when \overline{P} y ≠ 0 mod Q.

Then

φ̃ (χ•_{\frac{y}{Q}} ) = φ̃ (∑_{k=0}^{Q−1}χ_{\frac{y}{Q}} (kã) kã) = ∑_{k=0}^{Q−1}χ_{\frac{y}{Q}} (kã) φ̃ (kã)

= ∑_{k=0}^{q\overline{P} −1}χ_{\frac{y}{Q}} (kã) φ̃ \binom{}{a}^{k} + ∑_{k=q\overline{P}}^{Q−1}χ_{\frac{y}{Q}} (kã) φ̃ \binom{}{a}^{k}

= ∑_{k_{1}=0}^{q−1} ∑_{k_{0}=0}^{\overline{P} −1}χ_{\frac{y}{Q}} [(k_{1}\overline{P} + k_{0}) ã] φ̃ \left[{ \atop a}\right]^{k_{1}\overline{P} +k_{0}} + ∑_{n_{0}=0}^{r−1}χ_{\frac{y}{Q}} [(k_{1}\overline{P} + k_{0}) ã] φ̃ \left[{ \atop a}\right]^{k_{1}\overline{P} +k_{0}}

From Lemma 2 we have

φ̃ \left[{ \atop a}\right]^{k_{1}\overline{P} +k_{0}} = φ̃ \left[{ \atop a}\right]^{k_{0}} .

QUANTUM HIDDEN SUBGROUP ALGORITHMS 41

So,

φ̃ (χ•_{\frac{y}{Q}} ) = ( ∑_{k_{1}=0}^{q−1}χ_{\frac{y}{Q}} [(k_{1}\overline{P} ) ã]) ∑_{k_{0}=0}^{\overline{P} −1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ \binom{}{a}^{k_{0}}

+ χ_{\frac{y}{Q}} (q\overline{P} ã) ∑_{k_{0}=0}^{r−1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ \binom{}{a}^{k_{0}}

= ( ∑_{k_{1}=0}^{q}χ_{\frac{y}{Q}} [(k_{1}\overline{P} ) ã]) ∑_{k_{0}=0}^{r−1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ \binom{}{a}^{k_{0}}

+ ( ∑_{k_{1}=0}^{q−1}χ_{\frac{y}{Q}} [(k_{1}\overline{P} ) ã]) ∑_{k_{0}=r}^{\overline{P} −1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ \binom{}{a}^{k_{0}}

= (\frac{e^{2πi \frac{\overline{P} y}{Q} (q+1)} − 1}{e^{2πi \frac{\overline{P} y}{Q}} − 1}) ∑_{k_{0}=0}^{r−1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

+ (\frac{e^{2πi \frac{\overline{P} y}{Q} q} − 1}{e^{2πi \frac{\overline{P} y}{Q}} − 1}) ∑_{k_{0}=r}^{\overline{P} −1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

= e^{iπ \frac{\overline{P} y}{Q} q} (\frac{e^{πi \frac{\overline{P} y}{Q} (q+1)} − e^{−πi \frac{\overline{P} y}{Q} (q+1)}}{e^{πi \frac{\overline{P} y}{Q}} − e^{−πi \frac{\overline{P} y}{Q}}} ) ∑_{k_{0}=0}^{r−1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

+ e^{iπ \frac{\overline{P} y}{Q} (q−1)} (\frac{e^{πi \frac{\overline{P} y}{Q} q} − e^{−πi \frac{\overline{P} y}{Q} q}}{e^{πi \frac{\overline{P} y}{Q}} − e^{−πi \frac{\overline{P} y}{Q}}} ) ∑_{k_{0}=r}^{\overline{P} −1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

= e^{iπ \frac{\overline{P} y}{Q} q} (\begin{matrix}sin & (π \frac{\overline{P} y}{Q} (q + 1)) \\ sin & (π \frac{\overline{P} y}{Q} ) \end{matrix}) ∑_{k_{0}=0}^{r−1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

+ e^{iπ \frac{\overline{P} y}{Q} (q−1)} (\begin{matrix}sin & (π \frac{\overline{P} y}{Q} q) \\ sin & (π \frac{\overline{P} y}{Q} ) \end{matrix}) ∑_{k_{0}=r}^{\overline{P} −1}χ_{\frac{y}{Q}} (k_{0}ã) φ̃ (k_{0}ã)

For the exceptional case when \overline{P} y = 0 mod Q, we need only observe that

∑_{k_{1}=0}^{q}χ_{\frac{y}{Q}} [(k_{1}\overline{P} ) ã] = q + 1 and ∑_{k_{1}=0}^{q−1}χ_{\frac{y}{Q}} (k_{1}\overline{P} ) ã = q .

As an immediate consequence of above lemmas 2 and 3, we have:

Corollary 4. If the approximating map φ̃ is constructed from a Shor transversal, then

∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2} = \{ \begin{matrix}\frac{rChord_{2π}^{2}[ \frac{\overline{P} y}{Q} y(q+1)]+(\overline{P} −r)Chord_{2π}^{2}[ \frac{\overline{P} y}{Q} yq]}{Chord_{2π}^{2}( \frac{\overline{P} y}{Q} )} & if \overline{P} y ≠ 0 mod Q \\ r (q + 1)^{2} + (\overline{P} − r) q^{2} & if \overline{P} y = 0 mod Q \end{matrix}

Moreover, if the approximating map φ̃ is constructed from a maximal Shor transversal, then \overline{P} = P = lcm (P_{1}, P_{2}, …, P_{n}).

As a consequence of the inequalities found in Proposition 11, we have:

Corollary 5. If the approximating map φ̃ is constructed from a Shor transversal, then when \overline{P} y ≠ 0 mod Q we have

∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2} ≥ \frac{4}{π^{2}} (\frac{rArc_{2π}^{2} [\frac{\overline{P} y}{Q} y (q + 1)] + (\overline{P} − r) Arc_{2π}^{2} [\frac{\overline{P} y}{Q} yq]}{Arc_{2π}^{2} (\frac{\overline{P} y}{Q} )})

Moreover, if the approximating map φ̃ is constructed from a maximal Shor transversal, then \overline{P} = P = lcm (P_{1}, P_{2}, …, P_{n}).

Figure 3. The characters of ℤ_{P} and ℤ_{Q} as points on the circle 𝕊^{1} of radius 1, with P = 3 and Q = 8. The characters χ_{1}, χ_{3/8}, χ_{5/8} of ℤ_{Q} are close respectively to characters χ_{1}, χ_{\frac{1}{P}} , χ_{\frac{2}{P}} of ℤ_{P}. They are the characters of Arc_{2π} distance less

than \frac{π}{Q} (1 − \frac{P}{Q}) from some character of ℤ_{P}. Also, χ_{\frac{1}{P}} and χ_{\frac{2}{P}} are the primitive characters of ℤ_{P}. Unfortunately, since Q ≱ P^{2}, the characters χ_{3/8} and χ_{5/8} of ℤ_{Q} are not sufficiently close respectively to the primitive characters χ_{\frac{1}{P}} and χ_{\frac{2}{P}}

of ℤ_{P}. Hence, the continued fraction algorithm can not be used to find P.

19. When are characters of Ã = ℤ_{Q} close to some character of a maximal cyclic subgroup ℤ_{P} of H_{φ}?

Definition 13. Let ℤ_{P_{1}} ⊕ ℤ_{P_{2}} ⊕ ⋯ ⊕ ℤ_{P_{n}} be the hidden direct sum decomposition of the hidden quotient group H_{φ}, and let P = lcm (P_{1}, P_{2}, …, P_{n}). A character χ_{\frac{y}{Q}} of the group probe ℤ_{Q} is said to be close to a character of the maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ} provided either of the following equivalent conditions are satisfied

Closeness Condition 1 There exists an integer d such that

Arc_{2π} (\frac{y}{Q} − \frac{d}{P} ) ≤ \frac{π}{Q} (1 − \frac{P}{Q}) ,

or equivalently,

Closeness Condition 1′

Arc_{2π} (\frac{P y}{Q} ) ≤ \frac{πP}{Q} (1 − \frac{P}{Q})

If in addition, Q ≥ P^{2}, then the the character χ_{\frac{y}{Q}} of ℤ_{Q} is said to be sufficiently close to a character of the maximal cyclic subgroup ℤ_{P}.

It immediately follows from the theory of continued fractions [21, 33] that

Proposition 13. If a character χ_{\frac{y}{Q}} of ℤ_{Q} is sufficiently close to a character χ_{\frac{d}{P}} of ℤ_{P}, then \frac{d}{P} is a convergent of the continued fraction expansion of \frac{y}{Q}.

However, to determine the sought integer P from the rational \frac{d}{P}, the numerator and denominator of \frac{d}{P} must be relatively prime, i.e.,

gcd (d, P) = 1 .

This leads to the following definition:

Definition 14. A character χ_{\frac{d}{P}} of ℤ_{P} is said to be primitive provided that

it is a generator of the dual group ℤ̂_{P}.

Proposition 14. A character χ_{\frac{d}{P}} of ℤ_{P} is a primitive character if and only gcd (d, P) = 1. Moreover, the number of primitive characters of ℤ_{P} is ϕ (P), where ϕ (P) denotes Euler’s totient function, i.e., the number of positive integers less than P which are relatively prime to P.

Theorem 8. Assume that Q ≥ P^{2}, and that the approximating map φ̃ is constructed from a maximal Shor transversal. Then the probability that QRandφ̃() produces a character of the group probe ℤ_{Q} which is sufficiently close to a primitive character of the maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ} satisfies the following bound

P robφ̃ ( \begin{matrix}χ sufficiently close to some \\ primitive character of ℤ_{P} \end{matrix} ) ≥ \frac{4}{π^{2}} \frac{ϕ (P)}{P} (1 − \frac{P}{Q})^{2}

Proof. Let χ_{\frac{y}{Q}} be a particular character of the group probe ℤ_{Q} which is sufficiently close to some character of the maximal cyclic subgroup ℤ_{P}. We now compute the probability that QRandφ̃ () will produce this particular character.

First consider the exceptional case when P y = 0 mod Q. Using the expression

for ∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2} given in Corollary 5, we have

∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2} = r (q + 1)^{2} + (P − r) q^{2} ≥ P q^{2} = P (\frac{Q − r}{P} )^{2} ≥ \frac{1}{P} (Q − P)^{2} .

So

P robφ̃ (χ_{\frac{y}{Q}} ) = \frac{∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2}}{Q^{2}} ≥ \frac{1}{P} \frac{P (Q − P)^{2}}{Q^{2}} = \frac{1}{P} (1 − \frac{P}{Q})^{2} ≥ \frac{4}{π^{2}} \frac{1}{P} (1 − \frac{P}{Q})^{2} .

Next consider the non-exceptional case when P y ≠ 0 mod Q.

In this case, Proposition 12 can be applied to both terms in the numerator of the expression given in Corollary 5. Hence,

∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2} ≥ \frac{4}{π^{2}} (\frac{rArc_{2π}^{2} [\frac{P y}{Q} y (q + 1)] + (P − r) Arc_{2π}^{2} [\frac{P y}{Q} yq]}{Arc_{2π}^{2} (\frac{P y}{Q} y)})

≥ \frac{4}{π^{2}} (\frac{r (q + 1)^{2} Arc_{2π}^{2} [\frac{P y}{Q} y] + (P − r) q^{2}Arc_{2π}^{2} [\frac{P y}{Q} y]}{Arc_{2π}^{2} (\frac{P y}{Q} y)})

≥ \frac{4}{π^{2}} r (q + 1)^{2} + \frac{4}{π^{2}} (P − r) q^{2} ≥ \frac{4}{π^{2}} rq^{2} + \frac{4}{π^{2}} (P − r) q^{2}

≥ \frac{4}{π^{2}} P q^{2} = \frac{4}{π^{2}} \frac{1}{P} (Q − r)^{2} ≥ \frac{4}{π^{2}} \frac{1}{P} (Q − P)^{2}

Thus,

P robφ̃ (χ_{\frac{y}{Q}} ) = \frac{∥φ̃ (χ•_{\frac{y}{Q}} )∥^{2}}{Q^{2}} ≥ \frac{4}{π^{2}} \frac{1}{P} (1 − \frac{P}{Q})^{2}

So, in either case we have

P robφ̃ (χ_{\frac{y}{Q}} ) ≥ \frac{4}{π^{2}} \frac{1}{P} (1 − \frac{P}{Q})^{2} .

We now note that there is one-to-one correspondence between the characters of ℤ_{P} and the sufficiently close characters of ℤ_{Q}. Hence, there are exactly ϕ (P) characters of the group probe ℤ_{Q} which are sufficiently close some primitive character of the maximal cyclic group ℤ_{P}. The theorem follows.

The following theorem can be found in [21, Theorem 328, Section 18.4]:

Theorem 9.

lim inf \frac{ϕ(N)}{N/ ln ln N} = e^{−γ},

where γ denotes Euler’s constant γ = 0.57721566490153286061 …, and where e^{−γ} = 0.5614594836 ….

As a corollary, we have:

Corollary 6. P robφ̃ (χ sufficiently close to some primitive character of ℤ_{P}) is bounded below by

\frac{4}{π^{2} ln 2} · \frac{e^{−γ} − ϵ (P)}{lg lg Q} · (1 − \frac{P}{Q})^{2} ,

where ϵ (P) is a monotone decreasing sequence converging to zero. In terms of asymptotic notation,

P robφ̃ (χ sufficiently close to some primitive character of ℤ_{P}) = Ω (\frac{1}{lg lg Q}) .

For a proof of the above, please refer to [33, 43].

20. Summary of Vintage ℤ_{Q} Shor QHSAs

Let φ : A ⟶ S be a map with hidden subgroup structure with ambient group A free abelian of finite rank n, and with image of φ finite. Then as a culmination of the mathematical developments in sections 11 through 19, we have the following vintage ℤ_{Q} Shor QHSA for finding the order P = lcm (P_{1}, P_{2}, …, P_{n}) of the maximum cyclic subgroup Z_{P} of the hidden quotient group H_{φ} = ⨁_{j=1}^{n} ℤ_{P_{j}}. A flowchart of this algorithm is given in Figure 4.

Vintage Shor(φ, Q, n)

# Input: φ : A ⟶ S and Q and rank n of A

46 SAMUEL J. LOMONACO, JR. AND LOUIS H. KAUFFMAN

# Output: P = lcm (P_{1}, P_{2}, … P_{n}) if hidden quotient group

# is H_{φ} = ⨁\overline{n} ; j=1 ℤ_{P_{j}}

Step 1 Select a basis a′_{1}, a′_{2}, …, a′_{n} of A and a generator ã of ℤ_{Q} Step 2 (ι_{μ} : Z_{Q} ⟶ A) = Random Shor transversl( {a′_{1}, a′_{2}, …, a′_{n}} , Q, ã, n ) Step 3 Construct φ̃ = φ ∘ ι_{μ} : ℤ_{Q} ⟶ S Step 4 χ_{\frac{y}{Q}} = QRandφ̃ () Step 5 (d′′, P′′) = (0, 1) # 0-th Cont. Frac. Convergent of \frac{y}{Q}

(d′, P′) = (1, ⌊\frac{Q}{y}⌋) # 1-th Cont. Frac. Convergent of \frac{y}{Q} Inner Loop

(Save d′, Save P′) = (d′, P′)

(d′, P′) = Next Cont Frac ConvergEnt(\frac{y}{Q}, (d′, P′) , (d′′, P′′))

(d′′, P′′) = (Save d′, Save P′)

If φ (P′aj^{′}) = φ (0) for all j = 1, 2, …, n Then Goto Step 6

If \frac{d′}{P′} = \frac{y}{Q} Then Goto Step 2

Inner Loop Boundary

Step 6 Output P′ and Stop Figure 4. Flowchart for Vintage ℤ_{Q} Shor QHSA. This is a Wandering Shor

algorithm.

21. A cursory analysis of complexity

We now make a cursory analysis of the algorithmic complexity of the vintage ℤ_{Q} Shor algorithm. By the word “cursory” we mean that our objective is to find an asymptotic bound which is by no means the tightest possible.

Our analysis is based on the following three assumptions:

• Assumption 1. Conjecture 1 (found in Appendix B) is true.

• Assumption 2. Uφ̃ is of complexity O (n^{2} (lg Q)^{3}).

• Assumption 3. The integer Q is chosen so that Q = 2^{L} ≥ P^{2}, where P = lcm (P_{1}, P_{2}, …, P_{n}).

The following theorem is an immediate consequence of Assumption 2.

Theorem 10. Let

φ̃: ℤ_{Q} ⟶ S

be a map from the cyclic group ℤ_{Q} to a set S, where Q = 2^{L}.

If Uφ̃ is of algorithmic complexity

O (n^{2} (lg Q)^{3}) ,

then the algorithmic complexity of QRandφ̃ () is the same, i.e.,

O (n^{2} (lg Q)^{3})

Proof. Steps 1 and 3 are each of the same algorithmic complexity as the quantum Fourier transform^{17}, i.e., of complexity O ((lg Q)^{2}). (See [36, Chapter 5].). Thus the dominant step in QRandφ̃ () is Step 2, which is by assumption of complexity O (n^{2} (lg Q)^{3}).

The complexities of each step of the vintage Z_{Q} Shor algorithm are given below. An accompanying abbreviated flow chart of this algorithm is shown in Figure 5.

Step 1 Step 1 is of algorithmic complexity is O (n).

Step 2 By theorem 7 of section 14, Step 2 is of average case complexityO (n^{2} (lg Q)^{3}). By corollary 8 of Appendix B, the probability that this step will be successful, i.e., will produce a maximal Shor transversal, is Ω ((\frac{1}{lg lg Q})^{n}).

Step 3 Step 3 is of algorithmic complexity O (n).

Step 4 By theorem 10 given above, Step 4 is of algorithmic complexity O (n^{2} (lg Q)^{3}). By corollary 6 of section 19, the probability (given that Step 2 is successful) that this step will be successful, i.e., will produce a character sufficiently close to a primitive character of the maximal cyclic group ℤ_{P} is Ω (\frac{1}{lg lg Q}) .

Step 5 This step is of algorithmic complexity O (n (lg Q)^{3}). (See, for example, [30].)

17If instead the Hadamard-Walsh transform is used in Step 1, then the complexity of Step 1 is O (lg Q).

QUANTUM HIDDEN SUBGROUP ALGORITHMS 49

Step 6 For Step 5 to branch to this step, both Steps 2 and 4 must be successful. Thus the probability of branching to step 6 is P rob_{Success} (Step 2) · P rob_{Success} (Step 2) = Ω ((\frac{1}{lg lg Q})^{n+1})

Since the Steps 2 through 5 loop will on average be executed O ((lg lg Q)^{n+1}) times, the average algorithmic complexity of the Vintage Z_{Q} Shor algorithm is O (n^{2} (log Q)^{3} (lg lg Q)^{n+1}). (This is, of course, not the tightest possible asymptotic bound.) We formalize this analysis as a theorem:

Figure 5. An abbreviated flowchart of the vintage Z_{Q} Shor Algorithm. The probability of a successful exit to Step 6 is Ω ((\frac{1}{lg lg Q})^{n+1}). Hence, the average

number of times Steps 2 through 5 are executed is O ((lg lg Q)^{n+1}).

Theorem 11. Assuming the three assumptions given in section 21, the average algorithmic complexity of the Vintage ℤ_{Q} Shor algorithm for finding the maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ} = ⨁_{j=1}^{n} ℤ_{P_{j}} is

O (n^{2} (lg Q)^{3} (lg lg Q)^{n+1})

22. Two alternative vintage ℤ_{Q} Shor algorithms

As two alternatives to the algorithm described in the last two sections, we give below two other vintage ℤ_{Q} Shor algorithms. Unlike the above described algorithm, these two alternative algorithms do not depend on finding a maximal Shor transversal. The first finds the order of the maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}. The second finds the entire hidden subgroup K_{φ}. Flowcharts for these two quantum algorithms are given in Figures 6 and 7.

An optimal choice for the parameter K of the following algorithm is not known at this time.

Alternative1 Vintage Shor(φ, Q, n, K)

# Input: φ : A ⟶ S, Q, rank n of A, and number of # inner loop iterations K # Output: P = lcm (P_{1}, P_{2}, … P_{n}) if hidden quotient group

# is H_{φ} = ⨁\overline{n} ; j=1 ℤ_{P_{j}}

Step 1 Set P = 1

Step 2 Select a basis a′_{1}, a′_{2}, …, a′_{n} of A and a generator ã of ℤ_{Q}

Step 3 Outer Loop

Step 4 Inner Loop for K iterations

Step 5 (ι_{μ}: Z_{Q} ⟶ A) = Rand Shor transvr({a′_{1}, a′_{2}, …, a′_{n}} , Q, ã, n)

Step 6 Construct φ̃ = φ ∘ ι_{μ} : ℤ_{Q} ⟶ S
Step 7 χ_{\frac{y}{Q}} = QRandφ̃ ()
Step 8 (d′′, P′′) = (0, 1) # 0-th Cont. Frac. Converg. of \frac{y}{Q}

(d′, P′) = (1, ⌊\frac{Q}{y}⌋) # 1-th Cont. Frac. Converg. of \frac{y}{Q} Innermost Loop

(Save d′, Save P′) = (d′, P′)

(d′, P′) = Nxt Cont Frac Convrg(\frac{y}{Q}, (d′, P′) , (d′′, P′′)) (d′′, P′′) = (Save d′, Save P′) If φ (P′ι_{μ} \binom{}{a}) = φ (0) Then Goto Step 9

If \frac{d′}{P′} = \frac{y}{Q} Then Goto Step 4 Innermost Loop Boundary

QUANTUM HIDDEN SUBGROUP ALGORITHMS 51

– Step 9 P = lcm (P, P′) Step 10 Inner Loop Lower Boundary Step 11 If φ (P a_{j}) = φ (0) for j = 1, 2, …, n Then Goto Step 13

Step 12 Outer Loop Lower Boundary Step 13 Output P′ and Stop

Figure 6. The First Alternate Vintage ℤ_{Q} Shor QHSA. This is a Wandering Shor algorithm.

52 SAMUEL J. LOMONACO, JR. AND LOUIS H. KAUFFMAN

The following wandering Shor algorithm actually finds the entire hidden quotient group H_{φ}, and hence the hidden subgroup K_{φ}:

Alternative2 Vintage Shor(φ, Q, n)

# Input: φ : A ⟶ S, Q, rank n of A # Output: A matrix 𝔊 with row span equal to the # hidden subgroup K_{φ} = ⨁_{j=1}^{n} P_{j}ℤ

Step 1 Set 𝔊 = [ ] and NonZeroRows = 0 Step 2 Select a basis a′_{1}, a′_{2}, …, a′_{n} of A and a generator ã of ℤ_{Q} Step 3 Outer Loop Until NonZeroRows = n

– Step 4 (ι_{μ}: Z_{Q} ⟶ A) = RanShorTransvrsl({a′_{1}, a′_{2}, …, a′_{n}} , Q, ã, n) Step 5 Construct φ̃ = φ ∘ ι_{μ} : ℤ_{Q} ⟶ S Step 6 χ_{\frac{y}{Q}} = QRandφ̃ () Step 7 (d′′, P′′) = (0, 1) # 0-th Cont. Frac. Converg. of \frac{y}{Q}

(d′, P′) = (1, ⌊\frac{Q}{y}⌋) # 1-th Cont. Frac. Converg. of \frac{y}{Q} Inner Loop

(Save d′, Save P′) = (d′, P′)

(d′, P′) = NextContFracConverg(\frac{y}{Q}, (d′, P′) , (d′′, P′′)) (d′′, P′′) = (Save d′, Save P′) If φ (P′ι_{μ} \binom{}{a}) = φ (0) Then Goto Step 8 If \frac{d′}{P′} = \frac{y}{Q} Then Goto Step 11 Inner Loop Boundary: Continue

– Step 8 𝔊 = [ \begin{matrix}𝔊 \\ − − − − − − − − − − −− \\ P′λ′_{1} & P′λ′_{2} & … & P′λ′_{n} \end{matrix} ]

Step 9 𝔊 = Put In Echelon Canonical Form(𝔊) Step 10 NonZeroRows = Number of Non Zero Rows(𝔊)

Step 11 Outer Loop Lower Boundary: Continue Step 12 Output matrix 𝔊 and Stop

QUANTUM HIDDEN SUBGROUP ALGORITHMS 53

Figure 7. The Second Alternate Vintage ℤ_{Q} Shor QHSA. This is a Wandering Shor algorithm.

Part 6. Epilogue

23. Conclusion

Each of the three vintage ℤ_{Q} Shor QHSAs created in this paper is a natural generalization of Shor’s original quantum factoring algorithm to free abelian groups A of finite rank n . The first two of the three find a maximal cyclic subgroup ℤ_{P} of the hidden quotient group H_{φ}. The last of the three does more. It finds the entire hidden quotient group H_{φ}.

We also note that these QHSAs can be viewed from yet another perspective as wandering Shor algorithms on free abelian groups. By this we mean quantum algorithms which, with each iteration, first select a random cyclic direct summand ℤ of the ambient group A and then apply one iteration of the standard Shor algorithm on ℤ to produce a random character of the “approximating” group Ã = ℤ_{Q}.

From this perspective, under the assumptions given in section 21, the algorithmic complexity of the first of these wandering QHSAs is found to be

O (n^{2} (lg Q)^{3} (lg lg Q)^{n+1}) .

Obviously, much remains to be accomplished.

It should be possible to extend the vintage ℤ_{Q} Shor algorithms to quantum algorithms with more general group probes of the form

Ã = ⨁_{j=1}^{m}ℤ_{Q_{j}}

for m > 1. This would be a full generalization of Shor’s quantum factoring algorithm to the abelian category.

It is hoped that this paper will provide a useful stepping stone to the construction of QHSAs on non-abelian groups.

24. Acknowledgement

We would like to thank Tom Armstrong, Howard Brandt, Eric Rains, Fernando Souza, Umesh Vazirani, and Yaacov Yesha for some helpful discussions. We would also like to thank the referee for some helpful suggestions.

25. Appendix A. Continued fractions

We give a brief summary of those aspects of the theory of continued fractions that are relevant to this paper. (For a more in-depth explanation of the theory of continued fractions, please refer, for example, to [21] and [31].)

Every positive rational number ξ can be written as an expression in the form

ξ = a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+_{\frac{1}{a_{3}+ \frac{1}{···+ \frac{1}{a_{N}}}}}}}} ,

where a_{0} is a non-negative integer, and where a_{1}, …, a_{N} are positive integers. Such an expression is called a (finite, simple) continued fraction, and is uniquely determined by ξ provided we impose the condition a_{N} > 1. For typographical simplicity, we denote the above continued fraction by

[a_{0}, a_{1}, …, a_{N}] .

The continued fraction expansion of ξ can be computed with the following recurrence relation, which always terminates if ξ is rational:

\{ \begin{matrix}a_{0} = ⌊ξ⌋ \\ ξ_{0} = ξ − a_{0} \end{matrix} , and if ξ_{n} ≠ 0, then \{ \begin{matrix}a_{n+1} = ⌊1/ξ_{n}⌋ \\ ξ_{n+1} = \frac{1}{ξ_{n}} − a_{n+1} \end{matrix}

The n-th convergent (0 ≤ n ≤ N) of the above continued fraction is defined as the rational number ξ_{n} given by

ξ_{n} = [a_{0}, a_{1}, …, a_{n}] .

Each convergent ξ_{n} can be written in the form, ξ_{n} = \frac{p_{n}}{q_{n}}, where p_{n} and q_{n} are relatively prime integers ( gcd (p_{n}, q_{n}) = 1). The integers p_{n} and q_{n} are determined by the recurrence relation

\begin{matrix}p_{0} = a_{0}, & p_{1} = a_{1}a_{0} + 1, & p_{n} = a_{n}p_{n−1} + p_{n−2}, \\ q_{0} = 1, & q_{1} = a_{1}, & q_{n} = a_{n}q_{n−1} + q_{n−2} . \end{matrix}

The subroutine

Next Cont Frac Convergent

found in the vintage ℤ_{Q} Shor algorithm given in section 20 is an embodiment of the above recursion.

This recursion is used because of the following theorem which can be found in [21, Theorem 184, Secton 10.15]:

Theorem 12. Let ξ be a real number, and let d and P be integers with P > 0. If

|ξ − \frac{d}{P} | ≤ \frac{1}{2P^{2}} ,

then the rational number d/P is a convergent of the continued fraction expansion of ξ.

26. Appendix B. Probability Distributions on Integers

Let

P rob_{Q} : {1, 2, …, Q} ⟶ [0, 1]

denote the uniform probability distribution on the finite set of integers {1, 2, …, Q}. Thus, the probability that a random integer λ from {1, 2, …, Q} is divisible by a given prime p is

P rob_{Q} ( p|λ ) = \frac{⌊Q/p⌋}{Q} ≤ \frac{1}{p} ,

where ‘⌊−⌋’ denotes the the floor function.

The limit P rob_{∞} , should it exist, of the probability distribution P rob_{Q} as Q approaches infinity, i.e.,

P rob_{∞} = lim_{Q⟶∞} P rob_{∞} ,

will turn out to be a useful tool. Since P rob_{∞} is not a probability distribution, we will call it a pseudo-probability distribution on the integers ℤ. It immediately follows that

P rob_{∞} ( p|λ ) = \frac{1}{p}.

In this sense, we say that the pseudo-probability of a random integer λ ∈ ℤ being divisible by a given prime p is 1/p.

Theorem 13. Let n be an integer greater than 1. Let λ′_{1}, λ′_{2}, …, λ′_{n}, be n integers selected randomly and independently with replacement from the set {1, 2, …, Q} according to the uniform probability distribution. Then the probability that

gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1

is

P rob_{Q} (gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1) = ∑_{k=1}^{Q}μ (k) (\frac{⌊Q/k⌋}{Q})^{n} ,

where ‘ ⌊−⌋’ and ‘μ (−)’ respectively denote the floor and Möbius functions. Moreover,

P rob_{∞} (gcd (λ′_{1}, λ′_{2}, …, λ′_{n}) = 1) = ζ (n)^{−1} ,

where ζ (n) denotes the Riemann zeta function ζ (n) = ∑_{k=1}^{∞} \frac{1}{k^{n}}.

QUANTUM HIDDEN SUBGROUP ALGORITHMS 57

Proof. Let P rimes_{Q} denote the set of primes less than or equal to Q. For each prime p and integer 0 < j ≤ n, let A_{pj} denote the set

A_{pj} = \{\overrightarrow{λ} ∈ \{1, …, Q\}^{n} : p | λ_{j}\} .

Since

⋂_{p∈P rimes_{Q}} ⋃_{j=1}^{n}\overline{A}_{pj} = \{\overrightarrow{λ} ∈ \{1, …, Q\}^{n} : ∀p∃j p | λ_{j}\},

we have

P rob_{Q} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = P rob_{Q} ( ⋂_{p∈P rimes_{Q}} ⋃_{j=1}^{n} \overline{A}_{pj}) ,

where \overline{A}_{pj} denotes the complement of A_{pj}.

We proceed to compute P rob_{Q} ( ⋂_{p∈P rimes_{Q}} ⋃_{j=1}^{n} \overline{A}_{pj}) by first noting that:

P rob_{Q} ( ⋂_{p∈P rimes_{Q}} ⋃_{j=1}^{n} \overline{A}_{pj}) = 1 − P rob_{Q} ( ⋃_{p∈P rimes_{Q}} ⋂_{j=1}^{n} A_{pj}) .

So by the inclusion/exclusion principle, we have

P rob_{Q} ( ⋃_{p∈P rimes_{Q}} ⋂_{j=1}^{n} A_{pj}) = − ∑_{S⊆P rimes_{Q}_{S≠∅}} (−1)^{|S|} P rob_{Q} ( ⋂_{p∈S} ⋂_{j=1}^{n} A_{pj})

= − ∑_{S⊆P rimes_{Q}_{S≠∅}} (−1)^{|S|} P rob_{Q} ( ⋂_{j=1}^{n} ⋂_{p∈S} A_{pj})

Since the λ_{j}’s are independent random variables, we have

P rob_{Q} ( ⋂_{j=1}^{n} ⋂_{p∈S} A_{pj}) = ∏_{j=1}^{n}P rob_{Q} ( ⋂_{p∈S} A_{pj})

Moreover, it follows from a straight forward counting argument that

P rob_{Q} ( ⋂_{p∈S} A_{pj}) = ⌊Q/ ∏_{p∈S} p⌋ /Q ,

from which we obtain

P rob_{Q} ( ⋂_{j=1}^{n} ⋂_{p∈S} A_{pj}) = ∏_{j=1}^{n} ⌊Q/ ∏_{p∈S} p⌋ /Q = (⌊Q/ ∏_{p∈S} p⌋ /Q)^{n} .

Thus,

P rob_{Q} ( ⋂_{p∈P rimes_{Q}} ⋃_{j=1}^{n} \overline{A}_{pj}) = ∑_{S⊆P rimes_{Q}} (−1)^{|S|} (⌊Q/ ∏_{p∈S} p⌋ /Q)^{n}

This last expression expands to

1 − ∑_{p≤Q_{p Prime}} (\frac{⌊Q/p⌋}{Q})^{n} + ∑_{p<p′≤Q_{p,p′ Prime}} (\frac{⌊Q/pq⌋}{Q})^{n} − ∑_{p<p′<p′′≤Q_{p,p′,p′′ Prime}} (\frac{⌊Q/pp′p′′⌋}{Q})^{n} + …,

which can be rewritten as

∑_{k=1}^{Q}μ (k) (\frac{⌊Q/k⌋}{Q})^{n}

since μ (k) = 0 for all integers k that are not squarefree.

The last part of this theorem follows immediately from the fact that

lim_{Q⟶∞} ∑_{k=1}^{Q}μ (k) (\frac{⌊Q/k⌋}{Q})^{n} = ∑_{k=1}^{∞}μ (k) \frac{1}{k^{n}} = ζ (n)^{−1} .

(See [40], [42], or [21].)

Corollary 7. Let n be an integer greater than 1, and let λ′_{1}, λ′_{2}, …, λ′_{n} be n integers randomly and independently selected with replacement from the set {1, 2, …, Q} according to the uniform probability distribution. Let M be a fixed element of the group SL_{±} (n, ℤ) of invertible n × n integer matrices. Finally, let λ_{1}, λ_{2}, …, λ_{n} be n integers given by

(λ_{1}, λ_{2}, …, λ_{n})^{transpose} = M (λ′_{1}, λ′_{2}, …, λ′_{n})^{transpose} .

Then the probability that

gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1

is

P rob_{Q} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = ∑_{k=1}^{Q}μ (k) (\frac{⌊Q/k⌋}{Q})^{n} ,

where ‘ ⌊−⌋’ and ‘μ (−)’ respectively denote the floor and Möbius functions. Moreover,

P rob_{∞} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = ζ (n)^{−1} ,

where ζ (n) denotes the Riemann zeta function ζ (n) = ∑_{k=1}^{∞} \frac{1}{k^{n}}. Hence,

P rob_{Q} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = Ω (ζ (n)^{−1}) = Ω (1)

Proof. This corollary immediately follows from the fact that the gcd is invariant under the action of SL_{±} (n, ℤ).

Remark 11. We conjecture that a stronger result holds, namely that the func-

tion ζ (n)^{−1} is actually a lower bound for P rob_{Q} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) for

Q ≥ n.

We need to make the following conjecture to estimate the algorithmic complexity of Vintage ℤ_{Q} algorithms, also called wandering Shor algorithms.

Conjecture 1. Let n be an integer greater than 1, let P_{1}, P_{2}, …, P_{n} be n fixed positive integers, and let λ′_{1}, λ′_{2}, …, λ′_{n} be n integers randomly and independently selected with replacement from the set {1, 2, …, Q} according to the uniform probability distribution. Let M be a fixed element of the group SL_{±} (n, ℤ) of invertible n × n integral matrices, and let

(λ_{1}, λ_{2}, …, λ_{n}) = M (λ′_{1}, λ′_{2}, …, λ′_{n})

Then the conditional pseudo-probability

P rob_{∞} (gcd (λ_{j}, P_{j}) = 1 ∀j | gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1)

is given by

∏_{p Prime_{p|lcm(P_{1},... ,Pn)}} (1 − p^{−n})^{∏_{j=1}^{n} \frac{φ(P_{j})}{P_{j}}} ≥ ∏_{j=1}^{n} \frac{φ (P_{j})}{P_{j}} ,

where ζ (−) and φ (−) denote respectively the Riemann zeta and the Euler totient functions.

Plausibility Argument. (This is not a proof.)

We treat P rob_{∞} as if it were a probability distribution on the integers ℤ^{n} = {(λ_{1}, λ_{2}, …, λ_{n})}. We assume that M maps this distribution on itself, and that P rob_{∞} (p | λ_{j}) and P rob_{∞} (q | λ_{j}) are stochastically independent when p and q are distinct primes.

For fixed j, the probability P rob_{∞} (p ∤ λ_{j}) that a given prime divisor p of P_{j} does not divide λ′_{j} is

1 − \frac{1}{p}.

Hence, the probability that P_{j} and λ_{j} are relatively prime is

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1) = ∏_{p|P_{j}} (1 − \frac{1}{p}) .

This can be reexpressed in terms of the Euler totient function as

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1) = \frac{φ (P_{j})}{P_{j}}

Since λ_{1}, λ_{2}, …, λ_{n} are independent random variables, we have

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1∀j) = ∏_{j=1}^{n} \frac{φ (P_{j})}{P_{j}} .

On the other hand, the probability that a given prime p does not divide all the integers λ_{1}, λ_{2}, …, λ_{n} is

1 − \frac{1}{p^{n}}.

Thus,

P rob_{∞} (p ∤ gcd (λ_{1}, λ_{2}, …, λ_{n})∀p s.t. p ∤ lcm (P_{1}, P_{2}, …, P_{n}))

is given by the expression

∏_{p∤lcm(P_{1},P_{2},... ,P_{n})} (1 − p^{−n}) = \frac{ζ (n)^{−1}}{∏_{p|lcm(P_{1},P_{2},... ,P_{n})} (1 − p^{−n})} ,

where we have used the fact [21] that

ζ (n)^{−1} = ∏_{p Prime} (1 − \frac{1}{p^{n}} ).

We next note that the events ∀j gcd (P_{j}, λ_{j}) = 1 and ∀p p ∤ lcm (P_{1,}P_{2}, …, P_{n}) ⟶ p ∤ gcd (P_{1,}P_{2}, …, P_{n}) are stochastically independent since they respectively refer to the disjoint sets of primes {p : p | lcm (P_{1}, P_{2}, …, P_{n})} and {p : p ∤ lcm (P_{1}, P_{2}, …, P_{n})}. Hence, the probability of the joint event

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1 ∀j AND gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1)

is given by the expression

\frac{ζ (n)^{−1} ∏_{j=1}^{n} \frac{φ(P_{j})}{P_{j}}}{∏_{p|lcm(P_{1},P_{2},... ,P_{n})} (1 − p^{−n})} .

Using exactly the same argument as that used to find an expression for

P rob_{∞} (p ∤ gcd (λ_{1}, λ_{2}, …, λ_{n})∀p s.t. p ∤ lcm (P_{1}, P_{2}, …, P_{n})) ,

we have

P rob_{∞} (gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = ζ (n)^{−1} .

Hence the conditional probability

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1 ∀j | gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1)

is given by the expression

∏_{p|lcm(P_{1},P_{2},... ,P_{n})} (1 − p^{−n})^{∏_{j=1}^{n} \frac{φ(P_{j})}{P_{j}}}

Finally, since

∏_{p|lcm(P_{1},P_{2},... ,P_{n})} (1 − p^{−n}) ≤ 1 ,

it follows that the conditional probability

P rob_{∞} (gcd (P_{j}, λ_{j}) = 1 ∀j | gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1)

is bounded below by the expression

∏_{j=1}^{n} \frac{φ (P_{j})}{P_{j}} .

The following is an immediate corollary of the above conjecture.

Corollary 8. Let n be an integer greater than 1, and let P_{1}, P_{2}, …, P_{n} be n fixed positive integers. Let λ′_{1}, λ′_{2}, …, λ′_{n} be n integers randomly and independently selected with replacement from the set all integers ℤ according to the uniform probability distribution. Let M be a fixed element of the group SL_{±} (n, ℤ) of invertible n × n integer matrices. Finally, let λ_{1}, λ_{2}, …, λ_{n} be n integers given by

(λ_{1}, λ_{2}, …, λ_{n})^{transpose} = M (λ′_{1}, λ′_{2}, …, λ′_{n})^{transpose} .

Then, assuming conjecture 1, we have

P rob_{∞} (gcd (λ_{j}, P_{j}) = 1 ∀j | gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = Ω (∏_{j=1}^{n} \frac{1}{lg lg P_{j}} ) ,

where Ω (−) denotes the asymptotic lower bound ‘big-omega.’ Thus, if Q is greater than each P_{j}, we have

P rob_{Q} (gcd (λ_{j}, P_{j}) = 1 ∀j | gcd (λ_{1}, λ_{2}, …, λ_{n}) = 1) = Ω ((\frac{1}{lg lg Q})^{n})

Proof. Since^{18}

\underline{lim}\frac{φ (n) ln ln n}{n} = e^{−γ} ,

where γ denotes Euler’s constant, we have that

\frac{φ (P_{j})}{P_{j}} = Ω (\frac{1}{lg lg P_{j}} )

18See [21, Theorem 328, Section 18.4].

Thus, an asymptotic lower bound for the above conditional probability is given by the expression

Ω (∏_{j=1}^{n} \frac{1}{lg lg P_{j}} ) .

References

[1] Alber, G., T. Beth, M. Horodecki, P. Horodecki, R. Horodecki, M. Rotteler, H. Weinfurther, R. Werner, and A. Zeilinger, “Quantum Information: An Introduction to Basic Theoretical Concepts and Experiments,” Springer, (2001).

[2] Bach, Eric, and Jeffrey Shallit, “Algorithmic Number Theory: Volume I: Efficient Algorithms,” MIT Press, (1997).

[3] Bernstein, Ethan, and Umesh Vazirani, Quantum Complexity Theory, SIAM J. of Computing, Vol. 26, No. 5, (1997), pp 1411-1473.

[4] Boneh, Dan, and Richard J. Lipton, Quantum cryptanalysis of hidden linear functions, in “Lecture Notes in Computer Science – Advances in Cryptology – CRYPTO’95,” D. Coppersmith (ed.), Springer-Verlag, Berlin, (1995), pp 424-437.

[5] Brassard, Gilles, and Paul Bratley, “Algorithmics: Theory and Practice,” Printice-Hall, (1988).

[6] Brassard, Gilles and Peter Hoyer, An exact quantum polynomial-time algorithm for Simon’s problem, Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems – ISTCS, IEEE Computer Society Press, (1997), pp. 12-23.

[7] Cartan, Henri, and Samuel Eilenberg, “Homological Algebra,” Princeton University Press, (1956).

[8] Cheung, Kevin K.H., and Michele Mosca, Decomposing finite abelian groups, http://xxx.lanl.gov/abs/cs.DS/0101004.

[9] Cleve, Richard, Artur Ekert, Chiara Macchiavello, and Michele Mosca, Quantum Algorithms Revisited, Phil. Trans. Roy. Soc. Lond., A, (1997). http://xxx.lanl.gov/abs/quantph/9708016

[10] Coppersmith, D., An approximate quantum Fourier transform used in quantum factoring, IBM Research Report RC 19642, (1994).

[11] Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest, “Introduction to Algorithms,” McGraw-Hill, (1990).

[12] Cox, David, John Little, and Donal O’Shea, “Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra” (second edition), Springer-Verlag, (1996).

[13] Cox, David, John Little, and Donal O’Shea, “Using Algebraic Geometry,” Springer, (1998).

[14] Ekert, Artur K.and Richard Jozsa, Quantum computation and Shor’s factoring algorithm, Rev. Mod. Phys., 68,(1996), pp 733-753.

[15] Ettinger, Mark, and Peter Hoyer, On Quantum Algorithms for Noncommutative Hidden Subgroups, (1998). http://xxx.lanl.gov/abs/quant-ph/9807029

[16] Ettinger, Mark, Peter Hoyer, Emanuel Knill, Hidden Subgroup States are Almost Orthogonal, http://xxx.lanl.gov/abs/quant-ph/9901034.

[17] Fulton, William, and Joe Harris, “Representation Theory,” Springer-Verlag, (1991).

[18] Gathen, Joachim von zur, and Jurgen Gerhard, “Modern Computer Algebra,” Cambridge University Press, (1999).

[19] Geddes, Keith O., Stephen R. Czapor, and George Labahn, “Algorithms for Computer Algebra,” Kluwer Academic Publishers, Boston, (1992).

[20] Hall, Marshall, Jr., “The Theory of Groups,” Macmillan, New York, (1959).

[21] Hardy, G.H., and E.M. Wright, “An Introduction to the Theory of Numbers,” Oxford Press, (1965).

[22] Hirvensalo, Mika, “Quantum Computing,” Springer, (2001).

[23] Hoyer, Peter, Efficient quantum transforms, http://xxx.lanl.gov/abs/quant-ph/9702028.

[24] Ivanyos, Gabor, Frederic Magniez, and Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, (2001). http://xxx.lanl.gov/abs/quant-ph/0102014

[25] Jozsa, Richard, Quantum algorithms and the Fourier transform, quant-ph preprint archive 9707033 17 Jul 1997.

[26] Jozsa, Richard, Proc. Roy. Soc. London Soc., Ser. A, 454, (1998), 323 - 337.

[27] Jozsa, Richard, Quantum factoring, discrete logarithms and the hidden subgroup problem, IEEE Computing in Science and Engineering, (to appear). http://xxx.lanl.gov/abs/quantph/0012084

[28] Kemeny, John G., and J. Laurie Snell, “Finite Markov Chains,” Van Nostrand, (1960).

[29] Kitaev, A., Quantum measurement and the abelian stabiliser problem, (1995), quant-ph preprint archive 9511026.

[30] Knuth, Donald E., “The Art of Computer Programming,” (second edition), Addison-Wesley, Reading, Massachusetts, (1981).

[31] LeVeque, , William Judson, “Topics in Number Theory,” Addison-Wesley, (1956).

[32] Lomonaco, Samuel J., Jr., A Rosetta Stone for quantum mechanics with an introduction to quantum computation, in “Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium” PSAPM/58, American Mathematical Society, Providence, RI, (2002). (http://xxx.lanl.gov/abs/quant-ph/0007045)

[33] Lomonaco, Samuel J., Jr., Shor’s quantum factoring algorithm, in “Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium,” PSAPM/58, American Mathematical Society, Providence, RI, (2002). (http://xxx.lanl.gov/abs/quant-ph/0010034)

[34] Lomonaco,  Samuel  J.,  Jr.,  The  non-abelian  Fourier  trans-
form and quantum computation,  MSRI Streaming Video,  (2000),

http://www.msri.org/publications/ln/msri/2000/qcomputing/lomonaco/1/index.html

[35] Mosca, Michelle, and Artur Ekert, The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer, Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication, Springer-Verlag, (to appear). (http://xxx.lanl.gov/abs/quant-ph/9903071)

[36] Nielsen, Michael A., and Isaac L. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press, (2000).

[37] Preskill, John, “Quantum Computation,” Lecture Notes, http://www.theory.caltech.edu/people/preskill/ph229/#lecture

[38] Pueschel, Markus, Martin Roetteler, and Thomas Beth, Fast Quantum Fourier Transforms for a Class of Non-abelian Groups, (1998). http://xxx.lanl.gov/abs/quantph/9807064

[39] Roetteler, Martin, and Thomas Beth, Polynomial-Time Solution to the Hidden Subgroup Problem for a Class of non-abelian Groups, (1998). http://xxx.lanl.gov/abs/quant-ph/9812070

[40] Rosser, J. Barkley, and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math., v.6, (1962), pp. 64-94.

[41] Russell, Alexander, and Amnon Ta-Shma, Normal Subgroup Reconstruction and Quantum Computation Using Group Representations, STOC, (2000).

[42] Schoenfeld, Lowell, Sharper bounds for the Chebyshev functions θ (x) and ψ (x). II, Math. Comp., vol. 30, No. 134, (1976), pp. 337-360.

[43] Shor, Peter W., Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. on Computing, 26(5) (1997), pp 1484 - 1509. (http://xxx.lanl.gov/abs/quant-ph/9508027)

[44] Shor, Peter W., Introduction to quantum algorithms, in “Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium,” PSAPM/58, American Mathematical Society, Providence, RI, (2002). (http://xxx.lanl.gov/abs/quant-ph/0005003)

[45] Simon, Daniel R., On the power of quantum computation, SIAM J. Comput., Vol. 26, No. 5, (1997), pp 1474-1483.

[46] van Dam, Wim, and Sean Hallgren, Efficient Quantum Algorithms for Shifted Quadratic Character Problems, http://xxx.lanl.gov/abs/quant-ph/0011067.

[47] Vazirani, Umesh, On the power of quantum computation, Philosophical Tranactions of the Royal Society of London, Series A, 354:1759-1768, August 1998.

[48] van Dam, Wim, and Lawrence Ip, Quantum Algorithms, for Hidden Coset Problems, manuscript, http://www.cs.caltech.edu/˜ hallgren/hcp.pdf

(Samuel J. Lomonaco, Jr.) Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 21250

E-mail address, Samuel J. Lomonaco, Jr.: Lomonaco@UMBC.EDU

URL: WebPage:  http://www.csee.umbc.edu/~lomonaco

(Louis H. Kauffman) Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7045

E-mail address, Louis H. Kauffman: kauffman@uic.edu

URL: WebPage:  http://math.uic.edu/~kauffman