Improved Posiform Planting Algorithm for Random Generation of Binary Optimization Problems

Logical planted quadratic unconstrained binary optimization problems (QUBO) are artificial problems for benchmarking different Ising machines and optimization algorithms. In particular, they are suitable for investigating whether quantum annealers have an advantage over classical methods. In a recently published paper, an algorithm called posiform planting is proposed that enables a new class of logically planted QUBOs. These have a unique minimum for an arbitrary configuration and are generated via a randomly generated 2-satisfiability (2-SAT) problem. Moreover, these can also be created for sparsely connected architectures of current quantum annealers. By analyzing the phase transition from many to a unique solution of a 2-SAT problem, which is qualitatively different from the phase transition of a 2-SAT problem from satisfiable to unsatisfiable, we show that this algorithm has time complexity O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document}, where n is the number of binary variables of the QUBO. In addition, a large number of random 2-SAT clauses are required to ensure the uniqueness of the global minimum, which leads to the easy solvability of the QUBOs. Instead, we describe an algorithm of O(n) that requires fewer clauses and generates random QUBOs that are more difficult to solve and are therefore better suited for benchmarking.