Generating hard quadratic unconstrained binary optimization instances via the method of combining bit reduction and duplication technique

Li Xiaotian

Nakano Koji

Tsukiyama Shunsuke

Itou Yasuaki

Kato Takumi

Kawamata Yuya

International Journal of Parallel, Emergent and Distributed Systems

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables. We propose the method of combing bit reduction and duplication technique that can generate hard instances of QUBO problems from any original QUBO problem without changing the size. The idea is to reduce the original QUBO problem for a specified number of bits and duplicate the same number of bits while ensuring all duplicated pair of bits take the same binary values. Experimental results show that generated QUBO instances are much hard for solving.

Quantum computing

combinatorial optimization

benchmark

hard instances

英語

Taylor & Francis

This is an Accepted Manuscript of an article published by Taylor & Francis in International Journal of Parallel, Emergent and Distributed Systems on 09 Jul 2024, available at: https://doi.org/10.1080/17445760.2024.2376928.

This is not the published version. Please cite only the published version.

この論文は出版社版ではありません。引用の際には出版社版をご確認、ご利用ください。

[DOI] https://doi.org/10.1080/17445760.2024.2376928 ～の異版である