京大基研量子情報スクール用ノート
Kosuke Mitarai
2019/3/20

1 はじめに量子機械学習は、機械学習に量子コンピュータのパワーを使おういう試みである。近年の機械学習の発展に伴って、量子アルゴリズムによってそれらを加速しようという動きが加速している。[1]が良いレビュー。このノートでは、サブルーチンとして使われているテクニックやアルゴリズムを一通り見た後、最近の機械学習アルゴリズムについてまとめる。

2 機械学習とは
ここでは教師あり機械学習を例として機械学習とは何かを説明しよう。教師あり機械学習では、
以下のデータが訓練データとして与えられる。

• N 個の説明変数: {xi } (i = 1, · · · , N )– 例えば、手書き数字画像のピクセル値• 対応する N 個の教師データ: {yi } (i = 1, · · · , N )– 例えば、手書き数字のラベル
教師データ {yi } は、何らかの形で説明変数 {xi } と関連づいていると考えられる。背後に存在するこの「関係」を仮に g としよう。g(xi ) が教師データ yi を与えると考えるのだ。機械学習の目
的は、与えられた訓練データから g を近似する関数 f を構築することである。 f をデータから構築することを学習と呼び、学習によって構築される関数 f をモデルと呼ぶ。
通常モデル f には何らかの形のパラメータ付き関数を仮定し、パラメータを調整することによって学習を行う。 以下に少し例を挙げよう。

• 線型回帰 (連続値予測) においては
fw,b (x) = w · x + b

1(1)

• ロジスティック回帰 (2 値分類タスク) においては
fw,b (x) =1
1 + ew·x+b(2)• ニューラルネットでは
f{Wl } (x) = hL (WL hL−1 (· · · W3 h2 (W2 h1 (W1 x))))(3)

ここで Wl は行列であり、hl は何らかの非線形関数である。
これらのモデルでは、w, b や W といったパラメータを調整することで、背後に存在する関係 g を近似する。

3 Quantum arithmetics
Long-term の量子コンピュータを用いた計算では、量子コンピュータ上で適当な古典計算を行うことが多い。量子回路を用いた通常の論理演算は quantum arithmetics と呼ばれている。通常の論理演算をどのように行うか、その一番単純な説明を以下に述べよう。
まず前提として、NAND 演算が可能であればどのような論理演算でもその組み合わせによって実現可能である。NAND 演算は AND + NOT であるが、NOT 演算は X ゲートをかければよい。そこで AND 演算を実現できればユニバーサルな論理演算が可能となるが、それには Toﬀoli
ゲート (controlled bit が 2 つの CNOT ゲート) を用いて、
Toﬀoli|b0 ⟩ |b1 ⟩ |0⟩ −−−−→ |b0 ⟩ |b1 ⟩ |b0 · b1 ⟩(4)のようにすればよい。したがって原理的には、 Toﬀoli ゲートと X ゲートをうまく組み合わせることでどのような古典計算も実現できる。しかしここに述べたようなナイーブな実装では必要な補助ビットの数が多くなってしまうため、このビット数を落とすために様々な研究が行われている。
さて、量子コンピュータ上でどのような古典計算もできることを使うと、次のような複雑な演算も可能であることになる。例えば、適当な実数を r 、それを表すビット列*1 を b(r)、f : R → R を関数とし、|b(r)⟩ |0m ⟩ |0n ⟩ → |b(r)⟩ |Gabbage⟩ |b(f (r))⟩(5)という演算は、f が古典コンピュータ上で効率的に計算可能な関数ならば、効率的にできる。ここで用意した m qubit のレジスターは計算時の補助ビットとして扱われる部分である。もちろん、様々な実数の重ね合わせ状態を入力すれば
N
N
1 ∑
1 ∑
√
|b(ri )⟩ |0m ⟩ |0n ⟩ → √|b(ri )⟩ |Gabbage⟩ |b(f (ri ))⟩
N i=1
N i=1

というある意味での並列計算ができる。
*1 b(r) は例えば r の浮動小数点数表示

2(6)

4 データの取り扱い
一般的な機械学習では古典的なデータ (画像など) を取り扱う以上、量子状態に何らかの方法でデータを送り込む必要がある。ここではよく扱われるデータアクセスモデルについて記述する。

4.1 Quantum random access memory
Quantum Random Access Memory (QRAM) とは、あるバイナリデータ xi のアドレス i を記述する量子ビット列 |i⟩ が与えられたとき、そのデータ xi を量子ビット列 |xi ⟩ として取り出す機能のことである。具体的には、次のような機能が QRAM と呼ばれることが多いようだ。
QRAM|i⟩ |0⟩ −−−−−→ |i⟩ |xi ⟩(7)

通常 QRAM はユニタリーなプロセスとして実現することが仮定される。したがって、QRAM の存在を仮定するとき、以下のように重ね合わせ状態を入力すれば、同時並列的にデータを量子状態にエンコードすることが可能である。

1 ∑
1 ∑
QRAM
√
|i⟩ |0⟩ −−−−−→ √|i⟩ |xi ⟩
N i=1
N i
N

(8)

現実にこれが可能であるかどうかはまだわからない。具体的な実装方法としては [3] などで提案がある。

4.2 振幅エンコーディング
HHL アルゴリズムなど一部のアルゴリズムでは、N 次元のベクトル v を以下のように量子ビットに埋め込んだ状態を用いる。*2|v⟩ =ただし ∥v∥2 =∑1 ∑vi |i⟩
∥v∥ i

