🕌

量子コンピュータの仕組み

に公開
量子コンピュータ
量子力学
暗号
pqc
QKD
idea

はじめに

現在広く利用されている暗号技術は、量子コンピュータの登場によって安全性が揺らぐ可能性があると指摘されています。この問題への解決策として二つのアプローチが注目を集めています。一つは、量子コンピュータでも解けない計算問題に基づいた「耐量子計算機暗号（PQC）」 です。もう一つは、量子力学の原理を利用する「量子暗号（QKDなど）」 です。

私はこれらの最先端の暗号技術に強い関心があり、独学で得た知識を体系的に整理するために、記事シリーズとしてまとめています。

本記事では、その問題の背景となる量子コンピュータの仕組みや計算手法を直感的に理解することに焦点を当てて整理していきます。

なお、PQCやQKD、従来の暗号技術について詳しく知りたい方は、以下の記事もあわせてご覧ください。

量子コンピュータの分類：計算モデルによる違い

量子コンピュータは、採用している計算モデルによっていくつかの方式に分けられます。特に注目されているのが、次の二つです。

  • 量子ゲート方式（量子回路型計算）

    超伝導量子ビットや冷却原子（中性原子）などを用いて開発が進められています。

    Shorアルゴリズム をはじめ、多くの量子アルゴリズムはこの方式で記述されており、将来的に暗号への影響が大きいと考えられています。

  • 量子アニーリング方式（断熱量子計算の一種）

    超伝導磁束量子ビットを用いて開発が進められています。

    量子力学の「断熱定理」を応用しており、 組合せ最適化問題 を効率的に解くことに特化した方式です。

量子ゲート方式の仕組みと計算の流れ

  • 量子ゲート方式における量子ビットの仕組み1

この方式の量子コンピュータでは、 情報(量子状態)は　物理量子ビット という物理的なデバイスに保存されます。物理量子ビットは 「0」と「1」の重ね合わせ の状態をとることができ、この性質こそが量子計算の高速性を支えるポイントです。

しかし、物理量子ビットは非常にノイズに弱く、振動や温度変化といったわずかな外乱でも誤動作を起こしてしまいます。この課題を克服するために、複数の物理量子ビットを組み合わせて論理量子ビットを構成します。さらに量子誤り訂正 2という技術を活用し、物理量子ビットに生じるエラーを検出・補正することで、安定した計算を実現しています。

論理量子ビットと量子ゲートを組み合わせることで、大規模で正確な量子計算が可能になります。その流れを整理すると次のようになります。

  • 量子ゲート方式における計算の流れ3

    1. 物理量子ビットのエンコーティング
      複数の物理量子ビットを組み合わせ、エラーに強い論理量子ビットを作ります。これは単なる冗長化ではなく、計算中もエラーを訂正しながら情報を保持できるよう設計されています。

    2. 論理量子ゲートの実行
      実際の計算は論理量子ビットに対して行われます。ただし、論理量子ゲートの操作は抽象的なもので、実際には多数の物理量子ゲートが連携して動作することで実現されています。

    3. エラー訂正の並行処理
      計算中にノイズが入ると、量子誤り訂正の仕組みがそれを検出します。必要に応じて一部の物理量子ビットを測定し、誤りの種類や位置を特定して修正します。複数の物理量子ビットを用いることで、互いにエラーを補い合える仕組みになっています。

    4. 測定
      計算が終わると、論理量子ビットを構成する物理量子ビットを測定し、最終的に「0」または「1」として結果を取り出します。

