量子计算机秀尔算法的证伪方法
http://taipeibbs.cn/viewtopic.php?f=76&t=53

在 1997年3月25日星期二 UTC+8下午4:00:00，Kazuhiro Igeta写道：
> In article <5h2ugf$crh@mail.mfi.or.jp> "S.Kubo" <pao@mfi.or.jp> writes:
> 
> > > > 初心者（といっても、科学者向けだけど）には、日経サイエンス１９９５年１
> > > > ２月号「量子コンピュータ／Ｓ．ロイド」が良い論文だと思います。
> > > 
> > > 機会があったらぜひ見てみよーっと。（ウチの職場の図書館には
> > > なかったよな... 日経マイクロ／日経デバイスならあるけど、
> > > そんなものには載ってませんよね？）
> > 
> > 私は、書店に行ってバックナンバーを探すか取り寄せるしかないですね。
> 
> 図書館にいけばあるでしょう。
> Lloydの説明だけで、全てだとおもってはいけませんが。
> 
> > > > この偉大な計算理論のポイントは、すべての入力ビットにおいて、０と１を
> > > > （同じ振幅を持たせて等しく）重ねあわせると、すると、すべての計算可能な
> > > > 入力が入ったのと同じくなり、それを計算させると、計算可能なすべての出力
> > > > が得られる。つまり、量子コンピュータは、すべての計算可能な計算を同時に
> > > > 終了させるのです。これを「量子並列化」と呼びます。究極の並列計算法で
> > > > す。
> > 
> > ？？？？？。しばらく何回もこの文章を読んでみました。
> > 何かがわからない。もしかして、基本的なことがわかっていないのかな？
> > 閃いてこないと言うか、イメージが湧かないです。
> 
> わかなくても大丈夫です。これのみ本質というわけでもないですから。
> 物理的リソースを増やさなくても、並列化が可能ということは重要な
> ポイントではありますが。
> 
> > 入力ビット・振幅・重ね合わせ：から
> > 量子力学で言う波動に情報を乗せると言う意味でしょうか？
> > 量子力学で言う波動は粒子の存在する確立の値を波にしたものだから．．．。
> > うーーん。量子力学で言う波動の振幅を１と０に見立てると言う意味でしょうか？
> > するとその波の中に粒子が確率的に幾つか入っている。だから、その粒が
> > ビットで言うと１０億になる．．．。
> > その波動を幾つか集めて、「えい」とミックスするとその粒子が並列的に
> > ある種の計算をして出力としてある波動を返す。
> > その波動の粒子が答えである。
> > 
> > 以上のように漠然と解釈したのですが、自分で書いていてわからない。
> > 言っていること合っているのでしょうか？
> 
> まあ、なんとなく、そんなことをイメージとして、いってるようなもんでしょう。
> 実際に、どう「えい」とやるかを書かんといかんのですが、そこはなかなか難しい。
> 
> > すると
> > １．確率的な波動の粒子が何故情報として成り立つのか？
> 
> 量子的な重ね合わせの状態は、確率的なものではないです。
> ここを間違えると、アウトです。ここから始めましょう。
> 
> > ２．並列的な計算とはいかなる方法なのか？
> 
> おなじような手続きの計算を、初期値を変えて同時に行なうというような
> 表現が一番簡単でしょうか。
> 
> > ３．結果も確立ではないのか？
> 
> 確率的な結果です。
> 実際に、どのような計算機も確率的な結果しか返していません。
> 間違った結果を出す確率が、10-9とかそういうオーダーであるだけです。
> もちろん、通常の計算機は、確率的であることを利用しているわけではなく、
> 確定的につくりたいのだけれども、技術的な問題で、確率がはいってしまう
> わけですが。これとは、別に、確率的計算機という概念もあり、確定的な計算機
> で解けない（問題のサイズの巾のオーダーの時間で）問題を解きうるとされて
> います。
> 量子計算は、確率的計算とは、似ている部分もあります。
> 量子計算機を、実際にはつくることが難しい確率的計算機の、
> より現実的なバージョンとして考えることもできるかとおもいます。
> 
> しかし、先に記したように、確率的計算機と、量子計算機では、原理が
> 本質的に違います。その違いによって、現実性がみえてくるわけです。
> 
> 現実といっても、比較の上での話で、本当のところ、量子計算機が、
> 実現可能かどうかということは、まだはっきりしていません。
> 
> もし、近い将来に実現可能だとしたら、世の中大騒ぎになっているはずです。
> なぜなら、世の中でもっとも安全だと思われている、公開鍵暗号システムは、
> 量子計算機によって、クラックされてしまうことが示されているからです。
> しかしながら、この素因数分解の問題が巾時間でとけるというアルゴリズムは、
> 具体的に量子計算機の有用性を示す唯一の結果であるといってよいでしょう。
> その素姓からいって、同様の探索的な問題には、有用であるとは想像できます
> が、どれだけ汎用性があるかということにはまだ、疑問があります。
> 
> この素因数分解のアルゴリズムを実行する量子計算機も、その物理的な
> モデルがどのようなものかも提示されているわけではありません。
> 証明に必要なのは、巾か、指数かというオーダーエスティメイションなので、
> そこまでは必要ないのです。
> 
> 結局、量子計算機という言葉の意味するところは、いまのところ、
> ある種の拡張されたアルゴリズムを受け入れるプラットフォームとして、
> メモリーの同時多値性、コヒーレンスの保持、縦横無尽にユニタリ変換を適用
> できるチューリングマシンという意味づけがもっとも適当なものといえます。
> 
> 他にも、単に量子論理ゲートなどを扱う話も量子計算機といいますし、
> さらに、歴史的には、Benioff, Feynmanなどが考えたものもあります。
> 
> が、いま、世を賑わせているのは、peter shorの因数分解のアルゴリズムと、
> それのベースになっている、Deutcheの量子チューリングマシンといいきって
> よいとおもいます。
> 
> まだ、専門にやっている人は少ない分野ですので、ホットな分、玉石混交であ
> るのは仕方のないところでしょう。そのへんに気を付けたほうがよいでしょう。
> 
> アメリカあたりでは、多自由度の量子コヒーレンスが長く保存できる
> NMRなどの系を利用して、計算させるというような試みもはやっているようです。
> 
> まあ、もっと詳しく知りたいならば、物理学会にでも参加してみれば、
> 関連した話もあるかもしれません:-)
> 
> --
>      l_#_l(_0   Kazuhiro IGETA, not the number,,,    
>   _~C. C_~/   Adaptive Communications Labs
>  (((==)((@)  ATR ,  Kyoto,  JAPAN