I'm wondering about the $log_2(x)$ power of 2 that you mentioned. If I deal with three qubits in the control register, then there would be 8 different x values (from 0 to 7), and in the case of a=2, there should be 4 different quantum states from the modular exponentiation calculations, $|1>$ for x=0,4, $|2>$ for x=1,5, $|4>$ for x=2,6, $|8>$ for x=3,7. But if I try to apply the modular exponentiation calculation of the form $ f(x) = 2^{log_2(x)} mod 15$, there would be 8 different quantum states (from |0> to |7>). I'm wondering what I'm saying is correct. If right, doesn't it make sense?

Also, regarding the generation of truth table using $ f(x)=2^x mod 15$, if I use the repeated squaring algorithm classically, can't I make the truth table efficiently fast? As far as I know, that's what Shor said in his paper.

Thank you for your edit. But I still wonder the meaning of making the truth table of $log_2(n^2)$. The truth table should be as a function of $x$ but I cannot see any x in this case. Shouldn't $x$ be somewhere? If possible, could you let me know the exact equation for the generation of the truth table?

First, sorry, the first $log_2(x)$ was a quite confusing typo. For general base $a$ and number to be factored $n$, in order to obtain the period necessary, you at worst need to know every $a^{2^x} \pmod n$ up until you reach a $2^x$ that is greater than the number squared. If you generated every $a^x \pmod n$ up to there rather than every $a^{2^x} \pmod n$, even if you could do modular exponentiation quickly you'd have to do it a number of times comparable to the factored number itself, so it would be worse than trial division.

There's some confusion that comes from the fact your example base is also 2 and it's an exponent in an exponent. You only need the exponents that are powers of 2 up to the number squared, and, you can do each one tractably and will only need to do work out $log_2(n^2)$ times, which, from the perspective of big O notation on the factored number's bit count, is polynomial time.

Thank you for your information. In summary, what you are saying is that the modular exponentiation calculation for every x is possible in polynimial time classically (using repeated squaring algorithm). Then, with this algorithm, even though the number $N$ to factorize is high, we can generate the truth table and make a quantum circuit for that implementation. And this process is reasonale for Shor's algorithm, right?

The thing I am saying is you need to just generate the truth tables for every $a^{2^x} \pmod n$ up to $2^x > n^2$, the truth table you showed included $2^3 \pmod{15}$ which is unnecessary and, if you did go that far to include all those, there'd be too many to do.

May I ask you why only up to $2^x >n^2$? In that case, can't we get the full information of the modular exponentiation calculation for every x?

Hello

Can you see me?

Yep.

I'm really grateful for having a discussion with you

This is my first time doing a proper discussion room.

May I ask you the reason why calculating the modular exponentiation only up to $2^x >n^2$?

Alright.

Me too. I really want to have a discussion with you

Let's get a Shor's Algorithm reference up.

qiskit.org/textbook/ch-algorithms/shor.html

I know this website

There's a good picture in section 3 of factoring 15 using 7.

you mean the probability?

Your example was kinda inherently awkward since the period of a=2 is 4 which is a power of 2 itself.

Yes I can see it

Ok let's talk about a=7 case then

the period is also 4 in this case

So it shows the modular exponentiations for 7, 7^2, 7^4, 7^8, 7^16, 7^32, 7^64, 7^128.

Yes in the target register.

The thing is, you need just those, you don't also need 7^10, 7^55, etc.

Yeah I don't have to and the number of calculation depends on the number of qubits in the control register.

Then where does 7^10 and 7^55 come frome? 10 and 55 is x ?

The truth table you showed had a $2^3 \pmod{15}$, which would be like that. I think there's a lot of general confusion between what we are referring to here.

The truth table that I showed you in my post comes from a^x mod 15

Yep, not $a^{2^x} mod 15$

At that time I was considering two qubits in the control register, so there were 4 x (0~3)

so that's why I put 2^3 mod 15 in that table

But what you are saying is

if we want to make a quantum circuit shown in the figure above

I need to do just only 7, 7^2, 7^4, 7^8, 7^16, 7^32, 7^64, 7^128.

correct?

Yep, why that is a huge advantage becomes more apparent for larger numbers.

I understand. Let me tell you my situation

I'm trying to solve the Shor's algorithm using qudit

and I'm trying to calculate the modular exponentiation calculation a^x mod N using a qudit

Based on the truth talbe of the modular exponentiation calculation, I'm trying to order the results in the truth table in an increasing order.

For example the truth table shown in my post show |1>,|2>,|4>,|8> = |0>,|1>,|2>,|3>, respectively.

