#### Termes les plus recherchés

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

#### This is continuation of the approach to performing quantum algorithms using geometric structures which was presented by Aerts and Czachor. We solve the Simon's problem which, next to the Shor's alghorithm, is a representative of a quantum hidden subgroup class. We also highlight some advantages resulting from the fact that no quantum mechanics is involved.Télécharger gratuit 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

- 136.93 KB
- 15

##### Vous recherchez le terme ""

65

69