(9)

2
i vi 。この状態を準備する方法には、QRAM を用いる。以下でそのやり方を紹介しよう。なお、以下では簡単のため v は実数であると仮定する。

4.2.1 ナイーブな方法
1. QRAM を用いて v の各成分のビット列表示 b(vi ) をエンコードした以下の状態を用意する。ビット列は n bit であるとする。

1 ∑
1 ∑
QRAM
√
|i⟩ |0n ⟩ −−−−→ √|i⟩ |b(vi )⟩
N i=1
N i
N

(10)

*2 このノートではケットの中に太字を書いたとき、それは式 (9) のような状態を表すことにする。逆に太字でないときは、それはすべてビット列を表す。

3

2. もう一つ m bit のレジスターを用意し、quantum arithmetics によって m bit の精度で
1−1(vi ) を計算する。
π cos

(
)⟩
N
N
1 ∑
1 ∑
1
m arithmetics−1√|i⟩ |b(vi )⟩ |0 ⟩ −−−−−−−→ √|i⟩ |b(vi )⟩ bcos (vi )
π
N i=1
N i=1

(11)

簡単のため arithmetics に必要な補助ビットは省略しているが、本来はたくさんの補助ビットがあることは心に留めておこう。ここでの b

(1

π cos

∑
2
cos−1 (vi ) ≈2−k−1 bk
π
m−1

k=0

となるようなビット列であるとする。

3. 補助ビットを 1 bit 用意し、bk

(2

π cos

−1

−1

(

)
(vi ) は浮動小数点表示ではなくて、

2
cos−1 (vi )
π

)
(12)

)
(vi ) を格納しているレジスターから、controlled-Ry

ゲートをかける。それぞれのビット bk が 1 ならば Ry (2−k ) を補助ビットにかけるという操作をすれば、以下の演算が実現される。

1 ∑√|i⟩ |b(vi )⟩ b
N i=1
N

(

1
cos−1 (vi )
π

)⟩
|0⟩

