10 votes

What could be the possible future applications for HHL algorithm?

A couple years ago it was shown in Quantum algorithms and the finite element method by Montanaro and Pallister that the HHL algorithm could be applied to the Finite Element Method (FEM) which is a "...
user avatar
  • 1,556
9 votes
Accepted

Quantum phase estimation and HHL algorithm - knowledge of eigenvalues required?

You should know a bound on the eigenvalues (both upper and lower). As you say, you can then normalise $A$ by rescaling $t$. Indeed, you should do this to get the most accurate estimate possible, ...
user avatar
  • 46.2k
9 votes
Accepted

Efficiently performing controlled rotations in HHL

The setting is that you've got some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ on a register, you introduce an ancilla in state $|0\rangle$, and you want to create some state $$ \sum_{x\in\{0,1\}^...
user avatar
  • 46.2k
8 votes
Accepted

What exacty is "matrix sparsity" $s$?

You have the definitions in your paper you link page 12. Simply said, it is a matrix with many 0s. As an example take N = 16, and the polynomial function is just a simple function like 1.5*X, then ...
user avatar
  • 4,554
7 votes
Accepted

HHL algorithm -- why isn't the required knowledge on eigenspectrum a major drawback?

The restriction on the eigenvalues is usually given in the form of a condition number. This is the $\kappa$ that you see in all the runtimes in your table. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{...
user avatar
  • 11.9k
7 votes

Quantum circuit to implement matrix exponential

There is actually a nice way to do this in Qiskit, since it has decompositions for single-qubit unitaries built in. The QuantumCircuit.squ method takes a unitary ...
user avatar
  • 2,203
6 votes
Accepted

Solving linear systems represented by NxN matrices with N not power of 2

This is indeed a correct way to solve linear systems with dimension not equal to a power of 2. Solve the smallest possible system of dimension 2$^n$ that contains the system you want to solve, and pad ...
user avatar
  • 11.9k
6 votes
Accepted

Practical implementation of Hamiltonian Evolution

I don't know why/how the authors of that paper do what they do. However, here's how I'd go about it for this special case (and it is a very special case): You can write the Hamiltonian as a Pauli ...
user avatar
  • 46.2k
6 votes
Accepted

Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?

1. Definitions Names and symbols used in this answer follow the ones defined in Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018). A ...
user avatar
  • 4,467
6 votes
Accepted

How to draw Qiskit's HHL algorithm as a circuit?

You can draw the circuit using construct_circuit().draw(). In the tutorial you are talking about, if you scroll down to the 4x4 randomly generated section that ...
user avatar
  • 3,153
6 votes
Accepted

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

Given that the QFT is exponentially faster than the FFT, The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when ...
user avatar
6 votes

Problem with HHL algorithm on Qiskit

These aren't error messages, they are just outputs. The first message simply means it will be using your credentials for the session. This has probably popped up because you have run ...
user avatar
  • 3,153
6 votes
Accepted

Quantum Circuit for $e^{iAt}$ Hamiltonian Simulation in HHL algorithm

