#### Termes les plus recherchés

# [PDF](+54👁️) Télécharger Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit pdf

#### One of the most promising and versatile approaches to creating new quantum algorithms is based on the quantum hidden subgroup (QHS) paradigm, originally suggested by Alexei Kitaev. This class of quantum algorithms encompasses the Deutsch-Jozsa, Simon, Shor algorithms, and many more. In this paper, our strategy for finding new quantum algorithms is to decompose Shor's quantum factoring algorithm into its basic primitives, then to generalize these primitives, and finally to show how to reassemble them into new QHS algorithms. Taking an "alphabetic building blocks approach," we use these primitives to form an "algorithmic toolkit" for the creation of new quantum algorithms, such as wandering Shor algorithms, continuous Shor algorithms, the quantum circle algorithm, the dual Shor algorithm, a QHS algorithm for Feynman integrals, free QHS algorithms, and more. Toward the end of this paper, we show how Grover's algorithm is most surprisingly "almost" a QHS algorithm, and how this resultTélécharger gratuit Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit pdf

QUANTUM HIDDEN SUBGROUP ALGORITHMS: AN

ALGORITHMIC TOOLKIT

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

Abstract. One of the most promising and versatile approaches to creating

new quantum algorithms is based on the quantum hidden subgroup (QHS)

paradigm, originally suggested by Alexei Kitaev. This class of quantum al-

gorithms encompasses the Deutsch-Jozsa, Simon, Shor algorithms, and many

more.

In this paper, our strategy for finding new quantum algorithms is to de-

compose Shor's quantum factoring algorithm into its basic primitives, then to

generalize these primitives, and finally to show how to reassemble them into

new QHS algorithms. Taking an "alphabetic building blocks approach," we

use these primitives to form an "algorithmic toolkit" for the creation of new

quantum algorithms, such as wandering Shor algorithms, continuous Shor al-

gorithms, the quantum circle algorithm, the dual Shor algorithm, a QHS al-

gorithm for Feynman integrals, free QHS algorithms, and more.

Toward the end of this paper, we show how Grover's algorithm is most

surprisingly "almost" a QHS algorithm, and how this result suggests the pos-

sibility of an even more complete "algorithmic tookit" beyond the QHS algo-

rithms.

Contents

1.

Introduction!

2

2.

An example of Shor's Quantum factoring algoi'Mrm]

2

3.

Definition of Quantum hidden subgroup fOHS) algorithms!

6

4.

The generic QH^^^^^^^

7

5.

Pushing and Lifting hidden subgroup problems (HSPsI

8

Shor's algorithrnr^vj^h^dj

10

L_

Wandering Shor algorithms, a.k.a.. vintage Shor algorithms.!

11

8.

Continuous (variable) Shor alg^^^^^

16

9.

The Quantum circle and the dual Shor algorithms.!

17

10.

A QHS algorithm for Fevnman integrals]

22

11.

OHS algorithms on frcc^roug^

24

12.

Generalizing Shor's algorithm to free groups!

2G

13.

Is Grover's algorithm a OHS algorithm?!

28

14.

Bcvond OHS algorithms: The suggestions of a meta-scheme for creating new Quantum algorithms!

15.

Acknowledgement!

32

References!

33

Date: May 22, 2006.

2000 Mathematics Subject Classification. Primary 81P68; Secondary 68Q05, 81Q99.

Key words and phrases. Quantum algorithms, Quantum hidden subgroup algorithms, Quan-

tum computing, Quantum computation, Shor's algorithm, Grover's algorithm, Quantum informa-

tion, algorithms.

2

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

1. Introduction

One major obstacle to the fulfillment of the promise of quantum computing is the

current scarcity of quantum algorithms. Quantum computing researchers simply

have not yet found enough quantum algorithms to determine whether or not future

quantum computers will be general purpose or special purpose computing devices.

As a result, much more research is crucially needed to determine the algorithmic

limits of quantum computing.

One of the most promising and versatile approaches to creating new quantum

algorithms is based on the quantum hidden subgroup (QHS) paradigm, originally