The reason that I'm doing like this is to reduce the amount of qubits in the target register and I was wondering if I can make a truth table of the modular exponentiation calculation classically and order the results in an increasing order.

The order of the results isn't the thing, it's the order of the input.

what do you mean?

The way Shor's Algorithm works is the control registers control a group of gates that do modular multiplication to the target register by the results of the modular exponentiation (which you can calculate classically put into a table).

Yeah I know

So there should be an entanglement between control and target after the modular exponentiation calculation

And what I did is just changed the number in the target register 1,2,4,8 into 0,1,2,3, respectively

You understand what I mean?

I'm confused. The modular exponentiation can be done outside the circuit.

Let's say there are two qubits in the control register. After the modular exponentiation calculationm, the quantum state should be like |0>_c|1>_t + |1>_c|2>_t + |2>_c|4>_t + |3>_c|8>_t

You understand this quantum state generation?

where c and t are control and target register rexpectively

This state is generated from the table that I have posted in my post.

Two control qubits isn't in general enough, you need twice the bit count of the factored number in general.

I know, it's just an example

Well, there are some optimizations.

what optimization?

for the number of qubits?

arxiv.org/pdf/quant-ph/0205095.pdf gives one, but that's a special version, it's not the textbook Shor's Algorithm.

You mean the circuit optimization?

including the number of qubits?

Yeah, that one uses only $2n + 3$ qubits total.

I know

But I want to ask is not that

but just whether it is reasonable to do the modular exponentiation calculation classically before playing the shor's algorithm

So let's just think about the case that there are two qubits in the control register

The quantum state after the modular exponentiation calcualtion in the shor's algorithm should be like |0>_c|1>_t + |1>_c|2>_t + |2>_c|4>_t + |3>_c|8>_t

Yes, you can. Repeated squares is polynomial time.

Whatever the number that I try to factorize is?

So using repeated squaring algorithm, whatever the number $N$ that I want to factorize is, I can make the a^x mod N table classically?

It's a Big O polynomial of the bit count of the exponent, and for the algorithm you need exponents up to n^2.

I think what you are saying is the circuit that you showed me above correct?

Yes, but the table would have N^2 elements (way too many to do classically) unless you only did the a^{2^x} which will have far less.

No, what I'm asking is not that

The circuit that you showed me above is the individual unitary operator modular calculation

If I integrated the whole calculation of the above unitary operator, the circuit can be seen as one modular exponentiation calculator, f(x) a^x mod N.

sorry, it should be f(x) = a^x mod N.

where x is the computational basis of the control register.

What I'm asking is

whether it is reasonable to make a truth table of this function f(x) = a^x mod N with every possible computational basis.

Classically?

yes

Up to how many x.

It depends on the number that I try to factorize but I just want to know whether it is reasonble generally

If you are doing every x there it wouldn't, if you just do f(x) = a^{2^x} mod N, it's fine, since there aren't that many needed.

If I do it for every x, should I say that compiled version of Shor's algorithm?

I don't understand.

Ok you are theorist

What I wanted to do is

After making a truth table of the f(x) = a^x mod N classically,

sorry let me repharase it again

If we make a truth table for the f(x) = a^x mod N,

for example the truth table in my post

we can generate the entanglement between control and target like this: |0>_c|1>_t + |1>_c|2>_t + |2>_c|4>_t + |3>_c|8>_t

you know what I mean?

So you are asking how to go from the truth table to the circuit below it?

That's what I wanted to do

I'm an experimentalist

And what I''ve been thinking of is to generate this kind of quantum state: |0>_c|1>_t + |1>_c|2>_t + |2>_c|4>_t + |3>_c|8>_t

after the modular exponentiation calculation

using qudit

in the experiment that I'm thinking

this kind of quantum state can be generated using qudits

but in that case it requires the truth table information before performing the shor's algorithm

and my experiment cannot generate the target quantum state |1>,|2>,|4>,|8>

but can generate |0>,|1>,|2>,|3> instead

How does the table contribute to Shor's Algorithm?

After making a table I can see the quantum state in the target register after the modular exponentiation, correct?

Let's say that is |1>,|2>,|4>,|8>

and in qudit base, it can be written as |0>,|1>,|2>,|3>

What I did here is just changing the bases |1>,|2>,|4>,|8> into |0>,|1>,|2>,|3>

in increasing order

To change the basis from |1>,|2>,|4>,|8> to |0>,|1>,|2>,|3>

I should know the increasing order

You know what I mean?

nature.com/articles/srep03023.pdf

the equation (21) in this paper will help you understand what I mean

Reading now.