量子アニーリング方式の仕組みと計算の流れ

  • 量子アニーリング方式における量子ビットの仕組み4
    　
    量子アニーリング方式では、量子ゲート方式のような論理量子ビットは使いません。その代わりに、物理学でよく知られているイジング模型（磁石のスピンを表すシンプルな数理モデル）の原理を利用します。
    　　
    イジング模型では、格子上に配置されたスピン（小さな磁石)が互いに相互作用し、外部の磁場の影響を受けたりしながら、スピンが 上向き(↑) または 下向き(↓) の状態を取ります。全体の状態はスピンの向きの組み合わせで決まり、それに対応するエネルギー値(ハミルトニアン)が定義されます。

    このとき、エネルギーが最も小さい状態（基底状態）を見つけることは、そのまま 組合せ最適化問題の解を求めること と一致します。なぜなら、最適化問題の要素をイジング模型の構造に対応させることができるからです。

    組合せ最適化問題の要素 イジング模型への対応
    解 スピンの向き(↑↓の組み合わせ）
    目的関数 エネルギーが低いほど、「良い解」になるように設定
    制約条件 違反した解はエネルギーが高くなるように調整

  • 量子アニーリング方式における量子コンピュータの計算の流れ

    1. 問題のモデル化
      解きたい最適化問題を、量子ビット間の相互作用として表現します。
      エネルギーが低いほど「良い解」、高いほど「悪い解」となるように設計し、スピンの数を問題の変数の数に対応させます。

    2. 初期状態の設定
      すべての量子ビットに対して、スピンの向きとは垂直な方向に外部磁場を加えます。
      これにより量子的な揺らぎが生じ、各スピンは「上向き」と「下向き」の重ね合わせ状態になります。
      初期段階では全ての解候補が均等に扱われています。

    3. アニーリングの実行
      外部磁場を時間をかけてゆっくり弱めていきます。
      このとき、断熱定理に従って量子ビットは常に最も低いエネルギー状態を保ちながら変化し、最適な状態へと収束していきます。

    4. 最終状態の測定
      アニーリングが完了した時点で量子ビットを測定します。
      量子ビットは最もエネルギーが低い状態に落ち着いており、そのスピンの組み合わせが問題の 最適解 となります。

暗号を脅かす量子アルゴリズム

現在広く使われている公開鍵暗号（RSA暗号など）は、大きな数を素因数分解することが非常に難しいという性質に基づいて安全性が保たれています。しかし、量子コンピュータの発展により、この素因数分解を効率的に行えるアルゴリズムが現実味を帯びてきました。

ここでは、その代表的な手法としてShorアルゴリズムとQUBO（Quadratic Unconstrained Binary Optimization、組み合わせ最適化） を紹介します。

Shorアルゴリズム5

Shorアルゴリズムは、量子ゲート方式の量子コンピュータで実行される素因数分解用の量子アルゴリズムです。

大まかな流れは以下の3ステップです。
　
ステップ1 ： 位相の特定
素因数分解したい数 N（例：15）に対してランダムな数 x（例：7）を選びます。
量子コンピュータを使って、x に対応する特別な数 r（位相）[1]を見つけ出します。
ステップ2 ： 位相rの検証
見つけた位相rが 偶数 であり、かつx^{r/2}+1がNで割り切れないかを確認します。条件が満たされない場合は、別のxを選び、再度位相を探索します。
ステップ3 ： 因数の計算
条件を満たすrが得られたら、従来のコンピュータで簡単に計算が可能です。

gcd(x^{r/2}−1,N),gcd(x^{r/2}+1,N)　　(gcdは最大公約数)

を計算すると、高い確率でNの因数を見つけることができます。

具体例

  • N=15、x=7の場合、量子コンピュータr=4を見つけたとします。

（7^4（＝2401） mod 15 = 1）

次に 7^2=49を計算し、gcd(49-1,15)=gcd(48,15)=3
よって、15の素因数の一つである 3 が見つかります。

このように、Shorアルゴリズムは量子コンピュータの力を使って「位相」を高速に特定することで、素因数分解を効率的に実行できます。

QUBO

QUBOは、組合せ最適化問題の形式の一つで、量子アニーリング方式の量子コンピュータが得意とする問題形式です。

素因数分解も QUBO 形式に変換することで量子アニーリングで解くことが可能です。
具体的には、分解したい N に対応する ハミルトニアン(エネルギー関数) を定め、エネルギーが最小となる状態を探索することで、素因数を見つけます。

量子アニーリングは「エネルギー最小化問題」を解く手法であるため、素因数分解を QUBO 形式に落とし込むことで量子アニーリングで解ける、という仕組みです。

量子コンピュータの現状と今後の展望

ここまで、量子コンピュータの計算モデルや仕組み、従来の暗号を破る可能性のあるアルゴリズムについて紹介しました。ここでは、量子コンピュータの実用化がどの程度現実的か、開発の段階について説明します。

量子コンピュータ自体は「悪」ではなく、むしろ大きな可能性を秘めています。その高い計算能力を活かすことで、医療や産業などさまざまな分野で高度な分析や技術革新をもたらすことが期待されています。

性能による量子コンピュータの分類

現在の量子ゲート方式の量子コンピュータは、性能によって大きく二つの段階に分類できます。

  1. NISQ（Noisy Intermediate-Scale Quantum）デバイス

    搭載される物理量子ビットが数十〜数百程度で、計算中のノイズによるエラーが頻繁に発生します。そのため、量子誤り訂正や大規模な計算を行うには不十分な性能の量子コンピュータです。

  2. FTQC（Fault-Tolerant Quantum Computation)デバイス

    量子誤り訂正などを用いてノイズやデコヒーレンス[2]の影響を抑え、大規模かつ長時間の計算が可能な量子コンピュータです。
    　
    現在、実用化されている量子コンピュータはすべてNISQデバイスです。研究者たちは、FTQC の実現に向けて開発を進めています。一方で、NISQ と FTQC の中間的な性能でも、従来のコンピュータでは困難な計算が可能となる場合があります。特に暗号解読に特化した量子コンピュータ（CRQC：Cryptography-Related Quantum Computer）が登場する可能性も指摘されています。

