Fixstars Corp. · TSE:3687
Fixstars — Technical Presentation (2021)
29 slides from Fixstars's technical presentation, Sep 14, 2021
Slide 1: 一次元アーキテクチャにおける量子ビット割り当て問題
一次元アーキテクチャにおける 量子ビット割り当て問題 東京大学大学院 情報理工学系研究科 修士1年 内藤 壮俊 Twitter: @hamburg_soshun
Slide 2: 問題設定
問題設定 2
Slide 3: 量子ゲート型計算機
量子ゲート型計算機 量子ビットがゲートを通過 → 状態変化により計算を行う 量子回路の一例 量子回路はU3ゲートとCXゲートに展開可能 U3ゲート：1ビットの状態を任意に操作 CXゲート：2ビット間でXOR演算を行う 3
Slide 4: 量子ビット割り当て問題
量子ビット割り当て問題 設計図上の「論理ビット」とデバイス上の「物理ビット」を対応させる問題 CXゲートを作用させる物理ビットは隣り合っている必要がある SWAPゲートを使えば論理ビットの交換が可能．しかし，エラー率が高いため あまり使いたくない ＜設計図＞ ＜デバイス＞ 4
Slide 5: 量子ビット割り当て問題
量子ビット割り当て問題 設計図上の「論理ビット」とデバイス上の「物理ビット」を対応させる問題 CXゲートを作用させる物理ビットは隣り合っている必要がある SWAPゲートを使えば論理ビットの交換が可能．しかし，エラー率が高いため あまり使いたくない ＜設計図＞ ＜デバイス＞ 5
Slide 6: 先行研究
先行研究 “A QUBO formulation for qubit allocation" (2020) [1] Bryan Dury and Olivia Di Matteo エラー率と回路の深さを考慮して，QUBOの係数を設定 論理ビットの初期配置を最適化 ダイナミックな並び替えは考慮せず 6 [1] https://arxiv.org/abs/2009.00140
Slide 7: 今回扱いたい問題
今回扱いたい問題 初期配置だけでなく，並び替え全体を最適化する問題をAmplifyで解く 古典的解法では，𝑶 𝑴 ⋅ 𝑵! 𝟐 の計算量 回路の幅 𝑁 7 回路の深さ 𝑀
Slide 8: | Fe ae . ee
| Fe ae . ee
Slide 9: バイナリ変数を用いた定式化
バイナリ変数を用いた定式化 論理ビットの並び替えを， 𝑀𝑁 2 個のバイナリ変数で表現 one-hot 制約 物理ビットに関する one-hot 制約 論理ビットに関する one-hot 制約 CXゲートによる制約 作用させる物理ビットは隣り合っていなければならない 9
Slide 10: バイナリ変数を用いた定式化
バイナリ変数を用いた定式化 コスト = SWAPゲートの個数 厳密には，コストは 4次式 で表される 一応，補助変数を追加すれば定式化が可能 しかし，探索空間が広すぎたせいか上手くいかなかった... 10
Slide 11: バイナリ変数を用いた定式化
バイナリ変数を用いた定式化 コスト = SWAPゲートの個数 厳密には，コストは 4次式 で表される 一応，補助変数を追加すれば定式化が可能 しかし，探索空間が広すぎたせいか上手くいかなかった... コストを 2次式 で近似する作戦に 補助変数は不要になり，モデルの規模は 𝑂 𝑀𝑁 3 に 11
Slide 12: 実行時間の比較
実行時間の比較 1.0E+18 実行推定時間 (秒) 1.0E+12 古典的解法 1.0E+06 1 Amplify解法 1.0E-06 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 量子ビットの個数 N 12
Slide 13: 実行時間の比較
実行時間の比較 1.0E+18 100京倍 実行推定時間 (秒) 1.0E+12 古典的解法 1.0E+06 の高速化 1 Amplify解法 1.0E-06 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 量子ビットの個数 N 13
Slide 14: コストの比較
コストの比較 古典的解法 (低速・最適解) VS Amplify解法 (高速・近似解) 小規模な回路 → 最適解にほとんど一致 中規模な回路 → パラメータ調整で対処可能 それぞれの解法におけるコストの平均値 𝑁 3 4 5 6 古典的解法 (M = 5) 0.6 1.4 2.1 4.1 Amplify解法 (M = 5) 0.6 1.4 2.1 4.5 古典的解法 (M = 20) 3.8 13.0 15.0 24.9 Amplify解法 (M = 20) 3.8 13.1 18.9 34.0 14
Slide 15: アプリへの応用
アプリへの応用 15
Slide 16: 量子回路の描画機能
量子回路の描画機能 量子回路が描画されたアプリ画面の例 GUIアプリを実装 量子回路をリアルタイムで描画 16
Slide 17: 量子回路の描画機能
量子回路の描画機能 量子回路が描画されたアプリ画面の例 GUIアプリを実装 量子回路をリアルタイムで描画 作業の様子が一目でわかる！ 17
Slide 18: Amplifyの呼び出し機能
Amplifyの呼び出し機能 Amplify解法 実行結果の例 パラメータ調整 + Amplify解法の実行 良い解が見つかるまで調整が可能 18
Slide 19: Amplifyの呼び出し機能
Amplifyの呼び出し機能 Amplify解法 実行結果の例 パラメータ調整 + Amplify解法の実行 良い解が見つかるまで調整が可能 作業の効率化につながる！ 19
Slide 20: OpenQASMを用いた入出力
OpenQASMを用いた入出力 「OpenQASM」という言語を使って読み込み + 書き出しが可能 多くのソフトウェアと互換性がある 本アプリの位置付け 設計図 実機ハード 作成アプリ ウェア 実機搭載 の検討 ゲート情報 の翻訳 回路 見直し 20
Slide 21: アピールポイント
アピールポイント 問題設定 実験・評価 アプリへの応用 「量子ビット割り当て 近似により探索空間を 回路のリアルタイム 問題」をAmplifyで解く 削減 → 性能向上 描画 → 作業の効率化 「回路全体の最適化」 圧倒的な高速化に成功 他アプリとの互換性 は，まだ誰も挑戦して いない 新規性・進歩性 技術力 実用性 21
Slide 22: 補助スライド
補助スライド 22
Slide 23: 問題設定の詳細
問題設定の詳細 CXゲートを含むそれぞれのレイヤーに対して，論理ビットの配置を決定する 全てのレイヤーで，CXゲートの物理的制約が満たされる必要がある レイヤー間に挿入するSWAPゲートの個数を減らしたい 1次元アーキテクチャの場合， SWAPゲートの個数は転倒数に等しい 転倒数 =「順番が入れ替わったペアの数」 23
Slide 24: バイナリ変数を用いた定式化
バイナリ変数を用いた定式化 各レイヤーにおける論理ビットは 0, 1, ⋯ , 𝑁 − 1 の並び替えとなる 𝑸𝒎𝒏𝒗 : 「レイヤー 𝑚 において，物理ビット 𝑛 は論理ビット 𝑣 に対応する」 𝑀𝑁 2 個のバイナリ変数が必要 one-hot 制約 「物理ビットは単一ビットのみに対応する」 : σ𝑁−1 𝑣=0 𝑸𝒎𝒏𝒗 = 1 「論理ビットは単一ビットのみに対応する」 : σ𝑁−1 𝑛=0 𝑸𝒎𝒏𝒗 = 1 CXゲートによる制約 作用させる物理ビットは隣り合っていなければならない ペナルティ関数 : σ…
Slide 25: コスト関数の定式化 (厳密解法)
コスト関数の定式化 (厳密解法) コスト = SWAPゲートの個数 = 転倒数 厳密に定式化が可能 隣り合うレイヤー 𝐴, 𝐵 間における，論理ビットの移動 𝐶 を考える 𝐶𝑖𝑗 = 1 ↔ 𝐴 𝑖 = 𝐵 𝑗 補助変数+制約の追加による定式化 𝑆𝑖𝑗𝑣 = 𝐴𝑖𝑣 ⋅ 𝐵𝑗𝑣 ↔ 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 = 3𝑆𝑖𝑗𝑣 + 𝐴𝑖𝑣 𝐵𝑗𝑣 − 2𝑆𝑖𝑗𝑣 𝐴𝑖𝑣 + 𝐵𝑗𝑣 𝐶𝑖𝑗 = σ𝑣 𝑆𝑖𝑗𝑣 𝑐𝑜𝑠𝑡 = σ0≤𝑖1 <𝑖2 <𝑁…
Slide 26: 厳密解法の実行結果
厳密解法の実行結果 出力結果のコストが大きすぎる or 解が見つからないという結果に．．． 探索空間の大きさに対して，制約を満たす組が少ないことが原因か 用いたバイナリ変数の合計 = log 2 探索空間の状態数 = 𝑀𝑁 3 + 2𝑀𝑁 2 − 𝑁 3 − 𝑁 2 1 log 2 解となる状態数 < log 2 𝑁! 𝑀 ≈ log 2 𝑀 𝑁 log 𝑁 − 𝑁 ほとんど全てが「ハズレ」だった 26
Slide 27: 転倒数の近似によるアプローチ
転倒数の近似によるアプローチ 性能向上のため，近似解法を採用して状態数を削減することに 最初に用意したバイナリ変数だけを使って，転倒数を2次で近似する 重回帰分析によるフィッティング，期待値による推定を行った 重回帰分析，期待値による転倒数の推定結果 （横軸が正しい値，縦軸が推定値） 2つの推定結果は，互いに一次関数の関係になっていた 2𝑁−2 𝑁−1 𝑁−2 [重回帰分析による推定結果] = N 期待値による推定結果 − 4 27
Slide 28: コスト関数の定式化 (近似解法)
コスト関数の定式化 (近似解法) 𝑖+𝑗 𝑖𝑗 期待値による推定結果 ≈ σ0≤𝑖,𝑗<𝑁 − ⋅ 𝐶𝑖𝑗 2 𝑁−1 2𝑁−2 𝑁−1 𝑁−2 重回帰分析による推定結果へ変換： y = 𝑥 − N 4 2𝑁−2 𝑖+𝑗 𝑖𝑗 𝑁−1 𝑁−2 → 転倒数 ≈ σ0≤𝑖,𝑗<𝑁 − σ𝑁−1 𝑣=0 𝐴𝑖𝑣 𝐵𝑗𝑣 − と書ける N 2 𝑁−1 4 レイヤー 𝑚, 𝑚 + 1 間においては， 𝐴𝑖𝑣 = 𝑸𝒎𝒊𝒗 , 𝐵𝑗𝑣 = 𝑸 𝒎+𝟏 𝒋𝒗 …
Slide 29: Amplify解法モデルの構成
Amplify解法モデルの構成 𝑁−1 𝑖+𝑗 −2𝑖𝑗 𝑐𝑜𝑠𝑡 = σ𝑀−2 𝑚=0 σ0≤𝑖,𝑗<𝑁 σ𝑁−1 𝑣=0 𝑸𝒎𝒊𝒗 𝑸 𝒎+𝟏 𝒋𝒗 𝑁 2 2 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡 = σ𝑀−1 𝑁−1 𝑁−1 𝑚=0 ቄσ𝑣=0 1 − σ𝑛=0 𝑸𝒎𝒏𝒗 + σ𝑁−1 𝑁−1 𝑛=0 1 − σ𝑣=0 𝑸𝒎𝒏𝒗 + one-hot 制約 σ 𝑎,𝑏 ∈ 𝐶𝑋−𝑔𝑎𝑡𝑒𝑠 σ 𝑖,𝑗 , 𝑖−𝑗 ≥2 𝑸𝒎𝒊𝒂 𝑸𝒎𝒋𝒃 ቅ…