DEIM2022 チュートリアル

データ工学における量子コンピューティング
株式会社KDDI総合研究所

斉藤 和広，別府 翔平，黒川 茂莉，伊神 皓生，成定 真太郎
株式会社Jij

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

山城悠

目次
1. 量子コンピューティング概要（KDDI研 斉藤：15分）
2. 量子機械学習アルゴリズム（KDDI研 別府，黒川：20分）
3. 量子組合せ最適化アルゴリズム（Jij 山城，KDDI研 伊神：25分）
 イジングマシン（量子アニーリング等）
 量子ゲート

4. 量子探索アルゴリズム（KDDI研 成定：20分）※QAはoVice 1階（談話広場）で行います
https://deim2022.ovice.in
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

2

DEIM2022 チュートリアル

1. 量子コンピューティング概要
株式会社KDDI総合研究所

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

斉藤 和広

背景

「ムーアの法則」の終焉※18ヶ月で2倍の集積率

世界の取り組み・用途特化のアクセラレータ
・従来アーキテクチャの刷新

シ
リ
コ
ン
線
幅

狭線化
限界

『量子コンピュータ』が次世代コンピュータの有力候補として注目
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

4

量子コンピュータとは量子コンピュータ

古典コンピュータ
２進数で一つの情報を保持／演算「量子重ね合わせ」により同時に複数の情報を保持／演算

ビット bit

量子ビット qubit

0

0
観測A
：0

0

1

1

観測B
：1

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

5 qubit

𝟐𝟐𝟓𝟓 = 𝟑𝟑𝟑𝟑 通りの状態を同時保持32の並列計算が可能

超並列コンピュータ5量子コンピュータの効果的な用途
古典コンピュータで計算に長時間を要する，または計算が困難な問題
特に量子コンピュータの活用が検討されている領域
最適化＆探索問題

シミュレーション＆モデリング

AI＆機械学習概要

問題の規模に応じて計算量が指数関数的に膨大となる問題

物理学の基本方程式（力学／電磁気学
等）のように、微分積分などの計算量が膨大な数値計算を含む問題

ディープラーニングや強化学習などの計算量の多い機械学習手法

応用例

・信号機制御による渋滞解消
・資産ポートフォリオ最適化
・タンパク質設計最適化
・暗号解読

・電磁界シミュレーション
・触媒反応シミュレーション
・有機分子の結晶構造分析
・エンジンの熱伝達分析

・クラスタリングによる異常検知
・時系列分析
・次元圧縮
・画像と音声の分類

機械学習
データ工学で関連する用途： 組合せ最適化
データ探索Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

6量子コンピュータの実装と分類
量子コンピュータ

量子の物理現象でビットを表現

量子ゲート

演算回路を持つ汎用型

イジングマシン

組合せ最適化問題等に特化

産業界での実証が進められているマシン

開発組織

超電導方式

IBM, Google, Rigetti, USTC他, 等

イオントラップ方式

IonQ, Honeywell, AQT, 理研, 等

シリコン量子方式

Intel, TSMC, 等

光量子方式

Xanadu, USTC他, NTT, 等

その他の方式

Microsoft, Pasqal

アニーリング方式

研究段階だが利用可能なマシンも出現

実装方式

量子アニーリング(超電導方式)D-Wave, NEC他

デジタル回路
シミュレータ*

富士通, 日立製作所

ソフトウェアシミュレータ*日立製作所, NEC, Jij, Fixstars, 等

分岐方式 (ソフトウェア*)

東芝

レーザネットワーク方式* NTT他
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

* 厳密には量子コンピュータではない

7

量子コンピュータの活用方法
計算方式

要件定義

設計

実装

計算

古典コンピュータ

計算内容や課題を定義

アルゴリズムの構築／ソ
フトウェア設計／データ
構造設計

プログラム開発

プログラムに従って計算実行

イジングマシン

課題を明確化して組合せ最適化問題を定式化

イジングモデル（またはQUBO）の構築

量子ビット間の結合強度と量子ビットの重みを計算

エネルギーを最小化する解を算出量子ゲート

古典方式より高速化が期待できる計算内容や課題
を定義

量子アルゴリズムの構築／量子回路の設計

量子回路を実行するプログラム開発

量子回路の量子ビット操作に従って計算実行

量子コンピュータはどのような計算でも古典コンピュータより高速なわけではない→量子加速／超越性／優位性【量子アルゴリズム】

量子ビットの特性を用いた計算方法。
＜例＞
アダマールテスト：期待値推定
Shorアルゴリズム：素因数分解
Groverアルゴリズム：データ探索
HHL：連立１次方程式【量子回路】

量子ゲートを並べて量子アルゴリズ
ムを実現する回路。

量子アルゴリズムの効果的な活用、用途に応じた量子アルゴリズムと量子回路の開発が必要
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

8量子ビット 量子ビット：0と1の重ね合わせ状態（2行1列の複素ベクトルで表現）
 測定してはじめて状態が定まる
量子ビット

𝛼𝛼
𝛽𝛽

（極端な場合）1
0

必ず0

極端な場合を除き、0も1もとり得る
0
1

必ず1

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

状態
0

1
9

量子ビットが0と1をとる確率
状態

量子ビット
𝛼𝛼
𝛽𝛽
0をとる確率1をとる確率𝑝𝑝0
𝑝𝑝1

0

ブラケット記法
量子ビット𝜓𝜓の状態ベクトル|𝜓𝜓⟩ = 𝛼𝛼|0⟩ + 𝛽𝛽|1⟩
1
：古典の０
0
0
|1⟩ =
：古典の１
1

|0⟩ =

1
𝑝𝑝0 = 𝛼𝛼 2
𝑝𝑝1 = 𝛽𝛽 2足して1(規格化条件)

𝛼𝛼 2 + 𝛽𝛽 2 = 1

例：0と1の得られる確率50%|𝜓𝜓⟩ =

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

1

2
1
2

=

1

2

|0⟩ +

1

2

|1⟩
10

量子ゲート 量子ゲート：量子ビットに対する演算（量子演算）【量子ゲートの条件】

 線形性：量子ビットの状態ベクトルに対する線形変換である→ 一つの量子ビットに対する演算は2x2の行列
 ユニタリ性：エルミート共役をとると逆行列になる→ 規格化条件（ 𝛼𝛼 2 + 𝛽𝛽 2 = 1 ）を守った演算

例：Xゲート
0 1
𝑋𝑋 =
1 0

𝑋𝑋 |0⟩ = |1⟩, 𝑋𝑋 |0⟩ = |1⟩

古典のNOTゲートに対応

例：アダマールゲート（Hゲート）
𝐻𝐻 =

1

2
1
2

−

1

2
1

2

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

𝐻𝐻 |0⟩ =

1

2

|0⟩ +

1

2

|1⟩

重ね合わせ状態を作成

11

量子アルゴリズムとは
 量子コンピュータはn個のビットで2^n個の状態を同時に計算|𝜓𝜓⟩ =

�𝑖𝑖1 ,…,𝑖𝑖𝑛𝑛 ∈{0,1}

𝑐𝑐𝑖𝑖1 ,…,𝑖𝑖𝑛𝑛 |𝑖𝑖1 … 𝑖𝑖𝑛𝑛 ⟩ =n個の量子ビット

𝑐𝑐00…0𝑐𝑐00…1⋮
𝑐𝑐11…1

測定

𝟐𝟐𝒏𝒏 個の状態一つの解：|𝑖𝑖1 … 𝑖𝑖𝑛𝑛 ⟩より高い確率でほしい解を得られる設計が必要

