  Hybrid quantum-classical variational algorithms such as the variational
quantum eigensolver (VQE) and the quantum approximate optimization algorithm
(QAOA) are promising applications for noisy, intermediate-scale quantum (NISQ)
computers. Both VQE and QAOA variationally extremize the expectation value of a
Hamiltonian. All work to date on VQE and QAOA has been limited to Pauli
representations of Hamiltonians. However, many cases exist in which a sparse
representation of the Hamiltonian is known but there is no efficient Pauli
representation. We extend VQE to general sparse Hamiltonians. We provide a
decomposition of a fermionic second-quantized Hamiltonian into a number of
one-sparse, self-inverse, Hermitian terms linear in the number of ladder
operator monomials in the second-quantized representation. We provide a
decomposition of a general $d$-sparse Hamiltonian into $O(d^2)$ such terms. In
both cases a single sample of any term can be obtained using two ansatz state
preparations and at most six oracle queries. The number of samples required to
estimate the expectation value to precision $\epsilon$ scales as
$\epsilon^{-2}$ as for Pauli-based VQE. This widens the domain of applicability
of VQE to systems whose Hamiltonian and other observables are most efficiently
described in terms of sparse matrices.