suggested by Alexei Kitaev (201 • This class of quantum algorithms encompasses

the Deutsch-Jozsa, Simon, Shor algorithms, and many more.

In this paper, our strategy for finding new quantum algorithms is to decompose

Shor's quantum factoring algorithm into its basic primitives, then to generalize

these primitives, and finally to show how to reassemble them into new QHS algo-

rithms. Taking an "alphabetic building blocks approach," we will use these primi-

tives to form an "algorithmic toolkit" for the creation of new quantum algorithms,

such as wandering Shor algorithms, continuous Shor algorithms, the quantum circle

algorithm, the dual Shor algorithm, a QHS algorithm for Feynman integrals, free

QHS algorithms, and more.

Toward the end of this paper, we show how Grover's algorithm is most surpris-

ingly "almost" a QHS algorithm, and how this suggests the possibility of an even

more complete "algorithmic tookit" beyond the QHS algorithms.

2. An example of Shor's quantum factoring algorithm

Before discussing how Shor's algorithm can be decomposed into its primitive

components, let's take a quick look at an example of the execution of Shor's fac-

toring algorithm. As we discuss this example, we suggest that the reader, as an

exercise, try to find the basic QHS primitives that make up this algorithm. Can

you see them?

Shor's quantum factoring algorithm reduces the task of factoring a positive in-

teger A to first finding a random integer a relatively prime to A, and then next to

determining the period P of the following function

Z ZmodA

x i — ► a x mod N ,

where Z denotes the additive group of integers, and where ZmodA denotes the

integers mod A under multiplication 1 .

A random integer a with gcd (a, TV) = 1 is found by selecting a random integer, and then

applying the Euclidean algorithm to determine whether or not it is relatively prime to TV. If not,

then the gcd is a non-trivial factor of TV, and there is no need to proceed futher. However, this

possibility is highly unlikely if TV is large.

QHS ALGORITHMS

3

Since Z is an infinite group, Shor chooses to work instead with the finite ad-

ditive cyclic group Zq of order Q = 2 m , where N 2 < Q < 2N 2 , and with the

"approximating" map

Z Q ZmodTV

x i — ► a 11 mod N , < x < Q

Shor begins by constructing a quantum system with two quantum registers

| Left_Register) |Right_Register) ,

the left intended for holding the arguments x of tp, the right for holding the corre-

sponding values of yp. This quantum system has been constructed with a unitary

transformation

Uf.\x)\\)^\x)\<p(x))

implementing the "approximating" map p.

As an example, let us use Shor's algorithm to factor the integer N = 21, assuming

that a = 2 has been randomly chosen. Thus, Q — 2 9 = 512.

Unknown to us, the period is P = 6, and hence, Q = 6 • 85 + 2.

We proceed by executing the following steps:

STEP Initialize

m = io> ii>

STEP 1 Apply the inverse Fourier transform

511

T- 1 : |«) ^^=Ylo- ux \x)

512 „

to the left register, where u — exp(27ri/512) is a primitive 512-th root of

unity, to obtain

7 512 „

STEP 2 Apply the unitary transformation

U$ : \x) |1) i — ► \x) |2 x mod21)

to obtain

|V> 2 > = -^=J2\x)\2* mod 21)

Actually, for this step, the original Shor algorithm uses instead the Hadamard transform,

which for step 1, has the same effect as the 512-point Fourier transform.

STEP 3

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

Apply the Fourier transform

511

^ n

to the left register to obtain

511 511

511 /511

M*> = E E wBW if) i 2 " mod 21 > = m E iw> ( E ^ y i 2X mod 21

ie=0 y=0

512

a =0 \a;=0

^ Ely) It (2/))

y=0

where

511

|T(y)) = ^^12* mod 21)

z=0

sTEP 4 I Measure the left register. Then with Probability

T(y)\T(y))

Probq, (y)

(512)

the state will "collapse" to \y) with the value measured being the integer

y, where < y < Q.

A plot of Prob^p (y) is shown in Figure 1. (See |^] and [25] for details.)

0.1

Prob

0.08

