物理世界の計算可能性についての議論

TANIMURA Shogo @tani6s

@ayumu_sugita @qutrit_a ドイチュは、有限次元量子系なら普遍量子計算機でシミュレートできる、ということを言いたかったのでしょうね。古典系について徹底的に分析しているわけではないし、否定的なことを証明しているわけでもないです。

TANIMURA Shogo @tani6s

@ayumu_sugita @qutrit_a 話の流れ上、私は、古典計算機でできないことを証明したかったのではなく、計算リソースの物理原理を見直せば、できるようになることを強調したかったのです。

aya_furuta @qutrit_a

@ayumu_sugita @tani6s 杉田先生、谷村先生、面白い議論をされていますね。ドイチュ先生が私に量子計算を作った動機を話して下さった時には、古典との比較は本題ではなかったもので、その点についての詳しい議論はありませんでした。

aya_furuta @qutrit_a

@ayumu_sugita @tani6s 古典の話は、ユニタリー変換はゲート操作の組み合わせで書けることが証明可能だ、という文脈の中で、比較として出てきました。なので、この時は杉田先生が指摘されているような問題意識はなかったように思いますが、

aya_furuta @qutrit_a

@ayumu_sugita @tani6s それとは別に、量子を計算で記述する利点とは、みたいな話を聞いたことがあり、そちらが関係しそうな気もします。ツイッターで書くのは難しいですが、来週、立川でお会いできると思いますので、その時にお話しさせて頂けましたら幸いです。

シータ @Perfect_Insider

@ayumu_sugita @tani6s @qutrit_a 横槍ですが、四則演算器（古典で実現可能）が無限精度で実現できるなら、これはNP完全問題を多項式時間で解けるという研究はありますねlink.springer.com/chapter/10.100…

杉田歩 @ayumu_sugita

@Perfect_Insider @tani6s @qutrit_a 情報ありがとうございます。やはり無限精度の演算というのはものすごく強力なんですね。

ベッチー📦@療養中 @bechi0226

@qutrit_a 結果が一意でなく確率的に決まるなら出てきた結果が合ってるかどうか分からないような気がします。何度もシミュレーションして統計を取るのですか？

aya_furuta @qutrit_a

@bechi0226 例えば因数分解はすぐ検算できるので、外れたらまた計算します。答えを得るまでの試行回数が指数的に発散したら意味ないですが、多項式で行けることが保証されています。

ベッチー📦@療養中 @bechi0226

@qutrit_a すみません、言葉足らずでした。量子力学の過程をシミュレーションできるということがよく分からなくて、シミュレーションして結果を得ても同じことをした時に結果が変わるのではないかと思うのです

aya_furuta @qutrit_a

@bechi0226　失礼しました。その「シミュレーションできる」は任意のユニタリー変換を、ゲート操作の組み合わせで多項式時間で表せるという意味です。つまり量子過程は、原理的には量子コンピュータのゲート操作で実行できます。（間違ってたらご教示下さい。 @tani6s @fgksk

aya_furuta @qutrit_a

@bechi0226 なので、量子コンピュータで量子実験をシミュレートするアルゴリズムを組んで実行したら、実験と同様、毎回異なる結果を返して来ると思います。「シミュレートできる」というのは、理論上、そういうプログラムを組むことができるという意味です。 @tani6s @fgksk

aya_furuta @qutrit_a

@bechi0226 現実の量子コンピュータにはエラーがあるので、それほど単純な話ではないと思いますが。　@tani6s @fgksk

ベッチー📦@療養中 @bechi0226

@qutrit_a 詳しくありがとうございます！量子過程を量子コンピューターの中で行えるということですね。計算が速くなるのもすごいですけどシミュレーションできるってことの方がすごいなと思いました

aya_furuta @qutrit_a

@bechi0226 計算機というより、パラメーター可変の実験機、とも言えると思います。実用を考えている人は、そっちの側面に興味を持っている人が多いです。どんなクラスの計算ができるかを考えているのは、量子計算の本質とは何かとか、理論に興味を持っている人が多い印象ですね。