一种更小、更高效的QUBO独热编码方法

《Scientific Reports》：A smaller and more efficient one-hot encoding for QUBO

　　

摘要

One-hot约束在量子计算和模拟退火中的二次无约束二进制优化（QUBO）中被广泛用于解决优化问题。这些约束对应于布尔可满足性问题（SAT）中的“恰好一个解”的要求，针对SAT问题已经提出了多种不同的编码方式，主要是为了减小问题的规模。我们研究了QUBO的编码方式，包括之前提出的SAT编码方法以及新发明的编码方法，以确定在QUBO规模和解决方案质量方面最佳的编码方案。实验结果表明，我们新提出的“Reduced Commander”编码方法在本研究中的基准问题上实现了QUBO规模与解决方案质量之间的最佳平衡。