[y = 85| [y =

= 256 |

|y = 341] [ y =427]

JL

y

Figure 1. A plot of Prob^(y).

QHS ALGORITHMS

5

The peaks in the above plot of Prob^ (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

y_ _ d_

Q P

1 1

< 2Q K 2P2

In particular,

85 171 256 341 427

512' 512' 512 '512' 512' 512

are rationals respectively "closest" to the rationals

1 2 3 4 5

6' 6' 6' 6' 6' 6 '

The six rational numbers 0/6, 1/6, ... , 5/6 are "closest" in the sense that they 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

using the standard continued fraction recursion formulas.

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 obtained 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 0(6) /6 = 1/3, where </>(—) denotes the Euler phi (toticnt)

function. So the probability of finding P = 6 is actually not 0.78 + , but is instead

0.23".

As it turns out, if he repeats the algorithm O (lglg N) times, we will obtain the

desired period P with probability bounded below by approximately 4/n 2 . However,

this is not the end of the story. Once we have in our possession a candidate P' for

the actual period P = 6, the only way we can be sure we have the correct period

P is to test P' by computing 2 P mod 21. If the result is 1, we are certain we

have found the correct period P. This last part of the computation is done by the

repeated squaring algorithm 3 .

3 By the repeated squaring algorithm, we mean the algorithm which computes a p mod N via

the expression

Hi-)'"-

3

where P ' = £V P'p? is the radix 2 expansion of P' .

6

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

3. Definition of quantum hidden subgroup (QHS) algorithms

Now that we have taken a quick look at Shor's algorithm, let's see how it can

be decomposed into its primitive algorithmic components. We will first need to

answer the following question:

What is a quantum hidden subgroup algorithm?

But before we can answer the this question, we need to provide an answer to an

even more fundamental question:

What is a hidden subgroup problem?

Definition 1. A map (p : G — > S from a group G into a set S is said to have

hidden subgroup structure if there exists a subgroup K v of G, called a hidden

subgroup, and an injection l v : G/K v — > S, called a hidden injection, such

that the diagram

G S

G/K v

is commutative 4 , where G / K v denotes the collection of right cosets of K v in G,

and where v : G — ► G/K v is the natural surjection of G onto G/K v . We refer

to the group G as the ambient group and to the set S as the target set. If

K v is a normal subgroup of G, then H v = G/K v is a group, called the hidden

quotient group, and v : G — ► G/K v is an epimorphism, called the hidden

epimorphism. We will call the above diagram the hidden subgroup structure

of the map tp : G — > S. (See \M>fM-)

Remark 1. The underlying intuition motivating this formal definition is as follows:

Given a natural surjection (or epimorphism) v : G — ► G/K v , an "archvillain with

malice of forethought" hides the algebraic structure of v by intentionally renaming

all the elements of G/K v , and "maliciously tossing in for good measure" some

extra elements to form a set S and a map ip : G — ► S.

The hidden subgroup problem can be stated as follows:

Hidden Subgroup Problem (HSP). Let tp : G — ► S be a map with hidden

subgroup structure. The problem of determining a hidden subgroup K v of G is

called a hidden subgroup problem (HSP). An algorithm solving this problem

is called a hidden subgroup algorithm.

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

Hidden Subgroup Problem (Quantum Version). Let ip : G — ► S be a map

with hidden subgroup structure. Construct a quantum implementation of the map

ip as follows:

By saying that this diagram is commutative, we mean ip = i v o v. The notion generalizes in

an obvious way to more complicated diagrams.

QHS ALGORITHMS 7

Let Tie and Tis be Hilbert spaces defined respectively by the orthonormal bases

{\g) : 5 e G}and {\s) : s G S} and let sq = ip (1), where 1 denotes the identity 5 of

the ambient group A. Finally, let U v be a unitary transformation such that

n G ®n s — ► n G <g> H s

Iff) l s o> i-> \g) \ip(g)}

Determine the hidden subgroup K v with bounded probability of error by making

as few queries as possible to the blackbox U v . A quantum algorithm solving this

problem is called a quantum hidden subgroup ( QHS) algorithm.

4. The generic QHS algorithm

We are now in a position to construct one of the fundamental algorithmic prim-

itives found in Shor's algorithm.

Let if : G — ► S be a map from a group G to a set S with hidden subgroup

structure. We assume that all representations of G are equivalent to unitary rep-

resentations 6 . Let G denote a complete set of distinct irreducible unitary

representations of G. Using multiplicative notation for G, we let 1 denote the

identity of G, and let so denote its image in S. Finally, let 1 denote the trivial

representation of G.

Remark 2. If G is abelian, then G becomes the dual group of characters.

The generic QHS algorithm is given below:

Quantum Subroutine QRand(</?)

Step 0. Initialization

|Vo) = 1) |*o> e Hq ® H s

Step 1. Application of the inverse Fourier transform ^ r G " 1 of G to the left register

where \G\ denotes the cardinality of the group G.

Step 2. Application of the unitary transformation U v

IVJ2> = -mYi^Wis)) ^n G ®n s

'We are using multiplicative notation for the group G.

'This is true for all finite groups as well as for a large class of infinite groups.

8

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

Step 3. Application of the Fourier transform Tq of G to the left register

1^} = iiEW Trace E ^ (9) |7> Hd)) = 7^ E N Trace (It> W)» e w g® w «

where I7I denotes the degree of the representation 7, where 7^ denotes

at repn

|7| |7|

the contragradient representation (i.e., 7^ (g) = 7 (g^ 1 ) = 7(3) ), where

Trace (7+ | 7 )) = EE 7ji (s) l7y>. and where $ (7],)) = E 7j» (sO |<P (s))-

i=lj=l v // geG

Step 4. Measurement of the left quantum register with respect to the orthonormal

basis

{|7ii>:7eG,l<i,j<|7|} •

Thus, with probability

Prob v (7y) = X ^2 V "

the resulting measured value is the entry 7y, and the quantum system

"collapses" to the state

Step 5. Step 5. Output 7^, and stop.

5. Pushing and Lifting hidden subgroup problems (HSPs)

But Shor's algorithm consists of more than the primitive QRand.

For many (but not all) hidden subgroup problems (HSPs) ip : G — ► 5, the cor-

responding generic QHS algorithm QRand either is not physically implemcntablc

or is too expensive to implement physically. For example, the HSP ip is usually

not physically implcmentable if the ambient group is infinite (e.g., G is the infinite

cyclic group Z) , and is too expensive to implement if the ambient group is too large

(e.g., G is the symmetric group §10100). In this case, there is a standard generic

way of "tweaking" the HSP to get around this problem, which we will call pushing.

Definition 2. Let ip : G — ► S be a map from a group G to a set S. A map

