TransWikia.com

Shor's algorithm: initialization of second register

Quantum Computing Asked on May 30, 2021

I am trying to understand Shor’s algorithm. I am not quite sure why the initialization, indicated as $|1rangle$ in the below image at the bottom left is chosen as it is? I understand the modular exponentiation method in principle, but I am not sure which initialization should be chosen.

enter image description here

2 Answers

The initial state of Shor's algorithm is $frac{1}{sqrt N}displaystylesum_{a=0}^{N-1}|arangle$, and it is OK to move this state to $frac{1}{sqrt N}displaystylesum_{a=0}^{N-1}|a,xrangle$ as our initial state since the modular exponentiation takes $x$ as one of its input.

Here shows the model of a $text{controlled}-U$ gate, and a circuit for factoring (figure comes from this paper).

C-U shor

So I think the $|xrangle$ denoted here directs to $|xrangle$, although I do not know why they are doing so.

Answered by Yitian Wang on May 30, 2021

For preference, in a phase estimation algorithm, you would set the state of the second register equal to an eigenstate of the unitary operator $U$, the plan being to find its eigenvalue, which depends on the period $r$. In fact, any of the eigenvectors $|u_srangle$ would do for values $s=0,1,ldots r-1$ as these have eigenvalues related to $s/r$.

However, the eigenstates themselves depend on $r$, so without knowing $r$, you cannot make the eigenstate, and so you cannot find $r$. That's a problem.

The way to circumvent the problem is that you can prepare the state $|1rangle$, and it turns out that this state is an equal superposition of all the vectors $|u_srangle$. Using linearity, you now know the outcome - an equal superposition of the estimates of the different eigenvalues (entangled with the second register). Thus, in effect, what the phase estimation does is it measures one of the $s/r$ eigenvalues at random (with equal probability). (You then use the continued fractions algorithm to figure out which $s$ it was.)

Answered by DaftWullie on May 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP