動かして学ぶ量子コンピュータプログラミング ―シミュレータとサンプルコードで理解する基本アルゴリズム

13.1

 連立線形方程式を解く

257

13.1.1

 連立線形方程式の記述と解法

連立線形方程式を最も簡潔に表現する方法は、行列の乗算を用いる方法です。実際、方程式を解く

ことに慣れている人にとっては、「行列」と「線形方程式」は同義語です。例えば、

2

つの連立線形方程

式

3x

1

+4x

2

＝

3

、

2x

1

+x

2

＝

3

があるとしましょう。このとき式 13-1に示す単一の行列方程式を用いると、

これらをより簡潔に表現することができます。

式 13-1

3

2

4

1

x

1

x

2

=

3

3

行列の乗算規則を用いて

2

つの線形方程式を表現することができます。より一般的には、

n

個の変数

に対する

n

個の線形方程式からなる連立方程式は、

n

×

n

の行列

A

、および

n

次元のベクトル

b

→

からな

る行列方程式として記述することができます。

Ax

→

=

b

→

ここで、求めたい

n

個の変数からなるベクトル

x

→

=

[

x

1

,...,

x

n

]

＊

1

を導入しました。

この行列による定式化では、連立方程式を解くことは行列

A

の逆を求めることに帰すことができま

す。逆行列

A

–1

を得ることができれば、式 13-2 によって

n

個の未知の変数を簡単に決定できます。

式 13-2

x

→

=

A

–1

b

→

逆行列を求めるためのアルゴリズムは従来からたくさんありますが、効率的かどうかは、問題にして

いる行列が良い性質を持つかどうかによります。

行列に関する次のパラメータは、従来のアルゴリズムと量子アルゴリズムの両方のパフォーマンスに

影響を与え