Shor Algorithm - Post measurement state

In summary, the Shor algorithm involves using Hadamard gates and a unitary gate to construct a function, followed by a measurement in the second register to obtain a function value. This measurement will produce the values of k in the first register that correspond to the function value. However, the values of x and l, which are necessary to compute the function, cannot be determined and the second register can be discarded without affecting the first register's probabilities. The quantum Fourier transform is then applied to the first register, which is where the quantum aspect of the algorithm comes into play. The discrete Fourier transform should be understood separately before trying to understand it in combination with quantum computing. The deferred measurement principle is also used in Shor's algorithm,
  • #1
Ricardo Belchior
13
0
Hello!

So I'm working to try to understand shor algorithm and I have some doubts.

So, after the hadamard gates we apply the unitary gate that construct the function yk mod N. Next we do a measurement in the second register to get some function value. So, when I do this measurement on the second register, I will get, in the first register, only the values of k that correspond to that function value.

My question is, is that right? I'm I thinking straight? If so, who does that happen? Entanglement?

Thanks
 
Physics news on Phys.org
  • #2
You don't actually need to measure the second register. You can just throw it out.

But yes, if you measure the second register and get the result ##m## then that tells you the first register is in a state proportional to ##\sum_{j} |jl+x \rangle##, where ##x## is the value that satisfies ##b^x \equiv m \pmod{R}## and ##b^l \pmod{R} \equiv 1##. But you still don't know ##x## or ##l##, and they're intractable to compute, so really you haven't learned anything more at that point than you would by just classical random sampling. The fun quantum stuff only happens in the next step when you apply the quantum Fourier transform (and at that point it matters that you have a superposition instead of a probability distribution).

I wouldn't consider "entanglement" to be a good description of why this happens. It's just kinda what has to happen in order for things to be consistent. If you some register storing ##x##, then compute ##b^x## into another register, then obviously the relationship between the two isn't affected by the order you measure them. If you measured the second register and got ##m##, then measured the first register and got some value ##x## that didn't satisfy ##b^x = m##, that would be pretty ridiculous.
 
  • #3
Thanks for the great answer.

Exactly, that state cannot be computed. But if I throw away the second register, the first one will have the same probabilities for all values, just like the output of hadamard gates, right?

Strilanc said:
(and at that point it matters that you have a superposition instead of a probability distribution).

What do you mean by that?

I think my biggest struggle is to understand what goes into the QFT.

Sorry for all the questions, but I'm having a really hard time to understand all this.

Thanks
 
  • #4
You should learn about the discrete Fourier transform separately, classically, before trying to understand it in combination with quantum computing and in combination with a specific algorithm in quantum computing.
 
  • #5
Hello again,

So I have another question. In Shor algorithm it is applied the deffered measurment principle, right? I mean, if i did the measurment at the beginning, the results would be the same?

cheers
 
  • #6
What do you mean "at the beginning"? If you measure the phase-estimation register before the QFT, or the work register when only some of the multiplications have been done, no you won't get the same answer.
 
  • #7
Ok I get it. But i still have some hard times to understand the phase-estimation. I think the bottom question is : How do I implement the controlled-U to implement ax mod N?
 
  • #8
You break it down into simpler and simpler operations until you're left with just (a whole lot of) constant-sized operations.

I've been working on a paper that does this. Here's my simplified dependency graph:

dependencies.png


And two of the steps, as an example:

controlled-modular-multiply-accumulate.png


controlled-modular-double.png
 

1. What is the Shor Algorithm and how does it work?

The Shor Algorithm is a quantum algorithm that is used to efficiently factor large numbers. It works by using quantum operations to find the period of a function, which is then used to factor the number. This algorithm is much faster than classical algorithms for factoring large numbers.

2. What is the significance of the "post measurement state" in the Shor Algorithm?

The post measurement state in the Shor Algorithm refers to the state of the qubits after the quantum measurement is performed. This is an important step in the algorithm as it collapses the superposition of states and provides the desired result.

3. Can the Shor Algorithm be used for other applications besides factoring large numbers?

Yes, the Shor Algorithm has potential applications in other areas such as cryptography, optimization problems, and quantum simulation. However, it is most commonly known for its use in factoring large numbers.

4. What are the limitations of the Shor Algorithm?

One of the main limitations of the Shor Algorithm is its dependence on quantum computers. It is not possible to run this algorithm on classical computers due to the large number of qubits required. Additionally, the algorithm is susceptible to errors and noise in quantum systems, which can affect the accuracy of the results.

5. Are there any alternatives to the Shor Algorithm for factoring large numbers?

Yes, there are several classical algorithms that can be used for factoring large numbers, such as the General Number Field Sieve (GNFS) and the Quadratic Sieve (QS). However, these algorithms are much slower than the Shor Algorithm and can only be used for smaller numbers.

Similar threads

  • Quantum Physics
Replies
13
Views
817
  • Quantum Physics
Replies
11
Views
2K
  • Quantum Physics
Replies
5
Views
2K
  • Quantum Physics
Replies
3
Views
891
Replies
2
Views
2K
  • Quantum Physics
Replies
1
Views
644
  • Quantum Physics
Replies
1
Views
726
  • Quantum Physics
Replies
24
Views
1K
Replies
3
Views
754
Replies
5
Views
924
Back
Top