A smaller and more efficient one-hot encoding for QUBO
Abstract
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.
Fields of Study & Subjects
Advanced Data Compression Techniques
Algorithms and Data Compression
Advanced Wireless Communication Techniques
Publication details
- Journal / source
- Scientific Reports
- Publisher
- Springer Science and Business Media LLC
- Volume
- 16
- Issue
- 1
- Publication date
- 4 June 2026
- Language
- EN