こんにちは、論文を読んでいたら、全結合のグラフ問題がテンソルネットワークで隣接結合に変換されている図を見つけました。量子コンピュータでは全結合グラフ問題を何かしらのテクニックで隣接結合に変換できるのでしょうか？その謎に迫りました。
Variational Quantum Optimization with Multi-Basis Encodings
(https://arxiv.org/pdf/2106.13304.pdf)[https://arxiv.org/pdf/2106.13304.pdf]
こちらです。グラフ問題では結合が重要です。イオントラップ型量子コンピュータは全結合を実現していますが、その他のマシンはそうではないので考えてみたいと思います。下記の左上のグラフでは、赤い線は横断するように接続されています。これを右下のようにうかいできればローカルの少ない接続で問題を設定できますね。
MBEではこれをテンソルネットワークで実現していますが、量子回路ではなく、量子回路を古典でシミュレーションする際にテンソルネットワークでMPOと呼ばれる量子操作に落として、最終的な一次元のMPSという状態にもっていっています。MPSでは隣接の量子ビットの間の接続部分に遠距離の接続のもつれ情報も持っていますので、グラフ形状によっては効率的に解決をすることができます。
量子回路を想定してこのグラフ接続の迂回方法を考えます。時間発展計算をグラフの外側に想定し、点から伸びてエッジの先にノードがない部分には状態ベクトルを想定します。外側に時間発展をする際、先ほどのグラフのエッジはこの３つの量子計算の組合せで表現できます。理由は後述します。これによって、上のようなグラフ問題を量子もつれを使って表現できます。
このグラフ状態を単にMPS/MPO表現するだけではわかりづらいので、量子回路に直してみますが、かなり拍子抜けしました。。。
なんてことはない、量子回路で迂回をするためには、swapゲートを適用して量子状態を移動させればよいということに。これによって量子ビットをまたぐような操作は出ないので、隣接量子ビットの計算だけに帰着できます。なので、基本的に量子計算に縛りをつけてグラフ問題を考えるときに結合数はすべて隣接接続に帰着できますが、量子回路だとswapゲートの活用に終始するので計算リソースを消費します。シミュレーションとしては楽なので、有用であるとも考えられます。以上です。