量子アルゴリズム
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

12量子アルゴリズムの例：アダマールテスト
 量子ビット列|𝜓𝜓⟩に演算Uを作用したときの期待値を推定する量子アルゴリズム

|𝜓𝜓⟩

H
…

|0⟩

H
複数回
測定

U

𝑝𝑝0 ：0が得られる確率
𝑝𝑝1 ：1が得られる確率

期待値 = 𝒑𝒑𝟎𝟎 − 𝒑𝒑𝟏𝟏

※この回路は実数部の期待値のみ
虚数部の期待値も似た回路で計算可能

アダマールテストの量子回路：アダマールゲート（Hゲート）
初期状態|0⟩から重ね合わせ状態が得られる演算：制御ユニタリゲート（例：CNOTゲート）
制御量子ビット（上の●側）が|1⟩のときに演算Uをターゲット（下）に適用
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

13量子シミュレータ（SymPy）でアダマールテストを実行
 対象の演算：アダマールゲート
 本当に同じ値が得られるか確認 まずはアダマールゲートの期待値

 アダマールテストで得られる期待値→

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

14

SymPyとIBM Qの比較
 SymPyの期待値：0.707106781186548
 IBM Qの期待値：0.70884

SymPyの結果

 誤差0.2%程度

IBM Qの結果

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

15現在の量子コンピュータの課題とアプローチ
 重要な課題：量子ビットのエラー訂正

 エラー（ノイズ）とは、外的要因などによって情報が壊れること
 アプローチ：エラー訂正を備えた量子コンピュータの開発 or エラーを許容して利用
FTQC

NISQデバイス(Fault-Tolerant Quantum Computer)(Noisy Intermediate-Scale Quantum)

概要

エラー訂正を備えた量子ゲート方式の量子コンピュータ

エラー訂正を持たない小・中規模（～数100量子ビット）な量子ゲート方式の量子コンピュータ

特徴

 FTQC向けの量子アルゴリズムをLong-termアルゴ
リズムと呼ぶ エラー訂正に多数の余剰量子ビットが必要→実用には100万量子ビット以上が必要
 エラー訂正自体が新たなエラーを生むため，量子ゲートのエラー率の低下も必要

 NISQデバイス向けの量子アルゴリズムをNISQアル
ゴリズムと呼ぶ エラーを許容しつつ，エラー削減のため短い量子回路で実行
 古典コンピュータも併用する量子古典ハイブリッド
なNISQアルゴリズムが主流

実装例

 実装なし 各国で2030-2035年頃の実用化に向けて開発中

 IBM Quantum (127量子ビット, 2021)
 Google Sycamore (54量子ビット, 2019)

エラー訂正手法の開発、デバイスの進化

NISQアルゴリズムの開発と実証

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

16まとめ：量子コンピューティング概要
 量子コンピューティングの概要を紹介

 現在の量子コンピュータの種類：イジングマシン，量子ゲート
 活用が期待できる分野：最適化＆探索問題，シミュレーション＆モデリング，機械学習
 技術概要を紹介：量子ビット，量子ゲート，量子アルゴリズム
 量子アルゴリズムの種類：Long-termアルゴリズム，NISQアルゴリズム

 参考文献 Quantum Native Dojo： https://dojo.qulacs.org/ja/latest/index.html
 教科書（和書）：嶋田 義皓，量子コンピューティング: 基本アルゴリズムから量子機械
学習まで”
 教科書（洋書）：M. A. Nielsen & I. L. Chuang, “Quantum Computation and
Quantum Information”.
 量子コンピュータの実装方式：T. D. Ladd et al., “Quantum computing,” Nature, 2010.
 NISQ：J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum,2018.
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

17

DEIM2022 チュートリアル

2. 量子機械学習アルゴリズム
株式会社KDDI総合研究所

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

別府 翔平，黒川 茂莉

量子機械学習の定義
 量子機械学習

には様々なバリエーションがあるが、代表的な2種類を紹介する① 古典機械学習の特定の計算部分を量子コンピュータに委託し、高速に計算する• 機械学習の精度は古典のみで行った場合と同一• アダマールテストやGrover等の「量子加速に関して理論保証のあるアルゴリズム」を使う→ long-term と考えられている② 古典機械学習における表現（ニューラルネット、カーネル等）として量子系を使う• 機械学習の精度が古典を上回る可能性がある• たとえばノンパラメータ(SVM)、パラメータ(NN)の量子版がある• 雑音があってもある程度動作するとされ、大規模or/and複雑な量子系の表現力に期待する →near-termと考えられている

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

19

①古典機械学習の特定の計算を量子加速するタイプ
K-meansクラスタリングの量子加速(指数加速)①クラスター割り当て③重心に基づきクラスター再割り当て(最近接の重心を持つクラスターへ割り当て)②各クラスターの重心計算

重心

重心計算
＝ユークリッド距離計算＝内積計算＝Swap test で量子加速

O(poly(MN))→

O(log(MN))

M: クラスタ数
N: データ次元

S. Lloyd et al., “Quantum algorithms for supervised and unsupervised machine learning”, arXiv:1307.0411 (2013).
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

20

②古典機械学習におけるモデルとして量子系を使うタイプ

SVMの量子版による分類[1]NNの量子版による回帰[2][1] V. Havlíček et al., “Supervised learning with quantum-enhanced feature spaces,” Nature, vol. 567, no. 7747, pp. 209–212, 2019.
[2] K. Mitarai et al., “Quantum Circuit Learning,” Phys. Rev. A, vol. 98, no. 032309, 2018.
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

21量子機械学習の定義
 量子機械学習

には様々なバリエーションがあるが、代表的な2種類を紹介する① 古典機械学習の特定の計算部分を量子コンピュータに委託し、高速に計算する• 機械学習の精度は古典のみで行った場合と同一• アダマールテストやGrover等の「量子加速に関して理論保証のあるアルゴリズム」を使う→ long-term と考えられている② 古典機械学習における表現（ニューラルネット、カーネル等）として量子系を使う• 機械学習の精度が古典を上回る可能性がある• たとえばノンパラメータ(SVM)、パラメータ(NN)の量子版がある• 雑音があってもある程度動作するとされ、大規模or/and複雑な量子系の表現力に期待する →near-termと考えられている

Our focus
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

22

②古典機械学習におけるモデルとして量子系を使うタイプ

SVMの量子版による分類[1]NNの量子版による回帰[2][1] V. Havlíček et al., “Supervised learning with quantum-enhanced feature spaces,” Nature, vol. 567, no. 7747, pp. 209–212, 2019.
[2] K. Mitarai et al., “Quantum Circuit Learning,” Phys. Rev. A, vol. 98, no. 032309, 2018.
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

23量子サポートベクトルマシン(QSVM) QSVMでは、データを埋め込む特徴量空間として量子状態空間を採用する。
 N量子ビットの状態空間(*)は22N次元であり、指数的に広い
 複雑な分類が出来るのでは？と期待される

𝒙𝒙𝒙

𝒙𝒙

量子状態の空間
古典データの空間

N量子ビットであれば22N次元空間(*)ここでは実Blochベクトル表現を考えている
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

24量子サポートベクトルマシン(QSVM) QSVMでは、データを埋め込む特徴量空間として量子状態空間を採用する。
 N量子ビットの状態空間(*)は22N次元であり、指数的に広い
 複雑な分類が出来るのでは？と期待される

