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.
56
questions
2
votes
1answer
65 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
24 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 ...
2
votes
0answers
31 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
49 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 ...
0
votes
1answer
55 views
Angles of rotation in HHL example
I am trying to implement the 4-qubit example outlined in https://qiskit.org/textbook/ch-applications/hhl_tutorial.html#2.-The-HHL-algorithm (showed in Section 3 of the article). Does anyone know what ...
1
vote
1answer
49 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 ...
1
vote
0answers
35 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
72 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 ...
2
votes
1answer
127 views
Problem with controlled rotation in HHL
In HHL algorithm, for subroutine involving controlled rotation, after applying $R_y(\theta)$, where $\theta=\frac{2C}{\lambda}$ to the ancilla, the state changes to $\sqrt{1-\frac{C^2}{\lambda^2}}|0\...
2
votes
1answer
65 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 ...
4
votes
3answers
301 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
43 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/...
2
votes
1answer
111 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
145 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 ...
6
votes
2answers
313 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
28 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
61 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
72 views
Where will I find necessary math to understand HHL algorithm?
How can we show that HHL algorithm achieves exponential speedup?
1
vote
1answer
47 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
58 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 ...
4
votes
2answers
370 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
81 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
95 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
140 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
101 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><\tau|\...
3
votes
1answer
142 views
Showing that Matrix Inversion is BQP-complete - HHL Algorithm
I am trying to understand an argument that Matrix Inversion is BQP-complete for certain conditions on the matrix. This is explained here on page 39 (this paper is a primer to the HHL algorithm and ...
5
votes
2answers
150 views
Using the HHL algorithm to compute $A |b \rangle$ instead of $A^{-1} |b \rangle$
In the paper "Compiling basic linear algebra subroutines for quantum computers"
here, they discuss (page 2 bottom right) using the HHL algorithm to multiply a vector by a matrix. However, after ...
7
votes
2answers
218 views
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 ...
3
votes
0answers
75 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
86 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
1answer
173 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
393 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
96 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 ...
5
votes
1answer
448 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
290 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 ...
5
votes
1answer
143 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
63 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. $\...
7
votes
1answer
523 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
416 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
96 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
150 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 ...
6
votes
1answer
658 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
756 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
344 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
378 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
148 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 ...
21
votes
2answers
1k 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
267 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
539 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 ...
9
votes
1answer
541 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 ...
