一次元アーキテクチャにおける量子ビット割り当て問題
東京大学大学院 情報理工学系研究科

修士1年
内藤 壮俊

Twitter: @hamburg_soshun

問題設定
2

量子ゲート型計算機

量子ビットがゲートを通過 → 状態変化により計算を行う

量子回路の一例



量子回路はU3ゲートとCXゲートに展開可能


U3ゲート：1ビットの状態を任意に操作



CXゲート：2ビット間でXOR演算を行う

3

量子ビット割り当て問題


設計図上の「論理ビット」とデバイス上の「物理ビット」を対応させる問題

CXゲートを作用させる物理ビットは隣り合っている必要がある

SWAPゲートを使えば論理ビットの交換が可能．しかし，エラー率が高いためあまり使いたくない＜設計図＞＜デバイス＞

4

量子ビット割り当て問題


設計図上の「論理ビット」とデバイス上の「物理ビット」を対応させる問題

CXゲートを作用させる物理ビットは隣り合っている必要がある

SWAPゲートを使えば論理ビットの交換が可能．しかし，エラー率が高いためあまり使いたくない＜設計図＞＜デバイス＞

5

先行研究
 “A QUBO formulation for qubit allocation" (2020) [1]Bryan Dury and Olivia Di Matteo[1]

エラー率と回路の深さを考慮して，QUBOの係数を設定



論理ビットの初期配置を最適化

ダイナミックな並び替えは考慮せず

https://arxiv.org/abs/2009.00140

6

今回扱いたい問題


初期配置だけでなく，並び替え全体を最適化する問題をAmplifyで解く



古典的解法では，𝑶 𝑴 ⋅ 𝑵! 𝟐 の計算量

回路の幅

𝑁

回路の深さ

𝑀

7

実装・評価8バイナリ変数を用いた定式化


論理ビットの並び替えを， 𝑀𝑁 2 個のバイナリ変数で表現

one-hot 制約



物理ビットに関する one-hot 制約



論理ビットに関する one-hot 制約

CXゲートによる制約


作用させる物理ビットは隣り合っていなければならない

9

バイナリ変数を用いた定式化
コスト = SWAPゲートの個数

厳密には，コストは 4次式 で表される


一応，補助変数を追加すれば定式化が可能



しかし，探索空間が広すぎたせいか上手くいかなかった...

10バイナリ変数を用いた定式化
コスト = SWAPゲートの個数

厳密には，コストは 4次式 で表される



一応，補助変数を追加すれば定式化が可能



しかし，探索空間が広すぎたせいか上手くいかなかった...

コストを 2次式 で近似する作戦に

補助変数は不要になり，モデルの規模は 𝑂 𝑀𝑁 3 に

11

実行時間の比較

実行推定時間 (秒)1.0E+18

1.0E+12

古典的解法
1.0E+06

1

Amplify解法

1.0E-06

123

4

5678

9

10

11

12

13

14

15

量子ビットの個数 N
12実行時間の比較

実行推定時間 (秒)1.0E+18100京倍の高速化

1.0E+12

古典的解法
1.0E+06

1

Amplify解法

1.0E-06

123456789101112131415

量子ビットの個数 N
13コストの比較
古典的解法 (低速・最適解)

Amplify解法 (高速・近似解)VS

小規模な回路 → 最適解にほとんど一致

中規模な回路 → パラメータ調整で対処可能
それぞれの解法におけるコストの平均値

𝑁

3456