分類境界
量子状態の空間
古典データの空間

N量子ビットであれば22N次元空間(*)ここでは実Blochベクトル表現を考えている
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

25量子サポートベクトルマシン(QSVM)
 古典データをパラメータとする量子ゲート操作により、量子状態埋め込みを行う どのような埋め込みが与えられた分類問題に適するのか？

 量子状態ベクトル（指数的に高次元！）の内積はどうやって計算するのか
 内積計算も量子回路上で効率的に行うアルゴリズムが知られている
Quantum computer

𝒙𝒙𝒙

𝒙𝒙

1
0

U(x)

1
0

U(x)

𝜙𝜙 x =
1U(x)0

𝜙𝜙 x′ =1U(x′)
0Quantum feature map

𝜙𝜙 x′

𝜙𝜙 x

Quantum kernel
𝐾𝐾(x, x′): = |𝜙𝜙(x)𝜙𝜙(x′)† |2

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

SVM
training
𝐾𝐾 x, x ′for all (x,x’)

26

量子サポートベクトルマシン(QSVM)

データ埋め込み

出力(カーネルの値)生成された分類境界の様子
V. Havlíček et al., “Supervised learning with quantum-enhanced feature spaces,” Nature, vol. 567, no. 7747, pp. 209–212, 2019.
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

27

②古典機械学習におけるモデルとして量子系を使うタイプ

SVMの量子版による分類[1]NNの量子版による回帰[2][1] V. Havlíček et al., “Supervised learning with quantum-enhanced feature spaces,” Nature, vol. 567, no. 7747, pp. 209–212, 2019.
[2] K. Mitarai et al., “Quantum Circuit Learning,” Phys. Rev. A, vol. 98, no. 032309, 2018.
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

28

量子回路学習（QCL）
 量子コンピュータを機械学習に応用するためのアルゴリズム
 量子・古典ハイブリッドアルゴリズム（NISQで動作が期待される）
 2019年3月にIBMの実験チームによるQCLの実機実装論文がNatureに掲載
量子回路による評価
量子計算機

古典計算機
量子回路のパラメータ

 ポイント：指数的に高次元！の量子状態空間により表現力を向上
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

29

QCLのアルゴリズム
 基本的な考え方

 入力データxに対する出力yを予測したい．
 QCLはxに対してyを出力するためのパラメータθを学習する．

 推論の流れ
1.
2.
3.
4.

Neural NetworkのForward演算に相当

入力データxを量子ビット|𝜓𝜓⟩に埋め込み
パラメータθに従って量子ビット|𝜓𝜓⟩を操作し|𝜓𝜓′⟩を生成（変分量子回路）
量子ビット|𝜓𝜓𝜓⟩における何らかの演算Zの期待値<Z>を計測 ※ここまでが量子回路
期待値<Z>を何らかの関数(sigmoidなど)で変換した結果が予測値y 学習の流れ
1.
2.
3.
4.

学習用入力データx_trainに対して上記推論処理を実行し，予測値yを得る
正解データy_trainと予測値yのロスLを計算
ロスLを最小化するよう，パラメータθを更新
全ての学習用データで1.-3.を繰り返す．

Neural Networkとの違い：誤差逆伝搬せず、Forward演算を何度も実行して評価
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

30

QCL実装の詳細
量子コンピュータ
|0⟩
|0⟩
|0⟩

𝑼𝑼𝒊𝒊𝒊𝒊 x

入力データxを量子ビットに変換（埋め込み）
入力データx𝑼𝑼 θ

𝑼𝑼𝒐𝒐𝒐𝒐𝒐𝒐

パラメータθに依存した変分量子回路

期待値計算※必要に応じて期待値を何らかの関数で変換数値

パラメータθ
最適化法に基づいてコストLに対するパラメータθを更新（例：Nelder-Mead法）

コストL

期待値とその正解
データyからコストLを算出（例：平均二乗誤差）
教師データ分繰り返す

古典コンピュータ
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

31

QCLをQulacsで実行 問題：Curve fitting 対象の関数： 𝒚𝒚 = sin 𝝅𝝅𝝅𝝅

 まずは学習用データを作成

 xを[-1,1]でランダム生成し，対象の関数に少し誤差を与える
 学習データ数：50個

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

32

QCLをQulacsで実行
 QCLの学習を実行 → 量子ビット数：3
 層の深さ：3
 パラメータθの数：27個

学習時間 43秒• 量子ビット数＊層の深さ＊変分用ゲート数

 パラメータ初期値：[0,2π]のランダム生成
 ロス関数：平均二乗誤差（MSE）
 最適化法：Nelder-Mead法 学習結果の確認

 [-1,1]の連続値を学習済みQCLに入力
 その出力結果をプロット

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

33

QCLとNeural Networkと比較
 Kerasで実行→ 学習時間 6秒

 データは一緒
 中間層も3層で，それぞれ9ユニット，活性化関数はReLU，ロス関数はMSE• パラメータ数は210個• エポックは300

 最適化はAdam

QCLの結果（再掲）

NNの結果

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

34

QCLで分類問題を解く
 データ：scikit-learnのIris アヤメの品種データ
 Setosa, Versicolor, Virginicaの3品種のデータが150件
 特徴量：がく片の長さ／幅，花びらの長さ／幅• それぞれの相関関係 → 花びらの長さと幅で分類

 量子ビット数：3
 層の深さ：2
 パラメータθの数：18個
 ロス関数：平均二乗誤差（MSE）
 最適化法：BFGS法

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

35

QCLで分類問題を解く
 分類結果

→実行時間 43秒

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

36量子機械学習の提案いろいろ いろんな古典機械学習手法の量子版が提案されている

量子転移学習量子グラフNN

量子GAN

量子CNN

量子アンサンブル学習
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

https://pennylane.ai/
37量子機械学習の課題
 データの埋め込み・後処理がボトルネックとなる 大規模化すると、雑音やデコヒーレンスの影響が無視できない パラメータ最適化が大変（勾配の計算コストが高い、勾配消失が起こる）
 変分量子回路の設計指針が確立されていない
 量子アドバンテージがなかなか得られない
 etc.

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

38

DEIM2022 チュートリアル

3. 量子組合せ最適化アルゴリズム
株式会社Jij
株式会社KDDI総合研究所

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

山城 悠
伊神 皓生

量子組合せ最適化アルゴリズム（量子アニーリング）株式会社 Jij
山城

悠

目次
●
●
●
●
●
●
●

数理最適化
局所最適化と大域最適化
量子アニーリングイジングモデル・QUBOを使った最適化計算の実装
国内外の研究開発
まとめ
参考文献

Jij Inc.

41

数理最適化とは？

数理最適化とは？
計画
例:

解きたい課題● 配送計画（ルート最適化）● シフト作成（配置最適化）● 材料の構造（構造最適化）．．．

・配送計画問題
・基地局の周波数割り当て問題
・シフト作成問題

数理モデル

アルゴリズム目的関数
例: - 売上の最大化- 費用の最小化●●

汎用Solver
問題ごとにアルゴリズム実装
ヒューリスティクス

制約条件
例: 予算の上限
運用ルール...
Jij Inc.

43様々な数理モデル
連続最適化問題・線形計画問題（Linear programming problem: LP)・凸２次計画問題
・非線形計画問題● 変数は離散か連続か？
● 関数は線形か非線形か？
● 制約条件ありか？無しか？

