- 39 名前：37 mailto:sage [04/06/29 04:10]
- >素因数分解はチューリングマシンを前提としたモデルの上では
>準指数時間アルゴリズムしか知られていないが、量子チューリン
>グマシン上では多項式時間で解けるアルゴリズムがあるってのが
>Shorの主張かと思うということ。
これはその通り．
>それとShorのアルゴリズムは素因数分解アルゴリズムで
>離散対数問題がShorのアルゴリズムに帰着できると
>証明されているってことでよろしいか？
これはちょっと言い方が気持ち悪いんだが，大筋で正しい．
>実際に量子コンピュータが出来たとして
>Shorアルゴリズムは出来ませんでしたなんて
>オチはないだろうな、なんて期待してるんですが。
これについては同じ意見を持ってる計算機科学者，物理学者が多くいるらしく，
S. Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"
ttp://jp.arxiv.org/abs/quant-ph/0311039
に面白いことが書いてある．
