Skip to main content

Questions tagged [hhl-algorithm]

For questions related to the quantum algorithm for inverting linear systems of equations, developed by Harrow, Hassidim and Lloyd in 2009.

Filter by
Sorted by
Tagged with
4 votes
1 answer
112 views

HHL for the pseudoinverse in Qiskit

The HHL algorithm can be modified to compute the pseudoinverse of $A$ as is shown here and here. Is there anyway to do this in Qiskit without coding the entire thing manually?
1 vote
0 answers
49 views

What is the intuition behind achieving Quantum advantage in simulating non-hermitian dynamics using Quantum computer?

There have been several works on simulating ODE for classical systems like here and here. They are quantum techniques to solve the ODE related to classical systems. A generic methodology is: To solve ...
2 votes
2 answers
425 views

Question on qiskit.circuit.library.PiecewiseChebyshev Qiskit circuit library

This question follows the post https://quantumcomputing.stackexchange.com/posts/15070/. I am working on an implementation of HHL algorithm, to do so, I need to map $|\lambda\rangle\mapsto |\arcsin(\...
14 votes
2 answers
2k views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

I have been trying to get my head around the famous(?) paper Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009) (more popularly known as the HHL09 algorithm paper) ...
1 vote
0 answers
116 views

Changing the eigenvalues used in HHL algorithm

