量子計算と古典計算の関係

藤井先生のツイートをまとめました。
13
Keisuke Fujii @fgksk

量子計算と古典計算の違いを知る最も簡単な方法は、アダマールテストを知る事だと思います。アダマールテストを使うとユニタリ行列U(の積)の要素を要求する精度の逆数の多項式回の測定で推定することができます。

2015-02-04 12:29:17
Keisuke Fujii @fgksk

n量子ビットのユニタリ行列は2^n×2^n行列なので、古典計算で愚直にユニタリ行列の積を計算すると指数的に時間がかかってしまいますが、量子系だと時間発展がユニタリ演算の作用に対応するので、この積を計算する部分は時間発展によって多項式時間で実行できます。

2015-02-04 12:30:58
Keisuke Fujii @fgksk

たとえば、ユニタリ表現やユニタリ演算子の積で書ける対象物であればこの方法でその値を量子コンピュータで計算できます。その最たる例がブレイド群のユニタリ表現と結び目不変量であるJones多項式です。

2015-02-04 12:32:31
Keisuke Fujii @fgksk

純虚数パラメータをいれてもよいならば、イジング分配関数もどうようにユニタリ演算子の積でかけるので、やはり量子コンピュータで計算できます。一般の場合には古典ではやはり指数的に時間がかかると思います。

2015-02-04 12:33:58
Keisuke Fujii @fgksk

さらに、ユニタリ演算子ではなくても線形演算子であれば補助系をもってきて、合成系でユニタリー演算子になるように構成できるので、アダマールテストで線形演算子の要素を推定することもできます。

2015-02-04 12:35:25
Keisuke Fujii @fgksk

ただし、ユニタリからずれればずれるほど、近似のスケール因子が大きくなり、近似精度がわるくなります。たとえば、Jones多項式近似アルゴリズムをTutte多項式へと一般化するときは、ユニタリ表現ではないところも扱うので、この方法が採用されています。

2015-02-04 12:37:02
Keisuke Fujii @fgksk

実パラメータの2次元正方格子磁場ありイジング模型の分配関数もこのほうほうでアダマールテストをして計算することができますが、古典のMCMCやありとあらゆる手法にくらべてより良い近似になっているかはわかりません。

2015-02-04 12:38:05
Keisuke Fujii @fgksk

ただし、純虚数パラメータを入れていい場合や、Jones多項式などユニタリ表現、ユニタリ演算子の積で書ける場合は、その近似ができれば量子コンピュータでとける決定問題をすべて解けることが知られているので、そうとう変な事(P=NPに準ずるような)がなければ古典計算ではまねできません。

2015-02-04 12:39:47
Keisuke Fujii @fgksk

ただ、アダマールテストは多項式の逆数の精度の推定なので、指数的な精度を要求される場面では使えませんし、指数的な精度で任意のユニタリ演算子(の多項式個の積)の要素を計算できるというクラスは量子計算よりももっと難しいクラスに属するので、他のプロトコルでもできないでしょう。

2015-02-04 12:44:53
Keisuke Fujii @fgksk

しかし、modular exponentiationなどの特殊なユニタリの場合のみに、量子フーリエ変換やキタエフの位相推定アルゴリズムを用いて指数的な精度で(性格にはユニタリ演算子の固有値を)計算することができます。

2015-02-04 12:46:26
Keisuke Fujii @fgksk

よくうまいアルゴリズムがほとんどないといわれているのは、このような特殊なユニタリに帰着できる問題があまりない、という話だと思います。多項式の逆数精度でよいならいくらでも古典を凌駕する(しそうな)量子アルゴリズムを(とくに分配関数のような足し合わせ問題には)構成することはできます。

2015-02-04 12:48:15
Keisuke Fujii @fgksk

ちなみに、いま言った話はすべて波動関数の収縮の計算でうまくいきます。

2015-02-04 12:49:24
Keisuke Fujii @fgksk

ちなみに実パラメータの2次元正方格子イジング模型の分配関数を量子コンピュータで近似したらこの精度までいけます、ということについて阪大の学生さんといっしょに研究しましたjournals.aps.org/pra/abstract/1…

2015-02-04 12:56:14
Keisuke Fujii @fgksk

このパラメータ領域では残念ながら古典のありとあらゆる方法を凌駕しているという証拠はありません。代表的な古典の方法(MCMCなど)と比べてどのくらい優秀(or ダメダメ)か、というのに興味が有ります。

2015-02-04 12:57:56
Keisuke Fujii @fgksk

ちなみに速いアルゴリズムを作る事だけが量子計算の研究ではなくて、任意の古典統計模型(任意のグラフ上)の分配関数は、2次元正方格子のイジング模型に適当な結合定数を入れるとつくれる(定数因子をのぞいて同じ値になる)ことが量子計算の万能性を経由すると簡単に示せます。

2015-02-04 14:06:38
Keisuke Fujii @fgksk

ほかにもいろいろ量子を経由すると簡単に証明できる古典の問題があって、arxiv.org/abs/0910.3376 にまとめられています。

2015-02-04 14:10:19

余録:量子計算あるある

Keisuke Fujii @fgksk

[量子計算あるある] 量子回路は左から右にすすむのに、数式では演算子が右から状態に作用するので、ややこしい。いっそのこと明日から回路図を左右逆に書きましょうとなってほしい。

2015-02-02 16:19:03
Keisuke Fujii @fgksk

[量子計算あるある パート2] BABYMETALド・キ・ド・キモーニングの歌詞が、四次元、五次元、キタエフっ!キタエフっ!に聞こえる。熱的安定性のあるトポロジカルオーダーということだと思います。

2015-02-02 16:22:38
Hal Tasaki @Hal_Tasaki

確実にそう言ってますね。 @fgksk [量子計算あるある パート2] BABYMETALド・キ・ド・キモーニングの歌詞が、四次元、五次元、キタエフっ!キタエフっ!に聞こえる。熱的安定性のあるトポロジカルオーダーということだと思います。

2015-02-03 01:19:27
Kumano Tarou @kumano_tarou

@fgksk Kitaev, Shen, and Vyaviの教科書は右から入力を食べて左から出力を吐き出す量子回路の流儀ですね.CS出身だと逆に気持ち悪くて仕方なかった記憶があります.

2015-02-02 16:47:13
Keisuke Fujii @fgksk

@kumano_tarou 確かにそうですね。線に矢印書いてあるのでわかりやすいですね。物理でも時間の流れは左から右に書くことが多いような気がするので、逆にする場合はなにかしら書いておかないと紛らわしいですね。

2015-02-02 16:56:14