Combinatorics

Discrete mathematics

Physics

Mathematics

Combinatorial optimization

Binary code

Knapsack problem

Algorithm

Statistical physics

Encoding (memory)

Optimization problem

Quadratic unconstrained binary optimization

Artificial intelligence

Programming language

Geometry

Constraint (computer-aided design)

Computer science

Ising model

Integer programming

Quantum computer

Quantum mechanics

Integer (computer science)

Binary number

Unary operation

Quantum

Arithmetic

IEEE Access

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine