[PDF](+54👁️) Télécharger 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

• Taille
  628.65 KB
• Nombre de pages
  15