  Digital quantum simulation of electron-phonon systems requires truncating
infinite phonon levels into $N$ basis states and then encoding them with qubit
computational basis. Unary encoding and the more compact binary/Gray encoding
are the two most representative encoding schemes, which demand $\mathcal{O}(N)$
and $\mathcal{O}(\log{N})$ qubits as well as $\mathcal{O}(N)$ and
$\mathcal{O}(N\log{N})$ quantum gates respectively. In this work, we propose a
variational basis state encoding algorithm that reduces the scaling of the
number of qubits and quantum gates to both $\mathcal{O}(1)$ for systems obeying
the area law of entanglement entropy. The cost for the scaling reduction is a
constant amount of additional measurement. The accuracy and efficiency of the
approach are verified by both numerical simulation and realistic quantum
hardware experiments. In particular, we find using one or two qubits for each
phonon mode is sufficient to produce quantitatively correct results across weak
and strong coupling regimes. Our approach paves the way for practical quantum
simulation of electron-phonon systems on both near-term hardware and
error-corrected quantum computers.
