I asked how QUBO can be expanded to non-binary version to Perplexity Pro

2 min readJun 2, 2025

This was created by asking a question to Perplexity Pro on 6/2/2025

Get Tsubasa Kato’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

QUBO Quadratic Unconstrained Binary Optimization) can be expanded to handle non-binary variables through several mathematical reformulation techniques, though this expansion comes with increased complexity and computational overhead.
The most straightforward approach to expanding QUBO beyond binary variables involves encoding multi-valued discrete variables using multiple binary variables. For a variable that can take discrete values, you can represent it using binary variables in binary encoding, or use one-hot encoding with binary variables where exactly one variable equals 1 . For continuous variables, discretization is typically employed where the continuous domain is divided into discrete bins, and each bin is then represented using binary encoding techniques. This allows the QUBO framework to approximate continuous optimization problems, though with some loss of precision depending on the discretization granularity.
When expanding QUBO to handle more complex variable interactions, higher-degree polynomial terms often arise. These can be systematically reduced back to quadratic form using ancillary variables . The process involves:
Sequential Variable Introduction: For interactions involving 4 or more variables, new ancillary binary variables are introduced sequentially, reducing the polynomial degree by 1 at each step until only quadratic terms remain .
Minimum Selection Method: This technique exploits mathematical identities to substitute higher-degree terms. For example, a cubic term can be replaced with quadratic terms using an ancillary variable and the identity that preserves the optimization landscape .
QUBO can be reformulated as a linear constrained binary optimization problem by
substituting products with additional binary variables and adding appropriate linear
constraints . This transformation allows the use of integer linear programming solvers like
CPLEX or Gurobi, which can handle more general constraint structures.
The constraints added are:
how can QUBO be expanded to nonbinary version
Direct Extensions to Multi-valued Variables
1 Polynomial Degree Reduction Techniques
2 Reformulation to Other Optimization Frameworks
Notably, the auxiliary variables can even be relaxed to continuous variables within bounds, further expanding the solution spac.
While these expansion techniques are mathematically sound, they significantly increase the problem size. Each additional variable type or higher-degree interaction requires more binary variables and constraints, leading to exponential growth in the search space. The complexity remains NP-hard, and the number of candidate solutions grows as where is the total
number of binary variables after expansion. Modern quantum annealers and classical optimization tools can automatically perform these
reductions, making the expansion more practical for real-world applications. However, the trade-off between model expressiveness and computational tractability must be carefully considered when expanding QUBO to non-binary formulations.