10
votes
What could be the possible future applications for HHL algorithm?
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 "...
- 1,556
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, ...
- 46.2k
9
votes
Accepted
Efficiently performing controlled rotations in HHL
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\}^...
- 46.2k
8
votes
Accepted
What exacty is "matrix sparsity" $s$?
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 ...
- 4,554
7
votes
Accepted
HHL algorithm -- why isn't the required knowledge on eigenspectrum a major drawback?
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{...
- 11.9k
7
votes
Quantum circuit to implement matrix exponential
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 ...
- 2,203
6
votes
Accepted
Solving linear systems represented by NxN matrices with N not power of 2
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 ...
- 11.9k
6
votes
Accepted
Practical implementation of Hamiltonian Evolution
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 ...
- 46.2k
6
votes
Accepted
Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?
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 ...
- 4,467
6
votes
Accepted
How to draw Qiskit's HHL algorithm as a circuit?
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 ...
- 3,153
6
votes
Accepted
Does the quantum Fourier transform have many applications beyond period finding?
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 ...
6
votes
Problem with HHL algorithm on Qiskit
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 ...
- 3,153
6
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,...
- 12.3k
6
votes
Source code for a Qiskit algorithm: HHL Algorithm
Qiskit is an open source. Specifically for HHL, see https://github.com/Qiskit/qiskit-aqua/blob/master/qiskit/aqua/algorithms/linear_solvers/hhl.py.
- 711
5
votes
Accepted
Clarification of the "Calculations" section of the (HHL09) paper
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,...
- 46.2k
5
votes
How to speed up the matrix multiplication steps in multi-linear regression?
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 ...
- 11.9k
5
votes
Accepted
HHL algorithm -- controlled-by-eigenvalues rotations
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,...
- 1,676
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,467
4
votes
Accepted
HHL algorithm -- problem with the outcome of postselection
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 ...
- 1,676
4
votes
Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?
$\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 ...
- 46.2k
4
votes
Accepted
Controlled unitary from the HHL algorithm – practical implementation using Qiskit
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 ...
- 4,467
4
votes
Accepted
What does $||A|| = 1$ mean in the definition of QLSP?
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 ...
- 46.2k
4
votes
Accepted
Using the HHL algorithm to compute $A |b \rangle$ instead of $A^{-1} |b \rangle$
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 ...
- 4,467
4
votes
Accepted
Showing that Matrix Inversion is BQP-complete - HHL Algorithm
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=...
- 46.2k
4
votes
Accepted
Apply the conditional Hamiltonian evolution (HHL)
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|\...
- 46.2k
4
votes
Quantum circuit to implement matrix exponential
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 ...
- 46.2k
4
votes
Accepted
Quantum circuit to get expectation values of Pauli matrices, given state $|\psi\rangle$
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 ...
- 46.2k
4
votes
Problem with controlled rotation in HHL
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, ...
- 46.2k
4
votes
New Hybrid-HHL algorithm vs VQLS
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 ...
- 11.9k
4
votes
Accepted
How to effectively compute eigenvalue rotation in HHL
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 ...
- 391
Only top scored, non community-wiki answers of a minimum length are eligible