[PDF](+65👁️) Télécharger Geometric-Algebra Quantum-Like Algorithms: Simon's Algorithm pdf

Geometric-Algebra Quantum-Like Algorithms: Simon's Algorithm



Tomasz Magulski* Lukasz Oriowski"'"

Department of Theoretical Physics and Quantum Informatics
' Gdansk University of Technology, 80-952 Gdansk, Poland

o
o

. Abstract

>v

■ This is continuation of the approach to performing quantum algorithms using geometric structures
which was presented by D. Aerts and M. Czachor in pQ. We solve the Simon's problem which, next to
the Shor's alghorithm, is a representative of quantum hidden subgroup class. We also highlight some

' advantages resulting from the fact that no quantum mechanics is involved.

(N '
-f— >

we know that f is 1-to-l, or there exists s such that

3 :

3 se{0]1} n U0 („) } V x ^j,/(2;) = f(y) x = y®s, (2)

where © denotes componentwise addition mod 2, i.e. n-dimcnsional XOR.

■ The problem is to determine which of these conditions is satisfied by /, and, in second case, to find s.

ov

00
(N

"nt; ; 2 Quantum Solution

^ ■

Let us use two quantum registers, which consist of n and m qbits respectively. We start with n + m Os.

|0o> = |0_._0)|0_._0) (3)



X



1 Problem

Consider a function



/: {0, 1}" -> {0, l} m , where m > n - 1 (1)



Quantum algorithm solves the problem using 3 quantum gates. At first the Hadamard gate acts on the first
register. Note that using n-dimensional qubit space we have tensor power of n Hadamard gates.



Second gate's action depends on function /. The gate fills the second register with function / values, using
first register as a set of arguments.



a»-i



fe=0



*email: magul@rudy.mif.pg.gda.pl
t email: shangri@rudy.mif. pg. gda. pi



1



if£W>)l/W>) = ^ 2 £(-i)

VZ \fe=0 / i,k=0



Finally the Hadamard gate acts on the hrst register again.

1

<-^' Tiik) \iJ(k)) (6)
where a is a dot product of binary representations of i and k over {0, l} n space, i.e.

n

^•) = £« 2) (7)
fc=l

Now we measure the first register.

Remember that if / has the mask s then f(x) = f(x®s), which means that our amplitude is a superposition
of two amplitudes generated from \k, f(k)) and \k © s, f(k)) in Ifa).

a iJ{ k) = ^((-iy (i ' k) + (-iy (i ' k@s) ) (8)

Employing

a(i, k © s) = a(i, k) + a(i, s) (mod 2) (9)

then

a i , /w = i(-ir^)(i+(-ir('») (io)

Now if a(i, s) = 1 (mod 2) then both the amplitude and probability of getting such a state is 0. This implies
that every result of measurement satisfies

i s + ii-si H h i n _is„-i = (mod 2) (11)

So in order to determine whether the mask s exists the procedure has to be repeated until n — 1 linearly
independent states i are found.

Then the following system of equations has to be solved

* i o 1) s* + A 1) s* 1 + --- + i%<-i = 0(mod2)

4 2) »o+4 2) »;+-"+#V;-i = 0M2)

i i r 1) s*o + i ( r 1) s* 1 + --- + it-i ) <-i = 0(mod2)
There are two possible solutions of this system - 0^™^ and s* .

Now recalling the definition we know that / is 1-to-l or, there exists s which satisfies @. In the second
case the non-trivial solution of (|12p is the mask we are looking for. In the first one it is easy to show that s*
is just a random sequence. The easiest way to determine which of these conditions are satisfied by / is to
check if f(x) = f(x © s*) where x <E {0, 1}".

Originally Simon's problem was defined and solved in [2].



2



3 GA formulation

GA formulation of the problem is based on the binary parametrization [3]. Consider
(n + m)-dimensional space with orthonormal basis {ei . . . e„ +m } and its associated GA. Initial state is ana-
logical to \4>o)-

e O...O ( 13 )



Let us use a multivector



then



E «= J2 e A 1 A 2 ...A n O...O ( 14 )

Ai,A 2 ,...,A„=0 V " '