<p : G — ► S from a group G to the set S is said to be a push of p, written

p = Push (<p) ,

QHS ALGORITHMS

9

provided there exists an epimorphism v : G — ► G from G onto G, and a transversal

t : G — ► G of v such that tp = tp o t, i.e., such that the following diagram is

commutative

G S

Tr

G

If the epimorphism \i and the transversal r are chosen in an appropriate way,

then execution of the generic QHS subroutine with input tp — Push(tp) , i.e.,

execution of

QRand (tp) ,

will with high probability produce an irreducible representation 7 of the group G

which is sufficiently close to an irreducible representation 7 of the group G. If this

is the case, then there is a polynomial time classical algorithm which upon input 7

produces the representation 7.

Obviously, much more can be said about pushing. But unfortunately that

would take us far afield from the objectives of this paper. For more information

on pushing, we refer the reader to |27| .

It would be amiss not to mention that the above algorithmic primitive of pushing

suggests the definition of a second primitive which we will call lifting.

Definition 3. Let tp : G — ► S be a map from a group G to a set S. A map

ip: G — ► S from a group G to the set S is said to be a lift of tp, written

<p = Lift (tp) ,

provided there exists an morphism n : G — ► G from G to G such that tp = tp o n,

i.e., such that the following diagram is commutative

G

V I \£

G -2+ S

'Let v : A > B be an epimorphism from a group A to a group B. Then a transversal

t of v is is a map r : B > A such that u o r : B > A is the identity map b 1 — > b. (It

immediately follows that r is an injection.) In othere words, a transversal r of an epimorphism

v is a map which maps eacl element b of B to an element of A contained in the coset b, i.e., to a

coset representative of b.

10

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

Two Ways to Create New Quantum Algorithms

Pushing and Lifting

Figure 2. Pushing and Lifting HSPs.

6. SHOR'S ALGORITHM REVISITED

We are now in position to describe Shor's algorithm in terms of its primitive

components. In particular, we are now in a position to see that Shor's factoring

algorithm is a classic example of a QHS algorithm created from the push of an HSP.

Let N be the integer to be factored. Let Z denote the additive group of integers,

and Z^r denote the integers mod A" under multiplication.

Shor's algorithm is a QHS algorithm that solves the following HSP

ip : Z — ► Z^

m i — ► a m mod N

with unknown hidden subgroup structure given by the following commutative dia-

gram

Z ^ ^ N

Z/PZ

where a is an integer relatively prime to N, where P is the hidden integer period of

the map <p : Z — ► Z^ , where PZ is the additive subgroup of all integer multiples

of P (i.e., the hidden subgroup), where v : Z — > Z/PZ is the natural epimorpism

of the integers onto the quotient group Z/PZ (i.e., the hidden epimorphism) , and

where i : Z/PZ — > Z^r is the hidden monomorphism.

An obstacle to creating a physically implementable algorithm for this HSP is

that the domain Z of ip is infinite. As observed by Shor, a way to work around

this difficulty is to push the HSP.

QHS ALGORITHMS

11

In particular, as illustrated by the following commutative diagram

Z Z*

\l \\ T / Cf = Push (f) — if O T ,

a push tp = Push (if) is constructed by selecting the epimorphism fi : Z — ► Zq of

Z onto the finite cyclic group Zq of order Q, where the integer Q is the unique

power of 2 such that N 2 < Q < 2N 2 , and then choosing the transversal 8

t : Z Q — Z

to mod Q i — ► to '

where < to < Q. This push tp = Push (if) is called Shor's oracle.

Shor's algorithm consists in first executing the quantum subroutine QRand(£>),

thereby producing a random character

Jy/Q ■ to mod Q i — ► — — mod 1

of the finite cyclic group Zq. The transversal r used in pushing has been engineered

in such a way as to assure that the character 7 y /Q is sufficiently close to a character

kd

Jd/P '■ * mod P i — ► — mod 1

of the hidden quotient group Z/PZ = Zp. In this case "sufficiently close" means

that

1

y_ _ d_

Q P

which means that d/P is a continued fraction convergent of y/Q, and thus can be

found found by the classical polynomial time continued fraction algorithm 9 .

7. Wandering Shor algorithms, a.k.a., vintage Shor algorithms.

Now let's use the primitives described in sections 3, 4, and 5 to create other new

QHS algorithms, called wandering Shor algorithms.

Wandering Shor algorithms are essentially QHS algorithms on free abelian fi-

nite rank n groups A which, with each iteration, first select a random cyclic direct

summand Z of the group A, and then apply one iteration of the standard Shor algo-

rithm to produce a random character of the "approximating" finite group A = Zq,

called a group probe 10 . Three different wandering Shor algorithms are created in

|25j . The first two wandering Shor algorithms given in are quantum algorithms

which find the order P of a maximal cyclic subgroup of the hidden quotient group

H v . The third computes the entire hidden quotient group H v .

®A transversal for an epimorphism a v : Z > Zq is an injection r v : > TL such that

