8
The setting is that you've got some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ on a register, you introduce an ancilla in state $|0\rangle$, and you want to create some state
$$
\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle\otimes R_X(f(x))|0\rangle
$$
where $f(x)$ is some angle that you can compute. So, certainly, if you had to build that gate out of the $2^n$ ...
7
You have the definitions in your paper you link page 12.
Simply said, it is a matrix with many 0s.
As an example take N = 16, and the polynomial function is just a simple function like 1.5*X,
then your matrix has at most 1.5*log(16,2)=6 non-zero entries per row.
If you prefer a visual, you have it here:
6
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 $...
5
I don't know why/how the authors of that paper do what they do. However, here's how I'd go about it for this special case (and it is a very special case):
You can write the Hamiltonian as a Pauli decomposition
$$
A=15\mathbb{I}\otimes\mathbb{I}+9Z\otimes X+5X\otimes Z-3Y\otimes Y.
$$
Update: It should be $+3Y\otimes Y$. But I don't want to redraw all my ...
5
1. Definitions
Names and symbols used in this answer follow the ones defined in Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018). A recall is done below.
1.1 Register names
Register names are defined in Figure 5. of Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, ...
5
If $\tilde{\lambda_{k}} < C$, the controlled rotation becomes non-physical since you have coeffecient greater than 1 on your $|1\rangle$ state.
As a result $C < \lambda_{min}$ is a safer choice, and that is $O(1/\kappa)$ according to the 4th paragraph in the intro.
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 ...
4
Your intuition is correct for a single qubit, in that if I measure $$\alpha\vert 0 \rangle + \beta\vert 1 \rangle$$ I would get either $\vert 0 \rangle$ or $\vert 1 \rangle$. But since the qubits are in a large entangled state, the relevant information stored in the ratios of different probabilities is still held fixed, and the $\frac{C}{\lambda_j}$ factors ...
4
Certainly it is meant as the largest eigenvalue. I have no idea why the linked review paper uses the determinant. I don't see anywhere that they use that property (from an admittedly brief skim).
I presume you could rewrite conditions in terms of the determinant (you would have to alter the time step $t_0$) but it's not clear to me why you would want to. It'...
4
I know that $b$ can be decomposed mathematically as $b= c_1u_1 +
> \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis.
Why only consider the effect on $|u_j \rangle$?
As you say, you know you can decompose $b$ in terms of the $|u_j \rangle$, so by linearity, if we know the effect on one basis state (which is pedagogically easier to ...
4
Note: the graphics have been generated with the LaTeX code available here. Credits to @Niel de Beaudrap.
Yes it is possible!
The HHL algorithm can be schematically depicted as
Let's split down the parts:
The first part aims at computing an approximation of the eigenvalues of $H$, $H = A$ if $A$ is hermitian, else $H = \begin{pmatrix} 0 & A \\ A^\...
3
Let's assume that you have a Hermitian matrix
$$
H=\left(\begin{array}{cc} 0 & A^\dagger \\ A & 0 \end{array}\right).
$$
Let $|b\rangle$ be the state that we want to apply $A$ to, extended to work on the space that $H$ acts on. So, our aim is to implement $H|b\rangle$.
Let $X$ be the standard Pauli $X$ matrix. If we implement a unitary evolution
$$
...
3
The simplest method to implement $e^{iA\theta}$ for a small, Hermitian matrix $A$ is to:
Find the eigenvectors $|\lambda\rangle$ and eigenvalues $\lambda$ of $A$.
Construct the unitary $U=\sum_i|i\rangle\langle\lambda_i|$.
Implement the gate sequence:
$U$
$e^{i\theta\sum_i\lambda_i|i\rangle\langle i|}$
$U^\dagger$
Now, for one qubit, you have the middle ...
3
1) Are we not applying the conditional Hamiltonian evolution to $|\Psi_0 \rangle |b \rangle$?
The operation
$$\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau| \otimes e^{iA\tau t_0 / T}$$
is a controlled operation. You can read it as:
$\forall \tau \in [0, T-1]$, if the first register is in the state $\vert \tau \rangle$, apply $e^{iA\tau t_0 / T}$. ...
3
Disclaimer: I'm the one that wrote the code of the 4x4 HHL.
Controlling a quantum gate $U$ can be achieved by controlling each of the $U_i$ gates that are composing $U$.
For the specific example you are considering, the implementation is available online. Some remarks about the code:
I think the code is not up to date with the last version of Qiskit. I ...
3
It's not possible to create the initial states $\left| \Psi_0\right>$ and $\left|b\right>$ on the IBM 16 qubits version. On the other hand, it is possible to approximate them with an arbitrarily low error1 as the gates implemented by the IBM chips offer this possibility.
Here you ask for 2 different quantum states:
$\left| b \right>$ is not ...
3
$\newcommand{\bra}[1]{\left\langle#1\right|}\newcommand{\ket}[1]{\left|#1\right\rangle}\newcommand{\proj}[1]{|#1\rangle\langle#1|}\newcommand{\half}{\frac12}$In answer to your first question, I wrote myself some notes some time ago about my understanding of how it worked. The notation is probably a bit different (I've tried to bring it more into line, but it'...
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
A couple years ago it was shown in Quantum algorithms and the finite element method by Montanaro and Pallister that the HHL algorithm could be applied to the Finite Element Method (FEM) which is a "technique for efficiently finding numerical approximations to the solutions of boundary value problems (BVPs) for partial differential equations, based on ...
3
You are half right, in that the $C$ factor is only kept there for (what I assume being) explanatory purposes.
However, the $1/\lambda_j$ factors definitely stays there after postselection. One way to see this is that you can think of those factors as attached to the other registers, so that the state is equivalently written as
$$
\left(\sum_j\beta_j\sqrt{1-...
3
Define the states
$$
|\psi_t\rangle=\left\{\begin{array}{cc}
|t\rangle\otimes(U_{t-1}U_{t-2}\ldots U_1|\psi\rangle) & t=1,2,\ldots T \\
|t\rangle\otimes(U_{T}U_{T-1}\ldots U_1|\psi\rangle) & t=T+1,T+2,\ldots 2T \\
|t\rangle\otimes(U_{3T+1-t}U_{3T-t}\ldots U_1|\psi\rangle) & t=2T+1,2T+2,\ldots 3T
\end{array}\right.
$$
Now let
$$
U=\frac{2}{T}\sum_{...
3
Be careful! They don't apply $e^{i\pi A}$ and $e^{i\pi A/2}$. They apply
$$
|0\rangle\langle 0|\otimes I\otimes I+|1\rangle\langle 1| \otimes I\otimes e^{i\pi A}
$$
and
$$
I\otimes |0\rangle\langle 0|\otimes I+I\otimes |1\rangle\langle 1|\otimes e^{i\pi A/2},
$$
i.e. controlled versions of the gates, controlled off two different qubits.
So, consider the 4 ...
2
I believe the way they use it is as
The maximum number of non-zero elements in any row.
Although that’s different to the way Wikipedia defines sparsity, which is essentially the average:
the total number of non-zero elements divided by the number of elements.
2
One way to go about this is using the Linear Combination of Unitaries (LCU) algorithm. The LCU algorithm simulates the action of any operator that can be written as a linear combination of simulatable unitary operators. A full treatment of this can be found in Kothari's thesis. Using LCU algorithm, given the ability to apply $e^{i \rho t}$ to the state, the ...
2
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 ...
2
Quick answer: You will not be able to fully recover $x$.
Explanations:
By design, the HHL algorithm stores $x$ in the amplitudes of a quantum state. Because of how quantum mechanics works, the vector representing the quantum state (i.e. containing all the amplitudes of the quantum state) needs to be of unit-norm (according to the Euclidean norm). Because ...
Only top voted, non community-wiki answers of a minimum length are eligible