Thank you for your time

Yeah I saw that

I think I get the context here more now.

Ok anyway you know what I mean?

So getting the table requires more effort than what the Shor's Algorithm is trying to solve.

But it's a thing used for easier experimental demonstration?

Yes

but theoretically, making a table doesn't make any sense?

Yeah, it doesn't, you'd already need the order you are looking for.

I'm wondering why they are saying that we need an order

Since we are in the same page now, let's go back to our previous discussion

So the quantum state after the modular exponentiation calculation is |0>_c|1>_t + |1>_c|2>_t + |2>_c|4>_t + |3>_c|8>_t

and since I'm dealing with a qudit in the target register, i need to make |1>,|2>,|4>,|8> into |0>,|1>,|2>,|3>

which is just changing it in increasing order

even in that case, is this process based on the period?

since the period information is in the control register quantum state, the target quantum state can be anything. It is just only separating the control quantum state

So the changed quantum state should be like |0>_c|0>_t + |1>_c|1>_t + |2>_c|2>_t + |3>_c|3>_t

What would this look like if we did a = 7?

In that case, |0>_c|1>_t + |1>_c|7>_t + |2>_c|4>_t + |3>_c|13>_t

and by increasing order it should be like

|0>_c|0>_t + |1>_c|2>_t + |2>_c|1>_t + |3>_c|3>_t

So it a permutation

What is the use for doing this?

Because I cannot generate this kind of quantum state in my experiment

|0>_c|1>_t + |1>_c|7>_t + |2>_c|4>_t + |3>_c|13>_t

but it is possible to generate |0>_c|0>_t + |1>_c|2>_t + |2>_c|1>_t + |3>_c|3>_t

this kind of state

This is possible for every random number 2,4,7,8,11,13

in the case of factoring N=15

What relevance does ordering the values serve?

I cannot generate the exact quantum state from the modular exponentiation calculation

in my experiment

but ordering the target register quantum state is possible

|0>_c|0>_t + |1>_c|2>_t + |2>_c|1>_t + |3>_c|3>_t

like this

|0>_c|0>_t + |1>_c|2>_t + |2>_c|1>_t + |3>_c|3>_t

This case is for a=7

and |0>_c|0>_t + |1>_c|1>_t + |2>_c|2>_t + |3>_c|3>_t case

is for a=2

How is that used to factor?

After generating this quantum state, I perform the quantum Fourier transform

From the quantum Fourier transform, I can measure the computational basis

from there I can get the period r

quantum fourier transform is only on the control register

Still here, just thinking and reading that paper more.

Thank you

Have you used Quirk?

What is the dimension?

Quirk is a quick little thing online that can make circuit diagrams real quick.

I think I need to see some sort of diagram of what you are doing.

No i haven't used it at all before

May I ask you if you use skype?

I don't have Skype.

Ok then what are you confused?

Might be confused on how qudits are being notated here.

Can we have a zoom call?

The part I really don't get is how the additive order of the results of modular exponentiation matters for the fourier transform.

Prefer not.

Ok sorry

What I just did is only ordering the target quantum state

So the target quantum state is just only used for separating the control quantum state

What state is the whole system in just before the fourier transform?

This is it

Strictly speaking, I tried to deal with an 8 dimensional qudit in the control register

In that case, the quantum state after the modular exponentiation

After the fourier transform, you will see the peak at |0>_c,|2>_c,|4>_c,|6>_c

I mean in the output probability distribution

|2>_c and |6>_c give the correct period, 4, in this case

You understand what I mean?

I don't see the relevance of the value of the target.

Hold on a moment.

you mean ordering?

Yeah.

You understand the paer I sent you?

Looking deeper at it.

So let me try to summarize.

ok

So this is for factoring products of two fermat primes.

yes

Products of Fermat primes will always have orders that are powers of two for their bases, this means its a simpler case.

Yeah

The authors then argue that, in that case, the problem is in some sense equivalent to doing a period find of just |x>|x mod r>, abstracting out modular exponentiation?

yeah that's what they are saying

So the target quantum state has a role of separating the control quantum state

which means the target quantum state can be increasing order

According to the paper you just map a^x mod N -> x.

similar but different

What I did is exactly eq (21)

in the case a =7

this is the quantum state after the modular exponentiation

How did 7^2 mod 15 turn into 1?

I just changed the target quantum state in increasing order after calculating it classically

I don't get why you need to do that.

7^2 mod 15 = 4 actually, but in increasing order it is |1>

experimentally speaking

No theoreticall speaking

after the modular exponentiation

