パスワードを忘れた? アカウント作成
15988395 story
NTT

NTT、量子計算機で古典計算機より高速に解くための新たなアルゴリズムを考案 25

ストーリー by nagazou
考案 部門より
NTTは10月31日、量子計算機が古典計算機よりも高速に解けることを示す新たなアルゴリズムを世界で初めて考案したと発表した。この新たな量子アルゴリズムは、出力が周期性のような「構造」を持たない関数を用いた問題に対し、検証可能な量子計算機の優位性(量子優位性)を示すものだという。1994年のShorの素因数分解アルゴリズム以来の約30年ぶりの本質的に新しいアイディアに基づいたものだという。これまで量子計算機による高速なアルゴリズムが知られていなかった種類の問題に対しても、高速な量子アルゴリズムが発見されることが期待できるとしている(NTTリリースTECH+)。
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2022年11月08日 7時49分 (#4356141)

    ショアのアルゴリズム以降とは大きく出たな。
    1994年以降だと1996年のグローバーのアルゴリズムとか面白いのも多少はあると思うが、2年なら誤差だし実際「本質的に新しいアイディア」なんだろう。
    量子計算機のアルゴリズムってそもそも数が少ない。
    だからまぁすごい訳だが、実用は今でもまだ先。

    量子計算機は一応授業受けたけど、説明読んでもなんだかよく分からない。
    具体的にどんな関数(誤り訂正符号にもなってる…?)の探索がどれくらい速くなるのかランダウの記号とかで書いてくれないとよく分からん(まぁNPがBQPとかだろうけど)。
    アブストラクトはもう少し具体的だけど分かるような分からんような。
    とりあえず量子回路図はarXiv [arxiv.org]の29ページに一例らしきものが載ってるから雰囲気は掴める。
    いつ見てもシンプルだからランダム生成でたまたま有用なアルゴリズムを見つけられないかと思ったりするけど、複雑な計算は大きな四角にまとめてあるだけだろうから無理なんだろう多分。
    長くはないけど全文まで読む気はしない。

    実際言う通りならこのアルゴリズムは今授業を受けたら最後の方で説明されるんだろうな。
    古本で20年くらい前の科学系の解説本読んだら現代までの書かれていない続きが気になるパターンあるよね。

    • by Anonymous Coward on 2022年11月08日 9時09分 (#4356180)

      > 長くはないけど全文まで読む気はしない。
      これさえ書いときゃ、本当に詳しい人にどんなツッコミ受けても無敵だもんな。
      「たまたまボクの読んだところに書いてなかったー。読んだら絶対理解できてたー。」

      親コメント
      • by Anonymous Coward

        そのうえで長文の中身は授業の思い出という…

        愚者は教えたがり、賢者は学びたがる

        • by Anonymous Coward

          「わからない」と書いてあるのにマウントされたと感じるようではもう長くはないですね。来年あたりには死んでるかも。

          • by Anonymous Coward

            ん?マウントの話はどこからでてきたの?

    • by Anonymous Coward

      量子計算機の能力を非決定性チューリングマシンと同等と勘違いしてる人が結構いる気がするんだよな

      • by Anonymous Coward

        「量子計算機の能力」という点ではそう間違ってないかもね。取り出せないだけで。
        例えば「全人類の死後の意識をシミュレーション上で継続させる」ってんなら量子計算機は古典計算機ではほぼ一人分の規模で済む。

        • by Anonymous Coward

          能力はあるが取り出せないってナンセンスでしょ。
          「死後の意識をシミュレーション上で継続させる」ってどういうこと?
          SFと科学を勘違いしてない?

          • by Anonymous Coward

            SF的だけど「ビッグクランチの場合は終わりに近づくにつれ計算能力が増えていくので~」みたいな文脈では割と出て来る話だよ。
            科学なのかは知らないけど科学者が語る一般向けの話でもこういうの多いし別に良いでしょ。
            一応脳の振る舞いは概ね古典物理に従っていると言われているのと、外観上意識があるような振る舞いをするなら意識があるってのを前提にしている。違ったら無理。

            宇宙論で言えば宇宙の事象的地平面の向こうは観測できないけど存在してるでしょ。
            観測できなくても存在するってのはそんなおかしくない。
            「計算機」として見るとナンセンスかもしれないが。
            あと量子力学の文脈で量子状態を「観測できない」っていうのは間違いなく誤った言い方だけど。

            • by Anonymous Coward

              科学者と言ってもピンからキリまでいるわけで、中には詐欺師まがいの輩もいる。
              特に量子計算機界隈にはそういうのが多い。
              意識について語る前に意識を定義して欲しいものだね。

          • by Anonymous Coward

            意識とは何か、を科学的にきちんと説明しきらないと、この話に関してSFと科学の境界線を引くのは無理ですよ。
            今までの観測結果と矛盾しない説なら何であれ、そうかも知れないし、そうでないかも知れない、としか言いようがない。

            例えば、「意識というものは、人や猫、(以下、既知の種類の生き物の名前を全部並べる)、の脳や神経に宿るもので」と極端に狭く定義しても、それ以外に意識を持ってそうな何かを知らない以上、「その定義は間違ってる」とは言い切れない。

            同様に逆に「意識というのは十分に複雑なプログラムの類が動いていて、自分という概念を持っ

            • by Anonymous Coward

              「意識というのは十分に複雑なプログラムの類が動いていて、自分という概念を持っている状態」というのが定義ですか。
              「私は自分という概念を持っている」と繰り返すだけの
              一千万行くらいのスパゲッティプログラムが動くロボットは意識を持っていることになるな。

              • by Anonymous Coward

                うんそう。程度の差はあれ、あるかも知れない。明確に否定できるだけの論拠を示しようが無いですしね。お前に意識があると言うことを証明しろと言われても困るのと同程度には。

                SF作品だと、どの辺りに線引きをして人権を与えるか、みたいな話もありますよ。もうすぐSFから現実になっていく問題。

              • by Anonymous Coward

                チューリングテストとか中国人の部屋とか議論はあったけど、 外部から判断して自然人と区別がつかないなら('それ'が持ってる知識も含めて) 意識を持っていると見なしてよいのではないかと思う 機械生命でもレプリカント

              • by goldenslamber (49013) on 2022年11月08日 20時48分 (#4356670)

                自然人以外も意識を持ってるかもしれませんよ。サルとかネコとかカラスとかたまごっちとか。

                親コメント
              • by Anonymous Coward

                法人が意思を持つということにして、自然人としての経営者が免責されるようになるディストピアを思いついた。
                あれ、もしかして今も割とそう?

    • by Anonymous Coward

      > 説明読んでもなんだかよく分からない。

      > 長くはないけど全文まで読む気はしない。

      はて?
      「俺の中途半端な知識でわかるところだけ拾い読みしたけど理解できなかった。俺が授業で習った範囲だけで理解できるように書かなかった奴が悪い」ってことかな?

    • by Anonymous Coward

      有限環が合成数なのかみたいな、平たく言えば輪っかに波を立てて共鳴が起きるかどうか調べるという問題は量子の波動性と相性がよさそうだなと感覚的にはわかるのですが、実は構造とか関係なかったんですかね。

  • by Anonymous Coward on 2022年11月08日 7時28分 (#4356134)

    量子計算機で高速で古典計算機では低速になる問題を見つけたという話だな

    • by Anonymous Coward

      違う。
      「量子計算機で高速で古典計算機では低速になる問題を見つけ」るための方法を、
      「出力が周期性のような『構造』を持たない関数」に対しても示した、というもの。

      • by Anonymous Coward

        そもそも「量子計算機で高速で古典計算機では低速になる問題が存在する」こと(BPP≠BQP)って示せたんだっけ?

        • by Anonymous Coward

          今見つかっている古典的計算機を用いたベストなアルゴリズムより早く解ける事を示せば、とりあえず実用に使える。
          使いものになるなら、数学的な厳密な証明が無くてもそれでいいというニーズはある。

        • by Anonymous Coward

          P≠PSPACEも示されていないはずなのでBPP≠BQPは示せませんね。(P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE)
          今回のものも、古典計算機で計算が難しい問題が存在することは認めましょうという仮定(P≠NP)を置いたときにBPP≠BQPが導かれるというものです。

  • by Anonymous Coward on 2022年11月09日 5時42分 (#4356797)
    基礎数学研究センタの成果なのかな?
typodupeerror

吾輩はリファレンスである。名前はまだ無い -- perlの中の人

読み込み中...