A smaller and more efficient one-hot encoding for QUBO Authors: Shinji Takasugi, Hideo Nakaya, Yoshihiro Nakao, Kenta Sawamura Published: 2026 ABSTRACT AbstractOne-hot constraints are widely used for quadratic unconstrained binary optimization (QUBO) in quantum and simulated annealing to solve optimization problems. They correspond to exactly-one constraints for Boolean satisfiability problems (SAT), which have many different encodings proposed mainly to reduce SAT problem size. We have examined QUBO encodings, both corresponding to previously proposed SAT encodings and newly invented, to determine the best encoding in terms of QUBO size and solution quality. Our experiments show that reduced commander, our new encoding, gives one of the best trade-offs between QUBO size and solution quality for the benchmark problem studied in this work.Subject terms: Mathematics and computing, Physics Introduction Quadratic unconstrained binary optimization (QUBO) is an optimization problem that minimizes the following energy function: where is a vector of binary variables , are factors determined by the problem to solve, and C is a constant. For simplicity, we assume that the minimum value is 0 by assigning an appropriate value to C. The number of the non-zero terms of the energy function, hereinafter referred to as QUBO size, determines the problem size. Quantum or simulated annealing is commonly used to solve QUBO. Among the most common constraints in QUBO include at-most-one constraints and one-hot constraints, which require respectively that at most one of the given variables is allowed to be 1 and that exactly one of them must be 1. A way of formulating a constraint is called encoding. At-most-one constraints in QUBO are commonly encoded as the following penalty energy function: For example, when there are three variables, it is formulated as follows: which gives the minimum value of 0 if none or only one of the variables is 1, a value of 1 if only two of them are 1, and a value of 3 if all of them are 1. One-hot constraints in QUBO are commonly encoded as the following penalty energy function: When there are three variables, it is formulated as follows: which gives the minimum value of 0 if only one of the variables is 1, a value of 1 if none or only two of them are 1, and a value of 4 if all of them are 1. Prior research on one-hot constraints in QUBO has commonly overlooked the similarity between QUBO and the Boolean satisfiability problem (SAT), which checks whether a given Boolean formula can be made true by assigning appropriate truth values to the formula’s variables. In SAT, at-most-one constraints and exactly-one constraints require respectively that at most one of the given variables is allowed to be true and that exactly one of them must be true1–5, which are effectively the same as at-most-one constraints and one-hot constraints in QUBO. The most common encoding of at-most-one constraints in SAT is pairwise or binominal encoding as follows: where n is the number of variables and are Boolean variables. The formulation of exactly-one constraints in SAT is a conjunction of the at-most-one constraint and the trivial at-least-one constraint as follows: Through comparison between SAT and QUBO, we can see that making the negation of a SAT proposition false corresponds to minimizing a QUBO energy function as shown in Table 1. Table 1Correspondence between SAT and QUBO. P is a SAT proposition.SATQUBOSatisfied conditionUnsatisfied conditionConjunctionDisjunctionNegation Correspondence between SAT and QUBO. P is a SAT proposition. Equation 3 in QUBO corresponds to making the negation of the SAT at-most-one constraint false: Equation 5 in QUBO corresponds to making the negation of the SAT exactly-one constraint false: The correspondence between SAT and QUBO concerning exactly-one constraints allows us to adapt various previously published SAT encodings to QUBO. Prior research on one-hot encodings has primarily focused on reducing QUBO size, while their impact on solution quality, which is important in practical applications, has been largely overlooked. Therefore, in this work, we evaluate one-hot encodings from both perspectives and aim to find the best trade-off between QUBO size and solution quality. Methods First, we examine five existing one-hot encodings, then we propose a new one, to evaluate both QUBO size and solution quality. Note that QUBO size is an absolute limitation due to hardware constraints such as memory capacity, whereas solution quality is a performance factor where small differences are acceptable. To increase solution quality, we also demonstrate the optimizability of the parameters of each encoding, which, to our knowledge, has been overlooked. The parameters we optimize are not constraint weights but generalization of each encoding for a wider research scope. To compare solution quality, we use the median energy of obtained solutions of the same benchmark problem. Due to the probabilistic nature of quantum and simulated annealing, the minimum energy among the solutions may vary and it tends to become smaller (i.e. better) as the number of anneals increases, while the median energy remains approximately constant. For a one-hot set of size n, the feasible-state ratio is , and for one-hot sets of sizes , the total feasible-state ratio is calculated as follows: Pairwise As written above, the most common encoding of one-hot constraints is pairwise encoding: However, QUBO is more flexible than SAT and it can be generalized as follows: where α is an optimizable parameter satisfying 0.5<α <1.5, which has an effect similar, but unrelated, to the augmented Lagrangian method. Setting α =0.5 makes it an at-most-one constraint. Note that α is inside of and not a constraint weight applied to . There is prior research on the ratio of solutions according to the generalization6, but here we examine solution quality, which has been overlooked. The QUBO size of a one-hot set of n variables using pairwise encoding is , which can become prohibitively large since it scales in proportion to the square of n. Binary The basic idea of binary or bitwise encoding of at-most-one constraints in SAT3,7 is that the binary representation of an integer selects just one indexed variable. It is formulated as follows: where is the variable or its inverse if the bit j of i-1 is 1 or 0 respectively. can be true only if the conjunction of for all j is true. For QUBO, first we define an inverted variable as follows: Note that is used only for formulation and replaced by in QUBO. Then the binary encoding of one-hot constraints in QUBO is formulated as follows: where is or if the bit j of i-1 is 0 or 1 respectively and α is an optimizable parameter satisfying 0<α <2. Setting α =0 makes it an at-most-one constraint. The variable becomes 1 if and only if the sum of for all j is 0. For example, when α =1 and there are four variables, it has a structure shown in Fig. 1. The QUBO size of a one-hot set of n variables, with additional variables for the bit notation, is . The structure of binary encoding (n=4). Dashed lines show how the variables are grouped. The bit sequence selects the variable at . For example, selects . Product The basic idea of product or matrix encoding in SAT3,4,8 is that the horizontal axis and the vertical axis select just one point on a plane, like Cartesian coordinates. For n variables, it needs two additional sets of variables, and , where nłe pq and each of which has an exactly-one or at-most-one constraint, and each conjunction of a variable in U and a variable in V corresponds to a variable as follows: can be true only if and are true. To adapt it to QUBO, we use the following conjunction energy function that has a value of 0 if and a positive value otherwise: Then we obtain the following energy function: The last term above is necessary to prevent inappropriate combinations. For example, when n=4 and p=2, it has a structure shown in Fig. 2. It can be generalized as follows: where are optimizable parameters satisfying respectively. To our knowledge, no prior work has reported the optimizability of the conjunction function. Setting α =0.5 and makes it an at-most-one constraint. The QUBO size of a one-hot set of n variables is , and when , it is simplified to . The structure of product encoding (n=4,p=2). Dashed lines show how the variables are grouped. The horizontal axis and the vertical axis select just one from . Domain wall Sequential or ladder encoding in SAT9 corresponds to domain wall in QUBO10. A one-hot set of n variables is expressed by a domain wall of n-1 variables. For example, a one-hot set of four variables are expressed by a domain wall of three variables as shown in Table 2. In order to express a one-hot set with domain wall encoding in QUBO, it is necessary to replace the n variables in a one-hot set with the n-1 variables in a domain wall as follows: Table 2Correspondence between one-hot and domain wall. Each digit is a binary variable.One-hotDomain wall11 0 0 00 0 020 1 0 01 0 030 0 1 01 1 040 0 0 11 1 1 Correspondence between one-hot and domain wall. Each digit is a binary variable. Then we add the following energy function for the domain wall variables: The new QUBO is then used for quantum or simulated annealing, and each domain wall in the solutions is replaced by the original variables again. The QUBO size of a one-hot set of n variables, which is replaced by a domain wall of n-1 variables, is 2n-4. Commander The basic idea of commander encoding in SAT1 is two-level selection where one subset is selected first and then one variable is selected from the subset. It divides a set of n variables into p subsets. A commander variable is assigned to each subset, and the p commander variables have an exactly-one constraint. If a commander variable is false, all the variables of its assigned subset must be false. If a commander variable is true, its assigned subset must have at most one or exactly one true variable, depending on whether it is an at-most-one constraint or an exactly-one constraint respectively. To adapt it to QUBO, we treat a commander variable in each subset as an inverted variable as in Eq. 14, and we obtain the following energy function: The first term is the one-hot constraint for each subset, and the second term is the one-hot constraint for the commander variables. For example, when n=9 and p=3, it has a structure shown in Fig. 3. It can be generalized as follows: where are optimizable parameters satisfying respectively. Setting α =0.5 makes it an at-most-one constraint. The QUBO size of a one-hot set of n variables is as follows: The structure of commander encoding (n=9,p=3). Dashed lines show how the variables are grouped. It consists of four pairwise one-hot sets. When , one of is allowed to be 1. When , it is simplified to: Reduced commander We propose a new one-hot encoding, named reduced commander, based on commander encoding and a variable reduction method11, to reduce redundancy. In commander encoding, if the one-hot condition of the commander variables is satisfied, the following equations hold true: where . The first subset of commander encoding in Eq. 22 has the following energy function: By replacing according to Eq. 26, we obtain the following energy function: Since is a binary variable, a term replacing it must satisfy the at-most-one condition, and in this case, it is satisfied because it is inside the one-hot constraint. We can therefore delete the second term of Eq. 22 because it is always 0, and we obtain the following energy function: For example, when n=9 and p=3, it has a structure shown in Fig. 4. When p=1, it is the same as pairwise encoding. It can be generalized as follows: where p and α are optimizable parameters satisfying respectively. Setting α =0.5 makes it an at-most-one constraint. The QUBO size of a one-hot set of n variables is as follows: The structure of reduced commander encoding (n=9,p=3). Dashed lines show how the variables are grouped. It consists of three pairwise one-hot sets. When , one of is allowed to be 1. When , one of is allowed to be 1. Compare it with Fig. 3. When , it is simplified to: Benchmarking For benchmarking, we used a multi-agent path finding (MAPF) problem expressed as a QUBO problem12,13. Figure 5a shows a simple problem with two agents and four nodes. S(a) stands for the starting point and G(a) for the goal of agent a. It has two correct solutions as shown in Fig. 5b. Each node variable indicates whether agent a is located at node p at time t, and each movement variable indicates whether agent a moves from node p to node p′ between times t and t + 1. Each agent must occupy exactly one node at any given time, and each agent must take exactly one movement at any given interval, both of which are one-hot constraints. For example, with pairwise encoding, it is expressed by the following energy function, where and are constraint weights: (a) An example of MAPF problem with two agents and four nodes. (b) The two correct solutions. Discs indicate agents and arrows indicate movements. The one-hot sets have interactions with each other, which makes it sensitive to the efficiency of the one-hot encoding it uses. Next, each movement variable should satisfy the following conjunction function with the two node variables and , where is a constraint weight: Each node can have at most one agent at any given time, and each movement should not collide with the opposite movement at any given interval, which is expressed by the following energy function, where and are constraint weights: Finally, we add a small penalty for moving away from the goal as follows, where is a penalty weight: The total energy is the sum . The actual MAPF problem we used for benchmarking, shown in Fig. 6, has 343 one-hot sets, the largest of which has 198 variables. The total feasible-state ratio defined in Eq. 10 is . The constraint weights are shown in Table 3. We intentionally avoid using any QUBO reduction methods, as our aim is to compare one-hot encodings. We solve it with D-Wave Neal, a simulated annealing sampler from D-Wave, with the default temperature schedule, the default number of sweeps (1000), and 500 anneals, which is sufficient to stably estimate the median energy, and compare solution quality as well as QUBO size for each one-hot encoding. The energy of each solution is recalculated with the standard pairwise encoding of α =1, not with an encoding used in each test, to eliminate any energy differences due to different encodings or optimization. Although we use simulated annealing for the comparison here, findings can be utilized equally in quantum annealing. The map of the MAPF problem with 7 agents. Agents cannot enter gray squares. Table 3The weights of the MAPF problem.Constraints and penaltiesWeightNode one-hotMovement one-hotNode-movement matchingNode collisionMovement collisionMoving away from the goal The weights of the MAPF problem. Results Tables 4, 5, 6, 7, 8, 9, 10 show the QUBO size of the MAPF problem and the median, 25th percentile (Q25), and 75th percentile (Q75) of the energy distribution of solutions on D-Wave Neal for each encoding and parameters. The QUBO size includes not only one-hot constraints but also QUBO terms for MAPF. The lower the energy is, the higher solution quality is. Note that the energy of each solution is recalculated with the pairwise encoding of α =1 so that any energy resulted from additional variables such as in commander encoding is properly removed. Table 4Pairwise encoding.αQUBO sizeMedianQ25Q750.6251,569,0102053172923070.751,569,0104042705220.8751,569,0106014967201.01,569,010113897913231.1251,569,010153213501726 Pairwise encoding. Table 5Binary encoding.αQUBO sizeMedianQ25Q751.0420,99113,00512,74513,2421.25420,99111,08110,81911,3551.5420,9919323899596441.75420,9919032865994301.875420,99110,82010,09011,457 Binary encoding. Table 6Product encoding.αβγδεζQUBO sizeMedianQ25Q75121232358,97112,39212,08612,6756/77/41211/43/2358,9715539521158571/220231332,8296049571763891/27/403/221332,8155344501856851/220230331,745690965437212 Product encoding. Table 7Domain wall encoding.QUBO sizeMedianQ25Q75—358,501880784969173 Domain wall encoding. Table 8Commander encoding.pαβQUBO sizeMedianQ25Q75n0.50.751.0402,548440840324770n0.50.8751.0402,548160614191831n0.51.01.0402,548143212751606n0.51.1251.0402,548180915902012n0.50.751.25402,548468843665070n0.50.8751.25402,548167014901896n0.51.01.25402,548160114171798n0.51.1251.25402,548192817322178n0.50.751.5402,548462242654929n0.50.8751.5402,548169815091910n0.51.01.5402,548162514131826n0.51.1251.5402,548205218242264 Commander encoding. Table 9Reduced commander encoding.pαQUBO sizeMedianQ25Q75n0.50.75417,878381035144142n0.50.875417,878145112581616n0.51.0417,878136811891555n0.51.125417,878154913601768n0.40.75491,655216218902410n0.40.875491,6559738291118n0.41.0491,655123510581401n0.30.75637,889128610661476n0.30.875637,889792677927n0.31.0637,889117310191333n0.250.75747,4359617921123n0.250.875747,435729586855n0.251.0747,43511589861335n0.20.75941,386719573880n0.20.875941,386682547806n0.21.0941,386116010081326n0.150.751,024,207507390685n0.150.8751,024,207594472752n0.151.01,024,20711439711313 Reduced commander encoding. Table 10Reduced commander encoding with optimized α. See the discussion.pp0.75p0.875QUBO sizeMedianQ25Q75n0.537419,82810188351204n0.437491,6559858111169n0.337637,8898376641009n0.2537747,4359607831144n0.237941,386739592889n0.15371,024,207526391685n0.514419,828118910061368n0.414491,655771637916n0.314637,889740598863n0.2514747,435605491741n0.214941,386517390652n0.15141,024,207299209437 Reduced commander encoding with optimized α. See the discussion. Discussion Tables 4, 5, 6, 7, 8, 9 show results of each encoding with various parameters. Pairwise encoding generally gives better solutions than the other encodings. It is known that the Hamming distance, which is the number of different binary variables between two states, is related to the success probability of a QUBO problem14, and pairwise encoding has the smallest Hamming distance between two one-hot states. Suppose one of the one-hot states is the global optimum. The Hamming distance to it from another one-hot state is 2. In product encoding, for example, the Hamming distance is 4 if they share a variable in either U or V and 6 otherwise, which means that it is harder to reach the global optimum in product encoding than in pairwise encoding. That also explains why α =0.75 is better than α =1 in pairwise encoding. The former gives a lower energy to the state with all 0’s than to the states with two 1’s, while the latter gives the same energy to both. The Hamming distance to the global optimum from the state with all 0’s is 1, while that from a state with two 1’s is 1 if one of the two 1’s is also 1 in the global optimum, and 3 otherwise. Therefore, it is harder to reach the global optimum from a state with two 1’s, which should be avoided. The average Hamming distances of the encodings are shown in Table 11. Table 11Hamming distances. The average distance between two randomly chosen one-hot states and the distance between two closest one-hot states.EncodingAverageClosest neighborPairwise2Binary3Product4Domain wall1Commander2Reduced commander2 Hamming distances. The average distance between two randomly chosen one-hot states and the distance between two closest one-hot states. Binary and product encodings have large Hamming distances to the closest neighbor, which reduces the efficiency in simulated annealing and makes them unpractical in solving real-world problems. Domain wall encoding has the smallest Hamming distance of 1 to the closest neighbor, which means it allows a movement from a one-hot state to another without breaking the one-hot constraint, but the Hamming distance to the global optimum is large, which makes it difficult to reach it. We have also found that in simulated annealing, it needs many more steps to reach a one-hot state from an initial random state and therefore needs a much larger weight for constraints, which makes it difficult to use for real-world problems. Reduced commander encoding has the second smallest average Hamming distance from a one-hot state to the global optimum, after pairwise encoding. That means reduced commander encoding is the most practical encoding when pairwise encoding is not acceptable for its large QUBO size. Pairwise, commander, and reduced commander can be improved by choosing the best α as shown in Tables 4, 8, 9. The efficiency and the QUBO size in reduced commander encoding have a trade-off relationship as in Table 9. We also found that the optimal value of α varies with the number of subsets: α <1 performs best when the number of subsets is small whereas α =1 performs best when the number of subsets is large. Based on these findings, we have introduced two new parameters, and , as criteria for determining the number of subsets based on the one-hot set size, and set α as follows: As shown in Table 10 and Fig. 7, we have found that the combination of the parameters , , and gives the best median energy of solutions, which is even better than the best pairwise encoding. That suggests that pairwise encoding also has room for improvement based on one-hot size. Further optimization of reduced commander encoding. makes it the same as pairwise encoding, and pairwise of α =1 is prior research. Left is better in QUBO size, and lower is better in solution quality. We find that reduced commander encoding provides one of the best trade-offs between QUBO size and solution quality, especially when simple pairwise encoding produces a prohibitively large QUBO, because it produces solutions as good as pairwise encoding while requiring a smaller QUBO. This can be explained by its small average Hamming distances to the global optimum (Table 11). It has flexibility in QUBO size for the best performance possible on a given upper limit of QUBO size. Users should first optimize the reduced commander encoding parameters for each specific problem to achieve the best performance using a small number of anneals, since, in theory, the number of anneals does not influence the median energy, and then increase the number of anneals to obtain the best solution. The usefulness of reduced commander encoding depends on problems. For example, graph coloring problem uses rather small one-hot sets, and QUBO size reduction is not very large, whereas traveling salesman problem may use large one-hot sets where reduced commander encoding is useful. In addition, we also checked the one-hot encodings above in quantum annealing and found a similar trend, except that domain wall performs much better than in simulated annealing, which will be a subject of further study. Acknowledgements K.S.’s part of this work was supported by JST SPRING, Grant Number JPMJSP2114. Author contributions S.T. formulated the problem and conducted the experiments. H.N., Y.N., and K.S. checked the results. All the authors reviewed and approved the manuscript. Funding This study was funded by LG Electronics. Data availability The authors confirm that the data supporting the findings of this study are available within the article. Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References Associated Data Data Availability Statement The authors confirm that the data supporting the findings of this study are available within the article.