(
)⟩ m−1
( (
)
)
N
∏
1
1 ∑
1
controlled-Ry−−−−−−−−→ √|i⟩ |b(vi )⟩ b
Ry bk
cos−1 (vi )cos−1 (vi ) 2−k |0⟩
π
π
N i=1
k=0
(
)
(
)⟩
)
m−1
N
∑ (1
1
1 ∑
bk
|i⟩ |b(vi )⟩ bcos−1 (vi )Ry
cos−1 (vi ) 2−k |0⟩
(13)
=√
π
π
N i=1
k=0

ここで

Ry (θ) |0⟩ = cosθθ|0⟩ + sin |1⟩
2
2

(14)

なので、式 (12) から

Ry

(m−1
∑
k=0

(
bk

)
)
√
1
cos−1 (vi ) 2−k |0⟩ = vi |0⟩ + 1 − vi2 |1⟩π(15)である。したがってこのステップによって生成される状態 (式 (13)) は、

1 ∑√|i⟩ |b(vi )⟩ b
N i=1
N

(

)⟩ (
)
√
1
−1
2
cos (vi )vi |0⟩ + 1 − vi |1⟩
π

(16)

である。

4. 次に、前ステップで Ry をかけた補助ビットを測定する。もし |0⟩ を観測することができれば、量子状態は次のものに収縮する。

(
)⟩
N
1
1 ∑
vi |i⟩ |b(vi )⟩ bcos−1 (vi )|0⟩∥v∥ i=1π∑ 2
この状態が得られる確率は
i vi /N である。
4(17)

5. ステップ 1, 2 に相当するユニタリーの逆演算を行い、いらないレジスターを 0 に戻す。*3 こ∑
1の操作を終えれば、所望の状態 |v⟩ = ∥v∥
i vi |i⟩ を得られる。
なお、vi が index i から効率的に計算できる関数であるときには、直接 cos−1 (vi ) を計算すればよ
いので、QRAM を使わなくても |v⟩ を作り出せる。
ここで紹介した方法には、(QRAM を使っていることのほかに) 二つの問題点がある。

• ユニタリー操作でないこと。結果として、2 |v⟩ ⟨v| − I のような演算子*4 を作ることができ
ないこと。

•

∑

2
i vi (データの 2 次モーメント) が O(N ) でなければ、成功確率がどんどんと小さくなってしまうこと。
この二点を解決する手法が Prakash [7] により提案された。

4.2.2 Prakash 法
以下で説明する手法を便宜上 Prakash 法と呼ぶことにする。Praksh 法は Grover による提案[4] をベースとしていると思われる。Prakash 法ではまず、図 1 のように、∥v∥2 を次々に二分割していくデータ構造を準備する。∥v∥2 は規格化しておき、∥v∥2 = 1 となっていることにする。それぞれのノードに保持されているデータには|parent node address⟩ |0m ⟩→ |parent node address⟩ |bit-string stored at the childdren node⟩(18)のように O(poly log N ) 時間でアクセス可能であると仮定する。
さて、簡単な例として、Prakash 法によって図 1 のデータ構造を振幅エンコーディングする方
法をいかに記そう。

1. |000⟩ |0n ⟩ を準備する。
2. root の子である node 0 のデータを取得して、|000⟩ b(∑

3
2
i=0 vi)⟩とする。

3. 1 ビット目に、4.2.1 と同様の手順で controlled rotation をかけ、node 0 のデータはuncompute する。得られる状態は
v

v
u 7
u 3
u∑
u∑
t
vi2 |0⟩ + t
vi2 |1⟩ |00⟩ |0n ⟩
i=0

(19)

i=4

4. 1 ビット目をアドレスビットと見立てて、node 00, node 10 のデータを取得する。状態は
v
v
u 3
u 7
u∑
∑
( 2
)⟩ u
(
)⟩
2
t
2
(20)
vi |0⟩ |00⟩ b (v0 + v1 )/P + t
vi2 |1⟩ |00⟩ b (v42 + v52 )/P
i=0

i=4

*3 このような操作は量子計算で頻出し、uncompute と呼ばれる。
*4 このような演算子はデータを入力とした量子ウォークを実現するために必要子である。

5

root

Node 1
� +� +� +�

Node 0� +� +� +�

Node 00
� +��Node 000�, sign ��Node 001
�, sign ��Node 10� +��Node 01� +��Node 010
�, sign ��Node 011
�, sign ��Node 100�, sign ��Node 101�, sign ��Node 11� +��Node 110�, sign ��Node 111
�
, sign ��

図 1 Prakash [7] による振幅エンコーディングのためのデータ構造。P は各ノードの parent ノードの値。

5. 2 ビット目に同様の手順で controlled rotation をかけ、データビットを uncompute する。
得られる状態は(√

v02 + v12 |00⟩ +

)
√
√
√
2
2
2
2
2
2
v2 + v3 |01⟩ + v4 + v5 |10⟩ + v6 + v7 |10⟩ |0⟩ |0n ⟩(21)

6. 最後のデータも同様に取得し、3 ビット目に controlled rotation をかける。最後のノードには vi の符号も格納されているので、それに応じて符号も処理する。これにより
7∑

vi |i⟩(22)i=0が得られる。
ステップ数は O(log N ) となることは明らかだろう。QRAM 的な機能 (式 (18)) が O(poly log N )でできると仮定したので、全体でも O(poly log N ) の時間で実行可能である。この手法は quantum

recommendation system [5] などで使用例がある。ユニタリー操作で完結しているため使いやすい。

5 使用されるアルゴリズム・テクニック
5.1 Swap test
Swap test は量子状態を破壊することなく 2 つの状態 |v⟩ , |w⟩ の overlap | ⟨v|w⟩ |2 を測定す
るアルゴリズムである。図 2 のような量子回路を用いる。補助ビットの Z 期待値をとることで、| ⟨v|w⟩ |2 を測定できることは簡単に確かめられる。補助ビットの Z 測定によって |v⟩ , |w⟩ が壊
されないことに注意したい。したがって |v⟩ , |w⟩ 一組があれば何回でも測定を繰り返すことが可
能である。

6

|0⟩

| ⟩

| ⟩

H

� =

H

�
�

2

図 2 Swap test

5.2 Density matrix exponentiation
Density matrix exponentiation [6] は、ある密度行列 ρ をハミルトニアンとする時間発展演算
子 exp(iρT ) を量子状態に作用させるためのテクニックである。

ρ を n-qubit の密度行列、exp(iρT ) をかけるターゲットとなる n-qubit の量子状態を σ 、Snを n-qubit 量子状態に対する swap ゲートとする。δ を実数とし、exp(−iδSn ) というゲートを考えよう。Sn2 = I であるから、exp(−iδSn ) = I cos δ − iSn sin δ(23)である。Density matrix exponentiation では、以下の操作を行う。

1. ρ ⊗ σ を用意し、exp(−iδSn ) を作用させる。
exp(−iδSn )ρ ⊗ σ exp(−iδSn ) = ρ ⊗ σ cos2 δ + σ ⊗ ρ sin2 δ − i(Sn ρ ⊗ σ − ρ ⊗ σSn ) cos δ sin δ(24)
2. もともと ρ のあったレジスターを無視する。すなわち、部分トレースをとる。常識のそれ
ぞれの項はpartial traceρ ⊗ σ −−−−−−−−→ σ(25)partial traceσ ⊗ ρ −−−−−−−−→ ρ∑Sn ρ ⊗ σ = Sn
ρij σkl |i⟩ ⟨j| ⊗ |k⟩ ⟨l|(26)

i,j,k,l=∑ρij σkl |k⟩ ⟨j| ⊗ |i⟩ ⟨l|i,j,k,lpartial trace−−−−−−−−→∑

ρij σkl δkj |i⟩ ⟨l| = ρσ(27)i,j,k,lpartial traceρ ⊗ σSn −−−−−−−−→ σρ(28)となるので、もともと σ のあったレジスターに残る量子状態は

σ1 = σ cos2 δ + ρ sin2 δ − i[ρ, σ] cos δ sin δ7(29)である。δ を十分小さくとっておき、δ 2 の項を無視することにすると

σ1 = σ − i[ρ, σ]δ + O(δ 2 )(30)

3. ρ のコピーを T /δ 個用意し、ステップ 1, 2 を T /δ 回繰り返す。
アルゴリズムの誤差を評価しよう。ステップ 1 と 2 を合わせた操作を Fρ とする。

Fρ σ = σ − i[ρ, σ]δ + O(δ 2 )(31)e−iρδ σeiρδ = σ − i[ρ, σ]δ + O(δ 2 )(32)

Fρ σ = e−iρδ σeiρδ + O(δ 2 )

(33)

一方で

なので、

であるといえる。式 (33) の両辺に Fρ を繰り返しかければ、FρT /δ σ = e−iρT σeiρT + O(δ 2 )(34)となり、ステップ幅 δ の 2 乗のオーダーの誤差が現れることがわかる。

5.3 位相推定
量子位相推定 (Quantum Phase Estimation, QPE) は、適当なユニタリー U が与えられたとき、その固有値 ei2πϕi をビット列として取り出すためのアルゴリズムである。Nielsen-Chuangの教科書などを参照。QPE は、U の固有値 ei2πϕi に対応する固有ベクトルを |ui ⟩ とするとき、controlled-U と量子フーリエ変換を用いて、次の変換を実現する。
∑
QPE ∑αi |ui ⟩ |0m ⟩ −−−→
αi |ui ⟩ |b(ϕi )⟩i

ただし b(ϕi ) は ϕi =

∑m−1
k=0

(35)

i

2−k−1 bk (ϕi ) となるビット列である。

5.4 量子ウォーク
M
N 個の正規直交ベクトル {|vi ⟩}N
i=1 と M 個の正規直交ベクトル {|wj ⟩}j=1 を用いて以下の演算子を定義しよう。

(
W =

2

N
∑

)
|vi ⟩ ⟨vi | − I

i=1

2

M
∑


|wj ⟩ ⟨wj | − I 

(36)

j=1

この演算子 W は以下の有用な性質を持つ。D を Dij = ⟨vi |wj ⟩ を成分とする行列とし、D の右特異ベクトルのうち一つを a、対応する左特異ベクトルを b 、対応する特異値を σ = cos θ ̸= 0 とする。このとき、8∑∑• { i ai |vi ⟩ , j bj |wj ⟩} という 2 つのベクトルによって張られる空間は W の不変部分空間。

• その不変部分空間における W の固有値は e±i2θ 。
∑∑• 対応する固有ベクトルは |µ± ⟩ = e±iθ i ai |vi ⟩ + j bj |wj ⟩。
証明は説明が込み入るので避ける。|vi ⟩ , |w⟩j をうまく作れば、任意の行列 D についてその固有値を間接的に持つ演算子 W を作り出せることに注意したい。

5.5 HHL アルゴリズム
多くの量子機械学習アルゴリズムは、Harrow-Hassidim-Lloyd による逆行列計算アルゴリズム(HHL アルゴリズム) をベースとして構築されている。
HHL アルゴリズムは、N × N の疎行列 A、N 次元のベクトル v について、|v⟩ −−−→ A−1 v
HHL

⟩

(37)

という変換を効率良く計算するアルゴリズムである。その計算量は、現在知られているベストのもので、O(sκpoly log(sκ/ϵ)) である。(s は A の sparsity・κ は A の条件数・ϵ は出力状態⟩の A−1 v からの誤差) 一方で古典ベストのアルゴリズムは共役勾配法であり、その実行時間はO(N sκ log(1/ϵ)) なので、行列のスパース性 (s = O(poly log N )) を仮定すれば、HHL アルゴリ
ズムは行列の次元 N について指数加速を実現している。
オリジナルバージョンの HHL アルゴリズムは大まかに以下のようなものである。A の固有値を 0 < λi < 1、規格化された固有ベクトルを ai とするとき、

1. 状態 |v⟩ を QRAM などを駆使して用意する。
∑
2. controlled-ei2πA を使った位相推定によって i ⟨v|ai ⟩ |ai ⟩ |λi ⟩ をつくる。
3. 4.2.1 と同様のアルゴリズムによって、補助ビットに controlled rotation をかけ
√
(
)
∑
1
1
⟨v|ai ⟩ |ai ⟩ |λi ⟩|0⟩ + 1 − 2 |1⟩
λi
λi
i

(38)

を得る。

⟩
1
−1
4. 補助ビットを測定して |0⟩ が観測されれば、 ∥A−1
v を得る。
v∥ A
次のセクションで、HHL アルゴリズム、もしくはそれと似たアイデアを用いた量子機械学習ア
ルゴリズムについて述べていく。

9

6 HHL アルゴリズムベースの量子機械学習
6.1 量子線型回帰 [9]6.1.1 線型回帰
線型回帰では、

fw,b (x) = w · x + b(39)という形の関数によって教師データからモデル fw,b を作成する。データ x は M 次元の実数ベク
トル、データ数は N とする。オフセットのパラメータ b は、x = {xi }M
i=1 に一つデータ x0 を追加し、常に x0 = 1 としておけば w に含めてしまうことができる。そこで以下では、

fw (x) = w · x(40)をモデルとする。コスト関数としては二乗誤差

L(w) =

N∑(fw (xi ) − yi )

2

(41)

i=1

を選ぶ。xi の成分は xi = {xij }M
j=1 と書く。目標はこのコスト関数 L(w) を最小とする w を見つけることである。これは∂L(w)∂w = 0 の条件によって達成できる。この条件は以下の方程式に帰

着する。
N
N ∑
∑

xji xjk wk =N∑

xji yj(42)

j=1

k=1 j=1

X を xij をその成分として持つ行列とし、その転置を X T と書くとw∗ = (X T X)−1 Xy(43)が最適なモデルパラメータである。(X T X)−1 X ≡ X + は X の疑似逆行列と呼ばれ、X の特異値
分解 X = U diag(σ1 · · · σM )V † を用いると以下のように書き下せる。特異値は大きさの降順に並べ、r 個の特異値が非ゼロであったとするとき、

(

X

+

= V diag)
1
1, · · · , , 0, · · · , 0 U †
σ1
σr

(44)

となる。
未知のデータ x̃ が入力されたとき、モデルによる予測値は、上記で得た最適な w∗ を使って

fw∗ (x̃) =∑∗i wi x̃i によって与えられる。これを書き下すと

fw∗ (x̃) =

r
∑
1

σ
i=1 i


(
)
M
N
∑
∑

xj vji 
uik yk
j=1

(45)

k=1

N
ただし vij , uij は V, U の (i, j) 成分。 以下では vi = {vji }M
j=1 、ui = {uji }j=1 と書くことに

する。

10

6.1.2 量子アルゴリズム
ここでは [9] による HHL アルゴリズムをベースとした量子アルゴリズムについて述べる。先に概要を以下に書いておく。

1. X T X という行列を密度行列として準備する。つまり ρX T X =∑i,j (X

TX)ij |i⟩ ⟨j| を作る。

2. Density matrix exponentiation に よ っ て exp(−i2πρX T X ) の 位 相 推 定 を 状 態∑N2√1i=1 |xi ⟩ |i⟩ に対して実行し、σi のビット列を取得する。
N∑r
3. σi2 の逆数を補助ビットへの controlled rotation によって乗じる。すると i=1 σr−1 |vr ⟩ |ur ⟩が得られる。

4. |x̃⟩ |y⟩ という状態を作り、swap test によって内積を評価する。
わかりにくいと思われる点について以降で補足説明していく。
まず密度行列の準備について。実は、データを振幅エンコードした状態∑N

i=1 |xi ⟩ |i⟩ の部分系

が X X をエンコードした密度行列を持っている。|i⟩ の部分について部分トレースをとると、
T

(N
∑


) N
N
N ∑
∑
∑


|xi ⟩ ⟨xj | ⊗ |i⟩ ⟨j||xi ⟩ |i⟩⟨xj | ⟨j| =i=1

i=1 j=1

j=1

partial trace−−−−−−−−→N ∑N∑|xi ⟩ ⟨xj | δij

i=1 j=1=N∑|xi ⟩ ⟨xi |

i=1

=

N ∑
M ∑
M
∑

xij xik |j⟩ ⟨k|(46)

i=1 j=1 k=1となって ρX T X に等しいことがわかる。
位相推定の部分。まず、∑N

i=1 |xi ⟩ |i⟩

を Schmidt 分解すると、

N
∑

N ∑
M
∑

|xi ⟩ |i⟩ =i=1

xij |j⟩ |i⟩

i=1 j=1

=

=

N ∑
M ∑
r
∑

uik σk vjk |j⟩ |i⟩

i=1 j=1 k=1r∑

σk |vk ⟩ |uk ⟩

(47)

k=1

exp (i2πρX T X ) を作用させるのはこのうち |vi ⟩ の部分。つまり、|vi ⟩ の部分と∑N

i=1 |xi ⟩ |i⟩の |i⟩ の部分に対して少しだけ swap ゲートをかけることを繰り返し、5.2 の density matrix

11

exponentiation を行う。vk は X の右特異ベクトルなので、X T X の固有ベクトルであり、その固有値は σi2 である。したがって位相推定をかけると以下の状態が得られる。
r∑⟩σk |vk ⟩ |uk ⟩ b(σk2 )

(48)

k=1

さらに、HHL アルゴリズムと同様に controlled rotation → 測定 → 位相推定の uncompute を行うことによって

1
√∑

r
∑
1

σk
−2
k σk k=1|vk ⟩ |uk ⟩(49)

までもっていくことができる。これで式 (45) の vji と uik の部分を構築することができた。
最後に、式 (49) の状態を用いて未知データ x̃ に関する予測を行う。式 (45) から、式 (49) の状態と |x⟩ |y⟩ という状態との内積を評価できれば良いことがわかる。内積を一番簡単に評価できるのは 5.1 で紹介した swap test だが、|x̃⟩ |y⟩ と √∑1

∑r

−2
k σk

1
k=1 σk |vk ⟩ |uk ⟩ に対する swap テ

ストをただ行うだけでは、符号の情報が失われてしまう。そこで解決策として、全ての状態操作を

conditional に行い、


r
∑
1



1
1
√ |0 · · · 0⟩ + √∑|vk ⟩ |uk ⟩
σ
−2
2
k
σ k=1
k

k

1
√ (|0 · · · 0⟩ + |x̃⟩ |y⟩)2(50)のような状態を用意する。この二つの状態間の swap test を行えば、得られる期待値は | 12 +1
2∗∗
2 fw (x̃)| となるので、fw (x̃) の符号まで復元することができる。

6.2 量子サポートベクターマシン
6.2.1 サポートベクターマシン
サポートベクターマシン自体の詳細な説明に立ち入ると 4 ページ以上は必要になると思うので他の文献に譲る。*5 サポートベクターマシンは、与えられたデータセットの二値分類を行う手法の一つである。二値分類問題なので、各データ xi について教師データは yi = ±1 のどちらかの値をとることにする。サポートベクターマシンは、与えられた訓練データをもとに、xi を分割するのに最適な超平面 w · x + b = 0 を探すアルゴリズムである。最適化された超平面の片側には yi = 1のデータのみが存在し、もう片方には yi = −1 のデータのみが存在するような超平面を実現する
パラメータ w, b を探索する。サポートベクターマシンが構築するモデルは

fw,b (x) = sign (w · x − b)
*5 例えば [2] の 7 章や [10] の (20) 式。ネット検索でもたくさん出てくる。

12

(51)

である。
サポートベクターマシンは、この問題を線型連立方程式に帰着させて解く。その際、w は以下の関係式によって変数 α へと変換される。

w=

N
∑

αi xi

(52)

i=1

また、カーネル行列と呼ばれる行列 K を以下で定義する。

Kij =

M
∑

xik xjk(53)

k=1

これらを用いて、サポートベクターマシンが解く線型連立方程式は



0 1
 1

 1

 ..
 .

···

1

1

K + γ −1 I


(
) (
)

b
0

=

y
 α


(54)

1
である。ここで



0 1
 1


F :=  1
 ..
 .
′

(

α :=
′

y :=

(

1
b
α
0
y

···

1

K +γ

−1

1

I









(55)

)
(56)
)
(57)

と定義しておく。γ は正則化パラメータと呼ばれる実数のパラメータであり、上の行列が逆行列を持つようにする役割を持つ。例えば訓練データセットが線型分離不可能であるとき、γ → ∞ のとして正則化項 γ −1 I を消してしまうと、上式は解を持たなくなる。そのような事態をさけるため、訓練データに対してある程度の分類ミスを許す効果を持つのが γ である。
ちなみに変数変換によって、モデルは

fα′ (x) = sign(N∑)
αi xi · x − b

(58)

i=1

と書けることになる。

6.2.2 量子アルゴリズム
ここでは [8] にて提案された量子アルゴリズムを紹介する。大まかなアルゴリズムは以下のよう
になる。

13

1. QRAM を用いて |y ′ ⟩ を準備する。
2. カーネル行列 K を QRAM を使って密度行列として準備する。この密度行列を ρK =∑ij Kij |i⟩ ⟨j| とする。
3. Density matrix exponentiation を使って F の逆行列演算を |y ′ ⟩ に対して行う。→最適なモデルパラメータ α′∗ を保持した量子状態 |α′∗ ⟩ が得られる。

4. 未知のデータ x̃ について、swap test を用いて分類を行う。
細かな点の説明を書いていく。

1 は 4.2.1 を参考にすれば良い。2 については、6.1.2 と全く同じ操作をすれば良い。X T X = K
であることに注意したい。問題になるのは 3 の部分だと思う。3 は F の exponentiation を行わなければならないが、準備したのは ρK だけであって、F そのものではない。そこで、このアルゴ
リズムでは



0 1
 1 0


J :=  1 0
 .. ..
 . .
1 0

1
0
0
..
.

···
···
···
..
.


1
0 

0 

.. 
. 

0

···

0

とし、

eF δ ≈ eJδ eKδ eγ

−1

(59)

Iδ

(60)

と Trotter 展開によって e2πF を実行する。eKδ は ρK を使って density matrix exponentiation
を行えばよいし、eγ−1Iδは単純な位相ゲートとして実行可能である。eJδ については、行列 J が解析的に対角化できることを用いる。J は N − 1 重に縮退した固有値 0 と、非ゼロの２つの固有(√値 λ± = ± N を持ち、非ゼロの固有値に対応する固有ベクトルは √12 |0⟩ + √1

N

∑N

)

i=1 |i⟩である。よってこの２つのベクトルを計算基底に持ってくるゲートをかけたあとに、位相ゲートを作用させれば eJδ を実行できる。
最後の swap test に関しては、前章と同様に符号を復元するために以下のアプローチを取る。まず、式 (58) の∑N

i=1 αi xi に相当する状態を作り出す。それをするには、ステップ 3 で作り出した状態|α′∗ ⟩ = b |0⟩ +のN∑

αi |i⟩

(61)

i=1

∑N

*6
i=1 αi |i⟩ の部分に対して、xi をエンコードする以下のような変換を適用すればよい。
something+QRAM|i⟩ |0⟩ −−−−−−−−−−−−→ |i⟩ |xi ⟩(62)

すると、以下の状態を生成できる。

|ψmodel ⟩ = b |0⟩ |0⟩ +

N
∑
i=1

*6 この変換は例えば 4.2.1 の方法を使えば実現できる。

14

αi |i⟩ |xi ⟩(63)

この状態と同時に未知データを以下のようにエンコードした状態

1|ψdata ⟩ = √N +1(|0⟩ |0⟩ +N∑)|i⟩ |x̃⟩

(64)

i=1

を準備する。ただし、この２つの状態に対して単純に swap test を適用するだけでは、線型回帰と同じく符号が復元されない問題に陥ってしまう。そこで、[8] では、もう一つの補助ビットを用いて、conditional に |ψdata ⟩ , |ψmodel ⟩ を準備して、以下の状態を用意することが提案された。

1√ (|0⟩ |ψmodel ⟩ + |1⟩ |ψdata ⟩)2(65)

この状態を補助ビットの X 基底で測定すれば、fα′∗ を復元することができる。

6.3 行列の low-rank 近似サンプリング
このセクションの締めくくりに、量子推薦アルゴリズム [5] のサブルーチンとして提案された、行列の low-rank 近似を行うアルゴリズムについて紹介する。

6.3.1 特異値分解・次元削減
機械学習では、学習の前処理として、データ行列 X に対して特異値分解を行い、特異値の大きい成分のみを取り出すことがよく行われる。特異値が小さい成分は、教師データの説明に寄与しない部分であると考え切り捨てるのだ。機械学習の文脈では、この作業は主成分分析とか次元削減とも呼ばれる。実際、訓練データとして与えられるデータは少数の特異ベクトルを使えば十分再現できることが多い。
この主成分分析を定式化すると以下の様になる。

1. X の特異値分解を行う。X = U diag (σ1 · · · σM ) V † .
2. ある閾値 σth を超えた成分のみを取り出す。つまりしきい値を超えた特異値の数を kth と††して、Xth := Uth diag (σ1 · · · σkth ) Vth を作る。ただし Uth , Vth は kth 本の列・行ベクトル
を U, V † から取ってきた行列である。

3. 次元の削減されたデータ行列 Xth を使って、好きな機械学習アルゴリズムを走らせる。
量子コンピュータによってこの作業を加速することが可能である。

6.3.2 量子アルゴリズム
4.2.2 で紹介した Prakash 法を用いて量子ウォーク (5.4 参照) を構築することで実現する。大まかなアルゴリズムを先に示そう。

1. X を 5.4 における D として持つ量子ウォーク W を作る。
⟩
∑N∑r
2. √1N i=1 |xi ⟩ |i⟩ に対して W の位相推定を作用させる。 k=1 |µk,± ⟩ b(σk2 ) が得られる。
15

3. 補助ビットを追加し、σk2 が σth よりも大きいところ場合のみ |0⟩、それ以外の場合のみ |1⟩
⟩
⟩
∑kth
∑r
とするような演算を行う。 k=1|µk,± ⟩ b(σk2 ) |0⟩ + k=kth +1 |µk,± ⟩ b(σk2 ) |1⟩ を得る。
⟩
∑kth
4. 補助ビットを測定する。|0⟩ が出れば、 k=1|µk,± ⟩ b(σk2 ) |0⟩ となり、σth 以上の成分のみを取り出せる。

5. ステップ 1・2 を uncompute する。すると √1N∑N

i=1 |xth,i ⟩ |i⟩ が得られる。

ここで |µk,± ⟩ は 5.4 で定義した量子ウォーク W の固有ベクトルで、xth,i は Xth の行ベクトルである。
ほとんどの部分は 6.1.2 で説明した手法と同様の手法になるので説明は省略するが、ステップ 1の量子ウォーク W を作る部分だけは独立していると思うので説明する。W を作るには、以下のユニタリー操作 P と Q を使えば良い。

P |0⟩ |i⟩ = |xi ⟩ |i⟩

(66)

1 ∑
Q |j⟩ |0⟩ = |j⟩ √
|i⟩
N i=1
N

(67)

P は Prakash 法 (4.2.2 参照) によって構成する。P , Q によって生成できる状態 |xi ⟩ |i⟩ と∑N|j⟩ √1N i=1 |i⟩ の内積を取ってみると、(

1 ∑(⟨xi | ⟨i|) |j⟩ √
|k⟩
N k=1
N

)

xij
=√
N

(68)

となる。5.4 と見比べると、この 2 つのベクトルを |vi ⟩, |wj ⟩ として使って W を構成すればよい
ことがわかるだろう。式 (36) のようなゲートを構築するには、以下の事実を用いる。
N∑|xi ⟩ |i⟩ ⟨xi | ⟨i| =

i=1

N
∑

P |0⟩ |i⟩ ⟨0| ⟨i| P †i=1= P |0⟩ ⟨0| ⊗

(N
∑

(69)
)

|i⟩ ⟨i| P †i=1= P |0⟩ ⟨0| ⊗ IN P †

(70)
(71)

(IN は N 次元の単位行列。) これを使うと、
2N∑|xi ⟩ |i⟩ ⟨xi | ⟨i| − IM N = P (2 |0⟩ ⟨0| − IM ) ⊗ IN P †

(72)

i=1

が得られる。よって 2∑N

i=1 |xi ⟩ |i⟩ ⟨xi | ⟨i| − IM N は P, P†と conditional 位相ゲートによって構成できる。もう片方についても同様の手法で構成可能である。

16

7 NISQ デバイスによる機械学習
7.1 Noisy intermediate scale quantum デバイス
Noisy intermediate scale quantum、略して NISQ デバイスとは、スーパーコンピュータをもってしてもシミュレーションが難しくなるような qubit 数・ゲート精度を兼ね備えているが、無視できないレベルのノイズの影響下にある量子デバイスのこと。誤り訂正を備えていないため、上で紹介したようなアルゴリズムを実行することは不可能だし、QRAM に至っては夢のまた夢である。
しかしある意味でスーパーコンピュータを超えた計算能力を持っていることは確かなわけなので、これを何らかの形で応用しようという試みが広く研究されている。ここでは機械学習という文脈で最近の研究を紹介する。

7.2 変分量子アルゴリズム
NISQ デバイスを応用するために考えられた手法は、ほとんどが変分量子アルゴリズムという枠組みに入る。変分量子アルゴリズムと呼ばれているものの大まかなアルゴリズムは以下のようになる。

1. 適当なパラメータ θ を持つユニタリーゲート U (θ) を初期状態 |0⟩ に作用させ、|ψ(θ⟩ :=U (θ) |0⟩ を作る。
2. |ψ(θ⟩ について何らかのオブザーバブルを測定する。
3. 測定結果によってパラメータを更新し、θ ′ を使って 1, 2 を繰り返す。
U (θ) は NISQ デバイスでも実行できるような、比較的簡単なものでなければならない。そのような簡単なものであっても、qubit 数が十分多くなれば |ψ(θ)⟩ は古典コンピュータで表現できないと信じられている。変分量子アルゴリズムには、このことを存分に使うようなプロトコルが望まれている。

7.3 Quantum variational autoencoder
Variational autoencoder (VAE) はディープニューラルネットの事前チューニングの手法として提案された、次元削減のためのアルゴリズムである。その量子版として、quantum variational

autoencoder (QVAE) がある。QVAE は、n qubit の状態として与えられた複数の状態 {|φi ⟩}N
i=1
を m < n qubit の状態へと圧縮するためアルゴリズムである。そのアルゴリズムを以下に示す。

1. |φi ⟩ それぞれに対して U (θ) を作用させる。|ψi ⟩ := U (θ) |φi ⟩ とする。
2. |ψi ⟩ のうち、m − n qubit を Z 基底で測定する。測定後の状態を |ψi′ ⟩ とする。
3. |ψi′ ⟩ それぞれに対して U † (θ) を作用させる。
⟨⟩
4. | φi |U † (θ)|ψi′ |2 を測定する。
17

5.

∑N

i=1 |

⟨

⟩
φi |U † (θ)|ψi′ |2 が大きくなるようにパラメータを更新し繰り返す。

もし U (θ) が |φi ⟩ の全てに対して、その情報を m qubit の部分系に圧縮することができていれば、⟨⟩U † (θ) によって量子状態が完全に復元されるはずなので、理想的には | φi |U † (θ)|ψi′ |2 = 1 とな∑
1
るはずである。QVAE の限界は、ρ = Ni |φi ⟩ ⟨φi | とするとき、ρ の rank によって決まる。

7.4 量子回路学習
量子回路学習 (quantum circuit learning, QCL) は NISQ 上で教師ありの機械学習を行うため
Nのアルゴリズムである。訓練データは説明変数 {xi }N
i=1 と対応する教師データ {yi }i=1 のセットとする。そのアルゴリズムを以下に示す。

1. それぞれの xi について、適当な量子ゲート V (xi ) を使って、データをエンコードした状態|φ(xi )⟩ := V (xi ) |0⟩ を作る。
2. パラメータ付きの量子回路 U (θ) を使い、|ψ(xi , θ)⟩ := U (θ) |φ(xi )⟩ を作る。
3. |ψ(xi , θ)⟩ に対して、適当なオブザーバブルを観測する。例えば 1 qubit 目の Z 期待値。
4. 上記で観測した値と教師データ yi の差が小さくなるようにパラメータ θ を調節し、1 に戻る。
このアルゴリズムが NISQ をどのように使っているのか説明して、このノートの締めとする。
このアルゴリズムが構築するモデルは、例えば 1 qubit 目の Z 期待値を出力として測定するとき、fθ (x) = ⟨ψ(x, θ)|Z1 |ψ(x, θ)⟩(73)である。このモデル fθ (x) はどのような構造を持つか調べよう。
簡単な例として、x がスカラー x であるときを考えよう。入力ゲート V (x) としては、量子回路をできるだけ浅くするため、1 qubit の回転ゲート

V (x) |0⟩ = x |0⟩ +√1 − x2 |1⟩(74)

を独立に n qubit それぞれに作用させることを考えよう。このとき |φ(x)⟩ は()⊗n√|φ(x)⟩ = x |0⟩ + 1 − x2 |1⟩(75)となる。テンソル積構造によって、元のデータ x に対する非線形性が生まれていることに注目したい。このように生まれた非線形項が、U (θ) によって線型に組み合わされてモデル fθ (x) に現れる。量子状態には一般に 2n 個の係数を埋め込むことができるため、NISQ を使うことによって、指数関数的に多数の基底関数によって、fθ (x) を構成できる。これが QCL の利点となる可能性のあるポイントである。

18

参考文献
[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, andSeth Lloyd. Quantum machine learning. Nature, Vol. 549, No. 7671, pp. 195–202, sep
2017.
[2] Christopher M Bishop. Pattern Recognition and Machine Learning. New York, aug 2006.
[3] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum
random access memory. Phys. Rev. A, Vol. 78, No. 5, p. 052310, nov 2008.
[4] Lov Grover and Terry Rudolph. Creating superpositions that correspond to eﬃciently
integrable probability distributions. arXiv preprint, 2002.
[5] Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. arXiv
preprint, 2016.
[6] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component
analysis. Nat. Phys., Vol. 10, No. 9, pp. 631–633, sep 2014.
[7] Anupam Prakash. Quantum Algorithms for Linear Algebra and Machine Learning. PhD
thesis, EECS Department, University of California, Berkeley, Dec 2014.
[8] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum Support Vector Machinefor Big Data Classification. Phys. Rev. Lett., Vol. 113, No. 13, p. 130503, sep 2014.
[9] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. Prediction by linear regression
on a quantum computer. Phys. Rev. A, Vol. 94, No. 2, p. 022342, aug 2016.
[10] J.A.K. Suykens and J. Vandewalle. Least squares support vector machine classifiers.
Neural Processing Letters, Vol. 9, No. 3, pp. 293–300, Jun 1999.

19