15
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 only is it possible, it is an important fact about quantum computation that it is possible. It even has a name: a "phase kick", in which the control qubits (or ...
10
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 attached to a specific register, it's just an overall multiplicative factor.
Now let's use a superposition on the first register:
$$
(|0\rangle+|1\rangle)|u\rangle\...
9
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, spreading the values $\lambda t$ over the full $2\pi$ range. Bounding the eigenvalues is not typically a problem. For example, you're probably requiring your matrix $...
6
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 &= \lambda |\psi\rangle\\
\end{align}
$$
Conjugate and transpose both sides of the equation:
$$
\begin{align}
\langle\psi|U^\dagger &= \langle \psi| \...
6
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,X,Y,Z\}^{\otimes n} $$
note this linear combination can have up to $4^n$ terms. Thus, for a general Hamiltonian splitting it into linear combination of Pauli ...
6
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 answer).
The aim of PE is to find the phase, more specifically the $\phi$ in the book of Nielsen:
Suppose a unitary operator $U$ has an eigenvector $\mid u\...
5
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).
Rather, it estimates the eigenvalue of a given unitary $U$ that corresponds to the given eigenvector $|\psi\rangle$ - the angle $\alpha$ in the following equation:
...
5
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 disappear, i.e. $t = t_0 = 2\pi$.
The approximate eigenvalue is often written $\tilde \lambda$. In some paper this notation really means "the approximation of the ...
5
@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 Hamiltonian being the underlying thing that determines evolution, and unitaries are derived as a consequence. They start from the Schrödinger equation,
$$
i\...
5
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 state:
$$|\psi \rangle = \frac{1}{\sqrt{2}} \left( |0\rangle + e^{i\theta}|1\rangle\right)$$
We are going to execute $2$ different experiments in order to ...
5
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 the relative phase of a qubit? for the first qubit :-)
5
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 different values of $M$, from a geometric sequence, to cover the possibility space.
One improvement they make over what you've described is that they do the big ...
5
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 separate Hadamard Tests, that you mentioned, works. However, it requires $\mathcal{O}(1/\epsilon^2)$ samples to just get $\epsilon$-estimates of the real and ...
4
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$-qubit register to affect the change
$$
|0\rangle^{\otimes t}|u\rangle\mapsto|y\rangle|u\rangle.
$$
If $x$ is in integer, then the outcome is guaranteed to be $y=x$...
4
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 are interested in, meaning we want to find $\theta$ here. After applying all the Hadamard gates and the $U^{2^j}$, the state looks like this :
$$ \frac{1}{2^{n/2}...
4
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 improvement. For Grover alone, you need to do $O(2^{n/2})$ steps and in each step, you basically do a rotation. This rotation is very unlikely to be Clifford, thus ...
4
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 operation, with the first qubit as the control:
$A|11\dots \rangle$, this can be factored as the tensor product $A|1\rangle \otimes |1\rangle \otimes |\dots\rangle$. ...
3
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 it turns out that you can.
It is probably worth noting (iirc) that even if the best way of implementing controlled-$U^{2^k}$ is with $2^k$ controlled-$U$s, ...
3
I would just like to share a code for testing a phase measurement on IBM Q:
OPENQASM 2.0;
include "qelib1.inc";
qreg q[1];
creg c[1];
//measuring theta in
//(|0> + |1>*exp(i*theta))
h q[0]; //(|0> + |1>)
t q[0]; //(|0> + |1>*exp(i*pi/4))
//s q[0]; //(|0> + |1>*exp(i*pi/2))
//u1 (pi/8) q[0]; //(|0> + |1>*exp(i*pi/8))
...
3
The $U$ used in phase estimation is not only a diagonal matrix with the same diagonal elements. Instead, it is an arbitrary unitary matrix.
The way that you analyse it, instead, is that the input $|u\rangle$ is specifically chosen to be an eigenvector of $U$. That means $U|u\rangle=e^{i\phi}|u\rangle$. But there are different eigenvectors with different ...
3
I don't see the need for the swap gate either. Although I also don't think you need the set of swap gates that you're wanting. Remember that the standard implementation of the Fourier transform outputs the binary string $j\in\{0,1\}^4$ where the eigenvalues are of the form $2\pi j/16$ but in reverse order, so the least significant bit is at the top, and the ...
3
What am I missing here? Where did the factor of $\frac{t}{2\pi}$ vanish in their algorithm?
Remember that in Dirac notation, whatever you write inside the ket is an arbitrary label referring to something more abstract. So, it is true that you are finding the (approximate) eigenvector to $U$, which has eigenvalue $e^{-i\lambda t}$ and therefore what you're ...
3
These two circuits produce the same results - in both cases you'll get $|0\rangle \otimes |\psi\rangle$ with 50% probability or $|1\rangle \otimes U|\psi\rangle$ with 50% probability.
But I don't think this is going to help you with the phase estimation algorithm. In quantum phase estimation application of $U^c$ is followed by inverse Fourier transform ...
3
Let me augment the discussion by adding some insight into the derivation of the estimate provided. This will give you a good understanding of when the result is an approximation and when it is precise. After the algorithm has run, we are left with the following state on the first register:
$$\frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{...
3
If this is part of a debugging effort then you can use the DumpRegister function.
If you have a qubit q which is in the general state $\alpha|0\rangle + \beta|1\rangle$ where $\alpha$ and $\beta$ are complex numbers such that $|\alpha|^2+|\beta|^2=1$.
DumpRegister([q])
will give an output like this (Having Different Numbers)
# wave function for qubits with ...
3
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 the eigenvector, only the superposition of them, which is $|1 \rangle$. Now, what does phase estimation result in for a superposition? It is just a ...
3
No - the key intuition of QPE is that $e^{2 \pi i \theta} $ holds for $\theta \in [0, 1) $, and the reading out the ancilla provides the binary representation of the fraction.
If you changed the operator to $e^{2 e i \theta}$, $\theta \not \in [0, 1)$ necessarily. Instead, you should just use the typical QPE approach, but then find $\zeta$ where $2 e i \zeta ...
3
Quantum phase estimation does not have anything to do with $\theta$. I feel that you are confusing phase estimation with the implementation of HHL as given in the paper https://arxiv.org/abs/1804.03719.
As for quantum phase estimation, it works only on unitary matrices. Given a unitary matrix $U$ and and eigenvector $|\psi\rangle$ of $U$ with some eigenvalue ...
3
Your implementation is really close - on the website, here's the diagram that they used:
So, I think you reversed the angles - it should be $-\pi/2, -\pi/4, -\pi/2$. (Also: there's a QFT inverse that Quirk has, so you can verify that the first half of your circuit is correct).
3
In your code the measure clause means one shot, so the state collapses to one basis state as here:
By removing that last line the Statevector option shows the state before measurement, i.e. as a superposition of basis states:
Now you can see that for the basis states with q[0]=1 (that is 0001 and 1001) we get the right components of the solution vector $x$ ...
Only top voted, non community-wiki answers of a minimum length are eligible