古典的解法 (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

アプリへの応用
15

量子回路の描画機能
量子回路が描画されたアプリ画面の例

GUIアプリを実装



量子回路をリアルタイムで描画

16量子回路の描画機能
量子回路が描画されたアプリ画面の例

GUIアプリを実装



量子回路をリアルタイムで描画作業の様子が一目でわかる！
17

Amplifyの呼び出し機能
Amplify解法 実行結果の例



パラメータ調整 + Amplify解法の実行



良い解が見つかるまで調整が可能

18

Amplifyの呼び出し機能
Amplify解法 実行結果の例



パラメータ調整 + Amplify解法の実行



良い解が見つかるまで調整が可能

作業の効率化につながる！
19

OpenQASMを用いた入出力
「OpenQASM」という言語を使って読み込み + 書き出しが可能

多くのソフトウェアと互換性がある
本アプリの位置付け

設計図
作成アプリ

実機搭載の検討

実機ハードウェア
ゲート情報の翻訳

回路見直し

20

アピールポイント
問題設定

実験・評価

アプリへの応用「量子ビット割り当て問題」をAmplifyで解く

近似により探索空間を削減 → 性能向上



回路のリアルタイム
描画 → 作業の効率化

「回路全体の最適化」
は，まだ誰も挑戦していない

圧倒的な高速化に成功

他アプリとの互換性

新規性・進歩性

技術力実用性21

補助スライド22

問題設定の詳細



CXゲートを含むそれぞれのレイヤーに対して，論理ビットの配置を決定する

全てのレイヤーで，CXゲートの物理的制約が満たされる必要がある

レイヤー間に挿入するSWAPゲートの個数を減らしたい

1次元アーキテクチャの場合，SWAPゲートの個数は転倒数に等しい


転倒数 =「順番が入れ替わったペアの数」

23

バイナリ変数を用いた定式化


各レイヤーにおける論理ビットは 0, 1, ⋯ , 𝑁 − 1 の並び替えとなる

𝑸𝒎𝒏𝒗 : 「レイヤー 𝑚 において，物理ビット 𝑛 は論理ビット 𝑣 に対応する」


𝑀𝑁 2 個のバイナリ変数が必要

one-hot 制約「物理ビットは単一ビットのみに対応する」 : σ𝑁−1
𝑣=0 𝑸𝒎𝒏𝒗 = 1

「論理ビットは単一ビットのみに対応する」 : σ𝑁−1
𝑛=0 𝑸𝒎𝒏𝒗 = 1

CXゲートによる制約


作用させる物理ビットは隣り合っていなければならない

ペナルティ関数 : σ 𝑎,𝑏 ∈ 𝐶𝑋−𝑔𝑎𝑡𝑒𝑠 σ 𝑖,𝑗 , 𝑖−𝑗 ≥2 𝑸𝒎𝒊𝒂 𝑸𝒎𝒋𝒃

24

コスト関数の定式化 (厳密解法)
コスト = SWAPゲートの個数 = 転倒数

隣り合うレイヤー 𝐴, 𝐵 間における，論理ビットの移動 𝐶 を考える



厳密に定式化が可能

𝐶𝑖𝑗 = 1 ↔ 𝐴 𝑖 = 𝐵 𝑗

補助変数+制約の追加による定式化↔ 𝑝𝑒𝑛𝑎𝑙𝑡𝑦 = 3𝑆𝑖𝑗𝑣 + 𝐴𝑖𝑣 𝐵𝑗𝑣 − 2𝑆𝑖𝑗𝑣 𝐴𝑖𝑣 + 𝐵𝑗𝑣

𝑆𝑖𝑗𝑣 = 𝐴𝑖𝑣 ⋅ 𝐵𝑗𝑣

𝐶𝑖𝑗 = σ𝑣 𝑆𝑖𝑗𝑣

𝑐𝑜𝑠𝑡 = σ0≤𝑖1 <𝑖2 <𝑁 σ0≤𝑗2 <𝑗1 <𝑁 𝐶𝑖1 𝑗1 ⋅ 𝐶𝑖2𝑗2

25

厳密解法の実行結果


出力結果のコストが大きすぎる or 解が見つからないという結果に．．．

探索空間の大きさに対して，制約を満たす組が少ないことが原因か

用いたバイナリ変数の合計 = log 2 探索空間の状態数 = 𝑀𝑁 3 + 2𝑀𝑁 2 − 𝑁 3 − 𝑁 2

log 2 解となる状態数 < log 2 𝑁! 𝑀 ≈ log 2 𝑀 𝑁 log 𝑁 − 𝑁1

ほとんど全てが「ハズレ」だった

26

転倒数の近似によるアプローチ

性能向上のため，近似解法を採用して状態数を削減することに

最初に用意したバイナリ変数だけを使って，転倒数を2次で近似する

重回帰分析によるフィッティング，期待値による推定を行った

重回帰分析，期待値による転倒数の推定結果（横軸が正しい値，縦軸が推定値）



2つの推定結果は，互いに一次関数の関係になっていた[重回帰分析による推定結果] =2𝑁−2N

期待値による推定結果 −𝑁−1 𝑁−24

27

コスト関数の定式化 (近似解法)
𝑖+𝑗𝑖𝑗
−
2𝑁−1



期待値による推定結果 ≈ σ0≤𝑖,𝑗<𝑁

重回帰分析による推定結果へ変換： y =→ 転倒数 ≈

2𝑁−2Nσ0≤𝑖,𝑗<𝑁𝑖+𝑗𝑖𝑗
−2𝑁−1

⋅ 𝐶𝑖𝑗

2𝑁−2𝑁−1 𝑁−2𝑥−N4

σ𝑁−1𝑣=0 𝐴𝑖𝑣 𝐵𝑗𝑣−𝑁−1 𝑁−24と書ける

レイヤー 𝑚, 𝑚 + 1 間においては， 𝐴𝑖𝑣 = 𝑸𝒎𝒊𝒗 , 𝐵𝑗𝑣 = 𝑸 𝒎+𝟏 𝒋𝒗

代入すると，以下のように整理できる


σ𝑀−2𝑚=0 σ0≤𝑖,𝑗<𝑁

𝑁−1 𝑖+𝑗 −2𝑖𝑗
𝑁

σ𝑁−1𝑣=0 𝑸𝒎𝒊𝒗 𝑸 𝒎+𝟏 𝒋𝒗

この部分を最小化したい− 𝑀−1

𝑁−1 𝑁−24

定数項（無視してOK）

28

Amplify解法モデルの構成
𝑁−1 𝑖+𝑗 −2𝑖𝑗𝑁𝑐𝑜𝑠𝑡 = σ𝑀−2𝑚=0 σ0≤𝑖,𝑗<𝑁

σ𝑁−1𝑣=0 𝑸𝒎𝒊𝒗 𝑸 𝒎+𝟏 𝒋𝒗

𝑁−1𝑁−1𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡 = σ𝑀−1
𝑚=0 ቄσ𝑣=0 1 − σ𝑛=0 𝑸𝒎𝒏𝒗

2𝑁−1+ σ𝑁−1
𝑛=0 1 − σ𝑣=0 𝑸𝒎𝒏𝒗

σ 𝑎,𝑏 ∈ 𝐶𝑋−𝑔𝑎𝑡𝑒𝑠 σ 𝑖,𝑗 , 𝑖−𝑗 ≥2 𝑸𝒎𝒊𝒂 𝑸𝒎𝒋𝒃 ቅ2+one-hot 制約

CXゲートによる制約

𝑚𝑜𝑑𝑒𝑙 = 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡 × 𝜆 + 𝑐𝑜𝑠𝑡 として構成した

𝑚𝑜𝑑𝑒𝑙 の項数(= モデルの規模)は 𝑂 𝑀𝑁 3 個29