Scalable Integer Encoding in Quadratic Unconstrained Binary Optimization
TimeTuesday, June 23rd4:50pm - 4:55pm
DescriptionVarious real-world applications involve combinatorial optimization problems, such as graph coloring and job-shop scheduling, and they tend to be computationally expensive due to NP-hardness.
To solve them efficiently, several companies have developed specialized computers, e.g., D-Wave's quantum annealers, Fujitsu's digital annealers, and NTT's coherent Ising machines.
These computers employ the quadratic unconstrained binary optimization (QUBO) model as the native input format because combinatorial optimization problems mostly can be formulated as a QUBO problem.
QUBO formulation usually uses one-hot encoding to represent integer variables in original problems.
For example, integer variables represent a color of each node in the graph coloring problem.
Its QUBO formulation uses K binary variables per node, where K is the number of colors.
However, such one-hot encoding consumes binary variables in linear proportion to the value range of the integer.
Since QUBO computers can accommodate only the limited number of binary variables, one-hot encoding is not scalable to complex problems.
In this poster, we propose scalable integer encoding "qubyte" and QUBO formulation of mathematical relations between qubytes such as equal, and not equal.
A qubyte and its relation formulations reduce the consumption of binary variables to logarithmic order of value ranges; hence, we can solve larger and more complex problems on QUBO computers by using qubytes.
We also experimentally show efficiency of qubytes by applying it to the formulation of practical problems.