  The variational quantum eigensolver (VQE) is a hybrid quantum--classical
variational algorithm that produces an upper-bound estimate of the ground-state
energy of a Hamiltonian. As quantum computers become more powerful and go
beyond the reach of classical brute-force simulation, it is important to assess
the quality of solutions produced by them. Here we propose a dual variational
quantum eigensolver (dual-VQE) that produces a lower-bound estimate of the
ground-state energy. As such, VQE and dual-VQE can serve as quality checks on
their solutions; in the ideal case, the VQE upper bound and the dual-VQE lower
bound form an interval containing the true optimal value of the ground-state
energy. The idea behind dual-VQE is to employ semi-definite programming duality
to rewrite the ground-state optimization problem as a constrained maximization
problem, which itself can be bounded from below by an unconstrained
optimization problem to be solved by a variational quantum algorithm. When
using a convex combination ansatz in conjunction with a classical generative
model, the quantum computational resources needed to evaluate the objective
function of dual-VQE are no greater than those needed for that of VQE. We
simulated the performance of dual-VQE on the transverse-field Ising model, and
found that, for the example considered, while dual-VQE training is slower and
noisier than VQE, it approaches the true value with error of order $10^{-2}$.