dip o t v is the identity map on Zq, i.e., a map that takes each element of Zq onto a coset

representative of the element in Z .

9 The characters 7 h /q and Jd/P can m the obvious way be identified with points of in the unit

circle in the complex plane. With this identification, we can see that this inequalty is equivalent

to saying the the chordal distance bewteen these two rational points on the unit circle is less than

or equan to 1/2P 2 . Hence, Shor's algorithm is using the topology of the unit circle.

10 By a group probe A, we mean an epimorphic image of the ambient group A.

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

The first step in creating a wandering Shor algorithm is to find the right gener-

alization one of the primitives found in Shor's algorithm, namely, the transversal

i : Zq — > Z of Shor's factoring algorithm. In other words, we need to construct

the "correct" generalization of the transversal from Zq to a free abelian group A

of rank n. For this reason, we have created the following definition:

Definition 4. Let A be the free abelian group of rank n, let v : A — > Zq onto the

cyclic group Zq of order Q with selected generator a. A transversal 11 l : Zq — > A

of v is said to be a Shor transversal provided that:

1) l (no) = m (a) for all < n < Q

2) For each (free abelian) basis a[, a' 2 , ■ ■ . , a' n of A, the coefficients A^, A' 2 , . . . , \' Tl

of t (a) = A X satisfy gcd (Ai, . . . , \' n ) = 1.

Remark 3. Later, when we construct a generalization of Shor transversals to free

groups of finite rank n, we will see that the first condition simply states that a

Shor transversal is nothing more than a 2-sided Schreier transversal. The second

condition of the above definition simply says that I maps the generator a of Zq

onto a generator of a free direct summand Z of A. (For more details, please refer

to section 12 of this paper.)

Remark 4. In |25) . we show how to use the extended Euclidean algorithm to con-

struct the epimorphism v : A — ► Zq and the transversal i : Zq — ► A.

Let v : A > B be an epimorphism from a group A to a group B. Then a transversal

r of v is is a map r : B > A such that v o r : B > A is the identity map b i — > b. (It

immediately follows that r is an injection.) In othere words, a transversal r of an epimorphism

v is a map which maps eacl element b of B to an element of A contained in the coset b, i.e., to a

coset representative of b.

QHS ALGORITHMS

13

Vintage_Shor( <p , Q, n)

<Sp>

Select basis t a j } of A & gen. a of