離散最適化問題（組合せ最適化問題）
・典型問題
資源配分問題・ナップサック問題
最短経路問題・混合整数計画問題 (Mixed Integer programming problem : MIP)
・二次制約無し二値最適化問題(Quadratic Unconstrained Binary Optimization Problem: QUBO)(Unconstrained Binary Quadratic optimization Problem: UBQP)Jij Inc.

44

組合せ最適化問題 : グラフ彩色問題
グラフ彩色問題：辺で接続されているノードを違う色で塗りたい

min

目的関数

s.t.

制約条件

決定変数

Jij Inc.

45局所最適化と大域最適化
愚直に目的関数が下がる方向に動くと局所最適解にはまってしまう
コスト

局所最適化

Jij Inc.

46

局所最適化と大域最適化
シミュレーテッドアニーリング（焼きなまし法）
局所最適化

温度揺らぎで脱出

時間
Jij Inc.

47

量子アニーリング48

エネルギー

量子アニーリング
A, B

0

T

解きたいコスト関数

状態
エネルギー

量子揺らぎ

エネルギー

状態

時間
Jij Inc.

状態

49

イジングモデル
スピン・磁石を表現するための物理モデル
・イジングモデルの基底状態（上記のエネルギー関数の最小エネルギー解）と求めたい解が対応

Jij Inc.

50

エネルギー

横磁場量子アニーリング [3] T. Kadowaki, H. Nishimori, 1998

状態

エネルギー

1. 横磁場（量子効果）
を強くかけ、自明な状態にセット

2. 横磁場を徐々に
消していく

エネルギー

状態

3. 横磁場を消して知りたかった基底状態を得る時間
Jij Inc.

状態

51断熱量子計算 (Adiabatic Quantum Computing)
量子断熱定理(計算時間とエネルギーギャップの関係)

AQCでの量子プログラミング=> ハミルトニアンの設計(自由に量子ハミルトニアンを設計できることが前提)

量子揺らぎの設計と計算量の関係性は重要なテーマ
AQCについてまとまっているレビュー論文[4] Tameem Albash and Daniel A. Lidar, “Adiabatic quantum computation” Rev. Mod. Phys. 90, 015002 (2018)
Jij Inc.

52量子アニーリングマシン : D-Wave
横磁場量子アニーリング

扱えるグラフ構造
配線などの物理的な理由により制限されたグラフのイジングモデルしか扱えない
ペガサスグラフ
ノイズ
温度やノイズにより理想的な量子アニーリングを実行するのが難しい[5] D-Wave Advantage

Jij Inc.

53

イジングモデルを使った最適化