For an HHL algorithm implemented exactly as depicted in Figure 2 of this paper by Dutta et. al (https://arxiv.org/abs/1811.01726), how do I go about changing the eigenvalues that they use? Obviously, ...
3 votes
0 answers
96 views

How to achieve the controlled rotation in the HHL algorithm

I'm trying to implement the HHL algorithm generally for any 2 x 2 hermitian matrix, but I'm having trouble with the implementation of the controlled rotation of the ancilla qubit. I've read very many ...
1 vote
1 answer
111 views

How to read the result of this HHL algorithm circuit output?

I have computed the final states of a 1-qubit HHL circuit using initial conditions $$ A|x\rangle = |b\rangle$$ $$\begin{bmatrix} 8 & 6+i \\ 6-i & -1\end{bmatrix} |x\rangle = \begin{bmatrix} \...
1 vote
0 answers
49 views

Can I get valid solution with HHL algorithm even if the QPE is not completely correct?

Can I get the valid solution of linear problem using HHL algorithm even if the QPE is not completely correct? My example is $A=diag(0.5, 0.2, 0.3, 0.6)$, so the solution is $[0.5, 0.2, 0.3, 0.6]$ ...
1 vote
1 answer
33 views

Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

For Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, any idea why "we need oracle access to the nonzero entries of the rows and columns of A ...
4 votes
1 answer
179 views

Optimal dependency of HHL (or any QLSP) algorithm on condition number $\kappa$

This is conserning the optimal dependency on condition number for Quantum linear system problem (QLSP). For solving QLSP, the HHL (algorithm) paper mentions any polylog($\kappa$) quantum algorihm ...
4 votes
0 answers
80 views

What is the total number of qubits required for the Harrow-Hassidim-Lloyd algorithm?

I am fairly new to Quantum Computing and I know a bit of Linear Algebra. I am currently working on the HHL algorithm, I'm having confusion as to how many qubits are actually required in the circuit ...
9 votes
2 answers
428 views

How to recover the normalization constant of the HHL solution

HHL solves the linear equation $Ax=b$ by the quantum state $|x\rangle=A^{-1} |b\rangle$. However, the quantum state $|x\rangle$ is normalized and thus diffs a normalization constant from the solution ...
31 votes
3 answers
3k views

What could be the possible future applications for HHL algorithm?

Note on the vocabulary: the word "hamiltonian" is used in this question to speak about hermitian matrices. The HHL algorithm seems to be an active subject of research in the field of quantum ...
3 votes
2 answers
795 views

Implementation of matrix A in HHL algorithm circuit

In HHL algorithm, how do we implement matrix $A$ (where $A|x\rangle = |b\rangle$) in the circuit?
1 vote
1 answer
1k views

No module named 'qiskit.algorithms.linear_solvers'

I am trying to execute HHL algorithm. I referred to the code from https://quantumpedia.uk/quantum-algorithm-4-hhl-algorithm-for-linear-systems-of-equations-40619daec41d. I tried implementing all the ...
2 votes
2 answers
80 views

How to estimate the negative amplitude of multiple qubits?

The probability of measurement is the square of amplitude. After measurement, how to guess the original amplitude of state?? For example, in linear problem, we would like to know the exact solution, ...
3 votes
1 answer
84 views

Role of qubit registers in HHL circuit

I'm trying to figure out how the HHL algorithm works from reading Dervovic's paper and IBM's tutorial. Dervovic shows the following HHL circuit in Fig 5: whereas IBM uses: I want to clarify the IBM ...
4 votes
1 answer
101 views

Can we efficiently run HHL on a computational basis state without violating the BBBV theorem?

Recall that the linear systems algorithm of Harrow, Hassidim, and Lloyd purports to find a quantum state $|x\rangle$ proportional to $\vec x$, where $\vec x$ satisfies $A\vec x=\vec b$. In addition ...
4 votes
2 answers
1k views

Why was the HHL algorithm removed from the qiskit library?

I am a beginner in quantum computing and I was meddling with HHL algorithm for my class project. Turns out the linear solver algorithms (mainly HHL algorithm) are removed from qiskit library (see ...
4 votes
0 answers
56 views

We take the reciprocal $\lambda^{-1}$ of eigenvalues in HHL - but what's stopping us from raising them to a positive exponent $\lambda^m$?

The HHL algorithm generally can be thought of as diagonalizing our matrix $A$ with the quantum phase estimation algorithm, and applying a specific function $f(\lambda)=\lambda^{-1}$ to the eigenvalues ...
3 votes
1 answer
218 views

Determining the number of qubits to represent the eigenvalues in HHL algorithm?

I am trying to understand how well the HHL algorithm would scale. Therefore my first inquiry is how the number of qubits scale with the size of the problem ie the size of the Matrix A in the linear ...
6 votes
2 answers
885 views

How to draw Qiskit's HHL algorithm as a circuit?

Qiskit Aqua has a module that implements the HHL algorithm: https://qiskit.org/documentation/stable/0.32/stubs/qiskit.aqua.algorithms.HHL.html How does one draw the implemented circuit? *** EDIT *** I'...
3 votes
2 answers
125 views

What is the algebraic result of the matrix exponential operation $e^{i A}|b\rangle$?

The circuit for the HHL algorithm looks as follows: I am uncertain what is the algebraic operation of the matrix exponential $e^{i A}$ on $|b\rangle$? If $$|b\rangle = b_0|0\rangle + b_1|1\rangle$$ ...
7 votes
0 answers
326 views

Solving linear system $Ax=b$ with exponential speed-up via binary optimization?

The main disadvantage of HHL algorithm for solving $A|x\rangle = |b\rangle$ is that exponential speed-up is reached only in case we are interested in value $\langle x|M|x\rangle$, where $M$ is a ...
4 votes
1 answer
75 views

How is $\vec{b}$ loaded in terms of computational basis if we don't know the eigenvectors $\vec{u}_i$ of A?

In HHL, vector $\vec{b}$ is assumed to be decomposed in the eigenbasis {$u_i$}$_{i=1}^n$ of a Hermitian matrix $A$. However, as we do not calculate explicitly the eigenvectors $u_i$ in course of the ...
1 vote
1 answer
76 views

How to construct the matrix in the equation $Ax=b$ in the HHL algorithm?

I am trying to apply the HHL algorithm to a fluid mechanics problem, but I can't figure how to construct the matrix for the equation $ Ax=b $. Specifically, I am trying to reproduce this paper in code ...
1 vote
0 answers
118 views

HHL phase estimation step

I have got an HHL circuit that looks as follows: In the phase estimation part we are trying to find the eigenvalues of the matrix A. But what is the role of the piece of circuit hightlighted below? ...
3 votes
1 answer
117 views

HHL Algorithm: How to compute the signs of the solution vector

Let us assume we have used the HHL algorithm to approximately prepare $|x\rangle$, where $|x\rangle$ is a normalized quantum state corresponding to $\vec{x}$, the solution of a system of linear ...
2 votes
1 answer
139 views

Is a diagonal matrix with one non-zero element a measurable observable?

The HHL algorithm prepares the output state $|x\rangle$. However, we cannot efficiently measure the state directly to get its components. Instead, we can construct an operator $M$ to find $\langle x|M|...
0 votes
1 answer
149 views

hhl algorithm output

I'm trying to implement the HHL algorithm for the matrix and vecor as follows: $ A = \begin{bmatrix} 11 & 5 & -1 & -1 \\ 5 & 11 & 1 & 1 \\ -1 & 1 & 11 & -5 \\ -1 &...
3 votes
2 answers
573 views

Confusion regarding time complexity in the HHL algorithm

In the paper of HHL algorithm (Quantum algorithm for linear systems of equations), the time complexity of simulating $e^{i A t}$ for a hermitian matrix A is $\tilde{O}\left(\log (N) s^{2} t_0\right)$. ...
1 vote
1 answer
156 views

Confusing notation in Block-Encoding

I'm reading the lecture notes from Ronald de Wolf and got confused at the part where it introduces Block encoding, specifically by this notation at page 76: More generally we can define an $a$-qubit ...
2 votes
0 answers
63 views

Simulation of algorithms with QFT on a classical computer

In paper The Quantum Fourier Transform Has Small Entanglement the authors showed that strong entanglement of qubits caused by QFT comes mainly from ordering the qubits. QFT itself prepares only weak ...
1 vote
0 answers
66 views

What is the implementation of AQE on classic?

I want run the HHL, but if the matrices are big, I need to use HHL hybrid, but I was not able to found an implementation or pseudo algorithm of AQE or HHL hybrid. Any solution?
4 votes
1 answer
221 views

HHL algorithm: how running the process $N$ times gives the vector components of the solution?

In the HHL paper the authors have mentioned that if the user wants to get all the components of vector $\vec{x}$, one needs to run the process at least $N$ times, where $N$ is the dimension of the ...
2 votes
0 answers
86 views

What useful information can be efficiently extracted from solutions provided by the HHL-algorithm?

The result of the HHL-algorithm is the (amplitude-encoded) solution vector $|x\rangle$. I was wondering, which useful information could be extracted from this solution without loosing the algorithms ...
1 vote
0 answers
159 views

Amplitude Amplification applied to HHL Algorithm

I’m trying to understand and implement the amplitude amplification algorithm described in the HHL paper. I’m using the cirq implementation of the HHL algorithm as my starting point. I have a couple of ...
0 votes
0 answers
204 views

Implementation of conditional Rotation on ancilla qubit in HHL

In HHL algorithm, after we have encoded the eigenvalues onto the clock register qubits, we apply conditional rotation on ancilla qubit such that it changes from $|0\rangle$ to: To achieve this ...
2 votes
1 answer
136 views

I think I’m having endianness problems replicating the results of this paper?

So I am trying to implement the HHL algorithm depicted in this paper titled 'Quantum Circuit Design for Solving Linear Systems of Equations' by Cao et. al (https://arxiv.org/abs/1110.2232v2), but if I ...
8 votes
2 answers
259 views

What exactly is "matrix sparsity" $s$?

In many sources (like on Page 30 here), I found that the complexity of the original Harrow Hassidim Lloyd is stated as $\mathcal{O}(\log (N) s^2 \kappa^2/\epsilon)$ where $s$ is said to be the "matrix ...
3 votes
1 answer
198 views

Is it possible to compute a matrix inverse for an arbitrary matrix within a subroutine?

Suppose I want solve a lower diagonal linear system of equations given in block form by $ \left( {\begin{array}{cccc} I & 0 & \cdots & 0 &0\\ M & I & \cdots & 0 &...
2 votes
1 answer
226 views

HHL for non power of 2 matrix

I'm trying to see how HHL does on a series of matrices coming from a linear problem I'm interested in. These matrices are always square, real, and symmteric. They are not, however, very often exactly ...
4 votes
1 answer
183 views

Representation of a vector in the HHL algorithm

Reading about the HHL algorithm, which is used to solve the equation $Ax=b$, on Wikipedia, they say to represent $b$ as $|b\rangle=\sum_{i \mathop =1}^N b_i|i\rangle.$ I'm assuming $b$ is a vector ...
2 votes
0 answers
77 views

How to extract solution from HHL statevector on qskit?

I want to extract the HHL solution from the StateVector. I am doing this on a $4\times4$ matrix. For a $2$ by $2$ the solution is available in the StateVector $8$, $9$. However for a $4$ by $4$ matrix ...
1 vote
2 answers
233 views

How to extract a solution to HHL from the full statevector?

I am having a difficult time trying to extract an HHL matrix inversion solution from the full system statevector. I have a 32x32 size matrix A and a 32x1 vector b, and I ran HHL on 13 qubits. HHL ...
8 votes
1 answer
238 views

Why is HHL the popular choice to solve QLSP and not the Childs et al. (2017) algorithm?

The Childs, Kthari, and Rolando (2017) (CKS) algorithm can solve the quantum linear systems problem (QLSP) in $\operatorname{poly}(\log N, \log(1/\epsilon))$ time while the HHL algorithm solves it in $...
1 vote
0 answers
51 views

Plots of the result for the qiskit HHL tutorial

Could anyone make explicit the code which gives the two plots at the end of the HHL tutorial. They show the results of the jobs on a real IBM quantum device.
4 votes
0 answers
125 views

Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?

Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
3 votes
1 answer
142 views

Which observable $M$ provides the Absolute Average of a statevector?

My question should be fairly simple, though I did not find an answer to it here or anywhere else. I have been working on an algorithm which, similarly to the HHL algorithm, provides a state $|x\rangle$...
5 votes
1 answer
492 views

HHL algorithm, How can I get result from register $|b\rangle$?

From the paper A survey on HHL algorithm: From theory to application in quantum machine learning , I use qasm code from here. I try to follow the example in page 7. with Ax = b and the answer x ...