Re: 量子コンピュータって実用性があるの？

Article View: fj.sci.physics

Article #1798

#1798

From: Shinji KONO
Date: Fri, 13 Aug 2004 02:58

39 lines
3547 bytes

河野真治 @ 琉球大学情報工学です。

In article <040813113421.M0207444@flame.hirata.nuee.nagoya-u.ac.jp>, takao@hirata.nuee.nagoya-u.ac.jp (Takao Ono) writes
> ついでにいうと「古典コンピュータで時間がかかるとされている問題は,
> 量子コンピュータでもやっぱり時間がかかるとされている」んじゃなかっ
> たかな? 量子コンピュータは昔ちょっとききかじったくらいで全く専門
> じゃないのでこの辺の詳しい話は知らないのですが.

まぁ、まだ、こなれてない所もあるんだけど、計算量の理論っての
があって「時間がかかるっていうのがどういうことか」ってのはい
ろいろ解析されてます。入力の大きさに対して多項式時間とか指数
時間とかですね。ただ、どういう計算モデルを使うかっていう問題
があって、古典コンピュータっていう時は普通は、決定性テューリ
ングマシンですね。

で、量子コンピュータの計算モデルを決めることが出来れば、その
あたりの変換をすることができます。量子コンピュータは、その内
蔵する並列性と非決定性から、非決定性テューリングマシンに相当
する性能を持っているんじゃないかと期待されます。ってことは、
NP完全な問題を多項式時時間で解けるだろうってことです。これは、
かなり広い範囲の問題で高速化できるってことです。数百年かかる
計算が10秒で終るとか、そんな感じ。

NPが解けるとすると応用はかなり広くて、コンパイラの最適化とか
もできます。

ただ、計算量の理論でも下限が証明できているものはほとんどない
んですよね。NPの下限さえもわかってない。っていうか、それが
わかったらテューリング賞は取れる。

で、因数分解の下限もわかってない。NP困難ではなかったと思うん
だけど。指数よりは低いのかな。多項式じゃないだろうとは誰もが
思っているんだけど、P!=NPも証明できてない現状だと、多項式オ
ーダである可能性もあると思います。その時に必要な素数の生成に
必要な時間の下限も良くわかってないはずです。

---
Shinji KONO @ Information Engineering, University of the Ryukyus
河野真治 @ 琉球大学工学部情報工学科

Technical Details

Message-ID: <3990192news.pl@insigna.ie.u-ryukyu.ac.jp>

Path:

arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeed.news.ucla.edu!newsfeed.media.kyoto-u.ac.jp!oix.u-ryukyu.ac.jp!u-ryukyu.ac.jp!ie.u-ryukyu.ac.jp!not-for-mail

References:

<cfe605$s1c$1@news.jaipa.or.jp> <86isbpz15h.wl@soro1.cc.hokudai.ac.jp> <cfenic$11tn$1@news.jaipa.or.jp> <86fz6tyojb.wl@soro1.cc.hokudai.ac.jp> <cfetuh$13l6$1@news.jaipa.or.jp> <411b144b.6989%katoh@pop12.odn.ne.jp> <cfh2cs$1k8f$1@news.jaipa.or.jp> <040813113421.M0207444@flame.hirata.nuee.nagoya-u.ac.jp>

Show Full Headers

Complete Article Headers

X-Google-Thread: 114713,dc736a8182a7d6d9
X-Google-Attributes: gid114713,public
X-Google-Language: Japanese,JIS
Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!newsfeed.stanford.edu!newsfeed.news.ucla.edu!newsfeed.media.kyoto-u.ac.jp!oix.u-ryukyu.ac.jp!u-ryukyu.ac.jp!ie.u-ryukyu.ac.jp!not-for-mail
From: kono@ie.u-ryukyu.ac.jp (Shinji KONO)
Newsgroups: fj.sci.physics
Subject: Re: 量子コンピュータって実 用性があるの？
Date: Fri, 13 Aug 2004 02:58:16 +0000 (UTC)
Organization: Information Engineering, University of the Ryukyus
Lines: 39
Message-ID: <3990192news.pl@insigna.ie.u-ryukyu.ac.jp>
References: <cfe605$s1c$1@news.jaipa.or.jp> <86isbpz15h.wl@soro1.cc.hokudai.ac.jp> <cfenic$11tn$1@news.jaipa.or.jp>
    <86fz6tyojb.wl@soro1.cc.hokudai.ac.jp> <cfetuh$13l6$1@news.jaipa.or.jp> <411b144b.6989%katoh@pop12.odn.ne.jp> <cfh2cs$1k8f$1@news.jaipa.or.jp>
    <040813113421.M0207444@flame.hirata.nuee.nagoya-u.ac.jp>
NNTP-Posting-Host: insigna.ie.u-ryukyu.ac.jp
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-2022-jp"
Content-Transfer-Encoding: 7bit
X-Trace: naha.ie.u-ryukyu.ac.jp 1092365896 26505 133.13.48.71 (13 Aug 2004 02:58:16 GMT)
X-Complaints-To: news-admin@ie.u-ryukyu.ac.jp
NNTP-Posting-Date: Fri, 13 Aug 2004 02:58:16 +0000 (UTC)
X-Image-URL: http://www.ie.u-ryukyu.ac.jp/~kono/skono.gif
Fcc: send
X-Newsreader:  news.pl,v 1.11 2003/10/08 11:51:01 
Content-ID: <10491.1092365898.1@insigna.ie.u-ryukyu.ac.jp>

Reply to Parent Message

Article View: fj.sci.physics

Re: 量子コンピュータって実 用性があるの？

Re: 量子コンピュータって実用性があるの？