Lj£ = Ran_Shor_Transv({a'.}, Q , a, n )

X ,„ = QRand ~ ( )

y/Q

I -

[(d-,p"),(d',p')] =[(o,i),d,Ly / Qj)]

[(d",P"), (d'J 5 ')] = Next_CFC[(d'\P"), (d',P')]

^)(PV.)=^(s n ) Vj

[no

YES

Output P'

NO

YES

(Stog)

Figure 3. Flowchart for the first wandering Shor algorithm (a.k.a., a

vintage Shor algorithm). This algorithm finds the order P of a

maximal cyclic subgroup of the hidden quotient group H v .

Flow charts for the three wandering Shor algorithms created in |25| are given in

figures 3 through 5. In [25] . these were also called vintage Shor algorithms.

14

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

Altl_Vintage_Shor( <p, Q, n, K)

Select basis i a j I of A & gen. a of

Iter =

zzi —

tj^ = Ran_Shor_Transv({a'. }, Q , a, n )

J

H

X = QRand ~ ( )

y/Q ^

Kd",p»), (d',p-)] = [(o,d, d,Ly /Q J )i

[(d",P"), (d',P')] =Next_CFC[(d",P"), (d',P')]

|P = lcm(P, "F)

YES

£>(Pa\) = <£>(s ) Vj

YES

(Stop!) 1 Output P

Figure 4. Flowchart for the second wandering Shor algorithm (a.k.a., a

vintage Shor algorithm). This algorithm finds the order P of a

maximal cyclic subgroup of the hidden quotient group H v .

QHS ALGORITHMS

Alt2 Vintage_Shor( <p , Q, n , K)

I

& #NonZeroRows = & Iter =

Select basis i a j < of A »& gen. a of Z^

T

= Ran_Shor_Transv({a'.}, Q , a, n )

X „ = QRand „ ( )

y/Q <p

[(d"

,p"), (d',p-)] = [(o,d, (i,L y/Q J >]

|[(d",P"), (d',P')] =Next_CFC[(d",P"), (d',P')]

Q, = Echelon_Canonical( Q )

#NonZeroRows = NumNonZeroRows( Q )

Iter = Iter + 1

Iter = K

NO OR YES

#NonZeroRows

output Q, _(storj)

Figure 5. Flowchart for the third wandering Shor algorithm, a.k.a.,

vintage Shor algorithm. This algorithm finds the entire hidden

quotient group H v .

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

The algorithmic complexities of the above wandering Shor algorithms is given in

|25j . For example, the first wandering Shor algorithm is of time complexity

0(n 2 (lgiV) 3 (lglgiVr +1 ) ,

where n is the rank of the free abelian group A. This can be readily deduced from

the abbreviated flowchart given in figure 6.

Stepl O(n)

Figure 6. Abbreviated flowchart for the first wandering Shor algorithm.

8. Continuous (variable) Shor algorithms

In in and in (2H|, the algorithmic primitives found in above sections of this

paper were used to create a class of algorithms called continuous Shor algorithms.

By a continuous variable Shor algorithm, we mean a quantum hidden subgroup

algorithm that finds the hidden period P of an admissible function ip : K — > K

from the reals R to itself.

QHS ALGORITHMS

17

Remark 5. By an admissible function, we mean a function belonging to any suf-

ficiently well behaved class of functions. For example, the class of functions which

are Lebesgue integrable on every closed interval o/R. There, are many other classes

of functions that work equally as well.

Actually, the papers [27], |2H] give in succession three such continuous Shor

algorithms, each successively more general than the previous.

For the first algorithm, we assume that the unknown hidden period P is an

integer. The algorithm is then constructed by using rigged Hilbert spaces 0],

linear combinations of Dirac delta functions, and a subtle extension of the

Fourier transform found in the generic QHS subroutine QRand^), which has

been described previously in section 4 of this paper. In Step 5 of QRand^), the

observable

is measured, where Q is an integer chosen so that Q > 2P 2 . It then follows that the

output of this algorithm is a rational m/Q which is a convergent of the continued

fraction expansion of a rational of the form n/P.

The above quantum algorithm is then extended to a second quantum algorithm

that finds the hidden period P of functions (p : R — > R, where the unknown period

P is a rational.

Finally, the second algorithm is extended to a third algorithm which finds the

hidden period P of functions tp : R — ► R, when P is an arbitrary real number. We

point out that for the third and last algorithm to work, we must impose a very

restrictive condition on the map tp : R — > R, i.e., the condition that the map tp is

continuous.

9. The quantum circle and the dual Shor algorithms.

We have shown in previous sections how the mathematical primitives of pushing

and lifting can be used to create new quantum algorithms. In particular, we have

described how pushing and lifting can be used to derive new HSPs from an HSP

tp : G — ► S on an arbitrary group G. We now see how group duality can be

exploited by these two primitives to create even more quantum algorithms.

— oo

18

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

Another Way to Create New Quantum Algorithms

Duality

Figure 7. Using duality to create new QHS algorithms.

To this end, we assume that G is an abelian group. Hence, its dual group of

characters G exists 12 . It now follows that pushing and lifting can also be used to

derive new HSPs from an arbitrary HSP $ : G — > S' on the dual group G. In

|27j . this method is used to create a number of new quantum algorithms derived

from Shor-like HSPs ip : Z — ► S.

A roadmap is shown in figure 8 of the developmental steps taken to find and to

create a new QHS algorithm on Zq, which is (in the sense described below) dual

to Shor's original algorithm. We call the algorithm developed in the final step of

figure 8 the dual Shor algorithm.

Lifting & Duality

QHS Algorithm Based

on Shor HSP

Figure 8. Roadmap for creating the dual Shor algorithm.

If G is non-abelian, then its dual is not a group, but instead the representation algebra A

over the group ring CG. The methods described in this section can also be used to create new

quantum algorithms for HSPs $ : A > S on on the representation algebra A.

QHS ALGORITHMS

19

As indicated in figure 5, our first step is to create an intermediate QHS algo-

rithm based on a Shor-like HSP (p : Z — ► S from the additive group of integers Z

to a target set S. The resulting algorithm "lives" in the infinite dimensional space

defined by the orthonormal basis {(n\ : n G Z}. This is a physically unem-

plementable quantum algorithm created as a first steping stone in our algorithmic

development sequence. Intuitively, this algorithm can be viewed as a "distillation"

or a "purification" of Shor's original algorithm.

As a next step, duality is used to create the quantum circle algorithm.

This is accomplished by devising a QHS algorithm for an HSP $ : R/Z — > S on

the dual group R/Z of the additive group of integers Z. (By R/Z, we mean the

additive group of reals modi, which is isomorphic to the multiplicative group

{e 2 : < 9 < l}, i.e., the unit circle in the complex plane.) Once again, this

is probably a physcally unemplementable quantum algorithm 13 . But its utility

lies in the fact that it leads to the physically implcmentable quantum algorithm

created in the last and final developmental step, as indicated in figure 8. For in

the final step, a physically implementable QHS algorithm is created by lifting the

HSP $ : M/Z — ► S to an HSP $ : Z Q — ► S. For the obvious reason, we call the

resulting algorithm a dual Shor algorithm.

For detailed descriptions of each of these quantum algorithms, i.e., the "distilled"

Shor, the quantum circle, and the dual Shor algorithms, the reader is referred to

EH and [23.

We give below brief descriptions of the quantum circle and the dual Shor algo-

rithms.

For the quantum circle algorithm, we make use of the following spaces (each

of which is used in quantum optics):

• The rigged Hilbert space .Hr/z with orthonormal basis {\x) : x € R/Z}.

By "orthonormal" we mean that (x\y) = 5 (x — y), where " 8" denotes the

Dirac delta function. The elements of .Hr/z are formal integrals of the

form <f dx f{x) \x). (The physicist Dirac in his classic book[S[ on quantum

mechanics refers to these integrals as infinite sums. See also 0] and \W\.)

• The complex vector space H% of formal sums

< ^ a n |n> : a n £ C Vn E Z \

\n— — oo )

with orthonormal basis {\n) : n € Z}. By "orthonormal" we mean that

(n\m) = 8 nm , where S nm denotes the Kronecker delta.

We can now design an algorithm which solves the following hidden subgroup

problem:

Hidden Subgroup Problem for the Circle. Let <i> : R/Z — ► C be an ad-

missible function from the circle group R/Z to the complex numbers C with hidden

There is a possibility that the quantum circle algorithm may have a physical implementation

in terms of quantum optics.

20

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

rational period a £ Q/Z, where a <E Q/Z denotes the rational circle, i.e., the

rationals mod 1 .

Remark 6. By an admissible function, we mean a function belonging to any suf-

ficiently well behaved class of functions. For example, the class of functions which

are Lebesgue integrable on R/Z. There, are many other classes of functions that

work equally as well.

Proposition 1. If a = ai/a 2 (with gcd(ai,a 2 ) = 1) is a rational period of a

function $ : R/Z — ► C, then l/a 2 is also a period of $. Hence, the minimal

rational period of $ is always a reciprocal integer mod 1 .

The following quantum algorithm finds the reciprocal integer period of the func-

tion <I>.

Step 2. Step 2. Application of the unitary transformation U v : \x) \u) i— > \x) \u + &(x))

Circle- Algorithm (<&)

Step 0. Initialization

|Vo) = |0) |0) e H z ® H c

Step 1. Application of the inverse Fourier transform T 1 <£> 1

Step 3. Application of the Fourier transform T <£> 1

Remark 7. Remark. Letting have

a

m/a

^ ^ g-27rmm/i

m=0

a

QHS ALGORITHMS

21

where 1/a is the unknown reciprocal period. But

a — 1 ,

^ e -2imm/a _ a <5 n=0moda = J

if n — mod a

otherwise

m=0

Hence,

l/a

1-03} = £ |n> / dX e " 2 " ma; I* (*)> = ( E l"> *n=Omoda / e" 2 ™* |$ (*)>

E i £a >) i / ^ e ~ 2,Hnx i $ (*)> I = E i n ( fo )>

\iez

Step 4. Measurement of

with respect to the observable

E n ' n ) < n i

to produce a random eigenvalue la.

Remark 8. The above quantum circle algorithm can be extended to a quantum

algorithm which finds the hidden period a of a function $ : R/Z — ► C, when a is

an arbitrary real number mod 1 . But in creating this extended quantum algorithm,

a very restrictive condition must be imposed on the map $ : R/Z — ► C, namely,

the condition that $ be continuous.

We now give a brief description of the dual Shor algorithm.

The dual Shor algorithm is a QHS algorithm created by making a discrete ap-

proximation of the quantum circle algorithm. More specifically, it is created by

lifting the QHS circle algorithm for ip : R/Z — ► C to the finite cyclic group Zq, as

illustrated in the commutative diagram given below:

A* I \f = Push (ip) = ip o fj,

— ► S

Intuitively, just as in Shor's algorithm, the circle group R/Z is "approximated"

with the finite cyclic group 1q , where the group Zq is identified with the additive

group

1 Q-l\

and where the hidden subgroup Zp is identified with the additive group

22

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

with P = a<2-

This is a physically implementable quantum algorithm. In a certain sense, it is

actually faster than Shor's algorithm. For the last step of Shor's algorithm uses the

standard continued fraction algorithm to determine the unknown period. On the

other hand, the last step of the dual Shor algorithm uses the much faster Euclidean

algorithm to compute the greatest common divisor of the integers £±a, £2(1, 13a, . . .,

thereby determining the desired reciprocal integer period 1/a. For more details,

please refer to and

We now discuss a QHS algorithm based on Feynman path integrals. This

quantum algorithm was developed at the Mathematical Sciences Research Institute

(MSRI) in Berkeley, California when one of the authors of this paper was challenged

with an invitation to give a talk on the relation between Feynmann path integrals

and quantum computing at an MSRI conference on Feynman path integrals.

Until recently, both authors of this paper thought that the quantum algorithm to

be described below was a highly speculative quantum algorithm. For the existence

of Feynman path integrals is very difficult (if not impossible) to determine in a

mathematically rigorous fashion. But surprisingly, Jeremy Becnel in his doctoral

dissertation £Q actually succeeded in creating a firm mathematical foundation for

this algorithm.

We should mention, however, that the physical implementability of this algo-

rithm is still yet to be determined.

Definition 5. Definition. Let Paths be the real vector space of all continuous

paths x : [0,1] — ► R n which are L 2 with respect to the inner product

with scalar multiplication and vector sum defined as

• (Xx) (s) = Ax (s)

• (x + y) (s) = x(s)+y (s)

We wish to create a QHS algorithm for the following hidden subgroup problem:

Hidden Subgroup Problem for Paths. Let <p : Paths — > C be a functional

with a hidden subspace V of Paths such that

tp (x + v) = if (x) \fv € V

Our objective is to create a QHS algorithm which solves the above problem, i.e.,

which finds the hidden subspace V.

10. A QHS algorithm for Feynman integrals.

x ■ y = / ds x(s)y(s)

Jo

Definition 6. Let Hp ATHS be the rigged Hilbert space with orthonormal basis {\x) : x € Paths},

and with bracket product (x\y) = 6 (x — y).

QHS ALGORITHMS 23

We will use the following observation to create the QHS algorithm:

Observation. Paths = [J (v + V 1 -), where V 1 - denotes the orthogonal com-

plement of the hidden vector subspace V.

The QHS algorithm for Feynman path integral is given below:

Feynman(^)

Step 0. Initialize

Wo) = \0)\0)eH Patha ®Hc

Step 1. Apply T~ x <g> 1

= J Vx e 2m0 \x) |0> = J Vx \x) |0)

