A smaller and more efficient one-hot encoding for QUBO

One-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.