この記事の概要
2020年8月5日に投稿された論文、Date & Potok, "Adiabatic Quantum Linear Regression"を読んだので、その内容の理解を深めるためにアウトプットしたものです。
序章: 線形回帰
として、
組のデータ
に対する、線形回帰モデルは
となります。ここで
と、以下のの行列を定義します。
これらを用いて線形回帰モデルの式を表現すると
となります。ここから誤差の2乗和
の最小値を与えるを推定することを最小二乗法と呼びます。最適化において
は定数項なので、これを無視した
を最小にすることを目指します。
QUBO化
精度ベクトル
(1)式をQUBO化します。そのために精度ベクトルを導入します。ここで
の成分は2の冪乗で表現し、プラス・マイナス両方取りうるとします。ただし、
の成分は大きさ順に並べられていなければなりません。
例として次のような精度ベクトルが考えられます:
バイナリ変数
さらにのバイナリ変数の行列
を導入し、これと精度ベクトルを用いて
を表現します。
例としてを用意すると、
を表現することができます。
を用いることで、上式を行列形式に書き換えましょう。
QUBO化
以上より(1)式は
となります。これをD-Waveで解くことを目指します。この式は
と同じ形をしており、これはNP困難であることが知られています。
数値実験
比較対象
D-Wave 2000Qマシンを用いた量子アニーリングがどれほど有用であるかを検証するために、古典的なアプローチとして以下のようなものを用います。
- 3.6 GHz 8-Core Intel i9 プロセッサ
- 64GB 2.666 MHz DDR4 メモリ
- 用いた数値計算ライブラリ: Scikit-learn
数値実験結果
回帰エラー
回帰エラーを元に2つの比較結果を見てみましょう。
Experimental Runs Where | Scikit-learn Error | D-Wave Error |
D-Wave fit the data (80% runs) | 5.0261 | 5.0362 |
D-Wave fit the data (20% runs) | 4.8188 | 15.0657 |
Overall | 4.9846 | 7.0421 |
これを見るとD-Waveでの実行の方がエラーが大きくなっています。これは量子アニーリング実行中に量子ビット間の接続が切れると、誤った結果が出ることが知られているD-Waveマシンのハードウェアの問題だと考えられます。
データ数Nに対するスケーラビリティ

上図は横軸をデータ点の数、縦軸を計算時間にしてグラフを書いたものです。左図はデータ点数の小さいときの比較図、そそして右図はデータ点数が大きい時の比較図です。データ点数が1600万になると、D-Waveでの計算時間がScikit-learnでのそれよりも2.8倍高速であることがわかりました。
特徴量数dに対するスケーラビリティ

こちらの図は横軸を特徴量の数、縦軸を計算時間にしてグラフを書いたものです。特徴量数が32の時点で、D-Wave実行がScikit-learnでの計算時間よりも2.8倍高速であることがわかりました。
結言
古典コンピュータ上でScikit-learnによる線形回帰と、D-Wave上で同じ問題を解いた場合の比較実験を行いました。その結果、D-Waveのハード性能の問題から、精度には古典コンピュータに軍配が上がりました。一方で、データ点数が大量になるとD-Waveでの量子アニーリングの実行の方が高速であることがわかりました。