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 "...
  • 1,576
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, ...
  • 48.1k
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\}^...
  • 48.1k
8 votes
Accepted

What exactly 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 ...
  • 4,574
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{...
  • 12.1k
7 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 ...
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 ...
  • 2,338
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 ...
  • 12.1k
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 ...
  • 48.1k
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 ...
  • 4,552
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 ...
  • 3,203
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 ...
  • 3,203
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,...
  • 12.8k
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.
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,...
  • 48.1k
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 ...
  • 12.1k
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,...
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 ...
  • 4,552
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 ...
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 ...
  • 48.1k
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 ...
  • 4,552
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 ...
  • 48.1k
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 ...
  • 4,552
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=...
  • 48.1k
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|\...
  • 48.1k
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 ...
  • 48.1k
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 ...
  • 48.1k
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, ...
  • 48.1k
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 ...
  • 12.1k
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 ...
  • 391

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