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
3
votes
1answer
42 views

HHL algorithm, How to implement exp(iAt) gates?

From this paper Quantum Circuit Design for Solving Linear Systems of Equations, in figure 4 The paper shows what inside operator $e^{-iAt}$ but didn't shows how to connect the control qubit (register ...
1
vote
0answers
45 views

Why does solving linear systems of equations with HHL return imaginary numbers? [closed]

The textbook shows an example system of linear equations $Ax=b$ with $$ A=\begin{pmatrix} -\frac{1}{3} & 1 \\ 1 & -\frac{1}{3} \end{pmatrix} \,\,\,\, b=\begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$ ...
3
votes
1answer
66 views

Efficient QFT-based QPEA complexity

The HHL algorithm lies on an implementation of the Quantum Phase Estimation algorithm. One popular implementation is based on the Quantum Fourier Transform which can be divided in three steps. Let $U$ ...
4
votes
1answer
51 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 ...
3
votes
1answer
56 views

HHL and choice of observable for calculating the expectation value thereof

The chapter about solving linear systems in the qiskit textbook describes the last (6th) step of the HHL algorithm as follows Apply an observable $M$ to calculate $F(x):=\langle x |M|x\rangle$. How ...
-3
votes
1answer
50 views

Query on the HHL Algorithm in the Qiskit Aqua Library [closed]

This is a question regarding the Qiskit Aqua package. I have been studying HHL algorithm from QISKIT textbook and after understanding the math I finally got to the code part, I am having a hard time ...
7
votes
2answers
69 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 ...
3
votes
1answer
83 views

Gate-level implementation of Eigenvalue-Inversion in HHL

I am trying to understand how does the gate-level implementation of eigenvalue-inversion step in the HHL algorithm works. I am following this reference, where it is stated (Lemma 4) that this can be ...
4
votes
1answer
111 views

How to effectively compute eigenvalue rotation in HHL

In the HHL algorithm, how do you efficiently do the $\lambda-$controlled rotation on the ancillary qubit ? It seems to me after reading around some answers that this can be done in two steps : First, ...
5
votes
0answers
49 views

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

