Algorithms
Algorithm

Variational Quantum Eigensolver (VQE)

VQE is an algorithm for finding an (approximate) ground state of a given Hamiltonian $H$ by NISQ devices. It is based on the variational method of quantum mechanics and divides the task of finding the ground state into ones performed by classical computers and quantum computers.

The algorithm works as follows:

  1. Prepare an initial quantum state $|0\rangle$ on quantum computers.
  2. Generate an ansatz quantum state $|\psi(\vec{\theta})\rangle$ by applying a quantum circuit $U(\vec{\theta})$ parametrize by (classical) parameters $\vec{\theta}$, $|\psi(\vec{\theta})\rangle = U(\vec{\theta}) |0\rangle$.
  3. The expectation value of the Hamiltonian $H$ is measured on quantum computers, which is denoted as $E(\vec{\theta}) = \langle \psi(\vec{\theta})| H|\psi(\vec{\theta})\rangle$.
  4. Update the parameters $\vec{\theta}$ to get $E(\vec{\theta})$ smaller by using a classical optimizing algorithm.
  5. repeat the steps 1~4 until convergence.

If a minimum of $E(\vec{\theta})$ is reached at $\vec{\theta}'$, $|\psi(\vec{\theta}')\rangle$ is close to the ground state of $H$ and $E(\vec{\theta}')$ is close to the ground state energy (see variational method of quantum mechanics at Wikipedia). $U(\vec{\theta})$ determines the accuracy of the approximate ground state by VQE.

Reference

Subspace-Search VQE (SS-VQE)

SS-VQE is an extension of VQE for finding excited states of a given Hamiltonian $H$.

  1. Prepare a set of $k$ mutually orthogonal quantum states, $|\varphi_0 \rangle, ..., |\varphi_{k-1}\rangle$.
  2. For each $i$, generate $|\psi_{i}(\vec{\theta})\rangle = U(\vec{\theta})|\varphi_i\rangle$ and measure $ \langle\psi_{i}(\vec{\theta})|H|\psi_{i}(\vec{\theta})\rangle$ on quantum computers.
  3. sum up results of step 2 with some weights, $w_0 > \ldots > w_{k-1} > 0$, and compute a cost function $L(\vec{\theta})=\sum_{i}w_{i}\langle\psi_{i}(\vec{\theta})|H|\psi_{i}(\vec{\theta})\rangle$ on classical computers.
  4. Update the parameters $\vec{\theta}$ to make the cost function $L(\vec{\theta})$ smaller.
  5. repeat the steps 1~4 until convergence.

It can be shown that when a minimum of the cost function $L(\vec{\theta})$ is reached at $\vec{\theta}'$, approximate eigenvectors and eigenstates of $H$ are obtained as $|\psi_0(\vec{\theta}')\rangle, ..., |\psi_{k-1}(\vec{\theta}')\rangle$ and $\langle\psi_0(\vec{\theta}')|H|\psi_0(\vec{\theta}')\rangle, ..., \langle\psi_{k-1}(\vec{\theta}')|H|\psi_{k-1}(\vec{\theta}')\rangle $.

Reference

Quantum Subspace Expansion (QSE)

QSE is an algorithm for finding excited states of a given Hamiltonian $H$. It resembles the configuration interaction method in quantum chemistry.

  1. Determine a set of excitation operators $E_1,..., E_M$ and a reference (approximate) ground state $|\psi_{GS}\rangle$. Single excitations of electrons, $ c_j^\dagger c_l (j,l=0,1,...)$, are one of the common choices of the excitation operators. For notational convenience, we add $E_0= I$ (identity operator) to the set of excitation operators. Note that $E_0|\psi_{GS}\rangle = |\psi_{GS}\rangle $.
  2. Prepare the approximate ground state $|\psi_{GS}\rangle$, obtained by the VQE algorithm (or other methods), on quantum computers.
  3. Measure quantities $ h_{ij} = \langle \psi_{GS}| E_i^\dagger H E_j |\psi_{GS}\rangle$ and $ S_{ij} = \langle \psi_{GS}| E_i^\dagger E_j |\psi_{GS}\rangle$ on quantum computers ($i,j=0,...,M$).
  4. Diagonalize the Hamiltonian within the subspace spanned by $E_0|\psi_{GS}\rangle, ..., E_M|\psi_{GS}\rangle$. Namely, solve a generalized eigenvalue problem within the subspace, $hC=SCE'$, where $C$ is the coefficient vector for (approximate) eigenvectors and $E'$ is a diagonal matrix whose diagonal elements are (approximate) eigenvalues of $H$.

We note that the QSE also plays a role of mitigating noise errors inevitable in NISQ devices (see reference below).

Reference

  • "Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states", J. R. McClean et al., Phys. Rev. A 95, 042308 (2017).

Multistate, Contracted VQE (MC-VQE)

MC-VQE is an extension of VQE to calculate excited states of a given Hamiltonian $H$. It is similar to a simple version of the SSVQE algorithm.

  1. Calculate configuration interaction singles (CIS) states $|CIS\rangle_i $ on classical computer and compute a quantum circuit to prepare them on quantum computers, $|CIS\rangle_i = U_i|0\rangle$ ($i=0,1,...$).
  2. For each $i$, generate $|\psi_{i}(\vec{\theta})\rangle = U(\vec{\theta})|CIS_i\rangle=U(\vec{\theta})U_i|0\rangle$ and measure $ \langle\psi_{i}(\vec{\theta})|H|\psi_{i}(\vec{\theta})\rangle$ on quantum computers.
  3. Sum up results of step 2 and compute a cost function $L(\vec{\theta})=\sum_i \langle\psi_i(\vec{\theta})|H|\psi_i(\vec{\theta})\rangle$ on classical computers.
  4. Update the parameters $\vec{\theta}$ to make the cost function $L(\vec{\theta})$ smaller.
  5. Repeat the steps 1~4 until convergence.
  6. After convergence of $L(\vec{\theta})$ at $\vec{\theta}'$, diagonalize the Hamiltonian $H$ within the subspace of $|\psi_i(\vec{\theta}')\rangle : (i=0,1,...)$ in the same way as the QSE algorithm above.

Reference

VQE for excited states by including overlaps to cost function

These two papers below propose an algorithm to obtain excited states of a given Hamiltonian $H$ sequentially by including the overlap amplitudes between the ansatz state $|\psi(\vec{\theta})\rangle$ and previously-found eigenstates to the cost function of VQE.

Reference