性能を高めるための具体的な課題

  • 物理量子ビット数の増加

    FTQCには、数百万個以上の物理量子ビットが必要とされています。これは、量子誤り訂正によってノイズに強い論理量子ビットを構成するためです。そのため、ハードウェアの大規模化が不可欠です。

  • ゲート操作の正確性の向上

    量子ゲートは、量子ビットの状態を操作する装置です。操作にわずかな誤差があると計算に影響します。物理システムの制御精度を高め、ゲート操作の忠実度を向上させることが重要です。

  • コヒーレンス時間の延長

    コヒーレンス時間とは、量子ビットが量子状態を安定して保てる時間のことです。時間が長いほどノイズの影響を受けにくく、複雑な計算が可能になります。極低温環境の維持や量子ビット素材の改良により、延長が目指されています。

  • 量子ランダムアクセスメモリ（QRAM）の実現

    QRAM は量子ビットの重ね合わせ状態を利用してメモリ内のデータに同時アクセスする技術です。従来のメモリではデータごとにアクセスを繰り返す必要がありますが、QRAM では複数のアドレスに同時にアクセスでき、一度に複数のデータを取得可能です。

世界の取り組み

世界各国で、政府機関や企業、大学が大規模な投資と研究開発を進めています。

GoogleやIBMといった巨大IT企業は、独自の量子コンピュータを開発し、量子ビット数の増加、実行可能ゲート数の増加や、エラー率の低減に取り組むとともに、量子コンピュータをクラウドサービスとして提供し、誰でも利用できる環境を整備しています。日本でも、量子コンピュータのハードウェア開発や量子アルゴリズムの研究が精力的に進められています。

量子コンピュータは、従来のコンピュータでは困難な複雑な計算を効率的に行える能力を持つため、多くの分野で新しい可能性を拓くことが期待されています。しかし一方で、現在の暗号技術の安全性の根拠となっている計算問題も、量子コンピュータによって解かれる可能性があります。そのため、量子コンピュータでも安全に扱える計算問題に基づいた新しい暗号技術の開発が求められています。

量子コンピュータの具体的な計算手法やアルゴリズムについては、私自身も現在学んでいる最中です。学びを深めつつ、今後の記事で詳しく紹介していく予定です。

  1. https://qsw.phys.s.u-tokyo.ac.jp/assets/files/20220907_okubo.pdf
  2. https://global.fujitsu/ja-jp/technology/key-technologies/news/ta-fault-tolerant-quantum-computation-20240515
  3. https://www.cryptrec.go.jp/exreport/cryptrec-ex-3005-2020.pdf
  4. https://www.msiism.jp/article/quantum-annealing-for-combinatorial-optimization.html
  5. https://www.msiism.jp/article/quantum-shor-algorithm.html
脚注

  1. 位相 r：x^1 , x^2 , x^3 ,…とxを次々に掛けたとき、その結果をNで割った余りがはじめて1になる、その掛けた回数rのことです。この位数を、量子コンピュータは驚くほど速く見つけることができます。 ↩︎

  2. デコヒーレンス：量子の重ね合わせの状態が相互作用によって失われてしまう現象。 ↩︎

Discussion