Quantum Hardware-Efficient Selection of Auxiliary Variables for QUBO Formulations
arXiv
Damian Rovara, Lukas Burgholzer, Robert Wille
The Quantum Approximate Optimization Algorithm (QAOA) requires considered optimization problems to be translated into a compatible format. A popular transformation step in this pipeline involves the quadratization of higher-order binary optimization problems, translating them into Quadratic Unconstrained Binary Optimization (QUBO) formulations through the introduction of auxiliary variables. Conventional algorithms for the selection of auxiliary variables often aim to minimize the total number of required variables without taking the constraints of the underlying quantum computer-in particular, the connectivity of its qubits-into consideration. This quickly results in interaction graphs that are incompatible with the target device, resulting in a substantial compilation overhead even with highly optimized compilers. To address this issue, this work presents a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity. By specifically constructing an interaction graph with a regular structure and a limited maximal degree of vertices, we find a way to construct QAOA circuits that can be mapped efficiently to a variety of architectures. We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%. An implementation of all proposed methods is publicly available at https://github.com/munich-quantum-toolkit/problemsolver.
No comments yet. Be the first to share your thoughts!
Indexed by QCR Librarian
This entry was created automatically from publicly available records. QCR links to public sources and only stores repository content where the license permits redistribution.
QCR Librarian
Join the Discussion
Comments (0)
No comments yet. Be the first to share your thoughts!