TransWikia.com

In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?

Quantum Computing Asked by ToastyX on April 14, 2021

I’m studying the Shor algorithm as part of my thesis and have a question about the "measured" phases after the QPE.

So, I take the controlled-U operations on the second register and in cause of phase kickback the relative phase of the controll qubit in register one will change with a multiple of the eigenvalue of $U$. I understand, that $cU$ has multiple eigenvalues with a factor $s$. How can be guaranteed that each of the controlled-Us will kickback the same eigenvalue? Or, why it is not important?

Second, if I run the controlled-U operations and make the QPE, why it is possible to get different results? I thought that the transformation between the bases is unique. So, if my controlled-U makes a specific "change" on the quibit, how it is possible that the QPE generates a superposition with specific probabilities? (e.g. in Nielsen/Chuang Box 5.4 the final measurement will give 0, 512, 1024, 1536)

Thank you for your help.

2 Answers

I understand, that cU has multiple eigenvalues with a factor s. How can be guaranteed that each of the controlled-Us will kickback the same eigenvalue? Or, why it is not important?

All the $U$s in the various controlled-$U$ are the same $U$, with the same eigenvectors and the same eigenvalues. This is part of the construction of the circuit, and provides the guarantee that you are seeking.

Second, if I run the controlled-U operations and make the QPE, why it is possible to get different results?

Remember that, for QPE, if you input an eigenvector of $U$ (and if that eigenvalue has an exact $t$-bit representation) then a $t$-bit QPE will give exactly the eigenvalue, no probabilities.

However, for Shor's algorithm, we cannot create an eigenvector - it requires knowledge of the value $s/r$, which is exactly what we're trying to find out! So, instead of inputting an eigenvector, we input $|1rangle$, which is a superposition of several different eigenvectors. By linearity, the end result is a superposition of several different possible eigenvalues, and when we measure, the measurement just finds one of those values at random.

Correct answer by DaftWullie on April 14, 2021

Have you seen this document? https://qiskit.org/textbook/ch-algorithms/shor.html

Note that in Shor's algorithm, we use the quantum computer as a subroutine to essentially find the period of the function

$$ f(x) = a^x mod N$$

where $a$ is a guessed value between $1$ and $N-1$. So you have to create different circuit to implement each of the guessed $a$.


As for the QPE step, this is essentially as follow:

Let's suppose that

$$ U|psirangle = e^{2pi i phi} |psirangle$$

then

$$U^{2^j}|psi rangle = U^{2^j -1}bigg(U|psiranglebigg) = U^{2^j -1}bigg( e^{2pi i phi} |psiranglebigg) = cdots = e^{2pi i 2^j phi} |psi rangle$$

The phase-kickback turn each of the ancilla qubit (after going through Hadamard gate) from the state $dfrac{|0rangle + |1 rangle}{sqrt{2}}$ to the state $dfrac{ |0rangle + e^{2pi i 2^j phi}|1 rangle}{sqrt{2}}$ under $CU^{2^j}$ operator. To be mathematical precise,

$$CU^{2^j}: bigg( dfrac{1}{sqrt{2}} big( |0rangle + |1rangle big) bigg)|psirangle to dfrac{1}{sqrt{2}} bigg( |0rangle |psi rangle + |1rangle e^{2pi i 2^j phi} |psirangle bigg) = dfrac{1}{sqrt{2}} bigg( |0rangle + e^{2pi i 2^j phi} |1rangle bigg)|psirangle $$

Now if you apply the inverse QFT to all the ancilla qubit then you will get the binary expression of $phi$.


Answered by KAJ226 on April 14, 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