Qubit-Efficient Variational Quantum Optimization for Matching Problems with Quadratic Constraints

Variational Quantum Optimization is a promising approach for solving hard constrained combinatorial optimization problems in the NISQ era since it leverages shallow circuits. However, it is difficult to encode inequality constraints in the quantum circuit because this typically requires a large number of ancillary slack qubits. In addition, it is difficult to model problem instances at industrially relevant scales due to low qubit availability in the NISQ era. In this work we introduce a qubit-efficient problem encoding and a novel cost function that aims to push the limits of solving matching problems with quadratic constraints on IonQ quantum computers. This problem has commercial applications in areas like cargo loading, scheduling, and resource allocation, amongst others. We present results obtained using quantum simulators as well as IonQ's Forte QPU, which boasts 29 algorithmic qubits with excellent gate fidelities. The QPU's all-to-all qubit connectivity offers great flexibility for optimizing the quantum circuits by reducing the number of required entangling two-qubit gates. When paired with error mitigation techniques, we obtain optimal solutions with high sampling probability upon executing quantum circuits on the Forte QPU.