量子コンピュータは、「全部を同時に試すから」速いのではない

「量子コンピュータは、全部の答えを同時に試すから速い」——新聞にも、大企業の公式解説にも、そう書かれてきました。しかしこの分野の第一人者は、自分のブログの看板に「量子コンピュータは、すべての解を並列に試すことで難問を瞬時に解いたりはしない」と常設しています。実は、重ね合わせで膨大な候補を「同時に持てる」ことは本物です。誤解は「同時に持てるなら、同時に読み出せる」という飛躍のほう——観測者が一度に得られる結果は1つだけで、素朴な総当たりの成功確率は「古典コンピュータと同じ」だと1997年の論文が計算しています。本当の速さの正体は、間違った候補の波を打ち消し、欲しい答えの波だけを残す「干渉の設計」。そして最大の驚きは、「量子並列性」という語を導入した1985年の論文自身が、"Unfortunately"(残念ながら)という言葉付きで「読み出せる結果は1つだけ」という限定を最初から書いていたことです。原論文を直読して確かめていきます。 ■ この動画で解ける3つの謎 ① 「全部を同時に試す」説明の、どこまでが本物なのか(前半は本物でした) ② では量子コンピュータは、本当はどうやって速くしているのか(答えは「波の消し方」です) ③ 「同時に計算」という説明は、どこから来たのか(出生地は1985年の論文——そして同じページに、意外な一文がありました) ■ 目次 00:00 「全部同時に試すんでしょ?」——あなたの記憶 01:21 第1章 2の300乗の夢 02:53 第2章 開けた瞬間、1つ 04:35 第3章 間違いを、消す 08:25 第4章 説明の出生地 11:03 夢の、どこまでが本物か 12:08 締め——きっかけをくれたコメント ■ この動画の作り方 この動画は、紹介する論文・一次資料を実際に読んで作っています。 引用は出典つき、確かめられなかったことは「分からなかった」と動画内で言います。 疑問に思ったことがあれば、コメントで聞いてください。出典ごとお答えします。 自然科学と哲学が好きな人間が、一人で作っています。本業のかたわら、論文や文献を読み漁るのが趣味で、 教科書の一行のウラ側を一次資料までめくりに行く番組です。 高評価とチャンネル登録は、無理にしなくて大丈夫です。本当に面白かったときだけ押してください。 面白くなかったら、どこがダメだったかコメントで教えてもらえるほうが助かります。次はそこを直します。 ■ この動画の主題について この動画は量子コンピュータの「計算原理(速さの説明)」の話です。ハードウェアの実用化時期や産業応用の予測は扱いません(参考: 米国科学アカデミーの2019年報告は、スケーラブルな量子コンピュータの実現時期について「予測するにはまだ早すぎる」と評価しています。その後の進展は各社・各機関の発表をご参照ください)。また、この動画は「量子コンピュータは大したことがない」という主張をしていません。誤解を訂正した先にある本当の仕組み(干渉の設計)は、俗説よりずっと面白い、というのがこの回の結論です。 ■ きっかけをくれた視聴者の方へ この回の企画は、E01(シュレディンガーの猫)のコメント欄に @imawanokiwami さんが書いてくださった長文の解説がきっかけです。ありがとうございました。 ■ 参考文献 Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 400, 97-117.(「量子並列性」の語を導入した論文。「並列に干渉する宇宙たち」の一節、"Unfortunately, at most one of these results is accessible in each universe."、「量子並列性は並列化可能なアルゴリズムの平均実行時間の改善には使えない」は、いずれも原論文を直読して確認) Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. STOC 1996.(電話帳探索のアルゴリズム。「成功する計算どうしは強め合い、それ以外はランダムに打ち消し合う」は要旨の文言。古典N/2回に対しO(√N)回) Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing, 26(5), 1510-1523.(素朴な並列総当たりの成功確率が「古典コンピュータと同じ」1/2^nであることの計算と、非構造探索のΩ(√N)下限。本編の「近道は無い」はこの電話帳型の探索についての定理です) Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484-1509.(素因数分解のアルゴリズム。第5章冒頭の「直接因数分解する代わりに、(元の)位数を求める」の宣言と、量子フーリエ変換による周期抽出を原論文で確認) Feynman, R. P. (1982). Simulating Physics with Computers. International Journal of Theoretical Physics, 21, 467-488.(量子計算のアイデアの大きな出発点の一つ。文脈は量子系のシミュレーション) Aaronson, S. Shtetl-Optimized(ブログ)https://scottaaronson.blog/(ヘッダーの常設文言...) National Academies of Sciences, Engineering, and Medicine (2019). Quantum Computing: Progress and Prospects.(実用化時期についての慎重な評価の出典) ※ 本編で引用した「同時に計算」型の説明の実例は、東京新聞デジタル(2022)の記事です(https://www.tokyo-np.co.jp/article/45... ソフトバンク公式ビジネスブログ 2023)。誤解の「広まり」を示す例として引用しており、執筆者を批判する意図はありません。魅力的な説明ほど、限定より先に広まる——それがこの回の主題です。 ※ 本編の電話帳探索で「二分探索を使えばいいのでは?」と思った方へ——二分探索はソート済みデータが前提です。グローバーの問題設定は「でたらめな順番」(=ソートという構造が無い)の探索で、ソート済みなら古典の二分探索(100万件で約20回)のほうがはるかに速い。量子の探索が効くのは構造の無い探索だけ——本編の「効く形の問題にだけ効く」はこの意味です。 ※ 本編の「多世界解釈」に関する記述は、ドイチュ自身の立場の紹介です。多世界解釈は量子力学の解釈の一つであり、物理学者の間で見解が分かれています。 ■ クレジット 音声:AquesTalk(株式会社アクエスト) BGM:「コミカル・ピチカート」「静寂の星空」「寂寞」/ 甘茶の音楽工房(https://amachamusic.chagasi.com/) 効果音:「ロゴアニメーション1」「金属タイトル表示3」/ 効果音ラボ(https://soundeffect-lab.info/) 立ち絵:たぬき式ゆっくり(https://tanukiyukkuri.github.io/tanuk...) この動画は東方Projectの二次創作です。