関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.1M
各ページのテキスト
量子コンピュータの シミュレーション C++ MIX / gyu-don 1
自己紹介 gyu-don : x.com/beef_and_rice 数理最適化/量子コンピューティング系ソフトウェアエンジニア ←ブロックチェーンR&D ← 画像処理/NLP R&D ← Windowsソフト開発 ←プラントエンジニア (計装制御設計・現地試運転) 最近: 個人でDGX Sparkを注文したが、出荷が遅れている上に、 微妙な性能のベンチマークが出回ってきていて泣いています (教訓: メモリ帯域幅を軽視してはいけない) IBM Quantumで学ぶ量子コンピュータ (2021・秀和システム ) 2
今日話すこと 理想的な量子コンピュータを通常のコンピュータで模倣する 「状態ベクトルシミュレーション」の実装と、その前提知識を最短ルートで話す （全く or ほとんど）話さないこと ● ● ● 量子力学や線形代数学 量子コンピュータを用いたアプリケーションやアルゴリズム 量子コンピュータのハードウェア ○ ● NISQ, Early-FTQC, FTQC などの現状の話 ノイズと量子誤り訂正について 3
量子コンピュータの概要 量子ゲート方式は量子回路を計算モデルとする方式 量子アニーリング方式はイジングモデルを計算モデルとする方式(今回扱わない) 古典コンピュータ 量子ゲート方式 量子アニーリング方式 計算モデル チューリングマシン (TM) 量子回路モデル イジングモデル 汎用性 (計算可能性) チューリング完全 (TC) NAND相当のものが作れる 特定の数式の最小化 に特化 計算能力 (計算複雑性) TMと同等 (量子回路単発では TCではない) (ただしテープ長は有限 ) 問題によっては、 (古典)TMよ りも指数関数的に高速 定量的な比較が困難 元々は、計算量の意味で古典コンピュータを超えられることに関心を持たれていたが、 ハードウェア開発が進んだ近年は、経過実時間の意味で高速になるかの関心も高まっている 4
量子コンピュータは何ではないか? ● 「超高速なCPU」ではない ○ ● NP完全な問題を解く装置ではない ○ ○ ● NP完全な問題は量子コンピュータでも多項式時間で解けない (と信じられている ) 組合せ最適化の話では、ヒューリスティック解法のことを言っている ■ 全探索と比較して「スパコンでも解けない」はデマ 「すべての状態を重ね合わせて計算」は誤解を生む ○ ○ ● 1つ1つの命令を実行する速度は、 CPUよりも何桁も遅い 取りうるすべてのビット列を重ね合わせた入力を計算できるのは事実 測定をすると重ね合わせ状態が壊れて、ランダムに 1つの状態のみ選ばれる ■ 単純に重ね合わせただけでは、入力をランダムに選んで計算するのと変わらない 古典コンピュータを完全に置き換えるものではない ○ 日常の計算のほとんどは量子コンピュータでやるメリットがないので、補助的に使うのが有効 5
量子回路モデル 論理回路（配線に論理ゲートをかける)のように、量子ビットに量子ゲートをかける 横線で量子ビットを表し、図形で量子ゲートを表現し、図視する ほとんどのハードウェア実装では、実際には回路は作らない （例: マイクロ波を打ち込むことで、量子ビットにゲートが適用された状態になる） 量子回路は時系列的に並んだ操作を図で表したものと考えられる 6
量子アルゴリズム 古典コンピュータでは実現不可能な高速化を達成する「量子アルゴリズム」について とても長くなるので今日は話さない ←Zenn に書きました 量子コンピューターでRSA-2048を解くためには？ (2025年5月版) 機械学習や線形代数学に詳しい人に向けた 量子回路入門記事→ 量子カーネル法 7
量子コンピュータのシミュレーション手法 量子コンピュータは通常のコンピュータでシミュレーションできるが 制限があるか、計算がとても重い（そうでないと量子コンピュータいらない） 状態ベクトル シミュレーション スタビライザー シミュレーション テンソルネットワーク シミュレーション 原理 内部状態(=状態ベクトル)の全 体を計算 ゲート操作の群論的な 性質を利用 状態ベクトルを低ランクで表 現し計算量削減 利点 実装が素朴で、苦手な回路が 他実装より少ない 計算時間、メモリ使用量 が多項式的 状態ベクトルよりも量子ビッ ト数が増やしやすい 欠点 使用メモリ、ゲートごとの計算時 間が O(2量子ビット数) 一部のゲートのみ対応 実装が複雑 有名な実装 qiskit-aer, qulacs, cuQuantum Stim Quimb, cuQuantum 他にもdecision treeベースのものなどがある 8
状態ベクトル
量子コンピュータの内部状態 = 長さ2量子ビット数の複素数配列
古典コンピュータ→最小の情報単位「ビット」は, 0か1のいずれかを指す
量子コンピュータ→量子ビットは, |0〉, |1〉 と、その重ね合わせ状態を指す
量子ビットがたくさんだと|000…0〉, |000…1〉, …, |111…1〉 の重ね合わせ
|...〉 で示されているものはベクトル、特に |bbb…b〉 は単位ベクトルみたいなもの
例えば3次元座標 ax⃗ + by⃗ + cz⃗ を double v[3] = {a, b, c}; とするのと同様、
内部状態 complex<double> *v 各単位ベクトルの係数を入れる
めっちゃメモリを食う。
倍精度だと、20 qubits → 16MB, 30 qubits → 16GB, 32 qubits → 64GB, 36 qubits → 1TB
（算術演算を実装すると、とても苦しい）
9
1量子ビットゲートと2量子ビットゲート n量子ビットゲートは 2n × 2n 行列として表現される いくつかの1量子ビットゲートと、CNOTゲートがあればどんなゲートも作れる a|0〉+ b|1〉 u0 u 1 u2 u 3 (au0+bu1)|0〉+ (au2+bu3)|1〉 出典: https://en.wikipedia.org/wiki/Quantum_logic_gate#/media/File:Quantum_Logic_Gates.png by Rxtreme 10
状態ベクトルの測定 ある状態が測定される確率 = 係数(配列の値)の絶対値の2乗 状態ベクトルは、実際に測定された値に変化 サンプリングするなら、累積和と二分法か, Walker’s alias methodを使う 実際の量子コンピュータでは、量子回路をはじめから動かしてサンプリングが必要 (内部状態を直接 見たり、複製したり、できないため)だが、 状態ベクトルシミュレーションでは状態ベクトルを持っているので効率よくサンプリングできる 11
状態ベクトルへのゲートの適用
// 擬似コード
void apply_gate(
complex<double> *v,
unsigned int n_qubits,
unsigned int apply_to,
complex<double> u[4]
){
for (bbbb = 0; bbbb < (1<<(n_qubits - 1)); bbbb++) {
auto mask_low = (1<<apply_to) - 1;
auto mask_high = ~mask_low;
auto bb0bb = ((mask_high & bbbb) << 1) | (mask_low & bbbb);
auto bb1bb = bb0bb | (1<<apply_to);
auto v0 = v[bb0bb];
auto v1 = v[bb1bb];
v[bb0bb] = u[0] * v0 + u[1] * v1;
v[bb1bb] = u[2] * v0 + u[3] * v1;
}
}
12
実装のシンプルさと、やり込み要素の多さ とっつきにくいが、実装はそこまで高難易度ではない しかし、速くしようと思ったら、いくらでもやることがある ● 並列化 : シングルノードでは簡単 ○ ○ ○ ● マルチノードだと、ノード間でメモリスワップが頻発 量子ビットを並べ替えて同じノード内で処理できるゲートを増やすことで対処 all-to-allの入れ替えを避ける、チャンク化をするなども有効 量子回路の最適化、ゲートの合体 ○ ○ パターンマッチや代数的な方法で、量子回路中のゲート数自体を削減 事前計算で複数のゲートを合体させ、ゲート数を削る ■ 多量子ビットゲートは計算コストが大きく、ゲート数削減とのトレードオフ 13
まとめ ● 量子コンピュータを力技でシミュレーションする方法について解説した ○ ● ● ● メモリをバカ食い。普通の PCでは30量子ビット程度が現実的 シンプルだが、やり込み要素が大きく、数値計算屋さんには面白いはず アプリケーションやアルゴリズム→最後のディスカッションパートで話しましょう 量子コンピューティングオタクを増やしたい gyu-don : x.com/beef_and_rice 14