QUBO (Quadratic Unconstrained Binary Optimization

QUBO

イジングモデル等価

Jij Inc.

55

制約付き最適化問題のQUBO表現
ペナルティ法（罰金法）

制約付き最適化問題

Jij Inc.

56

制約付き最適化問題のQUBO表現 : グラフ彩色問題
制約付き最適化問題

ペナルティ法（罰金法）

Jij Inc.

57

PyQUBO[8, 9]を使った実装 : 数理モデリングペナルティ法（罰金法）$ pip install pyqubo

Jij Inc.

58

OpenJij[10]を使ってQUBOを解く$ pip install openjij

イジングモデル・QUBOを解くためのOSS
D-Waveを使う時と同じインターフェース

Simulated Annealing (焼き鈍し法)
Simulated Quantum Annealing(量子アニーリングのシミュレーションアルゴリズム)

Jij Inc.

59

国内外での研究開発

国内外で研究開発・実証実験が進む
ハードウェアの開発●

D-Wave (カナダ) : 量子アニーリングマシンのクラウドサービスの提供●

富士通 : 独自開発イジングマシン「デジタルアニーラ」の提供●

Microsoft (アメリカ): Microsoft QIO（FPGA実装・複数のアニーリングアルゴリズム） の提供●

NTT, 日立, 東芝: LASOLV, CMOSアニーリングマシン, SBM など独自のハードウェア・アルゴリズムを開発●

アメリカ・ヨーロッパでの国家プロジェクト
ONISQ プロジェクト (米)AVaQus プロジェクト (欧)応用プロジェクト
●Volkswagen : 交通流最適化 (リスボン市でのバス路線最適化)●

DENSO : 倉庫内 AGVの最適化●

OTI Lunimonics: 量子化学計算●

etc ...

Jij Inc.

61

まとめ
●

組合せ最適化を解く量子アルゴリズムとしての量子アニーリング●

現在の量子アニーリングハードウェアの課題
・限られた量子ハミルトニアン（量子揺らぎ）
・扱えるグラフ構造の制約
・ノイズ●

イジングモデル・QUBOを使った最適化計算の実装のやり方 (PyQUBO, OpenJij)●

量子アニーリングはアルゴリズムなので量子コンピュータ上でも実現可能 (QAOA)
限られた量子ハミルトニアンなどの課題は、量子コンピュータ上での実装で解決されるかもしれない。

Jij Inc.

62

参考文献
数理最適化を初めて学ぶための本[1] 穴井 宏和, 斉藤 努, “今日から使える!組合せ最適化 離散問題ガイドブック”, 講談社, 2015.
[2] 梅谷 俊治, “しっかり学ぶ数理最適化 モデルからアルゴリズムまで”, 講談社, 2020.
量子アニーリングの提案論文[3] T. Kadowaki, H. Nishimori, “Quantum Annealing in the Transverse Ising Model”, Phys. Rev. E 58, 5355, 1998.
AQCの理論研究についてまとまっているレビュー論文[4] Tameem Albash and Daniel A. Lidar, “Adiabatic quantum computation” Rev. Mod. Phys. 90, 015002, 2018.
D-Wave Advantage についてのホワイトペーパー[5] D-Wave Systems Inc., “Advantage Processor Overview”, D-Wave Technical Report Series, 2022.
イジング最適化の定式化集、これまでの産業界での応用例のレビュー[6] A. Lucas, “Ising formulations of many NP problems”, Frontiers in Physics 2, 5, 2014.
[7] S. Yarkoni, “Quantum Annealing for Industry Applications: Introduction and Review“, arXiv:2112.07491, 2021.
OSSのQUBOモデリングツール[8] K. Tanahashi, et al., Application of Ising Machines and a Software Development for Ising Machines, J. Phs. Soc. Jpn. 88, 061010, 2019.
[9] PyQUBO (GitHub): https://github.com/recruit-communications/pyqubo
OSSのイジング最適化ツール[10] OpenJij (GitHub): https://github.com/OpenJij/OpenJij

Jij Inc.

63

QAOA(Quantum Approximate
Optimization Algorithm)
株式会社KDDI総合研究所

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

伊神 皓生

QAOAの概要
 NISQアルゴリズムの一つ Quantum Approximate Optimization Algorithm (QAOA; 量子近似最適化アルゴリズム)を学ぶ。
 QAOAは、量子アニーリングと同様に、組合せ最適化問題の解を求めるためのアルゴリズムである
 QAOAは、古典コンピューターと量子コンピュータを用いるハイブリットアルゴリズム

古典コンピュータ

量子コンピュータ

初期値・問題用パラメータ

0

ビット

0
0

1

最適化

0: 70%
1: 30%

量子ビット
1

論理ゲート
出力解

量子重ね合わせ
0
観測

量子ゲート

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

65

QAOAのフロー概要
1. 準備：量子コンピュータで扱えるよう、組合せ最適化問題を変換
2. 探索：量子コンピュータに初期値とパラメータを入力し、解を探索
3. チューニング：量子コンピュータからの出力から探索パラメータを古典コンピュータで最適化
2. 解の探索

1. 準備
古典コンピュータ

量子コンピュータ

初期値・問題用パラメータ

0

ビット

0
0

0: 70%
1: 30%

量子ビット

1

1

論理ゲート
解・コスト

量子重ね合わせ
0
観測

量子ゲート

3. チューニング（最適化）
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

66

1. 準備 量子コンピュータに必要な要素に変換
 決定変数：𝒛𝒛 →量子状態|𝒒𝒒⟩ (ベクトル)で表現
 目的関数：𝒇𝒇(𝒛𝒛), 制約：𝒈𝒈(𝒛𝒛) ≤ 𝟎𝟎 → ハミルトニアン 𝐻𝐻(行列)で表現

 対象の組合せ最適化問題をコスト関数 𝑪𝑪 =< 𝒒𝒒 𝑯𝑯 𝒒𝒒 > を最小化する問題に変換
 ハミルトニアン𝐻𝐻は問題毎に生成し、以下のイジングモデルで記載する

𝑛𝑛

𝑖𝑖

𝑛𝑛

𝐻𝐻 = � � 𝐽𝐽𝑖𝑖𝑖𝑖 𝑍𝑍𝑖𝑖 𝑍𝑍𝑗𝑗 + � ℎ𝑖𝑖 𝑍𝑍𝑖𝑖
𝑖𝑖=1 𝑗𝑗=1

𝑖𝑖=1

𝑍𝑍 = 𝑍𝑍1 𝑍𝑍2 … 𝑍𝑍𝑛𝑛 𝑍𝑍𝑖𝑖 = 0,1

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

𝑱𝑱𝒊𝒊𝒊𝒊 : 𝒁𝒁𝒊𝒊 , 𝒁𝒁𝒋𝒋 の相互作用
𝒉𝒉𝒊𝒊 : 𝒁𝒁𝒊𝒊 の係数672. 探索 断熱量子計算

 求めたい解を基底状態に持つコスト関数ハミルトニアン𝐻𝐻𝑐𝑐 (𝑡𝑡 = 𝑡𝑡𝑓𝑓 ) 自明な基底状態を持つリファレンスハミルトニアン(初期値)𝐻𝐻𝑟𝑟 (𝑡𝑡 = 0)
 量子断熱定理と呼ばれる量子系の性質により、時間を 𝑡𝑡 =0 → 𝑡𝑡 = 𝑡𝑡𝑓𝑓 と少しずつ変化させること
で、𝐻𝐻𝑐𝑐 を得ることができる※詳細は量子断熱定理で調べてください

𝐻𝐻 𝑡𝑡 = 1 −𝑡𝑡
𝑡𝑡
𝐻𝐻𝑟𝑟 + 𝐻𝐻𝑐𝑐
𝑡𝑡𝑓𝑓
𝑡𝑡𝑓𝑓

 つまり、量子状態の時間発展を量子コンピュータで模擬できれば良い・汎用な量子コンピュータ(量子ゲート)で模擬→QAOA
・専用ハードウェア(D-WAVE等)で模擬→量子アニーリング

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

682. 探索 量子状態の時間発展は、ユニタリ変換𝑈𝑈 𝑡𝑡 = 𝑒𝑒 −𝑖𝑖𝑖𝑖𝑖𝑖 で表現できる

 𝑈𝑈 𝑡𝑡 = 𝑒𝑒 −𝑖𝑖𝑖𝑖𝑖𝑖 をトロッター分解で近似すると、2量子ビットゲートの多項式個の作用の積で表現できる→汎用の量子コンピュータで量子断熱定理の時間発展を近似演算することができる！
→初期値|𝒒𝒒𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊 ⟩ を量子コンピュータに入力、 |𝒒𝒒⟩ = 𝑈𝑈 𝛽𝛽, 𝛾𝛾 |𝒒𝒒𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊 ⟩ を演算し、近似的に最小エネルギーとなるコスト関数 𝑪𝑪 =< 𝒒𝒒 𝑯𝑯𝑯𝑯 𝒒𝒒 > を計算可能
QAA代入−𝑖𝑖𝑖𝑖 𝑡𝑡 𝑡𝑡

2. 解の探索1𝑡𝑡−𝑖𝑖 (1− )𝐻𝐻𝑟𝑟 𝑡𝑡
𝑝𝑝
𝑡𝑡𝑓𝑓

−𝑖𝑖

1𝑡𝑡
𝐻𝐻 𝑡𝑡
𝑝𝑝𝑡𝑡𝑓𝑓 𝑐𝑐

𝑝𝑝

トロッター分解でp分割

𝑈𝑈 𝑡𝑡 = 𝑒𝑒
≈ 𝑒𝑒𝑒𝑒
−𝑖𝑖𝛽𝛽𝑝𝑝 𝐻𝐻𝑟𝑟 −𝑖𝑖𝛾𝛾𝑝𝑝 𝐻𝐻𝑐𝑐 −𝑖𝑖𝛽𝛽𝑝𝑝−1 𝐻𝐻𝑟𝑟 −𝑖𝑖𝛾𝛾𝑝𝑝−1 𝐻𝐻𝑐𝑐
=𝑒𝑒
𝑒𝑒
𝑒𝑒
𝑒𝑒
… 𝑒𝑒 −𝑖𝑖𝛽𝛽0 𝐻𝐻𝑟𝑟 𝑒𝑒 −𝑖𝑖𝛾𝛾0 𝐻𝐻𝑐𝑐
量子ゲートで記載できる

𝛽𝛽 = 1/𝑝𝑝 1 − 𝑡𝑡⁄𝑡𝑡𝑓𝑓 𝑡𝑡、γ = 1/𝑝𝑝 𝑡𝑡⁄𝑡𝑡𝑓𝑓 𝑡𝑡
パラメータ(𝛽𝛽, 𝛾𝛾)𝑝𝑝

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

量子コンピュータ
0

量子重ね合わせ
0: 70%
1: 30%

量子ビット
1

0
観測

量子ゲート

69

3. チューニング
 量子コンピュータの動作パラメータ(近似パラメータ)を最適化する

1. 古典コンピュータを用いてコスト関数 𝑪𝑪 =< 𝒒𝒒 𝑯𝑯 𝒒𝒒 >がより小さくなるよう、量子ゲートのパラメータ(𝛽𝛽, 𝛾𝛾)𝑝𝑝 = 𝛽𝛽1 , 𝛾𝛾1 , … , 𝛽𝛽𝑝𝑝 , 𝛾𝛾𝑝𝑝 をアップデートする→これは、量子ゲートを最適化問題の性質に応じて調整することにあたる
2. パラメータが決まったら、量子状態|𝒒𝒒⟩を観測し最適化問題の解とする．

コスト関数を計算(𝛽𝛽, 𝛾𝛾)𝑝𝑝 を決定

量子ゲート
パラメータ

(𝛽𝛽, 𝛾𝛾)𝑝𝑝

2. 解の探索
量子コンピュータ
量子ゲート

最適化
量子状態、コスト値(ベイズ最適化など)|𝒒𝒒⟩ , 𝑪𝑪
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

70

まとめ
 QAOAは、量子ゲートのパラメータを対象とする問題に応じて古典コンピュータで最適化する
 問題の特性にあった量子ゲートパラメータ (𝛽𝛽, 𝛾𝛾)𝑝𝑝 を上手く見つけらさえすれれば、少ない試行回数で近似解|𝒒𝒒⟩を観測することができる→量子アドバンテージを得られる最適化問題の特徴を見極める必要 課題として、トロッター分解の𝑝𝑝を大きく(=ゲート数大)し、近似精度を高めようとすると量子雑音が増加するトレードオフが存在→直近の実用化に向け、 𝑝𝑝=1など、ゲート数を絞った解の精度向上へ向けた検討が進められている→長期的には、ゲート数が増えても量子雑音が僅かなHWが開発されれば、量子ゲートの表現力が向上し広範囲な問題への適応が可能？

コスト関数 𝑪𝑪 =< 𝒒𝒒 𝑯𝑯 𝒒𝒒 >1. 変換

古典コンピュータ
0

ビット

0
1

論理ゲート

|𝒒𝒒𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊 ⟩2. 解の探索 |𝒒𝒒⟩ = 𝑈𝑈 𝛽𝛽, 𝛾𝛾 |𝒒𝒒𝒊𝒊𝒊𝒊𝒊𝒊𝒊𝒊 ⟩(𝛽𝛽, 𝛾𝛾)𝑝𝑝

量子コンピュータ

初期値・問題パラメータ0

3. 最適化(𝛽𝛽, 𝛾𝛾)𝑝𝑝
量子状態、コスト値|𝒒𝒒⟩ , 𝑪𝑪

量子重ね合わせ
0: 70%
1: 30%

量子ビット
1

0
観測

量子ゲート

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

71

DEIM2022 チュートリアル

4. 量子探索アルゴリズム
株式会社KDDI総合研究所

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

成定 真太郎Groverのアルゴリズム
 量子探索アルゴリズムの1つ
 現在は分かりやすさの観点から、量子振幅増幅(QAA: Quantum Amplitude Amplification)の一部として論文上で紹介されることが多い
 𝑛𝑛ビットの探索問題を𝑂𝑂(2𝑛𝑛/2 )で求解する

 解が1つの場合
 全探索の計算量：𝑂𝑂(2𝑛𝑛 ) 様々な探索問題に応用できる（SAT問題、部分和問題、 積分、暗号解読、etc.）

𝑛𝑛 = 40000 0001 0010 0011
0100 0101 0110 0111
1000 1001 1010 1011
1100 1101 1110 1111
解

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

73

概要
Groverのアルゴリズム
1

1

1

1

入力：𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩ = 00 + 01 + 10 + |11⟩ (𝑛𝑛 = 2)2222
出力：解𝑤𝑤
2𝑛𝑛 個※各量子ビットのブラケット表記（中身はただのベクトルです）

 アルゴリズム① 𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩を入力② オラクル𝑈𝑈𝑤𝑤 を|𝑠𝑠⟩に作用させる： 𝑠𝑠𝑠 = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩

③ 振幅増幅操作𝑈𝑈𝑠𝑠 を|𝑠𝑠𝑠⟩に作用させる︓ 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 |𝑠𝑠𝑠⟩④ ②－③を2𝑛𝑛/2 回行った後に 𝑠𝑠 ′′ を測定

00 =

1
0
, 01 =
00

0
1, 10 =
00

0
0, 11 =
1
0

0
0
0
1

※ 𝒏𝒏 = 𝟐𝟐、解𝒘𝒘 = 𝟏𝟏𝟏𝟏 を考える

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

74

概要
Groverのアルゴリズム
1

1

1

1

入力：𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩ = 00 + 01 + 10 + |11⟩ (𝑛𝑛 = 2)2222
出力：解𝑤𝑤
2𝑛𝑛 個※各量子ビットのブラケット表記（中身はただのベクトルです）

 アルゴリズム① 𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩を入力② オラクル𝑈𝑈𝑤𝑤 を|𝑠𝑠⟩に作用させる： 𝑠𝑠𝑠 = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩

③ 振幅増幅操作𝑈𝑈𝑠𝑠 を|𝑠𝑠𝑠⟩に作用させる︓ 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 |𝑠𝑠𝑠⟩④ ②－③を2𝑛𝑛/2 回行った後に 𝑠𝑠 ′′ を測定

00 =

1
0
, 01 =
00

0
1, 10 =
00

0
0, 11 =
1
0

0
0
0
1

※ 𝒏𝒏 = 𝟐𝟐、解𝒘𝒘 = 𝟏𝟏𝟏𝟏 を考える

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

75

① 𝒏𝒏ビットの全状態の重ね合わせ |𝒔𝒔⟩を入力

 初期状態 00 に対してアダマール行列𝐻𝐻を適用する：
1
1
1
1
𝐻𝐻 ⊗ 𝐻𝐻 00 = 𝑠𝑠 = 00 + 01 + 10 + 112222
係数の二乗が各量子ビットの存在確率（それぞれ25%）

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

76

概要
Groverのアルゴリズム
1

1

1

1

入力：𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩ = 00 + 01 + 10 + |11⟩ (𝑛𝑛 = 2)2222
出力：解𝑤𝑤
2𝑛𝑛 個
 アルゴリズム① 𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩を入力② オラクル𝑈𝑈𝑤𝑤 を|𝑠𝑠⟩に作用させる： 𝑠𝑠𝑠 = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩

③ 振幅増幅操作𝑈𝑈𝑠𝑠 を|𝑠𝑠𝑠⟩に作用させる︓ 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 |𝑠𝑠𝑠⟩④ ②－③を2𝑛𝑛/2 回行った後に 𝑠𝑠 ′′ を測定※ 𝒏𝒏 = 𝟐𝟐、解𝒘𝒘 = 𝟏𝟏𝟏𝟏 を考える

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

77

オラクル
 入力ビット列𝑥𝑥に対して、𝑥𝑥が問題の解かどうか2択で教えてくれる関数
𝑓𝑓 𝑥𝑥 =

1 𝑥𝑥が解0 𝑥𝑥が解ではない オラクルの構築方法：①解そのものを使う
 例) 素因数分解：素数𝑥𝑥は𝑁𝑁の素因数？

