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.

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12 votes
0 answers
270 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 ...
Mark Spinelli's user avatar
7 votes
0 answers
316 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 ...
Martin Vesely's user avatar
6 votes
0 answers
123 views

What is the largest linear system of equations solved using HHL experimentally?

Can someone tell what is the largest system of equations solved using HHL algorithm experimentally? I know the $8$ x $8$ system has been solved experimentally. Has someone gone beyond this to solve $...
quankid's user avatar
  • 303
6 votes
0 answers
148 views

How exactly is the stated composite state of the two registers being produced using the $R_{zz}$ controlled rotations?

This is a sequel to How are two different registers being used as "control"? I found the following quantum circuit given in Fig 5 (page 6) of the same paper i.e. Quantum Circuit Design for ...
Sanchayan Dutta's user avatar
5 votes
0 answers
78 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 ...
Subhradeep Sarkar's user avatar
5 votes
0 answers
151 views

How can I express controlled unitary operation in QPE of this implementation of HHL?

I have found this implementation of HHL, and I don't understand why the controlled unitary operation is expressed in the form of $\exp(i t_0 A/2)$ and $\exp(i t_0 A/4)$. The rotation of $\pi$ and $\...
Macalcubo's user avatar
  • 133
5 votes
0 answers
127 views

Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?

The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3: I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
Sanchayan Dutta's user avatar
5 votes
0 answers
556 views

Error: Simulation of "Quantum algorithm for linear systems of equations" for $4\times 4$ systems on Quirk (without SWAP) - Global phase

Following @DaftWullie's answer I tried to simulate the circuit given in Fig. 4 of the paper (arXiv pre-print): Quantum circuit design for solving linear systems of equations (Cao et al, 2012), on ...
Sanchayan Dutta's user avatar
4 votes
0 answers
53 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 ...
Mark Spinelli's user avatar
4 votes
1 answer
106 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?
bonsh's user avatar
  • 41
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?
Mark234's user avatar
  • 51
4 votes
0 answers
90 views

What are the correct eigenvalues to use in controlled rotation in HHL?

I'm studying the HHL algorithm from the qiskit textbook, but I don't understand what $\lambda$ we have to use. If my matrix $A$ has eigenvalues that can be written in a binary representation, then, ...
Simona99's user avatar
  • 180
4 votes
0 answers
66 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 ...
user2249675's user avatar
4 votes
0 answers
249 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 ...
Iskander's user avatar
4 votes
0 answers
153 views

Is HHL executed in a single run? If yes, how do they carry out controlled rotation without knowing eigenvalues?

Even after reading several papers and almost all HHL related questions and answers here on Quantum Computing Stack Exchange, one thing is yet not clear. In several papers, for illustrating HHL they ...
user avatar
4 votes
0 answers
162 views

What are applications of HHL's "simple example" to determine similar stable states of different quantum processes?

The HHL paper "Quantum algorithm for linear systems of equations" [link] initially describes a "simple example" to illustrate the potential power of their algorithm. They state: Consider a ...
Mark Spinelli's user avatar
3 votes
0 answers
81 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 ...
brett037's user avatar
2 votes
0 answers
59 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 ...
Martin Vesely's user avatar
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 ...
mr.creme's user avatar
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 ...
Arnav Singh's user avatar
2 votes
0 answers
69 views

Difference in HLL applications

I am new to Qiskit and I have seen two types of simple 2X2 $Ax=b$ system solutions. I am wondering what the difference is exactly. They both occur on a simulator backend, but the first gives me a ...
Corey's user avatar
  • 127
2 votes
2 answers
407 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(\...
SRichoux's user avatar
  • 319
2 votes
0 answers
201 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 ...
Deliverer's user avatar
2 votes
0 answers
213 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: <...
Serwyn's user avatar
  • 116
1 vote
0 answers
45 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 ...
Manish Kumar's user avatar
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]$ ...
Nyyni's user avatar
  • 33
1 vote
0 answers
107 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? ...
Марина Лисниченко's user avatar
1 vote
0 answers
157 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 ...
Markivaira's user avatar
1 vote
0 answers
115 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, ...
ctimms137's user avatar
1 vote
0 answers
60 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?
João Eudes Lima's user avatar
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.
Holger's user avatar
  • 161
1 vote
0 answers
196 views

In HHL algorithm, how to find the angle of rotation of ancilla qubits?

In HHL algorithm, after the quantum phase estimation, what is the angle of rotation i.e. what is the value of $\theta$ in R$_y$($\theta$) that is used in rotating ancilla qubit? How to find this angle ...
quankid's user avatar
  • 303
1 vote
0 answers
339 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 ...
user3886914's user avatar
1 vote
0 answers
44 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–...
Alexander's user avatar
1 vote
0 answers
120 views

Adding Quantum State Tomography Step to HHL Algorithm (Cirq)

Over the past month, I have been learning about the HHL algorithm and am interested in extending the Cirq implementation to include the quantum state tomography step to extract the amplitudes or ...
quantum_novice's user avatar
1 vote
0 answers
60 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 $\...
andrew123's user avatar
1 vote
0 answers
162 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 ...
Malcolm Regan's user avatar
0 votes
0 answers
186 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 ...
saliha majeed's user avatar