- B " e 0...0= H e A 1 A 2 ...A n O...O ( 15 )

V " ' J 4i,A 2 ,...,A„=0 V " '

n + m m

This step is equivalent to the first Hadamard gate in quantum algorithm. Uf is an operation which performs
as follows

1

U f E n e 0...0= ^2 e A 1 A 2 ...A n f 1 (A 1 A 2 ...A n )...f m {A 1 A 2 ...A 7l ) (16)

' Ai,A 2 ,...,A n =Q

Note that fi{A\A2 . . . A n ) is the i-th function / value.
Let us consider the reverse of E n

1

F »= E e kB,..B„0...0 ( 17 )



Bi,B 2 ,...,B„=0



Employing [5J

and
we find
Therefore



ex 1 x 2 ...x n £Y 1 Y 2 ...Y n = {-l)^i<i 1 3 e {Xl ,„ Xn )(B(Y 1 ...Y n ) (18)
e x 1 x 2 -x n e x 1 x 2 -x n = 1 (19)



eW.*„ = (-l) Ei<J X,Xj e Xl x 2 ...x„ (20)



*"» = £ : L ) E ""</;/;,.../,.()...() (21)



Bi,B 2 ,...B rl =0



3



F n performs as follows

F n U f E n e Q = ( (- 1 )^ I<jBlBje s 1 s 2 ...s„0...0



/; ./>••.• // •.)

1



^2 eAiA 2 ...A n fi(A 1 A 2 ...A n )...f m {AiA 3 ...A n ) (22)

Ai,A 2 ,...,A„=0 J

Ai,...,A n ,Bi...,B„=0

e B 1 ...B„O...O e Ai...A n / 1 (A 1 ...A n ).../ m (A 1 ...A tl ) (23)

£ , ,:>: ;;/; e 1 "

Ai,...,A„,Bi,...,B n =0

e (B 1 ...B n (K^^©(A 1 ...A„/ 1 (A 1 ...A n ).../ m (Ai...A„)) ( 24 )

Now let us focus on the case in which / has the mask s. Think how the values standing next to each
blade of the state look like. Note that for each / value the inverse image of / is a two-element set. This
implies that for all (A n ) £ {0, 1}™, in a state UfE n eo...o there are exactly two blades with f((A n )) values on
the last to bits:

eA 1 ...A n f 1 (A 1 ...A„)...f m (Ai...A n ) (25)

and

e(A 1 ...A„)®(Si...S n ),f 1 (A 1 ...A n )...f m (A 1 ...A n ) (26)
where (A n ) is arbitrary and (S n ) is the mask we want to find.

Note that for all (A n ) £ {0, 1}™ there is a sequence in {0, 1}" which by means of XOR operation can create
an arbitrary sequence in {0, 1}". Therefore, since F n contains all possible blades with 0s on the last m bits,
its action on UfE n eo...o gives us (from blades (|125|) and (US])) two components of coefficient standing next to
the blade:

ex 1 ...X n fi(A 1 ...A n )...f m (Ai...A n ) (27)

where (X n ) is arbitrary.

Let us now consider (X n ) and (A n ). What is the coefficient standing next to ([27| ? It would be convenient

to denote it by ctx,f{A)-

The first component resulting from (|25p is



where (B n ) satisfies (X n ) = (A n ) (B n ). The second component resulting from (|26|) is

(_!)£,<, BfBf+^^JUeS^Bf = ( _ 1} E I<3 (Bf + (A^))Bf (2Q)

where (B®) satisfies (X n ) = ((A n )®(S n ))®(B®). Adding the values from flU and Q we get the coefficient

axf{A) = + ( _ 1) E^^f+(^®*))^ (30)



4



which corresponds to a blade in a state F n UfE n eQ...Q. The coefficients of this blade's binary parametrization
carry no infromation about (A n ) which means we also have no information about (B n ), {B®) 1 let alone (S n ).
However there are some conclusions to be drawn. Note that for all i



Xi =A i ®B i



which implies



Employing this in (130|) we have



By



Bf



{A, © Si) © Bf
Si



A,
Si



. 1) E i<3 (^+^)^ + (_i)E 4 <,((



B i ®S i ) + (Ai®Si))(B :i ®S j )



(31)

(32)
(33)

(34)



f(n) = (—1)™ is periodic with period 2 which allows us to switch some pluses for XOR operations and
the other way round



axj(A)



= (-






f (-1)^


= (-


-l)^i<3


(Bi+Ai)Bj




= (-


-i)E (<3 -


{Bi+Ai)Bj


f (-1)^


= (-




{Bi+Ai)Bj


f (-1)^


= (-


-i)E (<3 -


{Bi+Ai)Bj


(l + (-l)



(-B,©A,)(-Bj+Sj



(35)



Now we can see that whether the particular blade occurs in the final multivector or zeros itself depends on
the value of the exponent (expression in brackets).

Note that unlike the quantum solution where each measurement gives us only one of the basic states from
the superposition, in GA formulation the observation has no influence on the multivector so we can simply
observe every particular amplitude of the blade we are interested in.

We have reached the point where we are able to determine whether / is 1-to-l or there exists the mask s.
According to (|35|) / has the mask if absolute values of amplitudes from the multivector F n U fE n eo...o equal 2.
On the other hand, if / is 1-to-l, for all blades in (fTS"]) the last m bits in (fTB| are unique. This implies that
absolute values of all amplitudes in (f2"2")) equal 1.

Supposing that the mask s exists let us focus on finding it. From (|35p we have



J2i<j (Bi + Ai) Sj = (mod 2) for non-zero-blades
Ei<j (B* + -^») Sj = 1 (mod 2) for zero-blades



and because of modulo 2 operation



Ei<j (Bi © -^t) Sj = (mod 2) for non-zero-blades
Ei<j ( B i © A i) Sj = 1 (mod 2) for zero-blades



Employing flU])

/ Ei<j XiSj = (mod 2) for non-zero-blades
1 Ei<j X%Sj = 1 (mod 2) for zero-blades
In terms of Simon's problem we examine the amplitudes of blades which are in the form of



e 0.



_0n 0_



_0

-fe— 2



(36)



(37)



(38)



(39)



5



where k € (0, n — 2). Returning to our system we get



E
E

Employing ([MJ)



i<j<fe+2 -^i^j + E

Ej</c+2 X i S k+2



; _ 2 XiSk+2 + Ei<j,j>fc+2



(mod 2) for non-zero-blades
Ei<j,3>fe+2 = 1 ( mod 2 ) for zcro -blades



El<j<fe+2 OSj
El<j<fc+2 ®Sj

Again because of the modulo 2 operation



15&+2
l<Sfc + 2



Ej>fe+2 = (mod 2) for non-zero-blades
Ej>fc+2 — 1 (mod 2) for zero-blades



<Sfc + 2 = (mod 2) for non-zero-blades
<Sfc+2 = 1 (mod 2) for zero-blades



(40)



(41)



(42)



Now we can determine all the bits of our mask from S2 to 5„. To find Si we have to check two possible
masks s: (OS2 ■ ■ ■ 5„) and (152 ■ • ■ 5 n ).

4 Explicit Examples

In this section we want to show explicitly how GA formulation works. We present two examples.
Let us consider the following 1-to-l function



X


11
10 1


f{X)


10 10
11



Table 1: 1-to-l function



and perform Simon's algorithm

eoooo

-En eoooo = eoooo + eoioo + eiooo + enoo

n^oOOO — ^0010 ^0100 ^1011 ^1101

F n U f E

n^OOOO — ^-0000 ^0001 ~l~ ^0010 ^0011 ^0100 ^0101 ^0110 ^0111

— eiooo — eiooi + eioio + eion 4- enoo + e noi ~ enio — e im



(43)
(44)
(45)

(46)



We can see that the absolute value of every amplitude in the multivector is 1 which proves that / is 1-to-l.



6



Now let us define the function which has a mask



X


1 1 1 1
1 1 1 1
10 10 10 1


f{X)


10 10 10 10
10 10 10 1



Table 2: Function with mask s = (010)



and perform the algorithm

eooooo (47)

-EWeooooo = eooooo + e ooioo + eoiooo + eoiioo + eioooo + eioioo + enooo + emoo (48)

UfE n eooooo = eooon + eooioo + eoion + eono + eiooio + eioioi + enoio + emoo (49)

FnUfE n eooooo = 2(eooooo + eooooi + eoooio + eooon + eooioo + eooioi + eoono + eoom

-eoiooo — eoiooi + eoioio + eoion + eonoo + eonoi — eomo — eomi) (50)

In this case the absolute value of every amplitude in the multivector equals 2 and therefore the non-trivial
mask s exists.

In Sec. [3]we showed how to determine our mask s using blades in the form of (|39|) .
Let us illustrate how it works with the help of the following table



blade's binary parametrization


1 1 1 1
11111111

1 1 1 1
1 1 1 1
10 10 10 1


1

1 1
1
X X
X X


absolute value of an amplitude


22220000


2



Table 3: Blade's amplitudes



Thanks to (05]) we have

/ S0+2 = 5*2 = 1 because the amplitude of enoxx equals ,
\ S1+2 = S3 = because the amplitude of eonxx equals 2

and therefore s = (X10). To determine the first bit we need to evaluate /(000) and /(010). In our example
/(000) = /(010) so Si = 0. In this example the algorithm has proved that the mask s exists and equals (010).



7



5 Cartan's representation



Let us use the matrix algebra known as Cartan's representation of 1-blade in GA

B2k-1 — ® ' ' ' ® Pi ® a 3 ® J- ® ' ' ' ® 1

n— fc

e2fc = 01 ® • • • ® <7i ®cr 2 <g> 1 <g> • • • ® 1



n—k fc— 1



and obviously the scalar representation is

eo = l



where 01 , tJ2, cr^ are the Pauli matrices and 1 denotes 2x2 unity matrix.

An arbitrary blade can be represented by the adequate product of ((52]) and ([53]) .

We know that

Tr <j\ = Tr (T2 = Tr (73 =



and



Therefore for the scalar
and for 1-blades

It is easy to show that



Tr (gM* =Y[TrA l

\i=l ) i=l

(n \ n

i=l / i=l
Tr e = (Tr 1)" = 2"



Tr ezfe-! = (Tr n)" - * Tr <t 3 (Tr l) fc 1 =
Tr e 2k = (Tr ax)™-' Tr a 2 (Tr if" 1 =



( Tr (eA 1 ...A n es 1 ...s n ) =0 if 3 2 A l ^ B l

I Tr (e Al „V) = (-l) 2 ^ » 1 2"

So having a multivector

l

A = 22 XA 1 ...A n eA 1 ...A n
A 1 ,...,A n =Q

we can compute the coefficients by



Let us consider the problem for the 1-to-l function from the previous section (Table [T]).
The initial state eoooo has the following representation:



Note that



eoooo



(64)



E n — -En eoooo —



(65)



In general the second gate is not a multivector so it does not have Cartan's representation and therefore
only the result of UfE n eoooo can be represented:







































1 - i








-1 -









































1 + i


-1 + «












































1 - i


-1 - i









































1 + i








-1 +


























1 - i








-1 - i









































1 + i


-1 + i












































1 - i











































1 + i








-1 + i


























1 - i








-1 - i









































1 + i


-1 + «












































1 - i


-1 - i









































1 + i








-1 + i


























1 - i








-1 - i









































1 + «


-1 + i












































1 - i


-1 - i









































1 + 4








-1 + i







































Then



(66)



F n =



(67)



9



and its action on UfE n eoooo
I



1 - i


1 - i


-1 - i


1 + i


























1 - i


-1 + i


-1 - i


-1 - i




1 + 4


1 - i


1 - i


























1 + i


1 + i


-1 + i




1 - i


1 - i


1 + i




























-1 + i


1 - i




-1 - i


1 + 4


-1 - i


1 - i


1 - i


























1 + 4


1 + i


1 - i


-1 + 4
















1 - z


-1 - i


1 + i


1 - i


-1 + i


-1 - i




























-1 - i


1 + 4


1 - 4




1 + i


1 + 4


-1 + i


1 - i




























1 - i


1 + i


-1 - i


-1 + i


1 - i


-1 - i




























1 + 4


-1 - 4


1 - 4




1 + 4


1 + 4


1 - i


-1 + 4


























1 - i


-1 + i


-1 - i


-1 - i


1 - i


1 - i




1 + i


























1 + «


1 + 4


-1 + i




-1 - 4


1 + 4


1 - i


1 - i


























-1 + 4


1 - i


-1 - i


-1 - i


1 - i


1 - 4


1 + i


-1 - i


























1 + i


1 + z


1 - i


-1 + i


1 + i


-1 - i


1 - i


1 - i














1 — i


-1 + i


-1 - 4




























1 - i


1 - i




1 + i


1 + »


1 + i


-1 + i


1 - i


























-1 - i


1 + i


1 - i


1 - i


-1 + 4




-1 - i






























1 - i


1 + i


-1 - i


1 + «


1 + i


1 - i


-1 + i


























1 + i


-1 - i


1 - i


1 - i



\



Now using (|63|) we can find the amplitudes (Table H|)



(68)



Ax


























1


1


1


1


1


1


1


1


A 2














1


1


1


1














1


1


1


1


A 3








1


1








1


1








1


1








1


1


A 4





1





1





1





1





1





1





1





1


T~r(eA 1 A 2 A 3 A i F n UfE n eoooo)


16


16


16


-16


16


-16


-16


-16


-16


16


-16


-16


-16


-16


16


-16


amplitiude of e^A;,^^


1


1


1


1


1


1


1


1


-1


-1


1


1


1


1


-1


-1



Table 4: Traces of matrices



which give us the following multivector:



FnUfE n eoooo — eoooo + eoooi + eooio + eoon + eoioo + eoioi + eono + eom

— eiooo — eiooi + eioio + eion + enoo + enoi — emo — eim (69)



Note that it is the same as

Let us consider the function with non-trivial mask s = (10):



X


11
10 1


/PO


10 10
10 1



Table 5: Function with mask s = (10)



For some technical reason it is less dimensional function than (Table [2|) from the previous section.
Note that eoooo , E n — E n eoooo and Fn are exactly the same as (I6"5j) and (|6"T|) respectively. We have



U f E

n^OOOO



/



10



and



F n U f E

n^OOOO



2i 2 — 2 — 2x

\ 2 2i -2i -2

Again using (f53|) we can find the amplitudes (Table [5])



(71)



A 1


























1


1


1


1


1


1


1


1


A 2














1


1


1


1














1


1


1


1


A 3








1


1








1


1








1


1








1


1


Ai





1





1





1





1





1





1





1





1


Tr(eA 1 A 2 A 3 A 4 F n UfE n eoo(m)





32


32








-32


-32








32


-32








-32


32





amplitiude of e Al A 2 A 3 A i





2


2








2


2








-2


2








2


-2






Table 6: Traces of matrices

which give us the following multivector:

FnUfE n eoooo = 2(eoooi + eooio + eoioi + eono — eiooi + eioio + enoi — emo) (72)
Performing (|39M2p as we did in Sec. |4] using the function (Table [2]) we find the mask s = (10).

6 Acknowledgement

We are deeply indebted to Marek Czachor for stimulating sugestions, help and encouragement.



References

[1] D. Aerts, M. Czachor, "Cartoon computation: Quantum-like algorithms without quantum mechanics",
J. Phys. A: Math. Theor. 40, F259-F266 (2007)

[2] D.R. Simon, "On the Power of Quantum Computation", SIAM J. Comput. 26:1474-1483 (1997)

[3] D. Aerts, M. Czachor, and B. De Moor," On Geometric Algebra representations of Binary Spatter Codes" ,



cs.AI/0610075 (2006)



[4] D. Aerts, M. Czachor, "Notes on Geometric- Algebra Quantum-Like Algorithms", quantum-ph/0610178
(2006)



[5] Jaap Suter, "Geometric Algebra Primer", http://lomont.org/Math/GeometricAlgebra/Geometric Alge-
bra Primer - Suter - 2003.pdf (2003)

[6] P. Budinich, A. Trautman, "The Spinorial Chessboard", Springer, New York (1988).



11




Lire la suite

• Taille
  136.93 KB
• Nombre de pages
  15