Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?
@KeiichiroHiga

量子位相推定(Quantum Phase Estimation)

More than 1 year has passed since last update.

この記事に関して

ここでは量子アルゴリズムの一つである、量子位相推定( Quantum Phase Estimation )について、説明します。

量子位相推定

このアルゴリズムはユニタリ行列の固有値を求めるアルゴリズムです。
ユニタリ行列、固有値、固有ベクトルに関しては別の記事で説明します。

ユニタリ行列の固有値の絶対値は 1 なので $\lambda$ と置くと
$\lambda = e^{\theta i}$ と書けます。$(0≦\theta<2\pi)$
このことから $\theta$ が導出できれば固有値が求められることがわかります。

考えるユニタリ行列を $U$ とします。
この固有ベクトルを $\left|u\right>$ と置くと

U\left|u\right> = e^{\theta i}\left|u\right> = e^{2\pi ij}\left|u\right> \\
(0≦j<1)

と書けます。

また $U$ を $2^k$ かけると以下のように表せます。

U^{2^k}\left|u\right> = e^{\theta i 2^k}\left|u\right> = e^{2\pi i2^kj}\left|u\right> \\
(0≦j<1)

ここで $j$ は以下のように書けるとします。

j = \frac{j_1}{2^1} + \frac{j_2}{2^2} + \cdots + \frac{j_{n-1}}{2^{n-1}} + \frac{j_n}{2^n}

このように 2進数表示に書き直すことで $2^kj$ は以下のようになります。

e^{2\pi i 2^kj} = e^{2\pi i(\frac{j_{k+1}}{2}\cdots \frac{j_n}{2^{n-k}})} = e^{2\pi i0.j_{k+1}\cdots j_n}

これを用いて以下の状態を考えると量子フーリエ変換後と似たようなものになります。

\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{0}j}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{1}j}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i2^{n-1}j}\left|1\right>\right)\\
=\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right)

もしこのように書き表すことができれば逆量子フーリエ変換を施して、$j$ を取り出すことができます。

\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right) \xrightarrow{QFT^{-1}} j

これらから上の状態を作り出せることができれば良いことがわかります。

状態の作成

上の状態を作り出すために Hゲートを CUゲートを用います。
まずはじめの状態は $\left|00\cdots00\right> \otimes \left|u\right>$ とします。

$\left|00\cdots00\right>$ にHゲートを施すと以下のようになります。

H\left|0\right> \otimes H\left|0\right> \otimes \cdots \otimes H\left|0\right> = \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>)

ここで最初のビットの $\left|1\right>$ のみ $U$ を施すと $U\left|u\right> = e^{2\pi i 0.j_1j_2\cdots j_n}\left|u\right>$ より

\frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_1j_2\cdots j_n}\left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \left|u\right>

次に最初から 2番目のビットの $\left|1\right>$ に $U^{2^1}$ を施すと $U^{2^1}\left|u\right> = e^{2\pi i 0.j_2j_3\cdots j_n}\left|u\right>$ より

\frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_1j_2\cdots j_n}\left|1\right>)  \otimes \frac{1}{\sqrt2}(\left|0\right> + e^{2\pi i 0.j_2j_3\cdots j_n}\left|1\right>)  \otimes \cdots \otimes \frac{1}{\sqrt2}(\left|0\right> + \left|1\right>) \otimes \left|u\right>

以下同様にして繰り返し、最後のビットの $\left|1\right>$ に $U^{2^{n-1}}$ を施すと $U^{2^{n-1}}\left|u\right> = e^{2\pi i 0.j_n}\left|u\right>$ より

\frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_1\cdots j_n}\left|1\right>\right)\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_2\cdots j_n}\left|1\right>\right)\otimes \cdots\otimes \frac{1}{\sqrt2}\left(\left|0\right> + e^{2\pi i0.j_n}\left|1\right>\right)

上手く状態を作ることができました。

まとめ

今回は量子位相推定( Quantum Phase Estimation )について説明しました。
次回は Bernstein-Vaziraniのアルゴリズムについて説明しようと思います。

2
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gleap
九州大学公式のプログラミングサークルです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
2
Help us understand the problem. What is going on with this article?