Variational quantum optimization with qubit-efficient encoding of problems

Variational quantum optimization algorithms show promise in solving hard combinatorial optimization problems, which could have significant impact on operational domains such as supply chains and logistics. However, their use is currently limited by the number of qubits on the existing hardware which have O(100) qubits, while heuristic classical algorithms can solve problems with O(1000) variables. We implement a qubit-efficient mapping of optimization problems that will enable larger problems to be mapped to currently available quantum computers. The qubit-efficient mapping uses a many-to-one map from classical variables to qubits, and stores the variables in an entangled wavefunction of fewer qubits. We quantify the performance of variational quantum circuits in solving Ising spin glass problems up to 1000 variables, and investigate the tradeoff between algorithm performance and the qubit-efficiency of the encoding. The qubit-efficient mapping brings quantum algorithms into competition with classical heuristic algorithms in the problem sizes investigated.