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.
29 questions
6
votes
2answers
128 views
+100
Clarification of the “Calculations” section of the (HHL09) paper
I am reading this paper entitled "Quantum algorithm for linear systems of equations" and am trying to understand a portion of the algorithm described on page 2 and in more detail in the appendix ...
2
votes
0answers
38 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 $\...
3
votes
0answers
44 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 ...
4
votes
0answers
85 views
Does HHL implementation require a priori eigendecomposition?
I am interested in HHL algorithm and despite all the problems related to current technologies, I am trying to understand how it has to be implemented.
I have seen from these two available circuits (...
4
votes
1answer
114 views
Controlled unitary from the HHL algorithm – practical implementation using Qiskit
I have a question about the implementation of the controlled unitary $e^{iAt}$, from the paper Demonstration of a Quantum Circuit Design Methodology for Multiple Regression, using the Qiskit framework....
3
votes
0answers
52 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 ...
4
votes
1answer
169 views
Quantum algorithm for linear system of equations (HHL) - Final Step: How can I find my vector of solution $|x\rangle$?
I'm working on solving a linear system with the quantum algorithm HHL. I don't understand how I can recover my vector $|x\rangle$ of real solution of the system starting from the states measured with ...
3
votes
2answers
164 views
Implementing gate with two parameters using Qiskit in Python
I am trying to implement the HHL algorithm (for solving $Ax=b$). I am assuming $A$ to be unitary and Hermitian so that I can find the Hamiltonian simulation for it easily.
For any $A$ to be Hermitian ...
4
votes
1answer
107 views
How to find parameters for circuit decomposition of Hamiltonian simulation of any matrix $A$?
In version 2 of the paper Quantum Circuit Design for Solving Linear Systems of Equations by Cao et al., they have given circuit decomposition for $e^{iA\frac{2\pi}{16}}$, given a particular $A_{4\...
4
votes
0answers
55 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. $\...
6
votes
1answer
178 views
Efficiently performing controlled rotations in HHL
This question builds off of this question.
In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know ...
5
votes
3answers
265 views
How to speed up the matrix multiplication steps in multi-linear regression?
Context and Motivation:
As discussed here, in multilinear regression, we can express the linear system as $AX = b$. This leads to $A^TA \hat{X} = A^T b$. From here, the estimated value of $X$ is ...
4
votes
1answer
81 views
What does $||A|| = 1$ mean in the definition of QLSP?
In their 2017 paper, Childs et al. gave the definition of QLSP beginning with : "Let $A$ be an $N\times N$ Hermitian matrix with known condition numbers $\kappa$, $||A|| = 1$ and at most $d$ non-zero ...
7
votes
2answers
105 views
What exacty 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 ...
5
votes
1answer
594 views
Solving linear systems represented by NxN matrices with N not power of 2
As far as I have seen, when it comes to solving linear systems of equations it is assumed to have a matrix with a number of rows and columns equal to a power of two, but what if it is not the case?
...
8
votes
1answer
527 views
Practical implementation of Hamiltonian Evolution
Following from this question, I tried to look at the cited article in order to simulate and solve that same problem... without success. Mainly, I still fail to understand how the authors managed to ...
5
votes
0answers
239 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 ...
7
votes
1answer
223 views
SWAP gate(s) in the $R(\lambda^{-1})$ step of the HHL circuit for $4\times 4$ systems
Context:
On the 5th page of the paper Quantum circuit design for solving linear systems of equations (Cao et al, 2012) there's this circuit:
Schematic:
A brief schematic of what's actually ...
5
votes
1answer
84 views
Why does the quantum linear inversion algorithm allow to implement $e^{-ig(\rho)}$ efficiently using multiple copies of $\rho$?
In (Lloyd et al. 2013), the authors write (beginning of page 3) that the quantum matrix inversion techniques presented by some of the same authors in (Harrow et al. 2008) allow to efficiently ...
13
votes
2answers
573 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 ...
6
votes
2answers
159 views
HHL algorithm — problem with the outcome of postselection
See edit at the end of the question
All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009).
HHL algorithm ...
4
votes
1answer
347 views
HHL algorithm — controlled-by-eigenvalues rotations
All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009).
The question I have is about the step where they apply ...
8
votes
1answer
330 views
HHL algorithm — why isn't the required knowledge on eigenspectrum a major drawback?
This question is a continuation of Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?.
In the question linked above, I asked about the necessity for HHL to have ...
10
votes
1answer
408 views
Quantum phase estimation and HHL algorithm - knowledge of eigenvalues required?
The quantum phase estimation algorithm (QPE) computes an approximation of the eigenvalue associated to a given eigenvector of a quantum gate $U$.
Formally, let $\left|\psi\right>$ be an ...
5
votes
0answers
97 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 ...
8
votes
2answers
567 views
Quantum algorithm for linear systems of equations (HHL09): Step 2 - Preparation of the initial states $|\Psi_0\rangle$ and $|b\rangle$
This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?
In the paper: Quantum algorithm for linear systems of equations (Harrow, ...
8
votes
2answers
308 views
Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?
This is a sequel to Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm and Quantum algorithm for linear systems of ...
8
votes
1answer
246 views
Quantum algorithm for linear systems of equations (HHL09): Step 1 - Number of qubits needed
This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm
Questions (contd.):
Part 2: I'm not exactly ...
10
votes
2answers
714 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) ...
