23
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 ...
- 11.6k
17
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 ...
- 52.3k
9
votes
Accepted
Quantum phase estimation and HHL algorithm - knowledge of eigenvalues required?
You should know a bound on the eigenvalues (both upper and lower). As you say, you can then normalise $A$ by rescaling $t$. Indeed, you should do this to get the most accurate estimate possible, ...
- 52.3k
7
votes
Accepted
Quantum Circuit for $e^{iAt}$ Hamiltonian Simulation in HHL algorithm
As requested through the comment by the OP.
Given a Hermitian matrix $H$, we can always write it as linear combination of Pauli strings. That is,
$$ H = \sum_i \alpha_i P_i \hspace{1 cm} P_i \in \{I,...
- 13.3k
7
votes
Accepted
Clarification on state prep for quantum phase estimation
Your supposition is spot on. Indeed, quantum phase estimation (QPE) can be applied even when the input state is not an eigenstate of the unitary $U$. The key point to note is that, by expanding the ...
- 817
6
votes
Accepted
Are the squared absolute values of the eigenvalues of a unitary matrix always 1?
Good question. The answer turns out to be Yes.
You don't even need the vector to be normalized. Watch:
Start with the definition of eigenvalues and eigenvectors:
$$
\begin{align}
U|\psi\rangle &=...
- 12.8k
6
votes
Accepted
What is the difference between amplitude amplification, amplitude estimation, and phase estimation?
To find the differences between them, you only need to know the aim of the problems.
The aim of AA is to find the answers from unstructured data(or more directly, amplify the probability of the right ...
- 2,782
6
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 ...
- 314
6
votes
Accepted
Does phase kickback require the system to be in the eigenstate?
The first circuit equality fails when $|\psi_k\rangle$ is not an eigenstate of $U$.
A simple way to see this is to set the control qubit to $|1\rangle$. In this case, the RHS circuit is equivalent to $...
- 19.3k
5
votes
Accepted
Which angle is estimated by the phase estimation algorithm?
Neither.
Phase estimation algorithm does not estimate a property of a qubit state (and the angles $\theta$ and $\varphi$ in your question are exactly that - a property of a given qubit state).
...
- 8,296
5
votes
Accepted
Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm
It depends on the papers but I saw 2 approaches:
In most of the papers I read about the HHL algorithm and its implementation, the Hamiltonian evolution time $t$ is taken such that this factor ...
- 4,702
5
votes
Are the squared absolute values of the eigenvalues of a unitary matrix always 1?
@user1271772's answer is excellent, and absolutely the right answer. I just wanted to add in some additional perspective, given recent questions regarding Hamiltonians. Many physicists start from the ...
- 52.3k
5
votes
Accepted
Given a state $|\phi\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta}|1\rangle)$, how do I know the angle $\theta$?
Answer to the first question:
As mentioned in the comments of the question I assume that we can prepare $|\phi \rangle$ as many as we want. Let's calculate the relative phase for this one qubit pure ...
- 4,146
5
votes
Accepted
How to get the relative phase of an entangled pair of qubits
Apply a CNOT gate with one of the qubits as control and the other as target. You'll get
$$\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta}|1\rangle) \otimes |0\rangle$$
Use the methodology from How to get ...
- 8,296
5
votes
In the quantum phase estimation algorithm, why can't we directly compute the eigenvalue from the known eigenvector?
There are two different issues at play here. First is the difficulty of the calculation. If you have an $n$-qubit unitary $U$, then to evaluate $Ux$, you have to multiply a $2^n\times 2^n$ matrix with ...
- 52.3k
5
votes
Accepted
Can quantum search be performed without phase estimation?
I'm sure I'm not the first to notice this; does it appear somewhere?
Section 6 of the 1996 paper "Tight Bounds on Quantum Searching" by Boyer et al uses this strategy of iteratively trying ...
- 30.2k
5
votes
Accepted
Phase estimation using $U_3$ gate
If you were to apply QPE to this unitary, what you will get, assuming you start with a proper eigenvector $|\Lambda\rangle$, is an estimation of $x$, if the associated eigenvalue $\Lambda$ is written ...
- 4,636
5
votes
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
$\text{QFT}\big(|0\rangle^{\otimes n}\big) = \text{QFT}^{-1}\big(|0\rangle^{\otimes n}\big) = |{+}\rangle^{\otimes n}$, so a QFT, inverse QFT, or a column of Hadamard gates are all equivalent at the ...
- 788
5
votes
Accepted
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
Note that $\text{QFT}^2$ is a permutation $|k\rangle \rightarrow |(-k) \bmod 2^n\rangle$. This is a classical operation. It can be applied in the post processing of the measurements, and in fact it ...
- 30.2k
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$-...
- 52.3k
4
votes
Accepted
How to implement exponentiation of a gate without breaking complexity?
As a general rule, just because you can produce controlled-$U$, it does not mean that you can produce controlled-$U^{2^k}$ with the same complexity. Modular exponentiation is a very special case where ...
- 52.3k
4
votes
Accepted
Why can I use the Sum of Eigenvectors for Phase Estimation in Shor
As you say, we would be able to use phase estimation if we knew the eigenvector $|u_s \rangle$ that depends on the order $r$ and the integer $s$ which is $0 \leq s \leq r - 1$. However, we don't know ...
- 489
4
votes
A question regarding quantum phase estimation algorithm
The objective of all those gates is to put the quantum state in a "nice form" to manipulate. Let me explain. Let's note $U |\psi \rangle = e^{2i\pi\theta}|\psi\rangle$ all the variables we ...
- 2,522
4
votes
Accepted
Quantum Amplitude Estimation vs Quantum Phase Estimation
Ok let's break this down. Firstly the success probability for QPE and QAE are defined slightly differently.
With QPE there are two error bounds $|\hat{x} - x| < \epsilon$ to consider
$\epsilon < ...
- 919
4
votes
Accepted
Simulating QPE + Grover using Low-Rank Stabilizer Decomposition
I agree that the Bravyi et al. paper is not easy to understand and they should have made some reference implementation available.
Without going into details, I don't think it is likely to get an ...
- 4,167
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 ...
- 919
4
votes
Accepted
Interpreting the phase in QPE
Given your definition $U|\psi\rangle=e^{2\pi i\theta}|\psi\rangle$, then the $U$ that you use can be any value of $\theta$. However, the answer you get out will (with high probability) be the best $t$-...
- 52.3k
4
votes
Is Shor demonstration wrong?
In Equation 5.4, the expression of the state is given, which is:
$$\newcommand\ket[1]{\left|#1\right\rangle}\ket{\psi}=\frac1q\sum_{a=0}^{q-1}\sum_{c=0}^{q-1}\exp\left(\frac{2\mathrm{i}\pi ac}{q}\...
- 4,636
3
votes
Given a state $|\phi\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta}|1\rangle)$, how do I know the angle $\theta$?
I would just like to share a code for testing a phase measurement on IBM Q:
...
- 13.1k
3
votes
Accepted
Travelling salesman problem on quantum computer
Based on comment by DaftWullie and my experience with the algortihm, it seems that a title of the article is misleading.
The authors claim that algorithm they proposed is efficient. However, this is ...
- 13.1k
Only top scored, non community-wiki answers of a minimum length are eligible