9
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 ...
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 $...
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:
7
The restriction on the eigenvalues is usually given in the form of a condition number. This is the $\kappa$ that you see in all the runtimes in your table. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{min}}|$ where $\lambda_{\rm{max}}$ and $\lambda_{\rm{min}}$ are the maximum and minimum eigenvalues respectively.
In all runtimes listed in your table, it is ...
6
This is indeed a correct way to solve linear systems with dimension not equal to a power of 2. Solve the smallest possible system of dimension 2$^n$ that contains the system you want to solve, and pad the matrices and vectors with zeros to make it the right size. This is because the vector $|b\rangle$ in the HHL algorithm, is a quantum state, which means if ...
6
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 ...
6
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, ...
6
You can draw the circuit using construct_circuit().draw().
In the tutorial you are talking about, if you scroll down to the 4x4 randomly generated section that uses params5 you can run print(hhl.construct_circuit()), after the line hhl = HHL.init_params(params5, algo_input).
This may take a little while to complete but it should eventually print out ASCII ...
6
There is actually a nice way to do this in Qiskit, since it has decompositions for single-qubit unitaries built in. The QuantumCircuit.squ method takes a unitary 2x2 matrix $U$ and a qubit and computes the decomposition
$$
U = R_Z(\alpha) R_Y(\beta) R_Z(\gamma)
$$
This is a common decomposition, you can find a proof here https://arxiv.org/pdf/quant-ph/...
6
These aren't error messages, they are just outputs. The first message simply means it will be using your credentials for the session. This has probably popped up because you have run IBMQ.load_accounts() more than once. The second message appears to just be the output of the creation of the circuits variable.
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
Qiskit is an open source. Specifically for HHL, see https://github.com/Qiskit/qiskit-aqua/blob/master/qiskit/aqua/algorithms/linear_solvers/hhl.py.
5
You were correct to seek a new quantum algorithm for this rather than just using HHL to do step 3.
There are separate quantum algorithms to do regressions:
Quantum Algorithm for Data Fitting (same journal and same last author as HHL)
Quantum Algorithm for Linear Regression
Fast quantum algorithms for least squares regression and statistic leverage scores
...
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 ...
5
Given that the QFT is exponentially faster than the FFT,
The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when reading out the result, the desired result gets a high probability.
The power of quantum computing comes from the vast phase-space that grows exponentially with ...
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
$\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'...
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
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 ...
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^\...
4
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_{...
4
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 ...
4
You want to implement
$$
e^{i3\pi/4}e^{iX\pi/4}.
$$
I would rewrite this as
$$
e^{i3\pi/4}He^{iZ\pi/4}H.
$$
This is the same as
$$
-HS^\dagger H
$$
in standard gate terminology.
If you're only implementing the gate $e^{iAt}$, then you can neglect the global phase and just implement $HS^\dagger H$. Both of these gates are readily implemented in qiskit as sdg ...
4
To find the expectation value of a given Pauli matrix, you just measure in the basis defined by the Pauli matrix. For example, to evaluate the expectation value of the $X$ matrix, you find the basis vectors of the $X$ matrix. These are $|+\rangle$ and $|-\rangle$, with corresponding eigenvalues +1 and -1. You measure in the $|\pm\rangle$ basis many times and ...
4
You don't know the eigenvalues a priori, but you have performed phase estimation, and have (at least a good approximation to) your eigenvalues recorded on a register. If you control off that register, you can use it to decide the angle of the rotation for each eigenvector.
4
By a large margin, I would recommend VQLS rather than H-HHL. VQLS is significantly more well-tested, is a more significant leap from the previous state-of-the-art for hybrid quantum/classical linear solvers, and is far more in the "mainstream" realm of quantum computing, meaning that your study will be more relevant in today's quantum computing ...
4
There is a new approach that will be merged soon in qiskit terra (here for the PR) that uses polynomial approximation to compute $\arcsin(C/\lambda)$, and asymptotically this would be the efficient implementation.
In practice if you are solving a $2\times 2$ matrix or a very small system it would be better to hard code the rotations.
The theory and error ...
Only top voted, non community-wiki answers of a minimum length are eligible