The period-finding circuit for Shor's algorithm

In summary, the expert summarizer says that in order to build a circuit for modular exponentiation, you need to calculate the values of a to powers of two for all 0<k<2log_2(N). If you want to calculate the period of the function, you can do it classically but it will be exponential in the number of bits.
  • #1
tomdodd4598
138
13
TL;DR Summary
Building the period-finding circuit for Shor's algorithm & the classical complexity of finding the period of modular exponentiation
I've been trying to learn about Shor's algorithm by writing out implementations of the circuit for modular exponentiation, ##{ a }^{ x }\; ({ mod }\; N)##, to find the period ##r## for small numbers such as:

##(N=15,\quad a=11)\quad \longrightarrow \quad r=2##,

##(N=35,\quad a=13)\quad \longrightarrow \quad r=4##,

##(N=21,\quad a=5)\quad \longrightarrow \quad r=6##.

I know these are incredibly small numbers, but I realized that in order to actually start building the cicuit at all (using the binary exponentiation method), I needed to calculate the values of ##{ a }^{ { 2 }^{ k } }\; ({ mod }\; N)## for all ##0\;\le\;k \; <\; 2\; \lceil { \log _{ 2 }{ N } }\rceil ##, which pretty much immediately made the values of ##r## obvious before I'd even started building the circuit.

For example, take the least trivial case from the above, where ##r=6##. I needed to calculate:

##{ 5 }^{ 0 }\; ({ mod }\; 21)=1##,

##{ 5 }^{ 1 }\; ({ mod }\; 21)=5##,

##{ 5 }^{ 2 }\; ({ mod }\; 21)=4##,

##{ 5 }^{ 4 }\; ({ mod }\; 21)=16##,

##{ 5 }^{ 8 }\; ({ mod }\; 21)=4##,

##{ 5 }^{ 16 }\; ({ mod }\; 21)=16##.

Simply by inspection, I can already see what the value of ##r## must be, because the result is the same when ##x## increases by six or twelve, but not after increasing by two or three.

I therefore have two questions:

1. Is calculating these modular exponentials of ##a## to powers of two *required* when building these circuits, or is there some way of not even having to do that?
2. If we do need to calculate these values, can we not deduce the period ##r## of this modular exponentiation function classically in an efficient way, starting with these values and then using a method analogous to a binary search (or 'interval halving'), selectively calculating other values of ##{ a }^{ x }\; ({ mod }\; N)##, or an I being misled by using small numbers? [SEE EDIT]

Thanks in advance!

EDIT: It has been pointed out to me that the results of modular exponentiation have very little structure, and so although perhaps faster than ##O(N)##, such an 'interval halving' method would not have logarithmic complexity, thus would be slower than Shor's algorithm for large enough ##N##.
 
Last edited:
Physics news on Phys.org
  • #2
Yes, you can (and should) pre-calculate all of the numbers that need to be multiplied by and use that knowledge when generating the quantum circuit. In this sense Shor's algorithm is just a series of multiplications by easily computed constants, with the catch being that each multiplication is controlled (it may or may not occur) and each control qubit is in superposition.

I gave a talk on optimizing circuits for Shor's algorithm:

1. Is calculating these modular exponentials of a to powers of two *required* when building these circuits, or is there some way of not even having to do that?

I don't see any way to avoid computing them. You could obfuscate the fact that they were being computed, e.g. do the computation in ternary instead of binary, but basically you're asking for a way to perform modular exponentiation that doesn't use repeated squaring.

can we not deduce the period r of this modular exponentiation function classically in an efficient way

There's no known way to do this.
 
  • #3
Strilanc said:
Yes, you can (and should) pre-calculate all of the numbers that need to be multiplied by and use that knowledge when generating the quantum circuit.

I don't see any way to avoid computing them.
I see, thanks. I watched your talk, which was very interesting, though a bit beyond me for now at points :P
Strilanc said:
There's no known way to do this.
Right - for some reason I thought that as you already have to pre-calculate all of the numbers to build the gates anyway, you would already have made progress at working out what the period is, but the smallness of the examples I was looking at in detail are misleading; the amount of classical computation still required is still exponential in the number of bits.
 
  • #4
Strilanc said:
I gave a talk on optimizing circuits for Shor's algorithm:


I finally had time to watch the video and that was a very nice talk:bow:
I've been sending the link to everyone I work with suggesting that they should watch it.
 

1. What is the period-finding circuit for Shor's algorithm?

The period-finding circuit for Shor's algorithm is a key component in the quantum algorithm designed by Peter Shor for factoring large numbers. It is used to find the period of a function, which is necessary for the algorithm to work.

2. How does the period-finding circuit work?

The period-finding circuit utilizes quantum gates and quantum Fourier transforms to efficiently find the period of a function. It works by applying a quantum circuit to a superposition of inputs, which allows for multiple inputs to be evaluated simultaneously.

3. Why is the period-finding circuit important for Shor's algorithm?

The period-finding circuit is crucial for Shor's algorithm because it is used to find the period of a function, which is necessary for the algorithm to work. Without the period-finding circuit, the algorithm would not be able to efficiently factor large numbers.

4. What are the challenges in designing the period-finding circuit?

Designing the period-finding circuit for Shor's algorithm can be challenging due to the complexity of quantum gates and the need for precise control over quantum states. Additionally, the circuit must be able to handle a large number of inputs and outputs, making it difficult to implement in practice.

5. Are there any alternative methods for period-finding in Shor's algorithm?

While the period-finding circuit is the most commonly used method for Shor's algorithm, there are alternative methods such as the quantum phase estimation algorithm. However, these alternative methods may have different efficiency and accuracy trade-offs compared to the period-finding circuit.

Similar threads

  • Quantum Physics
Replies
13
Views
837
  • Quantum Physics
Replies
1
Views
661
Replies
2
Views
1K
  • Quantum Physics
Replies
11
Views
2K
  • Quantum Physics
Replies
5
Views
2K
Replies
2
Views
2K
Replies
14
Views
3K
Replies
1
Views
648
  • Introductory Physics Homework Help
Replies
14
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
2K
Back
Top