Paths Paths

Step 2. Apply U v : \x) \u) ^ \x) \u + ip(x))

|V> 2 ) = j Vx \x) \y{x))

Paths

Step 3. Apply T <g> 1

IVs) - J Vy J Vx e- 2 ™-y\y)\ V (x))

Paths Paths

= J Vy \y) j Vx e - 2mx -y \tp(x))

Paths Paths

But

J Vx e~ 2nix - y \<p(x)) = Jvv J Vx e - 2mx -y \<p(x))

Paths V v+V 1 -

= jvvjvx e -2^(v+x)-y |^ ( v + x y

V V-L

V 1

However,

y Pi; e- 2 ™^ = jvu5(y- u)

V V 1 -

24

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

So,

-- J Vy \y) jvv e- 2lTlv - y jvx e- 2mx - v \<p(x))

Paths™ V V 1 -

-- J Vy \y) jvu5{y-u) jvxe- 2 ™-y\<p{x))

Paths„ v-l v-l

= fpu |u) / Vx e- 2mx - u \ip (x))

J Vu \u) \Cl(u))

Step 4. Measure

|Vs) = /©u |«>|fi(«)>

with respect to the observable

A = J Vw \w) (w\

Paths

to produce a random element of V 1 -

The above algorithm suggests an intriguing question. Can the above QHS Feyn-

man integral algorithm be modified in such a way as to create a quantum algorithm

for the Jones polynomial? In other words, can it be modified by replacing Paths

with the space of gauge connections, and making suitable modifications?

This question is motivated by the fact that the integral over gauge transforma-

tions

$(K) = J VA ip (A) Wk (A)

looks very much like a Fourier transform, where

W K {A) = tr (^Pexp A

denotes the Wilson loop over the knot K.

11. QHS ALGORITHMS ON FREE GROUPS

In this and the following section of this paper, our objective is to show that a

free group is the the most natural domain for QHS algorithms. In retrospect, this

is not so surprising if one takes a discerning look at Shor's factoring algorithm. For

in section 6, we have seen that Shor's algorithm is essentially a QHS algorithm on

the free group Z which has been pushed onto the finite group Zq.

In particular, let ip : G — > S be a map with hidden subgroup structure from a

finitely generated (f.g.) group G to a set S. We assume that the hidden subgroup

QHS ALGORITHMS

25

K is a normal subgroup of G of finite index. Then the objectives of this section

are to demonstrate the following:

• Every hidden subgroup problem (HSP) (p : G > S on an arbitray f.g.

group G can be lifted to an HSP <p : F — ► S on a free group F of finite

rank.

• Moreover, a solution for the lifted HSP <p : F — ► S is for all practical

purposes the same as the solution for the original HSP ip : G — > S.

Thus, one need only investigate QHS algorithms for free groups of finite rank!

Before we can describe the above results, we need to review a number of defini-

tions. We begin with the definition of a free group:

Definition 7 (Universal Definition). A group F is said to be free of finite rank n

if there exists a finite set of n generators X — {x\,x 2 , ■ ■ ■ ,x n } such that, for every

group G and for every map f : X — ► G of the set X into the group G, the map f

extends to a morphism f : F — ► G. We call the set X a free basis of the group

F, and frequently denote the group F by F (x\,x 2 , ■ ■ ■ ,x n ), . It follows from this

definition that the morphism f is unique.

The intuitive idea encapsulated by this definition is that a free group is an

unconstrained group (very much analogous to a physical system without bo

Lire la suite

- 628.65 KB
- 15

##### Vous recherchez le terme ""

54

47

320