  Variational quantum eigensolvers (VQE) are among the most promising
approaches for solving electronic structure problems on near-term quantum
computers. A critical challenge for VQE in practice is that one needs to strike
a balance between the expressivity of the VQE ansatz versus the number of
quantum gates required to implement the ansatz, given the reality of noisy
quantum operations on near-term quantum computers. In this work, we consider an
orbital-optimized pair-correlated approximation to the unitary coupled cluster
with singles and doubles (uCCSD) ansatz and report a highly efficient quantum
circuit implementation for trapped-ion architectures. We show that orbital
optimization can recover significant additional electron correlation energy
without sacrificing efficiency through measurements of low-order reduced
density matrices (RDMs). In the dissociation of small molecules, the method
gives qualitatively accurate predictions in the strongly-correlated regime when
running on noise-free quantum simulators. On IonQ's Harmony and Aria
trapped-ion quantum computers, we run end-to-end VQE algorithms with up to 12
qubits and 72 variational parameters - the largest full VQE simulation with a
correlated wave function on quantum hardware. We find that even without error
mitigation techniques, the predicted relative energies across different
molecular geometries are in excellent agreement with noise-free simulators.
