Summary (DeepL訳)

量子アニーラーは基本的に、ブール変数上の特定の2次関数を高い確率で一定時間内に最適化できる量子コンピューターである。これらの関数は基本的に、アニーリング処理後に高い確率で基底エネルギー状態に到達するイジングモデルのハミルトニアンである。SATを解く方法として提案されている。これらのハミルトニアンは、Max2XOR問題、すなわち、満足する最大2変数のXOR句の数を最大にする割り当てを見つける問題と見なすことができる。本論文では、SATをMax2XORに還元するためのいくつかのガジェットを示す。それらを用いて、SATインスタンスを量子アニーラの初期設定に変換する方法を示す。