In the paper it just maps 7^2 mod 15 to 2, why do you need to change it to 1 to be increasing order?

To your question

if I try to follow their logic

7^4 mod 15 should be 4

but actually it is the same as 7^0 mod 15 = 7^4 mod 15

How does changing it into increasing order change the period finding routine?

to change it into increasing order

I need to calculate the modular exponentiation calculation classically

at that time I just use simple smart phone calculator

and make a truth table

based on the results in the truth table

I need to change it into increasing order

because

I cannot directly calculate the modular exponentiation in my experiment

The paper you showed doesn't need to change it into increasing order.

It doesn't

That's my plot

What I'm saying is

eq(21) in that paper is similar to how I transform the target quantum state

which is increasing order

From what I understand, your eq(21) equivalent depends directly on the values of a^x mod N.

yes

What purpose does that serve? Why do you want to do that?

Sorry, I really am confused.

because my experiment cannot perform the modular exponentiation calculation

i understand because it is an experimental thing

Why does it need to?

which one?

Let me explain it again

my experiment cannot perform the modular exponentiation calculation

If I understand correctly, the idea of this paper is to do an easy order-finding routine that disregards the direct modular exponentiation since it is sort of a meta-way to claim you factored a Fermat prime (which, IMO, is a cheat).

yes

May I showed you another paper?

Sure.

science.org/doi/pdf/10.1126/…

Do you know this paper?

If the values, for some base a and number factoring n, were 5, 13, 3, 2, 1, 7, 6 you'd change them to 4, 7, 3, 2, 1, 6, 5 with this increasing order procedure.

yes

I don't have access.

hold on

I don't see how making that substitution conveys anything relevant about the modular exponentiation for the purposes of factoring. Their order in an addition sense has little to do with their multiplicative nature.

What do you mean?

You mean target quantum state has no relevance in period finding?

If you see this paper, they tried to factorize 21 using qutrit in the target quantum state because only three levels were accessed in the modular exponentiation calculation.

The period finding is linked to multiplying the target register by each result controlled by the control register, their additive order is irrelevant.

You mean increasing order is irrelevant?

Pretty sure it is irrelevant.

Yeah I know because the period is in the control register

So why do you need to do it?

If I don't sort the control quantum state, the quantum state will be like (|0>_c+|1>_c+...+|7>_c)|1>_t

If we apply the quantum fourier transform in this quantum state

we cannot see the right period

and just |0>_c state will appear in the probability distribution

but if I sort the control quantum state based on the modular exponentiation calculation,

the state will be like (|0>_c+|4>_c)|1>_t + (|1>_c+|5>_c)|7>_t + (|2>_c+|6>_c)|4>_t + (|3>_c+|7>_c)|13>_t

and increasing order it should be like (|0>_c+|4>_c)|0>_t + (|1>_c+|5>_c)|2>_t + (|2>_c+|6>_c)|1>_t + (|3>_c+|7>_c)|3>_t

Why is just (|0>_c+|4>_c)|0>_t + (|1>_c+|5>_c)|1>_t + (|2>_c+|6>_c)|2>_t + (|3>_c+|7>_c)|3>_t not something that accomplishes what you are setting out to do?

After the fourier transform on this quantum state, we will get the probability distribution at |0>_c,|2>_c,|4>_c,|6>_c

what do you mean?

If you don't sort them by increasing order and just do (|0>_c+|4>_c)|0>_t + (|1>_c+|5>_c)|1>_t + (|2>_c+|6>_c)|2>_t + (|3>_c+|7>_c)|3>_t, you should still get 4.

Oh i see

That is for another random number

random numbers 2,7,8,13 has different permutation in the target quantum state

Okay, so, let me try to think here.

If I am understanding you right, you want to "prove" you did the modular exponentiation for the specific base by ordering the results.

yes

and by applying the fourier transform I want to prove the shor's algorithm

with every possible random number

in the case of N=15

a = 2,4,7,8,11,13

in the case of a=4, the quantum state after the modular exponentiation will be like (|0>_c+|2>_c+|4>_c+|6>_c)|0>_t + (|1>_c+|3>_c+|5>_c+|7>_c)|11>_t

sorry it shoud be (|0>_c+|2>_c+|4>_c+|6>_c)|1>_t + (|1>_c+|3>_c+|5>_c+|7>_c)|11>_t

in increasing order it should be like (|0>_c+|2>_c+|4>_c+|6>_c)|0>_t + (|1>_c+|3>_c+|5>_c+|7>_c)|1>_t

this is the case for a =11 , not a=4. sorry

