Qubit-efficient encoding schemes for binary optimisation problems

We propose a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of n_c classical variables can be implemented on as little as O(log n_c) qubits. By dividing the classical variables into subsystems, we use ancilla qubits to capture intra-subsystem correlations and register qubits to encode the address of each subsystem within the quantum state. We examine the limit where each subsystem consists of only a single classical variable. The resulting quantum state, without capturing any classical correlations, allows for an exponential reduction in the qubits required. With this minimal encoding, approximate solutions for a 64-variable problem can be found using only 7 qubits. We then show how two-body correlations can be encoded, and how these correlations can bring about an improvement in the quality of the solutions obtained. We demonstrate the encoding for two-body correlations by finding approximate solutions to a 42-variable Max-Cut problem using 8 qubits. Lastly, we present the general framework for extending the expressibility of the probability distribution for capturing multi-body correlations.