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.

35 questions
Filter by
Sorted by
Tagged with
47 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: <...
68 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, ...
87 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 ...
50 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|\...
73 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 ...
99 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 ...
189 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 ...
56 views

57 views

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. $\... 1answer 271 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 ... 3answers 288 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 ... 1answer 87 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 ... 2answers 112 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 ... 1answer 601 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? ... 1answer 603 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 ... 0answers 262 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 ... 1answer 262 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 ... 1answer 115 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 ... 2answers 784 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 ... 2answers 190 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 ... 1answer 394 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 ... 1answer 382 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 ... 1answer 514 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 ... 0answers 105 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 ... 2answers 732 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, ... 2answers 360 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 ...