Reducing QUBO Density by Factoring out Semi-Symmetries

Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing are prominent approaches for solving combinatorial optimization problems, such as those formulated as Quadratic Unconstrained Binary Optimization (QUBO). These algorithms aim to minimize the objective function xTQx, where Q is a QUBO matrix. However, the number of two-qubit CNOT gates in QAOA circuits and the complexity of problem embeddings in Quantum Annealing scale linearly with the number of non-zero couplings in Q, contributing to significant computational and error-related challenges. To address this, we introduce the concept of semi symmetries in QUBO matrices and propose an algorithm for identifying and factoring these symmetries into ancilla qubits. Semi-symmetries frequently arise in optimization problems such as Maximum Clique, Hamilton Cycles, Graph Coloring, and Graph Isomorphism. We theoretically demonstrate that the modified QUBO ma trix Qmod retains the same energy spectrum as the original Q. Experimental evaluations on the aforementioned problems show that our algorithm reduces the number of couplings and QAOA circuit depth by up to 45%. For Quantum Annealing, these reductions also lead to sparser problem embeddings, shorter qubit chains and better performance. This work highlights the utility of exploiting QUBO matrix structure to optimize quantum algorithms, advancing their scalability and practical applicability to real-world combinatorial problems.