RSQC: Recursive Sparse QUBO Construction for Quantum Annealing Machines

Quantum annealing algorithms have shown commercial potential in solving some instances of combinatorial optimization problems. However, existing mapping for general optimization problems into a compatible format for quantum annealing yields dense topology and complicated weighting, which limits the size of solvable problems on practical quantum annealing machines. To address this issue, we propose a novel mapping framework with three new techniques. First, to address the issue from general constraints, we introduce a recursive methodology to map constraints into interconnected Boolean gates and small algebraic cliques, which yields sparse topology and hardware-friendly biases/interactions. Second, to better address frequently-used constraints, we introduce a specialized penalty set based on this methodology with detailed optimizations. Third, to address the issue from the objective, we reformulate the complicated objective into a single multi-bit variable and apply binary search to its range, which turns each search step into a constraint-only problem. Compared with the state-of-the-art, experimental results and analysis over an exhaustive scan for operand bit-widths from 1 to 64 show that: (1) the growth order of the number of physical qubits with regard to operand bit-widths is reduced from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">w</i>), while the number is reduced by a factor of 10-1 in the best case; (2) the dynamic range of biases/interactions is reduced from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2<i>w</i></sup>) to < 32; (3) the graph minor embedding run time is reduced by a factor of 10<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−2</sup> in the best case. For the same optimization problem, our framework reduces the requirement of the number of physical qubits and machine precision, and shortens the time from problem to machine.