①

𝑓𝑓 𝑥𝑥 =

②解の判定条件を使う(𝑝𝑝, 𝑞𝑞を𝑁𝑁の素因数とする)②

1 𝑥𝑥 = 𝑝𝑝 𝑜𝑜𝑜𝑜 𝑥𝑥 = 𝑞𝑞
0 otherwise

𝑓𝑓 𝑥𝑥 =

1 𝑁𝑁 𝑚𝑚𝑚𝑚𝑚𝑚 𝑥𝑥 = 00 otherwise 量子ゲートで①もしくは②のオラクル𝑓𝑓(𝑥𝑥)を構築することを考える

 現実の問題を解くにはもちろん②でなければならないが、以降は簡単のため①を考える
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

78

② オラクル𝑼𝑼𝒘𝒘 を|𝒔𝒔⟩に作用させる： 𝒔𝒔𝒔 = 𝑼𝑼𝒘𝒘 |𝒔𝒔⟩

 オラクル𝑓𝑓(𝑥𝑥)の代わりに次のようなオラクル行列𝑈𝑈𝑤𝑤 を定義：

𝑓𝑓 𝑥𝑥 =

1 𝑥𝑥 = 110 otherwise

𝑈𝑈𝑤𝑤 |𝑥𝑥⟩ = 解が判明している場合、𝑈𝑈𝑤𝑤 は次のように構築できる：− 𝑥𝑥 𝑥𝑥 = 11|𝑥𝑥⟩ otherwise

