Shor's algorithm, definition of modulo

[mupsi]

Hi guys,
My question shouldn't take too long to be answered but I simply can't find anything using a google search. It's more of a problem from number theory rather than a physical one. I am referring to the Wikipedia article to Shor's algorithm and I still can't get my head around how the modulo operation can yield a negative remainder ( 6) under "classical part"). Both a^(r/2) and N are positive numbers and I am using the definition:

a mod N=r : Find numbers q and r such that: a=q*N+ r, with abs(r)<N
(Am I correct that if a<N, r=N-a ?)

There ist still a sign ambiguity but they choose r to be positive. So by definition the remainder can't be negative. My assumption: In Shor's algorithm they use a different definition.
Using anove definition without the restriction abs(N) yields a positive number r1 and a negative number r2 and they choose r=+/-min(abs(r1),abs(r2)). Am I correct? If not how else can this operation yield -1?

 

[Buzz Bloom]

(Am I correct that if a<N, r=N-a ?)

Hi mupsi:

I am quite rusty WRT this kind of problem, and I have never seen a problem like this where r is negative. However, I believe that if a < N, then r = a as q=0.

Hope this helps.

Regards,
Buzz

 

[andrewkirk]

You are correct that, strictly speaking, the result of a 'mod n' operation must be an integer between 0 and n-1. Writing '-1 mod n' is just a shorthand way of writing 'n-1'.
You can think of it as a formula rather than a constant, ie '-1' denotes the additive inverse of 1 in the ring that is the integers mod n.

 

[mupsi]

yes you're right. I was half asleep,when I posted this. In the first case, a mod N = a, when a<N. So we agree

 

[mupsi]

You are correct that, strictly speaking, the result of a 'mod n' operation must be an integer between 0 and n-1. Writing '-1 mod n' is just a shorthand way of writing 'n-1'.
You can think of it as a formula rather than a constant, ie '-1' denotes the additive inverse of 1 in the ring that is the integers mod n.

I give you an example:
(first definition)
15 mod 9 : 15= 1*9+6, therefore r=6 > 0
but we also have
15= 2*9 - 3,
according to the secound definition we have r=-3 since abs(-3)<abs(6)
Am I right in assuming that they use the latter definition in Shor's algorithm?

 

[andrewkirk]

@mupsi There is no role for the use of an absolute value in defining what x mod y means.
The following definition quoted above is faulty:

a mod N=r : Find numbers q and r such that: a=q*N+ r, with abs(r)<N

It should be

a mod N=r iff $a, N$ and $r$ are integers, with $0\leq r<N$, and there exists an integer q such that: a=q*N+ r

Nor is there, as far as I can see from the wiki article, any role for absolute values in the Shor algorithm.

15 mod 9 is 6, not 3.

 

[mupsi]

@mupsi

It should be

a mod N=r iff $a, N$ and $r$ are integers, with $0\leq r<N$, and there exists an integer q such that: a=q*N+ r

Nor is there, as far as I can see from the wiki article, any role for absolute values in the Shor algorithm.

15 mod 9 is 6, not 3.

Ok and I understand that. But this still doesn't explain the case a^(r/2) mod N = -1. I didn't understand what you meant in your first post. Can you give a specific example (maybe with numbers). How is M mod N =r with r<0 to be interpreted?

 

[andrewkirk]

Interpret it as $a \mod N=N+r$. Then you will have $0\leq N+r<N$.

 

[mupsi]

Interpret it as $a \mod N=N+r$. Then you will have $0\leq N+r<N$.

so a^(r/2) mod N =-1 actually means a^(r/2) mod N = N-1 in other words: find integers k and r such that a^(r/2)=k*N +N-1 ? Which of course satisfies remainder=N-1<N. To avoid any confusions: we have used r to denote the remainder before but in this case it's the exponent.

 

[mupsi]

so a^(r/2) mod N =-1 actually means a^(r/2) mod N = N-1 in other words: find integers k and r such that a^(r/2)=k*N +N-1 ? Which of course satisfies remainder=N-1<N. To avoid any confusions: we have used r to denote the remainder before but in this case it's the exponent.

r is already defined from the subroutine in the step before.

 

[zinq]

Strictly speaking, an integer K modulo a (positive) integer N should be an element of the group "the integers modulo N", which is sometimes denoted by Z_N. (Technically, this is the quotient group of the integers Z by its subgroup NZ.)

For the purposes of calculation, it suffices to represent Z_N as a set of integers containing just one representative for each of its elements.

The most obvious way to do this is to use {0, 1, 2, ..., N-1}. But this is not the only way to do this.

For instance, if N is an odd number, it's frequently more convenient to use as representatives the nice and symmetrical set {-M, -M+1, ..., M} where M = (N-1)/2.

So for example, Z₇ could be represented by {-3, -2, -1, 0, 1, 2, 3}. Compared to the obvious method, -3 ≈ -3+7 = 4; -2 ≈ -2+7 = 5, etc., where ≅ means "represents the same element of Z₇ as".

You want to know the 4th power in Z₇ of -2 ? Just take its 4th power as an integer, and then add or subtract enough 7's to put the result in the range -3, ..., 3 again. So you would get (-2)⁴ = 16, and 16 - 7 - 7 = 2, which is again in range. (If instead you had to take the 4th power of the equivalent representative, namely 5, this would be more work.)

[[[NOTE: Originally I wrote that Z_N is a group. In fact, a commutative group. This is true, with respect to the group operation of addition. But as in the example of

(-2)⁴​

in Z₇, it also makes perfect sense to multiply elements of Z_N as well. And as you might hope, multiplication distributes over addition, just as with the integers, reals, and complexes. Also, 1 in Z_N behaves as a multiplicative identity.

All these things make Z_N into what mathematicians call a ring. What you often don't have are multiplicative inverses. The only cases where all the nonzero elements do have multiplicative inverses are when N is a prime number. Otherwise, only some of the nonzero elements will have multiplicative inverses.]]]

 

[mupsi]

that makes perfect sense. Thank you. Basically, to get from the "new" representation (the ring) to the one that is commonly used, do:
r->N+r, in case the remainder is negative and r->r when the remainder is positive. That way you have unique mapping between the two representations.
Thanks mate

 

[zinq]

Just to be ultra clear, if you were somewhat ornery (or had a special reason for doing so), you could even take the set of integers {11, 12, 13, 14, 31, 37, 50} as your representatives. Not that I can think of any reason to do that. So to get these to correspond to the usual set {0, ..., 6} you might have to subtract more than just one times 7 to get to the usual set. In fact, {11, 12, 13, 14, 31, 37, 50} would correspond — if listed in the same order — to {4, 5, 6, 0, 3, 2, 1} in the usual set.