マイナー埋め込み

量子アニーリングマシンであるD-Wave 2000Qでは、物理的な量子ビットはキメラグラフという独特な構造になっています。最適化問題を解く際には、図1のキメラグラフ上にマッピングを行う必要があります。

図1: キメラグラフ

例えば、図2のようなグラフ構造を持つ問題であれば、そのまま解きたい問題をマッピングすることが出来ます。

図2: マッピングが容易な例

しかし、図3のようにノード1とノード3の間に結合がある場合、キメラグラフ上に直接マッピングすることが出来ません。そのため、図3の右図のように、複数の量子ビットで1つのノードを表すようなマッピングを行います。これを、マイナー埋め込み(minor embedding)と言います。

図3: マッピングが複雑な例

図3の場合、解きたい問題のノード数は4個ですが、ハードウェア上では6個の量子ビットが使用されてしまいます。解きたい問題のグラフが密になればなるほど、使用する量子ビットは増加します。このようなハードウェア上の制限により、D-Wave 2000Qは最大2048個の量子ビットが使用可能ですが、実際に解ける問題サイズはかなり小さいものになってしまいます。現在はD-Wave 2000Qのサービスは終了してしまいましたが、最新のD-Wave Advatageでも依然この問題は残っています。

チェーン

図3には、ノード1が2つの量子ビットとしてハードウェア上に示されています。このように、1つのノードを複数の量子ビットにマッピングするグループをチェーン(Chain)と呼びます。チェーン内の全ての量子ビットは同じ値を持つことが期待されるため、同じ値を取るように力が加えられます。この力の強さをチェーン強度(Chain Strength)と呼びます。ただし、強度を単純に強くするだけが解決策ではありません。D-Waveマシンは相互作用や局所磁場をエンコードする精度に限界があるため、チェーン強度を大きくしすぎるとこれらの係数が埋もれてしまい、上手く最適解が求められなくなってしまいます。一方で、チェーン強度が弱すぎるとチェーン内の量子ビットが異なる値を取る、チェーンブレイク(Chain Break)が起きる可能性があります。これが生じた場合、投票(vote)に基づき、値が決定されます。最も単純な方法は多数決で、チェーン内の量子ビットで最も多い値を採用します。しかし、投票によって定めた値が正しい保証はありません。従って、解くべき問題によって適切なチェーン強度を設定することが必要不可欠です。