  Due to the limitations of present-day quantum hardware, it is especially
critical to design algorithms that make the best possible use of available
resources. When simulating quantum many-body systems on a quantum computer,
straightforward encodings that transform many-body Hamiltonians into qubit
Hamiltonians use $N$ of the available basis states of an $N$-qubit system,
whereas $2^N$ are in theory available. We explore an efficient encoding that
uses the entire set of basis states, where terms in the Hamiltonian are mapped
to qubit operators with a Hamiltonian that acts on the basis states in Gray
code order. This encoding is applied to the commonly-studied problem of finding
the ground state energy of a deuteron with a simulated variational quantum
eigensolver (VQE). It is compared to a standard "one-hot" encoding, and various
trade-offs that arise are analyzed. The energy distribution of VQE solutions
has smaller variance than the one obtained by the one-hot encoding even in the
presence of simulated hardware noise, despite an increase in the number of
measurements. The reduced number of qubits and a shorter-depth variational
ansatz enables the encoding of larger problems on current-generation machines.
This encoding also demonstrates improvements for simulating time evolution of
the same system, producing circuits for the evolution operators with reduced
depth and roughly half the number of gates compared to a one-hot encoding.
