2022年06月09日

量子計算機による高次二値最適化問題の求解と無線応用
横浜国立大学 大学院工学研究院
知的構造の創生部門
准教授 石川 直樹
1/21

2022年06月09日

技術背景• ムーアの法則– 半導体の集積率は18ヶ月で2倍[1]– 2020年代には限界[2]• 新しい計算パラダイム– イジングマシン– 量子アニーリング– 量子計算[1] G. E. Moore, Cramming more components onto integrated circuits,Electronics, vol. 38, no. 8, pp. 114–117, 1965.
[2] F. B. McCormick et al., U.S. Department of Energy Big Idea Summit III,SAND-2018-2328R, Mar. 2018.
2/21

2022年06月09日

新技術①～③の概要• 二値変数最適化問題の二次加速が証明されている
量子アルゴリズム「グローバー適応探索」– 整数係数の高次項を含む目的関数に対応[3]– 実数係数への対応を可能とする技術（①特願2022-058075）• 応用事例– マルチアンテナ無線通信システムの復号処理と量子加速（②特願2022-058078）– 無線資源割当問題の量子ビット数削減（③特願2022-058084）[3] A. Gilliam, S. Woerner, and C. Gonciulea, “Grover adaptive search for constrainedpolynomial binary optimization,” Quantum, vol. 5, Apr. 2021.
3/21

2022年06月09日

本技術に関する知的財産権

発明の名称
新技術①：量子計算プ
ログラム、量子計算装
置及び量子計算方法
新技術②：量子計算プ
ログラム、量子計算装
置及び量子計算方法
新技術③：量子計算プ
ログラム、量子計算装
置及び量子計算方法

出願番号

出願人

発明者

特願2022-058075

石川直樹、
横浜国立大学法本雅矢

特願2022-058078

石川直樹、
横浜国立大学法本雅矢

特願2022-058084

石川直樹、
横浜国立大学佐野友貴
4/21

2022年06月09日

従来技術とその問題点• 二値最適化問題は数理計画ソルバ、コヒーレントイジングマシン、量子アニーリング等で解かれる• 3次以上の項を含む場合は2次以下に変形される• 変形する過程で二値変数が増え解の候補数が指数関数的に増える

5/21

2022年06月09日

従来技術とその問題点• グローバー適応探索[3]は高次二値変数最適化を可能とする新しい量子アルゴリズム• 問題サイズが小さい場合は実機においても二次加速が確認されている• ただし係数が整数の場合のみに対応している[3] A. Gilliam, S. Woerner, and C. Gonciulea, “Grover adaptive search for constrainedpolynomial binary optimization,” Quantum, vol. 5, Apr. 2021.
6/21

2022年06月09日

新技術①の特徴・従来技術との比較• 論文[3]の量子アルゴリズムを改変し実数係数への対応を可能とした– 従来技術1は実数係数を整数で近似する必要があった（＝量子ビット数増加）– 従来技術2はアルゴリズムが正常動作しない場合がある（Fejér分布に従うため量子計算の結果が真値より小さくなる）[3] A. Gilliam, S. Woerner, and C. Gonciulea, “Grover adaptive search for constrainedpolynomial binary optimization,” Quantum, vol. 5, Apr. 2021.
7/21

2022年06月09日

新技術①の内容• 目的関数：1 + 𝑥𝑥1 − 1.8𝑥𝑥2 𝑥𝑥3 𝑥𝑥4𝑥𝑥1 : 0𝑥𝑥2 : 0𝑥𝑥3 : 0𝑥𝑥4 : 0000

𝐇𝐇⨂71⋅𝜋
𝐔𝐺
4+11⋅𝜋𝐔𝐺
4+1𝑥𝑥11.8 ⋅ 𝜋
𝐔𝐺 −4−1.8𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

IQFT

𝐆𝐿𝐿8/212022年06月09日

新技術①の内容• 目的関数：1 + 𝑥𝑥1 − 1.8𝑥𝑥2 𝑥𝑥3 𝑥𝑥4観測結果（𝐿𝐿 = 0） 観測結果（𝐿𝐿 = 1） 観測結果（𝐿𝐿 = 2） 観測結果（𝐿𝐿 = 3）