1
𝑈𝑈𝑤𝑤 = 𝐼𝐼 − 2 𝑤𝑤 ⟨𝑤𝑤| = 𝐼𝐼 − 2|11⟩⟨11| = 000 𝑠𝑠 ′ = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩は次のようになる：

𝑠𝑠 ′𝑥𝑥 が解の時
符号を反転

0 0 0
1 0 0
0 1 0
0 0 −1

1
1
1
1= 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩ = 00 + 01 + 10 − |11⟩2222

 解（に対応する量子ビット）のマーキング操作ととらえることもできる
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

79

概要
Groverのアルゴリズム
1

1

1

1

入力：𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩ = 00 + 01 + 10 + |11⟩ (𝑛𝑛 = 2)2222
出力：解𝑤𝑤
2𝑛𝑛 個
 アルゴリズム① 𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩を入力② オラクル𝑈𝑈𝑤𝑤 を|𝑠𝑠⟩に作用させる： 𝑠𝑠𝑠 = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩

③ 振幅増幅操作𝑈𝑈𝑠𝑠 を|𝑠𝑠𝑠⟩に作用させる︓ 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 |𝑠𝑠𝑠⟩④ ②－③を2𝑛𝑛/2 回行った後に 𝑠𝑠 ′′ を測定※𝒏𝒏 = 𝟐𝟐、解𝒘𝒘 = 𝟏𝟏𝟏𝟏 を考える

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

80

③ 振幅増幅操作𝑼𝑼𝒔𝒔 を|𝒔𝒔𝒔⟩に作用させる︓ 𝒔𝒔′′ = 𝑼𝑼𝒔𝒔 |𝒔𝒔𝒔⟩

 ②でマーキングした解に対応する量子の存在確率を増幅させ、それ以外の量子の存在確率を減衰
 振幅増幅行列𝑈𝑈𝑠𝑠 ：𝑈𝑈𝑠𝑠 = 2 𝑠𝑠 ⟨s| − 𝐼𝐼−11
 2量子ビットの場合、𝑈𝑈𝑠𝑠 = +1
2 +1
+1
 𝑠𝑠 ′′ は次のようになる︓

+1
−1
+1
+1

+1
+1
−1
+1

※𝑠𝑠は重ね合わせ状態

+1
+1
+1
−1

𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 𝑈𝑈𝑤𝑤 𝑠𝑠 = 0 ⋅ 00 + 0 ⋅ 01 + 0 ⋅ 10 + 1 ⋅ |11⟩
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

81

概要
Groverのアルゴリズム
1

1

1

1

入力：𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩ = 00 + 01 + 10 + |11⟩ (𝑛𝑛 = 2)2222
出力：解𝑤𝑤
2𝑛𝑛 個
 アルゴリズム① 𝑛𝑛ビットの全状態の重ね合わせ |𝑠𝑠⟩を入力② オラクル𝑈𝑈𝑤𝑤 を|𝑠𝑠⟩に作用させる： 𝑠𝑠𝑠 = 𝑈𝑈𝑤𝑤 |𝑠𝑠⟩

③ 振幅増幅操作𝑈𝑈𝑠𝑠 を|𝑠𝑠𝑠⟩に作用させる︓ 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 |𝑠𝑠𝑠⟩④ ②－③を2𝑛𝑛/2 回行った後に 𝑠𝑠 ′′ を測定※ 𝒏𝒏 = 𝟐𝟐、解𝒘𝒘 = 𝟏𝟏𝟏𝟏 を考える

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

82

④ ②－③を𝟐𝟐𝒏𝒏/𝟐𝟐 回行った後に 𝒔𝒔′′ を測定 𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 𝑈𝑈w |𝑠𝑠⟩に対して、 𝑠𝑠 ′′ を解（ 𝑤𝑤 ）とそれ以外（ 𝑠𝑠̂ ）に分けて考える sin 𝜃𝜃 =12𝑛𝑛に対して、 ②－③を𝑗𝑗回行った後の 𝑠𝑠 ′′ は次のように書ける：

𝑠𝑠 ′′ = 𝑈𝑈𝑠𝑠 𝑈𝑈𝑤𝑤 𝑗𝑗 𝑠𝑠 = sin 2𝑗𝑗 + 1 𝜃𝜃 𝑤𝑤 + cos 2𝑗𝑗 + 1 𝜃𝜃 𝑠𝑠̂ 1イテレーション毎に解の量子ビット 𝑤𝑤 の存在確率が増幅、それ以外が減衰 𝑤𝑤 の存在確率が最大化するのは、 sin 2𝑗𝑗 + 1 𝜃𝜃 = 1 ⇔ 2𝑗𝑗 + 1 𝜃𝜃 =𝜋𝜋 𝑛𝑛 1𝑗𝑗 ≤2 − ≤ 𝟐𝟐𝒏𝒏/𝟐𝟐
42

 𝑗𝑗 = 2𝑛𝑛/2 回後に測定すると、 𝑤𝑤 が高確率で出力される
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

𝑗𝑗 = 1
𝑗𝑗 = 0𝜋𝜋、sin 𝜃𝜃 ≤ 𝜃𝜃より：
2

2𝜃𝜃

𝜃𝜃

83

Groverを使った量子探索の応用

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

Groverのアルゴリズムのユースケース 様々な研究領域においてGroverのアルゴリズムが活用されています 一例：
データベース
計算複雑性
衝突問題
SAT

彩色問題
部分和問題

クエリ（SELECT句など）
集合演算 関係演算

暗号解読（共通鍵暗号、
公開鍵暗号、ハッシュ関数）

通信
機械学習
最近傍法
SVM
Neural Network クラスタリング
強化学習
k-means

セキュリティ

信号検出
ルーティング数学
多変数多項式
積分
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

文字列学
文字列照合
共通文字列

85

Groverのアルゴリズムのユースケース 様々な研究領域においてGroverのアルゴリズムが活用されています 一例：
データベース
計算複雑性
衝突問題
SAT

彩色問題
部分和問題

クエリ（SELECT句など）
集合演算 関係演算

暗号解読（共通鍵暗号、
公開鍵暗号、ハッシュ関数）

通信
機械学習
最近傍法
SVM
Neural Network クラスタリング
強化学習
k-means

セキュリティ

信号検出
ルーティング数学
多変数多項式
積分
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

文字列学
文字列照合
共通文字列

86

応用例：部分和問題
 参考：Quantum algorithm and experimental demonstration for the subset sum problem,
2022

部分和問題
入力：𝑛𝑛個の自然数からなる集合𝑆𝑆 = {𝑠𝑠1 , 𝑠𝑠2 , … , 𝑠𝑠𝑛𝑛 }、ターゲット自然数𝑡𝑡
出力：

 例：

𝐼𝐼

� 𝑠𝑠𝑖𝑖
𝑖𝑖

= 𝑡𝑡

𝑆𝑆:

𝑖𝑖

𝑠𝑠𝑖𝑖

を満たす整数集合の部分集合 𝐼𝐼 ∈ {1,2, … , 𝑛𝑛}

1

11

2

20

3

36

4

52

𝑡𝑡 = 67

解：{1,2,3} (11 + 20 + 36 = 67)

解をビット列で表現（𝑆𝑆の各要素を「選ぶ」「選ばない」）

解：11102𝑛𝑛 通りの組み合わせ

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

87

部分和問題を求解する量子回路

Reg 0
Reg1

0
0
0
0
0
0

𝐻𝐻
𝐻𝐻
𝐻𝐻
𝐻𝐻

部分和の計算

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝐻𝐻
𝐻𝐻
重ね合わせ

