Combinatorial optimization problem processing apparatus, combinatorial optimization problem processing method, and program

Abstract

A combinatorial optimization problem processing apparatus includes an annealing unit that acquires, using an annealing scheme, a candidate for a first solution that is a variable q satisfying a first condition regarding a partition function whose Hamiltonian is a function representing a combination optimization problem that is an analysis target and the function includes third- or higher-order terms of a variable q, the Hamiltonian being represented by an integral representation using a variable X, the Hamiltonian being represented by a sum of a first equation that includes only second- or lower-order terms of the variable q and a second equation that does not include the variable q, in an alternate optimization algorithm in which first optimization processing for acquiring the first solution and second optimization processing for acquiring a second solution that is a variable X satisfying a second condition regarding the partition function are repeated until an end condition is satisfied, a calculation unit that acquires the second solution, and a solution candidate acquisition unit that acquires a candidate for the immediately preceding first solution when the end condition is satisfied, as a candidate for a solution of the combinatorial optimization problem.