Arithmetic Block in Shor Algorithm

In summary: Let me ask another question then. If I do a controlled operation on qubit2 with qubit1 in an unknown state, does that also affect qubit1 in an unknown state?No, the operation will only affect the part of the superposition where the control is on.In summary, the author explains how to implement Shor Algorithm from top to bottom using 2n+1 qubits. The majority of the work is classical reversible circuits with some quantum gates optimizations. There is a known-good construction plus its inverse added to the circuit and tested for stability.
  • #1
Ricardo Belchior
13
0
Hello everyone!

So I was looking at Shor Algorithm for prime factorization and I have some doubts in the arithmetic part.

Let's define a function f that : f(x) = ax mod N. The middle step in shor algorithm is to calculate, simultaneously, all values of f. In some papers and books, I saw some high level implementation of this block, but nothing concrete. Can someone explain to me, how they do this?

In some implementations they use Controlled-Gates. Ok, that's fine, but the control qubit is always in some superposition of states. So what happens in this cases?Thanks!
 
Physics news on Phys.org
  • #2
I've been working on a paper that explains how to implement Shor's algorithm from top to bottom using 2n+1 qubits (w/ n-1 in an unknown state that must be preserved) (the previous best was 2n+2 w/ none in an unknown state). Here's a few diagrams from it.

The fact that the exponentiation is calculated under superposition doesn't really matter at all. All the arithmetic can be done with classical reversible circuits. There are some optimizations made possible by quantum gates, and of course the very top level has some quantum stuff, but all the arithmetic really is just standard classical reversible stuff.

An adder (not novel):

inline-adder.png


Incrementing (novel):

controlled-increment-odd.png


Scaled modular addition (not really novel; clearly I should just be adding 2^p*K instead of doing this doubling stuff):

controlled-modular-multiply-accumulate.png


Transitive reduction of the dependency graph between constructions:

dependencies.png


As that last diagram shows, there's a rather lot of constructions on the path from exponentiation to Toffolis. But they all basically look like the diagrams I showed: take what you've built up so far, and combine it to build the next thing.
 
Last edited:
  • #3
Incidentally, you can simulate the period-finding part of Shor's algorithm in my quantum circuit simulator Quirk.

You can't do the follow-up continued fractions algorithm to turn the period into a factor in Quirk, so mostly you can just see that "Yup, there's strong peaks near 2^n*k/p where p is the period and k is arbitrary". But still Quirk is a tool I used when looking for / optimizing / checking most of the constructions. I would add a known-good construction plus its inverse to the circuit, set up a "test harness" that made/unmade random test vectors, and then just watched to make sure the output stayed consistently off as I tried to optimize one of the constructions.
 
  • #4
Thanks a lot! That schemes where very helpful. But I still don't get that superposition thing. If I don't know the control qubit value, how do I do it? I suppose you assume some value? I think that I do not get that superposition part.
 
  • #5
You just do a controlled operation with the appropriate phase estimation qubit as the control. The operation will only affect the part of the superposition where the control is on.

Controlled operations are also a classical reversible computing concept, so again you don't need to know any quantum computing to implement circuits that do controlled arithmetic. (Notice that the diagrams do include controls)
 
  • #6
Ok Thanks, I think I got it.
 

1. What is the arithmetic block in Shor's algorithm?

The arithmetic block in Shor's algorithm is a crucial step in the quantum algorithm used to factor large integers. It involves performing modular exponentiation and modular multiplication operations to find the period of a function, which is then used to determine the factors of the original integer.

2. How does the arithmetic block work?

The arithmetic block works by taking in an input number, performing modular exponentiation and modular multiplication operations, and then measuring the resulting quantum state to obtain the period of a function. This period is used to determine the factors of the original integer through a classical algorithm.

3. Why is the arithmetic block important in Shor's algorithm?

The arithmetic block is important because it is the quantum part of Shor's algorithm, which allows for the efficient factorization of large integers. Without this block, the algorithm would not be able to find the period of the function and would not be able to determine the factors of the original integer.

4. What are the challenges in implementing the arithmetic block in Shor's algorithm?

The main challenges in implementing the arithmetic block in Shor's algorithm include finding a suitable quantum circuit to perform the modular exponentiation and multiplication operations, dealing with the noise and errors in the quantum system, and optimizing the circuit to minimize the number of quantum gates and qubits required.

5. Can the arithmetic block be used for other applications besides integer factorization?

Yes, the arithmetic block in Shor's algorithm can be adapted for other applications that involve finding the period of a function, such as discrete logarithm problems and certain types of optimization problems. However, these applications may require modifications to the original algorithm and circuit design.

Similar threads

Replies
2
Views
1K
  • Quantum Physics
Replies
11
Views
2K
Replies
2
Views
2K
  • Quantum Physics
Replies
1
Views
644
  • Quantum Physics
Replies
1
Views
2K
  • Quantum Physics
Replies
7
Views
2K
  • Quantum Physics
Replies
2
Views
1K
Replies
3
Views
2K
Replies
2
Views
2K
  • Quantum Physics
Replies
1
Views
1K
Back
Top