As requested through the comment by the OP. Given a Hermitian matrix $H$, we can always write it as linear combination of Pauli strings. That is, $$ H = \sum_i \alpha_i P_i \hspace{1 cm} P_i \in \{I,...
user avatar
  • 12.3k
6 votes

Source code for a Qiskit algorithm: HHL Algorithm

Qiskit is an open source. Specifically for HHL, see https://github.com/Qiskit/qiskit-aqua/blob/master/qiskit/aqua/algorithms/linear_solvers/hhl.py.
user avatar
5 votes
Accepted

Clarification of the "Calculations" section of the (HHL09) paper

I know that $b$ can be decomposed mathematically as $b= c_1u_1 + > \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis. Why only consider the effect on $|u_j \rangle$? As you say,...
user avatar
  • 46.2k
5 votes

How to speed up the matrix multiplication steps in multi-linear regression?

You were correct to seek a new quantum algorithm for this rather than just using HHL to do step 3. There are separate quantum algorithms to do regressions: Quantum Algorithm for Data Fitting (same ...
user avatar
  • 11.9k
5 votes
Accepted

HHL algorithm -- controlled-by-eigenvalues rotations

If $\tilde{\lambda_{k}} < C$, the controlled rotation becomes non-physical since you have coeffecient greater than 1 on your $|1\rangle$ state. As a result $C < \lambda_{min}$ is a safer choice,...
user avatar
5 votes
Accepted

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

It depends on the papers but I saw 2 approaches: In most of the papers I read about the HHL algorithm and its implementation, the Hamiltonian evolution time $t$ is taken such that this factor ...
user avatar
  • 4,467
4 votes
Accepted

HHL algorithm -- problem with the outcome of postselection

Your intuition is correct for a single qubit, in that if I measure $$\alpha\vert 0 \rangle + \beta\vert 1 \rangle$$ I would get either $\vert 0 \rangle$ or $\vert 1 \rangle$. But since the qubits are ...
user avatar
4 votes

Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?

$\newcommand{\bra}[1]{\left\langle#1\right|}\newcommand{\ket}[1]{\left|#1\right\rangle}\newcommand{\proj}[1]{|#1\rangle\langle#1|}\newcommand{\half}{\frac12}$In answer to your first question, I wrote ...
user avatar
  • 46.2k
4 votes
Accepted

Controlled unitary from the HHL algorithm – practical implementation using Qiskit

Disclaimer: I'm the one that wrote the code of the 4x4 HHL. Controlling a quantum gate $U$ can be achieved by controlling each of the $U_i$ gates that are composing $U$. For the specific example you ...
user avatar
  • 4,467
4 votes
Accepted

What does $||A|| = 1$ mean in the definition of QLSP?

Certainly it is meant as the largest eigenvalue. I have no idea why the linked review paper uses the determinant. I don't see anywhere that they use that property (from an admittedly brief skim). I ...
user avatar
  • 46.2k
4 votes
Accepted

Using the HHL algorithm to compute $A |b \rangle$ instead of $A^{-1} |b \rangle$

Note: the graphics have been generated with the LaTeX code available here. Credits to @Niel de Beaudrap. Yes it is possible! The HHL algorithm can be schematically depicted as Let's split down the ...
user avatar
  • 4,467
4 votes
Accepted

Showing that Matrix Inversion is BQP-complete - HHL Algorithm

Define the states $$ |\psi_t\rangle=\left\{\begin{array}{cc} |t\rangle\otimes(U_{t-1}U_{t-2}\ldots U_1|\psi\rangle) & t=1,2,\ldots T \\ |t\rangle\otimes(U_{T}U_{T-1}\ldots U_1|\psi\rangle) & t=...
user avatar
  • 46.2k
4 votes
Accepted

Apply the conditional Hamiltonian evolution (HHL)

Be careful! They don't apply $e^{i\pi A}$ and $e^{i\pi A/2}$. They apply $$ |0\rangle\langle 0|\otimes I\otimes I+|1\rangle\langle 1| \otimes I\otimes e^{i\pi A} $$ and $$ I\otimes |0\rangle\langle 0|\...
user avatar
  • 46.2k
4 votes

Quantum circuit to implement matrix exponential

You want to implement $$ e^{i3\pi/4}e^{iX\pi/4}. $$ I would rewrite this as $$ e^{i3\pi/4}He^{iZ\pi/4}H. $$ This is the same as $$ -HS^\dagger H $$ in standard gate terminology. If you're only ...
user avatar
  • 46.2k
4 votes
Accepted

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

To find the expectation value of a given Pauli matrix, you just measure in the basis defined by the Pauli matrix. For example, to evaluate the expectation value of the $X$ matrix, you find the basis ...
user avatar
  • 46.2k
4 votes

Problem with controlled rotation in HHL

You don't know the eigenvalues a priori, but you have performed phase estimation, and have (at least a good approximation to) your eigenvalues recorded on a register. If you control off that register, ...
user avatar
  • 46.2k
4 votes

New Hybrid-HHL algorithm vs VQLS

By a large margin, I would recommend VQLS rather than H-HHL. VQLS is significantly more well-tested, is a more significant leap from the previous state-of-the-art for hybrid quantum/classical linear ...
user avatar
  • 11.9k
4 votes
Accepted

How to effectively compute eigenvalue rotation in HHL

There is a new approach that will be merged soon in qiskit terra (here for the PR) that uses polynomial approximation to compute $\arcsin(C/\lambda)$, and asymptotically this would be the efficient ...
user avatar
  • 391

Only top scored, non community-wiki answers of a minimum length are eligible