9/21

2022年06月09日

新技術①の内容

目的関数値全探索（参考）
新技術

問合せ回数（古典領域）

10/21

2022年06月09日想定される用途• 二値変数最適化問題の求解– 本技術の適用により、実数係数を含む高次二値最適化問題を解けるようになるため、幅広い問題への応用が期待される– 実数係数をそのまま扱えるため必要な量子ビット数を削減できる• 無線分野における応用例：– 新技術②：マルチアンテナ無線通信システムの復号処理– 新技術③：無線資源割当問題• 他分野における応用例（未検証）：– 金融、物流、広告配信における最適性の保証

11/21

2022年06月09日

新技術②：復号処理の量子加速• 通信データの復号処理– 受信データシンボル → ビット列と対応づける処理– 最尤検出は高信頼な代わりに通信速度に応じて指数関数的に複雑化– 軽量検出技術は性能を代償に計算量削減– 量子計算による性能と計算量のトレードオフ打破
12/21

2022年06月09日

新技術②：復号処理の量子加速• 技術詳細– 受信シンボル𝐲𝐲 = 𝐇𝐇𝐇𝐇 + 𝐯𝐯

– 最尤検出 𝐬𝐬� = arg min 𝐲𝐲 − 𝐇𝐇𝐇𝐇 2𝐹𝐹
𝐬𝐬– 5G NRのビット列とシンボルの関係式を利用• 16-QAM: 𝑠𝑠 𝑖𝑖 =+1
1 − 2𝑏𝑏 4𝑖𝑖 [2 − 1 − 2𝑏𝑏 4𝑖𝑖 + 210𝑗𝑗
1 − 2𝑏𝑏 4𝑖𝑖 + 1 [2 − 1 − 2𝑏𝑏 4𝑖𝑖 + 310• 目的関数は4次 (16-QAM), 6次 (64-QAM), …
– 目的関数値の確率分布を導出し初期しきい値を決定

]

13/21

2022年06月09日

新技術②：復号処理の量子加速

ビット誤り率

ランダム初期値
MMSE初期値
提案初期値
提案&MMSE初期値

問合せ計算量の削減を確認
問合せ回数（古典領域）

14/21

2022年06月09日

新技術③：無線資源割当問題• 無線通信分野のNP困難な最適化問題– 基地局/アクセスポイント数（𝑁𝑁𝐴𝐴𝐴𝐴 ）やチャネル数（𝑁𝑁𝐶𝐶𝐶𝐶 ）の増加に伴い組合せ爆発• 必要な二値変数の個数：𝑁𝑁𝐴𝐴𝐴𝐴 ⋅ 𝑁𝑁𝐶𝐶𝐶𝐶• 解の候補数：2𝑁𝑁𝐴𝐴𝐴𝐴⋅𝑁𝑁𝐶𝐶𝐶𝐶– 従来技術はコヒーレントイジングマシンや量子アニーリングにより求解• 実時間で実用的な解に到達（産業応用の可能性大）• 一方で、最適性の保証なし
高速化の理論的裏付けなし
15/21

2022年06月09日

新技術③：無線資源割当問題• 技術詳細– チャネルのインデックスを二進数で表現• 二値変数の個数：𝑁𝑁𝐴𝐴𝐴𝐴 ⋅ 𝑁𝑁𝐶𝐶𝐶𝐶 → 𝑁𝑁𝐴𝐴𝐴𝐴 ⋅ log 2 𝑁𝑁𝐶𝐶𝐶𝐶• 例：𝑁𝑁𝐴𝐴𝐴𝐴 = 3，𝑁𝑁𝐶𝐶𝐶𝐶 = 3の場合
AP1

従来

𝑥𝑥111𝑥𝑥120AP2𝑥𝑥13𝑥𝑥210𝑥𝑥220

AP1はCH1提案0𝑥𝑥231𝑥𝑥3100𝑥𝑥300AP3𝑥𝑥41𝑥𝑥33
1AP3はCH3AP2𝑥𝑥2𝑥𝑥320

AP2はCH2AP1𝑥𝑥1AP3𝑥𝑥51𝑥𝑥60

AP1はCH1 AP2はCH2 AP3はCH3

AP1とAP2の干渉(同チャネル)
𝑥𝑥11 𝑥𝑥21+𝑥𝑥12 𝑥𝑥22+𝑥𝑥13 𝑥𝑥23

1 − 𝑥𝑥1 1 − 𝑥𝑥2 1 − 𝑥𝑥3 1 − 𝑥𝑥4+ 1 − 𝑥𝑥1 𝑥𝑥2 1 − 𝑥𝑥3 𝑥𝑥4+𝑥𝑥1 (1 − 𝑥𝑥2 )𝑥𝑥3 (1 − 𝑥𝑥4 )16/21

2022年06月09日

新技術③：無線資源割当問題

量子ビット数

量子ビット数削減
探索空間縮小
問合せ計算量削減
量子ゲート数増加

従来
2解析 𝑂𝑂 𝑁𝑁𝐴𝐴𝐴𝐴
提案
解析 𝑂𝑂 𝑁𝑁𝐴𝐴𝐴𝐴 log 2 𝑁𝑁𝐴𝐴𝐴𝐴
問合せ回数（古典領域）
アクセスポイント数𝑁𝑁
𝐴𝐴𝐴𝐴

17/21

2022年06月09日

実用化に向けた課題• 本技術は誤り耐性量子計算機の実現を前提としている• 量子誤り訂正には多くの量子ビットを必要とする[4, 5]– 距離𝑑𝑑のトポロジカル表面符号は1論理量子ビットあたり2 𝑑𝑑 + 1 2 物理量子ビットを必要とする– 𝑑𝑑 = 27の場合は1568倍の量子ビットが必要になる– 量子アルゴリズム共通の課題として認知されている• これらの課題解決に向けて激しい研究開発競争が世界的に繰り広げられている[4] K. Fujii, “Noise threshold of quantum supremacy,” arXiv:1610.03632 [quant-ph],Oct. 2016.
[5] C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20
million noisy qubits,” Quantum, vol. 5, p. 433, Apr. 2021.
18/21

2022年06月09日

企業への期待• 無線通信、量子計算、組合せ最適化等の関連技術を持つ企業との共同研究を希望している– 無線通信の観点では、技術者の夢である性能と計算量のトレードオフ打破が期待できる– 量子計算の観点では、キラーアプリケーションとしての発展が期待できる– 組合せ最適化の観点では、高次最適化問題を効率良く解く唯一のアプローチであり、他の様々なNP困難問題への応用が期待できる
19/21

2022年06月09日

本技術に関する知的財産権（再掲）

発明の名称
新技術①：量子計算プ
ログラム、量子計算装
置及び量子計算方法
新技術②：量子計算プ
ログラム、量子計算装
置及び量子計算方法
新技術③：量子計算プ
ログラム、量子計算装
置及び量子計算方法

出願番号

出願人

発明者

特願2022-058075

石川直樹、
横浜国立大学法本雅矢

特願2022-058078石川直樹、
横浜国立大学法本雅矢

特願2022-058084

石川直樹、
横浜国立大学佐野友貴
20/21

2022年06月09日

お問い合わせ先• 横浜国立大学 研究推進機構• 産学官連携推進部門 澁谷 規子• ＴＥＬ：０４５－３３９ －４４５０• ＦＡＸ：０４５－３３９ －３０５７• e-mail ： sangaku-cd@ynu.ac.jp

YouTube動画「電子情報通信学会
若手研究者弾丸プレゼン」
https://www.youtube.com/watch?
v=G-YCDUgd9Tw

基本原理の解説資料「無線通信と量子計算の数学的類似性および最新の応用研究動向」
https://researchmap.jp/naoki-ishikawa/presentations/36956014/attachment_file.pdf

21/21