17
votes
Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm?
A first remark
This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not ...
- 10.7k
12
votes
Accepted
Who discovered the phase kickback trick?
The phase kickback trick appears in this paper:
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca. Quantum Algorithms Revisited. Proceedings of the Royal Society of London A, 454(1969):...
- 4,413
11
votes
Accepted
Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm?
Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't ...
- 46k
5
votes
Accepted
Can we use Hadamard test to estimate phases?
So QPE using $\mathcal{O}(1/\epsilon)$ queries to $U$ outputs an estimate of the eigenphase $\theta$ given a corresponding eigenvector with additive error and $\Omega(1)$ probability.
The method using ...
- 294
4
votes
What is Quantum Phase Estimation in Shor's Algorithm?
Phase estimation is the process by which you are given a controlled-$U$ unitary, and a state that you are promised is an eigenvector of $U$ with eigenvalue $e^{2\pi ix/2^t}$, then you can use a $t$-...
- 46k
4
votes
Question about the phase kickback in the phase estimation algorithm
The phase is applied to the overall wave function $|\phi\rangle$, therefore you can factor the phase to any individual qubit.
For example if we have a wave function as a result of a controlled ...
- 849
3
votes
Accepted
In the Bernstein-Vazirani circuit, if the secret is all 0s, would the oracle just be nothing?
Yes, this is because the initial state will be starting as $|\psi_{init} \rangle = |000\cdots0\rangle = |0\rangle^{\otimes 8} $. Then you apply a layer of Hadamard gates, follow by the Oracle ...
- 12.3k
3
votes
Unitary Operator impact on both - the Control Qubit and the Target Register in Shor's Algorithm
The key idea in understanding phase kickback is that phase factors do not belong to one register or the other, but instead belong to terms in superposition and are shared by the registers.
For example,...
- 13k
3
votes
How to understand intuitively the quantum gate phase kickback?
Part of the problem people usually have here is a sort-of-classical intuition. Because you're trying to describe the action of a gate such as controlled-$U$, we divide it up as "if the control ...
- 46k
3
votes
Is the $|-\rangle$ state the only one that can do the trick for Grover's algorithm?
Remember that the states $|+\rangle$ and $|-\rangle$ form a basis. That means that any state $|\psi\rangle$ that you use can be written as
$$
|\psi\rangle=\alpha|+\rangle+\beta|-\rangle.
$$
By ...
- 46k
3
votes
Accepted
Is the $|-\rangle$ state the only one that can do the trick for Grover's algorithm?
It would still work if you rotated the $|−\rangle$ state, you refer to, by an angle with cosine less than $\frac{1}{L}$ where $L$ is the square root of the size of the search space (which is a power ...
- 306
2
votes
Show that these two expressions for the oracle transformation are equivalent
You are given a quantum circuit for $U$ compiled into the H/CNOT/T gateset. Derive a controlled version of $U$ by adding a control qubit $q$, replacing every H with a controlled H, every CNOT with a ...
- 21.8k
2
votes
Accepted
How to decompose a multi-target controlled gate?
An example of constructing (with help of Qiskit) a controlled version of some simple 4x4 unitary matrix:
$$
U = \begin{pmatrix}
\mathrm{e}^{i g_1} & 0 & 0 & 0 \\
0 & \mathrm{e}^{i g_2}...
- 3,998
2
votes
What is Quantum Phase Estimation in Shor's Algorithm?
If you want to learn more generally about phase estimation, the book I am helping write has a whole chapter on it, Learn Quantum Computing with Python and Q# (chapter 8).
Ping me here or via email ...
- 814
2
votes
Accepted
In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?
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 ...
- 46k
2
votes
Accepted
Resources and references about phase kickback trick
The IBM Qiskit text has a section on this that you may find useful.
For something more "academic" Mermin Sections 4.2-4.5, Schuld and Petruccione Sections 3.5.1-3.5.3, or Nielson and Chuang ...
- 1,626
2
votes
Who discovered the phase kickback trick?
As to "who discovered/invented the quantum phase estimation algorithm," in his 2011 lecture at Keio University describing the linear equations algorithm, at about the 18 minute mark Lloyd claims that ...
- 6,767
1
vote
Accepted
Understanding phase kickback caused by the CNOT gate
There are two ways to see this.
simply factor the sum you have:
$$\frac{1}{2}(|00\rangle - |01\rangle - |10\rangle + |11\rangle) \\
= \frac{1}{2}(|0\rangle - |1\rangle)(0\rangle - |1\rangle) \\
=|-\...
- 988
1
vote
In the Bernstein-Vazirani circuit, if the secret is all 0s, would the oracle just be nothing?
With the Quantum Oracle $|x \rangle \xrightarrow{f_s} (-1)^{s\cdot x} |x \rangle$ (between the Hadamard sandwich) for the BV algorithm, with ($n$-bit) input secret bits $s$, here is what it does:
$|00\...
- 160
1
vote
Accepted
Why does the phase of the eigenstate get kicked up to the ancilla qubit?
Here is a basic example of a two system that might help you to see this better. Suppose I have these two circuits:
Circuit 1: Which put the "Controlled qubit" in the state $|1\rangle$ and ...
- 12.3k
1
vote
In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?
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 ...
- 12.3k
1
vote
controlled-Z rotation gates in symmetrical fashion
For the mathematical explanation, check here: Why is the action of controlled-Z unaltered by exchanging target control qubits?
Maybe it would help you to see CZ in a different (symmetric) notation, ...
- 3,771
1
vote
Accepted
Phase Kickback and Controlled Operations
Without a bit more context of how they use the notation in the rest of the book, I'm not certain, but the way I would interpret that is saying "if the control qubit is 0, apply unitary $\hat U_{f(0)}$ ...
- 46k
1
vote
Accepted
How does Inverse QFT work in Quantum Phase Estimation?
The expression you obtain after applying the QFT contains sums of the unit square, $e^{2\pi i/2^n}$, which sum up to 0 if you sum over the full range of $2^n$:
$$
\sum_{k=0}^{2^n - 1} e^{\frac{2\pi i}...
- 2,203
1
vote
Quantum Phase Estimation implementation
3 things I see from your implementation of inverse QFT:
SWAP gates are missing prior to applying Hadamard gates and cu1 gates.
The Hadamard gate should come first before cu1 gates.
The angles of cu1 ...
- 3,998
1
vote
Obtaining phases of all basis states
So, are you asking whether it's possible (in the qubit case) to perform an arbitrary map of the form
$$
ae^{i\theta}|0\rangle+be^{i\phi}|1\rangle\rightarrow \frac{1}{\sqrt{2}}(e^{i\theta}|0\rangle+e^{...
- 46k
1
vote
Accepted
Show that these two expressions for the oracle transformation are equivalent
If we express the action of $O_x$ on the basis $\mid i, \pm \rangle$ instead of $\mid i , b \rangle$
\begin{eqnarray*}
O_x \mid i , + \rangle = \mid i , + \rangle\\
O_x \mid i , - \rangle = (-1)^{x_i}...
- 3,503
Only top scored, non community-wiki answers of a minimum length are eligible