This sounds to me like a kind of metaphysical "What counts as doing the algorithm?" The paper, which I would argue against but nevermind, suggests that finding an order of a mod n period on a quantum circuit counts as factoring a fermat prime.

Ok so you don't think that their case is not the genuine shor's algorithm?

Personally, no, but maybe some other people would.

Yeah that's what I'm saying

People say differently about the definition of the genuine shor's algorithm

The "increasing order" stipulate seems unrelated to this, though.

So you don't think that my case is also not the genuine?

sorry you think that my case is also not the genuine?

because it requires the truth table classically?

Personally, yes.

because of the truth table?

The algorithm in the paper is "Find a power of 2 period you already know, but it's through a quantum circuit akin in structure Shor's Algorithm."

And since Fermat primes always have power of 2 periods, finding one is factoring.

But in my case it is not just for a power of 2 period

any period is available

for example, when factoring N=21, there are some cases that r=6.

And it is obtainable

So you aren't being exclusive to products of Fermat primes.

yes

Any number is possible

and it depends on the dimension of qudits

but it requires the truth table classically

you know, factoring number N=15 requires 8 qubits on the control register?

but experimentally speaking, 8 qubit generation is very difficult so people usually try to use 3 qubits

8 qubit can give the correct period for factoring N=15

In my case, I'm thinking of an 8-dim qudit in the control register

which means I have 8 different x values for making the truth table

before performing the modular exponentiation, I should make the table classically.

Based on that table, I do the modular exponentiation calculation in increasing order

My concern is the truth table

In my case, the number of x is just 8, so it's not so big.

But I'm wondering whether the generation of the truth table classically is reasonable

If x is 8, it is: just do the 8 with a classical modular exponentiation algorithm.

yes

If I try to factorize a higher number like 21

I should increase the dimension further

and the number of x will increase

If you are doing only the exponents that are powers of 2 it would increase reasonably, otherwise, not.

I have to go very soon.

so this calculation is a^x mod N

Can I have a chat later if possible?

Maybe. Are there other people you know more directly that can help, like at your uni?

there is, but this topic is very difficult and people say differently on this topic

May I let you know my email address?

Hmm, well, maybe talk with them if you can in the meantime.

Sure.

I'm really thankful to you today

Your welcome.

BTW, do you know this paper?

arxiv.org/pdf/1507.08852.pdf

They are saying that they are the first who did the genuine Shor's algorithm using qubit recycling

I'll look at it later.

Gtg.

Not in the paper, but in their website

Please send me an email to me. any email so that we can chat later.

Probably better to use this.

I know but since we don't have any contact, we might not meet here again. That's why I let you know my emial.

We can come here later after contacting via email.

You can just check in.

I see how it works. When can we see next time?

This will stay open so it could just gradually go asynchronous, my schedule isn't clear cut enough for me to choose a direct time.

I see. I wish I could meet you again to be honest

Hello, are you there?

Good likelihood of being available in about ~4 hours.

4 hours from now. I see

arxiv.org/pdf/1310.6446.pdf

I want you to read this paper if available. This is about the circuit design method using truth table.

What I want to mention is that even though I use the truth table, I don't try to discard any redundant qubits or qudits in the modular exponentiation calculation. Above all, in some cases I still cannot find the period from the truth table, for example, when a=4 and N=15 with 2 qubits in the control register.

In that case the quantum state after the modular exponentiation is like |0>_c|1>_t + |1>_c|7>_t + |2>_c|4>_t + |3>_c|13>_t

What I do from here is just ordering the target quantum state in increasing order like |0>_c|0>_t + |1>_c|1>_t + |2>_c|2>_t + |3>_c|3>_t

From here, I still cannot get the right period, so I need to perform the QFT on the control register.

From this respective, I think this kind of process for small numbers N with a few x values would be fine for the genuine Shor's algorithm.

I want to hear your opinion.

Furthermore, what you said yesterday in my post was " If you then have a way to make a set of controllable gates U(a) that do modular multiplication on the computational basis by a, then you take the consecutive results a of your table, use the corresponding U(a) on a register started at |1⟩ based on the controls that will be inverse QFTed, and you will be able to implement Shor's Algorithm without having used exponential classical or quantum resources."

Come to think of it, this is what I said to you yesterday.

Also, I found that the repeated squaring algorithm can be applied to the exponentiation calculation a^x

mathlesstraveled.com/2018/08/18/…

In this post, someone's saying that the repeated squaring algorithm is applicable to f(x) a^x mod N. When I looked into the Shor's paper, he also mentioned about the repeated squaring algorithm to f(x) = a^x mod N to obtain the unitary operator a^(2^j) mod N