NTTは10月31日、量子計算機が古典計算機よりも高速に解けることを示す新たなアルゴリズムを世界で初めて考案したと発表した。この新たな量子アルゴリズムは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子計算機の優位性（量子優位性）を示すものだという。1994年のShorの素因数分解アルゴリズム以来の約30年ぶりの本質的に新しいアイディアに基づいたものだという。これまで量子計算機による高速なアルゴリズムが知られていなかった種類の問題に対しても、高速な量子アルゴリズムが発見されることが期待できるとしている（NTTリリース、TECH+）。
量子回路図 (スコア:1)
ショアのアルゴリズム以降とは大きく出たな。
1994年以降だと1996年のグローバーのアルゴリズムとか面白いのも多少はあると思うが、2年なら誤差だし実際「本質的に新しいアイディア」なんだろう。
量子計算機のアルゴリズムってそもそも数が少ない。
だからまぁすごい訳だが、実用は今でもまだ先。
量子計算機は一応授業受けたけど、説明読んでもなんだかよく分からない。
具体的にどんな関数(誤り訂正符号にもなってる…？)の探索がどれくらい速くなるのかランダウの記号とかで書いてくれないとよく分からん(まぁNPがBQPとかだろうけど)。
アブストラクトはもう少し具体的だけど分かるような分からんような。
とりあえず量子回路図はarXiv [arxiv.org]の29ページに一例らしきものが載ってるから雰囲気は掴める。
いつ見てもシンプルだからランダム生成でたまたま有用なアルゴリズムを見つけられないかと思ったりするけど、複雑な計算は大きな四角にまとめてあるだけだろうから無理なんだろう多分。
長くはないけど全文まで読む気はしない。
実際言う通りならこのアルゴリズムは今授業を受けたら最後の方で説明されるんだろうな。
古本で20年くらい前の科学系の解説本読んだら現代までの書かれていない続きが気になるパターンあるよね。
Re:量子回路図 (スコア:1)
> 長くはないけど全文まで読む気はしない。
これさえ書いときゃ、本当に詳しい人にどんなツッコミ受けても無敵だもんな。
「たまたまボクの読んだところに書いてなかったー。読んだら絶対理解できてたー。」
Re: (スコア:0)
そのうえで長文の中身は授業の思い出という…
愚者は教えたがり、賢者は学びたがる
Re: (スコア:0)
「わからない」と書いてあるのにマウントされたと感じるようではもう長くはないですね。来年あたりには死んでるかも。
Re: (スコア:0)
ん？マウントの話はどこからでてきたの？
Re: (スコア:0)
量子計算機の能力を非決定性チューリングマシンと同等と勘違いしてる人が結構いる気がするんだよな
Re: (スコア:0)
「量子計算機の能力」という点ではそう間違ってないかもね。取り出せないだけで。
例えば「全人類の死後の意識をシミュレーション上で継続させる」ってんなら量子計算機は古典計算機ではほぼ一人分の規模で済む。
Re: (スコア:0)
能力はあるが取り出せないってナンセンスでしょ。
「死後の意識をシミュレーション上で継続させる」ってどういうこと？
SFと科学を勘違いしてない？
Re: (スコア:0)
SF的だけど「ビッグクランチの場合は終わりに近づくにつれ計算能力が増えていくので～」みたいな文脈では割と出て来る話だよ。
科学なのかは知らないけど科学者が語る一般向けの話でもこういうの多いし別に良いでしょ。
一応脳の振る舞いは概ね古典物理に従っていると言われているのと、外観上意識があるような振る舞いをするなら意識があるってのを前提にしている。違ったら無理。
宇宙論で言えば宇宙の事象的地平面の向こうは観測できないけど存在してるでしょ。
観測できなくても存在するってのはそんなおかしくない。
「計算機」として見るとナンセンスかもしれないが。
あと量子力学の文脈で量子状態を「観測できない」っていうのは間違いなく誤った言い方だけど。
Re: (スコア:0)
科学者と言ってもピンからキリまでいるわけで、中には詐欺師まがいの輩もいる。
特に量子計算機界隈にはそういうのが多い。
意識について語る前に意識を定義して欲しいものだね。
Re: (スコア:0)
意識とは何か、を科学的にきちんと説明しきらないと、この話に関してSFと科学の境界線を引くのは無理ですよ。
今までの観測結果と矛盾しない説なら何であれ、そうかも知れないし、そうでないかも知れない、としか言いようがない。
例えば、「意識というものは、人や猫、(以下、既知の種類の生き物の名前を全部並べる)、の脳や神経に宿るもので」と極端に狭く定義しても、それ以外に意識を持ってそうな何かを知らない以上、「その定義は間違ってる」とは言い切れない。
同様に逆に「意識というのは十分に複雑なプログラムの類が動いていて、自分という概念を持っ
Re: (スコア:0)
「意識というのは十分に複雑なプログラムの類が動いていて、自分という概念を持っている状態」というのが定義ですか。
「私は自分という概念を持っている」と繰り返すだけの
一千万行くらいのスパゲッティプログラムが動くロボットは意識を持っていることになるな。
Re: (スコア:0)
うんそう。程度の差はあれ、あるかも知れない。明確に否定できるだけの論拠を示しようが無いですしね。お前に意識があると言うことを証明しろと言われても困るのと同程度には。
SF作品だと、どの辺りに線引きをして人権を与えるか、みたいな話もありますよ。もうすぐSFから現実になっていく問題。
Re: (スコア:0)
チューリングテストとか中国人の部屋とか議論はあったけど、 外部から判断して自然人と区別がつかないなら('それ'が持ってる知識も含めて) 意識を持っていると見なしてよいのではないかと思う 機械生命でもレプリカント
Re: Re: Re:量子回路図 (スコア:2)
自然人以外も意識を持ってるかもしれませんよ。サルとかネコとかカラスとかたまごっちとか。
Re: (スコア:0)
法人が意思を持つということにして、自然人としての経営者が免責されるようになるディストピアを思いついた。
あれ、もしかして今も割とそう？
Re: (スコア:0)
> 説明読んでもなんだかよく分からない。
> 長くはないけど全文まで読む気はしない。
はて？
「俺の中途半端な知識でわかるところだけ拾い読みしたけど理解できなかった。俺が授業で習った範囲だけで理解できるように書かなかった奴が悪い」ってことかな？
Re: (スコア:0)
有限環が合成数なのかみたいな、平たく言えば輪っかに波を立てて共鳴が起きるかどうか調べるという問題は量子の波動性と相性がよさそうだなと感覚的にはわかるのですが、実は構造とか関係なかったんですかね。
新たな解法を見つけたというよりは (スコア:0)
量子計算機で高速で古典計算機では低速になる問題を見つけたという話だな
Re: (スコア:0)
違う。
「量子計算機で高速で古典計算機では低速になる問題を見つけ」るための方法を、
「出力が周期性のような『構造』を持たない関数」に対しても示した、というもの。
Re: (スコア:0)
そもそも「量子計算機で高速で古典計算機では低速になる問題が存在する」こと(BPP≠BQP)って示せたんだっけ?
Re: (スコア:0)
今見つかっている古典的計算機を用いたベストなアルゴリズムより早く解ける事を示せば、とりあえず実用に使える。
使いものになるなら、数学的な厳密な証明が無くてもそれでいいというニーズはある。
Re: (スコア:0)
P≠PSPACEも示されていないはずなのでBPP≠BQPは示せませんね。(P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE)
今回のものも、古典計算機で計算が難しい問題が存在することは認めましょうという仮定(P≠NP)を置いたときにBPP≠BQPが導かれるというものです。
この前ストーリーに出てた (スコア:0)