Solving Linear Equations via VQE (Variational Quantum Eigensolver)

In this article, we introduce how to solve simultaneous linear equations with NISQ, which is the abbreviation for Noisy Intermediate Scaled Quantum, from Xu et al. [1].

We consider the following linear equation:
\begin{align*}
Ax=b, \tag{1}
\end{align*}
where an invertible matrix $A\in \mathbb{C}^{n\times n}$ , a vector $b\in\mathbb{C}^n$ , and an unknown variable $x\in\mathbb{C}^n$ .

For calculation on quantum computers, let $n$ be a power of 2 and assume $\|b\|=1$ , where $\|\cdot\|$ represents the norm of $\mathbb{C}^n$ induced by the usual inner product $\langle\cdot,\cdot\rangle$ of $\mathbb{C}^n$ .
We note that $\langle\cdot,\cdot\rangle$ is antilinear with respect to the right side in our notation.

We now put
\begin{align*}
H = A^*(I - b\hat{\otimes}b)A,
\end{align*}
where $\hat{\otimes}$ represents the Schatten form; that is, for $x,y\in\mathbb{C}^n$ ,
\begin{align*}
x\hat{\otimes}y\colon \mathbb{C}^n\ni z\mapsto \langle z,y\rangle x \in \mathbb{C}^n,
\end{align*}
which corresponds to the "ket-bra" $|x\rangle\langle y|$ in the quantum mechanics/information.

Proposition. $H$ defined as above is Hermitian and positive semidefinite, and has a minimal eigenvalue 0. Furthermore, the solution to equation (1) is an eigenvector corresponding to eigenvalue 0 of $H$ .

Proof. It is obvious that $H$ is Hermitian. We see the remaining assertion since $I-b\hat{\otimes}b$ is a projection to the orthogonal complement of the subspace spanned by $b$ . $\Box$

Let $e\in \mathbb{C}^n$ be an initial quantum state and $U(\theta)\in\mathbb{C}^{n\times n}$ , $\theta\in\mathbb{R}^d$ be a parametrized unitary operator called "ansatz" and denote $u(\theta)=U(\theta)e$ .
Then, by minimizing
\begin{align*}
L(\theta):= \langle Hu(\theta),u(\theta)\rangle
\end{align*}
with respect to $\theta$ , we get an approximated solution to (1) on a quantum computer.