Scholarlink

<p>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 <i>posiform planting</i> 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="42979_2025_3964_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(n \log n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>n</i> 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 <i>O</i>(<i>n</i>) that requires fewer clauses and generates random QUBOs that are more difficult to solve and are therefore better suited for benchmarking.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Improved Posiform Planting Algorithm for Random Generation of Binary Optimization Problems

  • 期刊论文

  • 发表日期：

    2025年5月17日

查看全文
  • Stefan Isermann

摘要

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(n \log n)\) O ( n log n ) , 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.