前処理

Grover (2𝑛𝑛/2 回イテレーション)

測定 Reg 0 ： Reg1 に対応する部分和とターゲット𝑡𝑡との差を格納する𝑛𝑛量子ビットのレジスタ
 Reg1 ：整数集合𝑆𝑆の取り方の組み合わせを格納する𝑛𝑛量子ビットのレジスタ※実際は量子位相推定(QPE)というものを使っているので、厳密な回路の形は異なります

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

88

部分和問題を求解する量子回路

Reg 0
Reg1

0
0
0
0
0
0

𝐻𝐻
𝐻𝐻
𝐻𝐻
𝐻𝐻

部分和の計算

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝐻𝐻
𝐻𝐻
重ね合わせ

前処理

Grover (2𝑛𝑛/2 回イテレーション)

測定 Reg 0 ： Reg1 に対応する部分和とターゲット𝑡𝑡との差を格納する𝑛𝑛量子ビットのレジスタ
 Reg1 ：整数集合𝑆𝑆の取り方の組み合わせを格納する𝑛𝑛量子ビットのレジスタ※実際は量子位相推定(QPE)というものを使っているので、厳密な回路の形は異なります

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

89部分和の計算と量子回路上へのエンコード
 Reg 0 には組合せの部分和とターゲット𝑡𝑡の差が格納 部分和の計算・ Reg1 と Reg 0 の対応付けには
量子位相推定（QPE）が使用される
 𝑆𝑆の各要素は角度情報(位相)として𝑅𝑅ゲートに格納 部分和は位相の和としてエンコードされる※実際は部分和は[0,1]に正規化され、0から2𝜋𝜋𝜋𝜋までの位相として表現されています。
位相は逆FFTを使うと Reg0 に取り出せます例）𝑆𝑆 = 2,3,5,7 , 𝑡𝑡 = 12Reg 0（𝑡𝑡のための補助量子ビット）

部分和を計算する量子回路の一部

𝑅𝑅𝑡𝑡

Reg1 = 0011 のとき、
Reg1
Reg 0 = 12 − (5 + 7) = 0 が対応付けられる Reg 0 = 0 が解に対応

𝑅𝑅𝑛𝑛

𝑅𝑅𝑡𝑡2
𝑅𝑅2

𝑅𝑅1

 オラクル𝑈𝑈𝑤𝑤 は、 Reg 0 = 0 に対応する Reg1 をマーキング（反転）すればいい
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

𝑅𝑅𝑛𝑛2

𝑅𝑅22

𝑅𝑅12

90

部分和問題を求解する量子回路
0

部分和

0

Reg1

0

Reg 0

組み合
わせ

0
0
0

𝐻𝐻
𝐻𝐻
𝐻𝐻
𝐻𝐻

部分和の計算

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝑈𝑈𝑤𝑤

𝑈𝑈𝑠𝑠

𝐻𝐻
𝐻𝐻
重ね合わせ

前処理

Grover (2𝑛𝑛/2 回イテレーション)

測定 Reg 0 ： Reg1 に対応する部分和とターゲット𝑡𝑡との差を格納する𝑛𝑛量子ビットのレジスタ
 Reg1 ：整数集合𝑆𝑆の取り方の組み合わせを格納する𝑛𝑛量子ビットのレジスタ
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

91

Grover (量子振幅増幅)
 Reg 0 = 0 に対応する量子ビット Reg1 をマーキング（位相を反転）するオラクル𝑈𝑈𝑤𝑤
 実際は1補助量子ビット c （ Reg1 Reg 0 の符号に相当）の符号を反転する
 Reg1 1 0 → − Reg1 1 0 とする

 量子回路上はControlled-Zを使ってこんな感じになります→

Reg 0
 Reg1 1 0 を増幅させる行列𝑈𝑈𝑠𝑠 中身は省略しますが、結果として振幅は以下のように増幅します（ 𝑤𝑤 ：解となるビット列、 𝑠𝑠̂ ：それ以外、 𝜙𝜙 ：0以外の角度）

sin 2𝑗𝑗 + 1 𝜃𝜃 𝑤𝑤 1 0 + cos 2𝑗𝑗 + 1 𝜃𝜃 𝑠𝑠̂ 1 𝜙𝜙

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

𝑐𝑐

Reg1
92

まとめ・今後の課題
 量子探索アルゴリズムであるGroverのアルゴリズムを紹介しました Groverのアルゴリズムを使うと𝑛𝑛ビットの探索を𝑂𝑂(2𝑛𝑛/2 )で求解できます 様々な研究領域でGroverのアルゴリズムが活用されています 応用例として、部分和問題（暗号解読等に関連が深い）を紹介しました

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

93

参考文献
 衝突問題：Quantum algorithms for element distinctness

methods for supervised and unsupervised learning 彩色問題：Improved Complexity of Quantum Oracles for
Ternary Grover Algorithm for Graph Coloring k-means：Quantum algorithms for supervised andunsupervised machine learning

 SAT：An Introduction to Quantum Computing, Without the  信号検出：A Quantum Search Based Signal Detection for
Physics
MIMO-OFDM Systems
 部分和問題：Quantum algorithms for subset finding クエリ：Quantum databases: Trends and challenges
 集合演算：Quantum Search Algorithm for Set Operation
 関係演算：Quantum Computation and Its Effects in
Database Systems
 SVM：Quantum optimization for training support vector
machines Neural Network：Quantum artificial neural networkarchitectures and components
 クラスタリング：Quantum clustering algorithms
 強化学習：Quantum reinforcement learning 最近傍法：Quantum algorithms for nearest neighbor ルーティング：A modified ant colony optimization
algorithm (mACO) for energy efficient wireless sensor
networks
 共通鍵暗号：Introduction to Post-Quantum Cryptography
 公開鍵暗号（符号暗号）：A Complete Quantum Circuit to
Solve the Information Set Decoding Problem
 ハッシュ関数：Quantum Cryptanalysis of Hash and ClawFree Functions
 多変数多項式：Solving Binary MQ with Grover’s Algorithm 積分：Practical numerical integration on NISQ devices
 文字列照合：String matching in O(n+m) quantum time
 共通文字列：Near-Optimal Quantum Algorithms for String
Problems

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

94

まとめ：全体
 データ工学における量子コンピューティングを紹介※QA：https://deim2022.ovice.in 量子コンピューティング概要
 量子機械学習アルゴリズム：QSVM、QCL
 量子組合せ最適化アルゴリズム：量子アニーリング等イジングマシン、QAOA
 量子探索アルゴリズム：Groverアルゴリズム、部分和問題

 量子コンピュータのユースケース
最適化＆探索問題

シミュレーション＆モデリング

AI＆機械学習概要

問題の規模に応じて計算量が指数関数的に膨大となる問題

物理学の基本方程式（力学／電磁気学
等）のように、微分積分などの計算量が膨大な数値計算を含む問題

ディープラーニングや強化学習などの計算量の多い機械学習手法

応用例

・信号機制御による渋滞解消
・資産ポートフォリオ最適化
・タンパク質設計最適化
・暗号解読

・電磁界シミュレーション
・触媒反応シミュレーション
・有機分子の結晶構造分析
・エンジンの熱伝達分析

・クラスタリングによる異常検知
・時系列分析
・次元圧縮
・画像と音声の分類

まだ見ぬ効果的なユースケースがデータ工学分野にもあるはず！
Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.

95

Copyright(C) 2022 KDDI Research, Inc. All Rights Reserved.