Quantum approximate optimization of the exact-cover problem on a superconducting quantum processor

Superconducting qubits are one of the leading technologies for building useful quantum processors. Currently available devices, where error correction and fault tolerance is not yet possible, are usually referred to as noisy intermediate-scale quantum (NISQ) devices. Such processors hold yet great promise, for instance they might allow for running heuristic quantum algorithms solving combinatorial optimization. On small-scale quantum processors, these algorithms serve as important technology demonstrators. Here, we use the quantum approximate optimization algorithm (QAOA) to solve small instances of the NP-complete exact-cover problem. This problem has many real-world applications, such as work-shift scheduling and tail assignment for airlines. We implement the QAOA on our hardware platform consisting of two superconducting transmon qubits and one parametrically modulated coupler. We explore iteration levels of the algorithm up to two, and compare the performance of three different black-box optimizers. Our results show that the exact-cover problem can be solved by the QAOA with high success probability.