The Childs et al. (2017) 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 $\operatorname{poly}(...
0
votes
0answers
43 views

HHL algorithm Qiskit version

...
1
vote
1answer
91 views

Given a matrix, how do I proceed with the quantum phase estimation algorithm and choose $\theta$?

Given a matrix, say $\begin{bmatrix} 1.5 & 0.5\\ 0.5& 1.5 \end{bmatrix}$, with eigenvalues $1$ and $2$, how do I proceed with the quantum phase estimation algorithm? In particular, how do I ...
0
votes
1answer
81 views

Qiskit HHL algorithm BrokenProcessPool error

I try to run HHL algorithm on qasm_simulator. I took the example from here. I try to solve 8x8 random matrix and adjust some parameters in create_eigs. ...
4
votes
0answers
33 views

In the HHL algorithm, how large should the eigenvalue estimation register be?

In the HHL algorithm, we need to estimate the eigenvalues of a matrix $A$. The result is stored in a register with $l$ qubits. Let $T = 2^l$. $T$ cannot be too small, otherwise the result would have a ...
2
votes
0answers
61 views

HHL example solution on Qiskit

In the example on the Qiskit page (https://qiskit.org/textbook/ch-applications/hhl_tutorial.html#A.-Some-mathematical-background) section 3 for the HHL algorithm the author is trying to solve the ...
1
vote
1answer
59 views

How to increase matrix size and getting high fidelity for HHL algorithm in Qiskit?

I have followed an example that Qiskit provides here. I tried to increase the matrix size to 16x16 and change num_ancillae and ...
1
vote
0answers
68 views

Implementing the HHL algorithm with negative eigenvalues (Cirq)

How do I implement the HHL with negative eigenvalues? This paper (https://arxiv.org/abs/1803.01486) says that: what if $\lambda<0$? This problem actually does not hard to solve, since we can ...
2
votes
1answer
143 views

Error when running HHL algorithm in Qiskit

I tried to solve a simple system of two simultaneous linear equations in with HHL algorithm in Qiskit. In particular the system is $Ax=b$, where $$ A = \begin{pmatrix} 1.5 & 0.5 \\ 0.5 & 1.5 \...
1
vote
1answer
76 views

How to optimize my HHL algorithm on qiskit?

I am following this HHL tutorial to solve the $Ax=b$ problem and have been using the general (inefficient) approach with the BasicAer simulator that they describe in section 4a. I would now like to ...
1
vote
1answer
51 views

How can I use the quantum volume to design the scale of my experiment?

I am designing an experiment which involves solving a linear system of equations of the form $Ax=b$. To do this, I am using the HHL algorithm on the IBMQ system. My experiment is scalable such that ...
3
votes
1answer
70 views

Is it required to input full matrix when using Qiskit HHL algorithm for sparse matrices?

I am working with a very sparse matrix and it seems inefficient to load the full matrix as input into the Qiskit HHL algorithm. Is it possible to input only the non-zero elements, instead ? I am ...
1
vote
0answers
55 views

Help Understanding Line in Source Code

In Qiskit's implementation of the HHL algorithm, they have the following line at the end of their code that allows them to compute the global phase we need to add on to the solution. ...
8
votes
0answers
146 views

Is HHL still BQP-complete when the matrix entries are only in {0,1}?

I'm studying BQP-completeness proofs of a number of interesting problems of Janzing and Wocjan, and Wocjan and Zhang. Janzing and Wocjan show that estimating entries of matrix powers $(A^m)_{ij}$ with ...
3
votes
0answers
47 views

Comparison of matrix inversion algorithms

Since 2009, many matrix inversion algorithms have appeared. Is there somewhere a table, or recently released overview, comparing the speed of matrix inversion algorithms, like done in this table taken ...
1
vote
0answers
26 views

Using matrix inversion and summation together. How to compute $(A+B^{-1})^{-1}|x\rangle$

I need to compute $(A+B^{-1})^{-1}|x\rangle$, where A and B is hermitian for simplicity. I read out about matrix inversion algorithms (HHL, QSVE,...), and algorithms of summing up of matrices(LCU, Lie–...
3
votes
1answer
122 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
0answers
51 views

Adding Quantum State Tomography Step in Cirq HHL Algorithm Implementation

Over the past month, I have been learning about the HHL algorithm and am interested in extending the implementation provided here (https://github.com/quantumlib/Cirq/blob/master/examples/hhl.py) to ...
4
votes
1answer
96 views

How do I optimize HHL algorithm in Qiskit?

How do I optimize HHL algorithm in Qiskit? I tried to follow this tutorial on HHL in Qiskit. My project requires solving a very specific type of linear equations $Ax=b$ like the one below. ...
2
votes
1answer
98 views

The maximum depth possible on quantum computers

I hope you don't mind me having two questions. Firstly, I was running a Qiskit HHL simulation on a 12x12 matrix and a 12x1 vector, leading to a 16x16 matrix after expansion, and it resulted in a ...
2
votes
1answer
91 views

Angles of rotation in HHL example

I am trying to implement the 4-qubit example outlined in showed in section 3 of the qiskit tutorial on the HHL algorithm. Does anyone know what are the 2 angles that the ...
1
vote
1answer
64 views

In the rotation part of HHL algorithm, how do you decompose $R$ in terms of universal gates?

In this paper, there is a diagram explaining how HHL works, which I attached below: My question is, for the rotation part, how do you write $R$ as a combination of universal set of gates without ...
5
votes
1answer
127 views

New Hybrid-HHL algorithm vs VQLS

A team of researchers has realized hybrid quantum algorithm for solving a linear system of equations with exponential speedup that utilizes quantum phase estimation, the algorithm demonstrates quantum ...
2
votes
1answer
120 views

Problem with HHL algorithm on Qiskit

I try to run HHL algorithm on quantum computer in Qiskit Notebooks on the site. I take it from here https://qiskit.org/textbook/ch-applications/hhl_tutorial.html but it doesn't work. The error message ...
3
votes
2answers
330 views

Problem with controlled rotation in HHL

In HHL algorithm, for subroutine involving controlled rotation, after applying $R_y(\theta)$, where $\theta=2\sin^{-1}\left(\frac{C}{\lambda}\right)$ to the ancilla, the state changes to $\sqrt{1-\...
2
votes
1answer
145 views

Quantum circuit to get expectation values of Pauli matrices, given state $|\psi\rangle$

I'm trying to solve 2 linear equations with the help of HHL algorithm. I've taken $A=\begin{pmatrix} 1.5 & 0.5\\ 0.5 & 1.5\\ \end{pmatrix}$ and $b=\begin{pmatrix} 1\\ 0\\ \end{pmatrix}$. I've ...
7
votes
3answers
523 views

Quantum circuit to implement matrix exponential

I want to build a circuit which will implement $e^{iAt}$, where $ A= \begin{pmatrix} 1.5 & 0.5\\ 0.5 & 1.5\\ \end{pmatrix} $ and $t= \pi/2 $. We see that $A$ can be written as, $A=1.5I+0.5X$. ...
1
vote
0answers
67 views

Explanation of HHL Cirq implementation [closed]

Can someone help me in understanding the program on the link given below? I would really appreciate if someone could give a detailed explanation ... https://github.com/quantumlib/Cirq/blob/master/...
3
votes
1answer
228 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?
3
votes
5answers
192 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home-made 2 qubits device. I am wondering if there are any other ...
9
votes
3answers
556 views

Does the quantum Fourier transform have many applications beyond period finding?

(This is a somewhat soft question.) The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster. The QFT is famously at the core of Shor's ...
1
vote
0answers
30 views

How to prepare the three-dimensional register S in HHL?

$\newcommand{\ket}[1]{\left|#1\right>}$ In the original HHL paper, in step 4 of the $U_{\text{invert}}$ subroutine (Appendix A.1), it says to adjoin a three-dimensional register S in the state $\...
2
votes
1answer
78 views

How to encode eigenvalues of matrix $A$ in solving $A\vec{x} = \vec{b}$ using the HHL Algorithm

I am trying to implement multiple parallel subroutines of HHL algorithm, each working on a different set of matrix $A$ (when solving for $x$, in $A\vec{x} = \vec{b}$), to find the expectation values ...
1
vote
1answer
87 views

Where will I find necessary math to understand HHL algorithm?

How can we show that HHL algorithm achieves exponential speedup?
1
vote
1answer
81 views

HHL Algorithm: Relation between Eigenvalues and condition number

I have been going through the original HHL paper (2009), and I see that they call a linear system of equations "well behaved" / "well-conditioned", if $$ |\lambda| \in \left[\frac{1}{\kappa}, 1\right]$...
1
vote
0answers
72 views

Exponentiating Hermitian Matrix for use in QPE/HHL

I am currently trying to understand HHL by implementing a very inefficient Qiskit simulation script that performs HHL on an arbitrary hermitian matrix $A$ and a vector $b$. Because I am currently ...
6
votes
2answers
557 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/_modules/qiskit/aqua/algorithms/single_sample/hhl/hhl.html How does one draw the implemented circuit? * ...
2
votes
0answers
107 views

Running HHL tutorial on real backend

I tried to follow the HHL tutorial. Since the 8x8 problem is not realistically simulable (I stopped after a few minutes), I tried to make it run on another backend, starting on the easiest example: <...
3
votes
1answer
116 views

Matrix Inversion is BQP-complete proof in HHL and the probability of measuring $T+1 \leq t \leq 2T$

I am continuing to try and fully understand the argument why Matrix inversion is BQP-complete according to the proof given in the HHL paper here, and I have hit another snag. In this question here, ...
3
votes
1answer
187 views

Understanding the filter functions in the HHL algorithm

I am continuing my studies of the HHL algorithm here. In applying the controlled rotation conditioned on the eigenvalues of the matrix, the authors use so called filter functions in order to filter ...
3
votes
1answer
141 views

Apply the conditional Hamiltonian evolution (HHL)

I have a problem with the conditional Hamiltonian. In the original article on HHL (p.3) they wrote that applying the conditional Hamiltonian correspond to: $$ \sum_{\tau=0}^{T-1}|\tau\rangle\langle\...