Space-Efficient Embedding of the Clique Cover Problem for Quantum Optimization
Bence Bakó, Dániel Nagy, Péter Hága, Zsófia Kallus, Zoltán Zimborás · 2023
Current quantum computer prototypes exhibit various strengths and weaknesses based on their individual architectures. Consequently, the development of flexible circuit design approaches becomes a critical tool. To tackle this challenge in the case of clique cover optimization, we propose a novel embedding method of this problem, efficiently reducing the width of the required quantum circuit exponentially in the number of cliques. We compare this new embedding based on a Polynomial Unconstrained Binary Optimization reformulation to the traditional one-hot encoded quadratic problem and present numerical simulations of the Quantum Approximate Optimization Algorithm for both methods, studying in particular the solution quality. The results obtained from the numerical experiments provide valuable insights into the performance gains achieved by employing our space-efficient embedding method, verified through both analytical and stochastic simulation benchmarks. Our results highlight the effectiveness of the space-efficient embedding method for the clique cover problem and extend the set of problems formulated with this technique.