QUBO Coefficient Dynamic Ratio Shrinking Method for Quantum Annealers

Quantum annealers search for optimal solutions to a combinatorial optimization problem by solving a quadratic unconstrained binary optimization (QUBO) model. Due to integrated control errors (ICEs), input QUBO coefficients are temporarily erroneous while a quantum annealer is running. Previous studies indicate that ICEs prevent quantum annealer from accurately running to obtain an optimal solution. This paper proposes a new method for reducing the ICE-induced noise effect. After a QUBO is input to a quantum annealer, the range of the QUBO coefficients is scaled within the hardware limitation. At that time, if the range is too large, the lowest absolute value (LAV) and near-LAV coefficients of the QUBO become too much small after scaling and these small coefficients can be more sensitive to the noise. To reduce the noise effect, our proposed method shrinks the range of QUBO coefficients by splitting it into multiple QUBOs. In splitting, LAV and near-LAV coefficients are left only in one QUBO, and the other coefficients are equally split so that each QUBO has a shrunk range. Finally, comparing the (quasi- )optimal solutions obtained from all split QUBOs, we obtain a solution closer to the original optimal solution. Experimental evaluation results show that the proposed method obtains more near-optimal solutions than the QUBO input as-is for all benchmarks.