量子フーリエ変換

このQiskit in Classroomsモジュールでは、以下のパッケージがインストールされた Python 環境が必要です：

• qiskit v2.1.0 または新しい
• qiskit-ibm-runtime v0.40.1 または新しい
• qiskit-aer v0.17.0 または新しい
• qiskit.visualization
• numpy
• pylatexenc

上記のパッケージをセットアップしてインストールするには、 Qiskitのインストールガイドをご覧ください。 実際の量子コンピュータ上でジョブを実行するには、 IBM Cloud アカウントの設定ガイドの手順に従って、 IBM Quantum® のアカウントを設定する必要があります。

このモジュールはテストされ、13秒のQPU時間を使用した。 これは善意の見積もりであり、実際の使用量は異なる場合があります。

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

概要

フーリエ変換は、数学、物理学、信号処理、データ圧縮、その他無数の分野で応用されているユビキタスなツールである。 フーリエ変換の量子版は、量子フーリエ変換と名付けられ、最も重要な量子アルゴリズムの基礎となっている。

本日は、古典的なフーリエ変換について説明した後、量子コンピュータ上でどのように量子フーリエ変換を実装するかについて説明する。 次に、量子フーリエ変換の応用例の1つである位相推定アルゴリズムについて説明する。 量子位相推定は、量子コンピューティングの "至宝 "と呼ばれることもあるショールの有名な因数分解アルゴリズムのサブルーチンである。 このモジュールは、ショールのアルゴリズムに関する別のモジュールに向かって構築されているが、独立したものでもある。 量子フーリエ変換は、それ自体が魅力的で有用なアルゴリズムである！

古典フーリエ変換

量子フーリエ変換に入る前に、まず古典フーリエ変換を思い出してみよう。 フーリエ変換は、いわゆる "基底 "から別の "基底 "に変換する方法である。 2つのベースは、同じ問題に対する異なる視点と考えることができる。関数を表現する方法としてはどちらも有効だが、目の前の問題によっては、どちらか一方の方がより示唆に富んでいるかもしれない。 フーリエ変換で結ばれる塩基のペアの例としては、位置と運動量、時間と周波数などがある。

フーリエ変換が、オーディオ波形から楽器がどの音を演奏しているかを知るのに役立つかもしれない例を見てみよう。 通常、波形は時間基準で表される。つまり、波の振幅は時間の関数として表される。

この波形をフーリエ変換して、時間ベースから周波数ベースにすることができる：

周波数ベースでは、約260Hzに明確なピークがあるのがよくわかる。 ミドルCだ！

さて、フーリエ変換を使わなくてもミドルCが演奏されていると判断できたかもしれないが、複数の音が同時に演奏されていたらどうだろう？ 時間軸でプロットすると、波形はより複雑になる：

しかし、周波数スペクトルを見ると、明らかに3つのピークが確認できる：

これはハ長調のコードで、C、E、Gの音を弾いている。

このようなフーリエ解析は、あらゆる種類の複雑な信号の周波数成分を抽出するのに役立つ。

離散フーリエ変換

フーリエ変換は、あらゆる信号処理アプリケーションに有用である。 しかし、このような実世界のアプリケーションのほとんどは（上で使った音楽の例も含めて）、 $N$ データ点の離散集合を変換したいのであって、連続関数を変換したいわけではない。 この場合、 離散フーリエ変換を使う。 離散フーリエ変換（DFT）は、ベクトル $(x_0, ..., x_{N-1})$ に作用し、式に従ってベクトル $(y_0, ..., y_{N-1})$ にマッピングする：

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

ここで、 $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$ とする。 (指数にマイナス記号を付ける規則は他にもあるので、DFTを見かけたら注意してほしい) $e^{2\pi i \frac{jk}{N}}$ は周期関数で、周期は $\frac{N}{k}$ である。したがって、この関数を掛け合わせることで、フーリエ変換は本質的に、（離散）関数 $\{x_{j}\}$ を、周期 $\frac{N}{k}$ を持つ周期関数の線形結合に分解する方法なのである。

量子フーリエ変換

さて、フーリエ変換を使って、いわゆる "基底関数 "の新しい集合の線形結合として関数を表現する方法を見てきた 基底変換は、量子ビットの状態に対しても定期的に行われている。 例えば、1つの量子ビット $|\psi\rangle$ の状態は、基底状態 $|0\rangle$ と $|1\rangle$ を持つ計算基底 $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$、または基底状態 $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ と $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$ を持つ $X$ 基底 $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ で表すことができる。どちらも同じように有効ですが、解こうとしている問題の種類によっては、どちらかの方がより自然かもしれません。

Qubitの状態はフーリエ基底でも表現することができ、通常の計算基底状態 $|x\rangle$ ではなく、フーリエ基底状態 $|\phi_y\rangle$ の線形結合で表現される。このためには、量子フーリエ変換（QFT）を適用する必要がある：

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

上記のように $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ であり、 $N$ は量子系の基底状態の数である。 量子ビットを扱うため、 $m$ 個の量子ビットでは $2^m$ 個の基底状態が得られ、 $N=2^m$ となる。ここで基底状態は単一の数 $|x\rangle$ で表され、 $x$ は $0$ から $N-1$ の範囲となる。ただし、基底状態は通常 $|00...00\rangle$、 $|00...01\rangle$、 $|00...11\rangle$、...、 $|11...11\rangle$ の形式で表現される。各2進桁は右から左へ、量子ビット0から $m-1$ の状態を表す。 これらの二進状態を単一の数値に変換する簡単な方法があります：単にそれらを二進数として扱うだけです！ したがって、 $|00...00\rangle = |0\rangle$、 $|00...01\rangle = |1\rangle$、 $|00...10\rangle = |2\rangle$、 $|00...11\rangle = |3\rangle$、そして $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$ に至るまで、すべてが該当します。

フーリエ基底状態に対する直感力を養う

つまり、計算基底状態とは何か、どのように並べられるかを説明しました。計算基底状態とは、それぞれの量子ビットが $0$ または $1$ のどちらかにある状態の集合で、すべての量子ビットが $0$, $|00...00\rangle$ の状態から、すべての量子ビットが $1$, $|11...11\rangle$ の状態まで並べられます。

しかし、 フーリエ基底状態をどのように理解すればいいのだろうか？ すべてのフーリエ基底状態は、すべての計算基底状態の等しい重ね合わせであるが、各状態は成分の位相の周期性において他と異なる。 これをより具体的に理解するために、2量子ビット系の4つのフーリエ基底状態を見てみよう。 最低のフーリエ状態とは、位相がまったく変化しない状態である：

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

各項の複素振幅をプロットすることで、この状態を可視化することができる。 赤い線は、この振幅の位相が計算基底状態の関数として複素平面上をどのように旋回しているかを示す目印である。 $|\phi_0\rangle$ の場合、位相は一定のままである：

次のフーリエ基底状態は、その成分の位相が $0$ から $2\pi$ まで一度だけ回っているものである：

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

そして、複素振幅対計算基底状態のプロットで、この巻き上がりを見ることができる：

つまり、この例では4つの基底状態( $N=4$ )があるので、標準的な方法で並べると、各状態はその前の状態より $2\pi/4$ ラジアン高い位相を持つ。次の基底状態は、0から2 $\pi$ まで2回巻きます：

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

最後に、最も高いフーリエ成分は、位相が最も速く変化するものである。 量子ビットが2つある例では、位相が0から $2\pi$ の間を3回回るものだ：

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

一般に、 $m$ 量子ビット状態に対しては、 $2^m$ 個のフーリエ基底状態が存在し、その位相変動の周波数は、 $|\phi_0\rangle$ では一定である一方、 $|\phi_{2^m-1}\rangle$ では急速に変化する。これにより、状態の重ね合わせに対して、 $2\pi$ を $2^m-1$ 巻き巡る。 したがって、量子状態の量子場理論（QFT）を扱う際、我々は基本的にイントロで音楽の波形に対して行ったのと同じ分析を行っているのです。 我々は、関心のある量子状態の生成に寄与するフーリエ周波数成分を特定している。

いくつかの例となる量子場理論を試してみてください

量子フーリエ変換の直感を、計算基底で状態を作り、それにQFTを適用するとどうなるかを見ることで構築し続けよう。 今のところ、QFTをブラックボックスとして扱い、 Qiskit回路ライブラリの QFTGate 後ほど、それがどのように実装されているのか、ボンネットの中を覗いてみよう。

必要なパッケージをロードし、回路を実行するデバイスを選択することから始めます：

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load IBM Quantum Compute Service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

Output:

ibm_pinguino2

もしあなたのアカウントに空き時間がなかったり、何らかの理由でシミュレーターを使いたい場合は、以下のセルを実行して、上で選択した量子デバイスを模倣するシミュレーターをセットアップすることができます：

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

単一計算基底状態

まず、1つの計算基底状態を変換してみよう。 まずはランダムな計算状態を作ることから始めよう：

# Step 1: Map

qubits = 4
N = 2**qubits


qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)


# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()


qc.measure_all()
qc.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Output:

さて、この状態を QFTGate でフーリエ変換してみよう：

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Output:

おわかりのように、各状態の母集団は、多少の実験的・統計的ノイズはあるにせよ、多かれ少なかれ等しいと測定している。 つまり、1つの計算基底状態のQFTをとると、結果はすべての状態の等しい重ね合わせになる。 フーリエ変換に慣れ親しんでいる人なら、おそらく驚かないだろう。 ある関数とそのフーリエ変換の間に直感的な関係を築くのに役立つ一つの基本原理は、関数の幅はそのフーリエ変換の幅に反比例するということである。 そのため、例えば非常に短いパルスのように、時間的に非常に局所的なものは、そのパルスを発生させるために広範囲の周波数を必要とする。 その信号はフーリエ空間では非常にブロードになる。

この事実は、実は量子の不確定性に関係している！ ハイゼンベルクの不確定性原理は通常、 $\Delta x \Delta p \ge \hbar / 2$ のように記述される。つまり、 $x$ ( $\Delta x$ ) の不確かさが小さければ、運動量 ( $\Delta p$ ) の不確かさは大きくなるはずであり、逆もまた然りである。 位置基底（ $x$ ）から運動量基底（ $p$ ）への変換は、フーリエ変換によって達成されることがわかった。

注：各基底状態におけるポピュレーションを測定しているため、重ね合わせの様々な部分間の相対位相に関する情報が失われていることに留意してほしい。 つまり、計算上の基底状態のQFTは、すべての基底状態にわたって同じように均等に分布するが、 位相は必ずしも同じにはならない。

二つの計算基底状態

では、計算基底状態の重ね合わせを用意するとどうなるか見てみよう。 この場合、フーリエ変換はどのようになると思いますか？

重ね合わせを選択しよう：

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits


qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)


qc_qft = qc.copy()


qc.measure_all()

qc.draw("mpl")

Output:

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Output:

さて、この状態を QFTGate でフーリエ変換してみよう：

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Output:

これはちょっと意外かもしれない。 状態 $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ のQFTは、すべての偶数基底状態の重ね合わせのように見える。 しかし、各基底状態 $|\phi_y\rangle$、各成分の位相がどのように $2\pi$ $y$ 回を巻いているかを可視化したことを思い返せば、この結果が得られる理由が明らかになるかもしれない。

理解度チェック

上記のヒントを用いて、 $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ の量子場理論において得られた結果が予想通りである理由を説明しなさい。

• 回答

  元の状態は、重ね合わせの2つの部分の間の相対位相が0（または $2\pi$ の整数倍）である。 つまり、この状態には、そのように位相が一致するフーリエ成分があることがわかる。つまり、｜0000｜項と｜1000｜項の間の位相シフトが0であるものだ。 各フーリエ基底状態 $|\phi_y\rangle$ は、位相が $2\pi y/N$ の割合で累積する項によって構成される。つまり、通常の方法で並べると、重ね合わせの各項の位相は、前の項より $2\pi y/N$ 大きい。 したがって、中間点 $N/2$ において、位相 $2\pi y/N * N/2$ が $2\pi$ の整数倍になるようにしたい。これは $y$ が偶数のときに起こる。

すべての奇数（2進数）にピークを持つ量子場理論には、どのような計算上の状態の重ね合わせが対応するだろうか？

• 回答

  $\psi = |0\rangle - |N/2\rangle$ 状態のQFTをとれば、すべての奇数二進数の状態にピークが見られるだろう。

QFTアルゴリズムを分解する

さて、計算基底とフーリエ基底における量子ビット状態の関係についてより直感的になったところで、QFTアルゴリズムそのものを掘り下げてみましょう。 言い換えれば、この変換を実現するために、量子コンピューターにどのようなゲートを実装するのか？

まずは小さく、1量子ビットから始めよう。 つまり、2つの基礎状態を持つことになる。 QFT $_2$ は、計算基底状態 $|0\rangle$ と $|1\rangle$ をフーリエ基底状態 $\phi_0$ と $\phi_1$ に変換する：

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

理解度チェック

前の節で示した量子場理論の式を用いて、上記の2つのフーリエ基底状態を検証せよ。

• 回答

  一般的なQFTの公式は次の通りである：

  $| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

  単一量子ビット（ $n=1$ ）については、 $N=2^n=2$、 $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$。したがって、次のようになる

  $| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

  $| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

この2つの方程式を見てみよう。 この変換を実行するために使用できる量子ゲートをすでにご存知かもしれない。 すなわち、計算基底状態 $|0\rangle$ と $|1\rangle$ をそれぞれのフーリエ基底状態 $|\phi_0\rangle$ と $|\phi_1\rangle$ に変換するゲートがある。 これはハダマードゲートである！ QFT $_N$ の行列表現を導入すれば、このことはさらに明確になる：

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

量子演算子を表現するこの記法に馴染みがなくても大丈夫だ！ これは $N \times N$ 行列を表す方法で、 $x$ と $y$ は行列の列と行のインデックス、 $0$ から $N-1$ まで、 $\omega_N^{xy}$ は特定のエントリーの値である。 つまり、例えば0列目2行目のエントリーは、 $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$。

この表現では、各計算基底状態は、基底ベクトルのひとつと関連付けられている：

この表現についてもっと深く学びたい方は、 量子情報の基礎コースのジョン・ワトラスの多重システムに関するレッスンをご覧ください。

QFT $_4$ の行列を作ってみよう。上の式を使うと

$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$

この行列を量子コンピューターに実装するには、どのゲートをどの量子ビットに適用すれば、上の行列と一致するユニタリー変換が得られるかを見つけ出す必要がある。 私たちはすでに、必要となるゲートのひとつ、ハダマードを知っている。 これは、制御量子ビットが $|1\rangle$ の状態にある限り、ターゲット量子ビットの状態に相対位相 $\alpha$ を適用します。マトリックス形式では次のようになります：

$\text{CP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\alpha} \\ \end{pmatrix}$

状態（ $|11\rangle$ ）だけが変更されるので、どの量子ビットを "コントロール "と見なし、どちらを "ターゲット "とするかは実は問題ではない 結果はどちらでも同じだ。

最後に、SWAPゲートも必要だ。 SWAPゲートは2つの量子ビットの状態を入れ替える。 そのようだ：

$\text{SWAP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

$m$ の量子ビットにQFT $_{2^m}$ 回路を構築する手順は反復的である。まず、 $1$ から $m-1$ の量子ビットにQFT $_{2^{m-1}}$ を適用し、次に、 $0$ と他の $m-1$ の量子ビットの間にいくつかのゲートを追加する。 しかし、QFT $_{2^{m-1}}$ を適用するには、まず量子ビット2から $m-1$ にQFT $_{2^{m-2}}$ を適用し、次に量子ビット1と残りの量子ビット $2$ から $m-1$ の間にいくつかのゲートを追加する必要があります。これはロシアの入れ子人形のようなもので、各人形がQFT回路の次元を2倍ずつ増やしていき、一番中心にある一番小さな人形がQFT $_2$、つまりハダマードゲートとなります。

人形の中に次の大きさの人形を入れ、QFTの次元を2倍大きくするには、いつも同じ手順を踏む：

1. まず、一番下の $m-1$ の量子ビットに QFT $_{2^{m-1}}$ を適用する。 これはロシアの入れ子人形セットの「小さな人形」で、すぐに次の大きな人形の中に入れることになる。
2. 次の量子ビットを制御として使用し、制御された位相ゲートを一番下の $m-1$ の各クビットに適用する。位相は残りの $m-1$ の各クビットの標準基底状態に適用する。
3. 位相ゲートで制御として使われたのと同じ一番上の量子ビットにハダマードを実行する。
4. SWAPゲートを使って量子ビットの順序を入れ替え、最下位ビット（最上位ビット）が最上位ビット（最下位ビット）になり、それ以外のビットは1つずつシフトアップするようにする。

すでにQiskit回路ライブラリの QFTGate 関数を使ってきたが、今度はこれらのQFTゲートの内部を見て、上記の手順を検証してみよう。 これは decompose() で可能だ。

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Output:

つまり、最初の4つのQFTから、それぞれのQFTが次の大きなQFTの中にどのように入れ子になっているかがわかると思う。 また、SWAPは各サブルーチンの後に現れるのではなく、QFT全体の一番最後にのみ現れる。 これにより、回路が長くなり、エラーが発生しやすくなる不必要なゲートを省くことができる。 各ネストドールの後にSWAPを実行する代わりに、回路は各クビット状態がどこにあるべきかを追跡し、それに応じてフェーズゲートを適用する量子ビットを調整する。 そして最後のSWAPで、すべてのものをあるべき場所に収める。

量子場理論を適用する：位相推定

量子コンピュータの有用な問題を解くために、QFTがどのように使われるかを見てみよう。 逆量子フーリエ変換の計算は、量子位相推定（QPE）として知られるアルゴリズムに必要なステップであり、それ自体、量子アルゴリズムの "王冠の宝石 "であるショールのファクタリングアルゴリズムを含む、他の多くのアルゴリズムのサブルーチンである。

QPEの目的は、ユニタリー作用素の固有値を推定することである。 ユニタリー作用素は量子コンピューティングではどこにでもあるもので、多くの場合、関連する固有ベクトルの固有値を求めることは、より大規模なアルゴリズムにおいて必要なステップである。 問題によっては、固有値はシミュレーションタイプの問題でハミルトニアンのエネルギーを表したり、ショールのアルゴリズムで数の素因数を求めるのに役立ったり、その他の重要な情報を含んでいたりする。 QPEは量子コンピューターで最も重要かつ広く使われているサブルーチンの1つである。

では、量子フーリエ変換との関係は？ 思い出すかもしれないが、ユニタリー作用素の固有値 $\lambda$ は、大きさ $|\lambda| = 1$ を持つ。したがって、各固有値を大きさ1の複素数として書くことができる：

$\lambda = e^{2\pi i \theta}$

$\theta$ は0から1の間の実数。 ユニタリー行列についてもっと知りたい方は、量子情報の基礎のジョン・ワトラスのレッスンを参照してください。

$\lambda$ は $\theta$ において周期的である。すでに、周期関数の解析にQFTがいかに有用であるかを見たので、これはQFTが関与している可能性を示唆しているかもしれない。 以下では、そのアルゴリズムを通して、QFTがどのように作用するかを正確に見ていく。

QPEの仕組み

まず、2進数1桁の精度で位相を大まかに推定する、最も単純なQPEアルゴリズムから始めます。 言い換えれば、このアルゴリズムは $\theta = 0$ と $\theta = 1/2$ を区別することはできるが、それ以上のことはできない。 これが回路図だ：

量子ビットは $|\pi_0\rangle = |\psi\rangle|0\rangle$ の状態に準備され、 $0$ の量子ビットは $|0\rangle$ の状態にあり、残りの量子ビットは $U$ の固有状態である $|\psi\rangle$ の状態にある。最初のハダマードの後、量子ビットの状態は次のようになる：

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

次のゲートは "controlled- $U$ "ゲートである。 これは、量子ビット0が状態 $|1\rangle$ にある場合、状態 $|\psi\rangle$ にあるボトム量子ビットにユニタリー演算 $U$ を適用するが、量子ビット0が状態 $|0\rangle$ にある場合、 $|\psi\rangle$ には何もしない。これは量子ビットを状態に変換します：

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

奇妙なことが起きた。controlled- $U$ ゲートは、制御量子ビットとして量子ビット $0$ を使うだけなので、このゲートは量子ビット0の状態を全く変えないと思うかもしれない。 でも、なぜかそうなる！ 演算が下位の量子ビットに適用されたとしても、ゲートの全体的な効果は、量子ビット $0$ の位相を変化させることである。これは "位相キックバック機構 "として知られており、Deutsch-JoszaやGroverのアルゴリズムを含む多くの量子アルゴリズムで使用されている。 フェーズ・キックバックのメカニズムについて詳しく知りたい場合は、量子アルゴリズムの基礎の中の量子クエリーアルゴリズムに関するジョン・ワトラスのレッスンを参照されたい。

位相キックバックの後、qubit $0$ にもう一回ハダマードを適用する：

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

従って、最後に量子ビット $0$ を測定するとき、 $\theta = 0$ ならば100％の確度で $|0\rangle$ を測定し、 $\theta = \frac{1}{2}$ ならば100％の確度で $|1\rangle$ を測定することになる（そして、量子コンピューターがノイズのない完璧なものであれば）。 $\theta$ がこれ以外のものであれば、最終的な測定は確率的なものでしかなく、多くのことしかわからない。

QPEの精度向上：より多くの量子ビット

この単純な概念を、任意の精度を持つより複雑なアルゴリズムに拡張することができる。 位相を測定するために量子ビット $0$ を使う代わりに、 $m$ の量子ビット $0$ から $m-1$ を使えば、 $m$ ビットの精度で位相を推定することができる。 どう動くか見てみよう：

このより正確なQPE回路は、シングルビット版と同じようにスタートする：ハダマードは最初の $m$ qubitsに適用され、残りのqubitsは $|\psi\rangle$、状態を作成する：

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

これで、コントロールされたユニットが適用される。 Qubit $0$ は前回と同じユニタリー $U$ のコントロールである。 しかし今、量子ビット $1$ は、単純に $U$ を2回適用したユニタリー $U^2$ の制御である。 したがって、 $U^2$ の固有値は $e^{2*2\pi i \theta}$ となる。一般に、0から $m-1$ までの各クォビット $k$ は、ユニタリー $U^{2^k}$ の制御となる。つまり、これらの各量子ビットは $e^{2^k*2\pi i \theta}$ の位相キックバックを経験することになる：

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

これは計算基底状態の和として書き直すことができる：

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

この数字に見覚えはないだろうか？ QFTだ！ 量子フーリエ変換の式を思い出してほしい：

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

したがって、位相が $0$ と $2^m-1$ の間のある整数 $y$ に対して $\theta = y/2^m$ である場合、この状態の逆QFTをとると、状態が得られる：

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

そして、 $|y\rangle$ から、 $\theta$ を推論することができる。

しかし、 $\theta/2^m$ が整数の倍数でない場合、逆QFTは $\theta$ を近似するだけである。 $\theta$ つまり、常に最良の近似が得られるわけではありませんが、かなり近い近似が得られます。また、 $m$、より多くの量子ビットを使えば使うほど、より良い近似が得られます。 この $\theta$ の近似を定量化する方法については、Fundamentals of quantum algorithmsのJohn Watrousの Phase estimation and factoringのレッスンを参照。

おわりに

このモジュールでは、QFTとは何か、QFTは量子コンピューター上でどのように実装されるのか、そしてQFTが問題を解く上でどのように役立つのかについて概観した。 ユニタリー行列の固有値を知るために量子位相推定でどのように使用できるかを見たとき、その有用性を味わっていただけただろう。

重要な概念

• 量子フーリエ変換は、離散フーリエ変換の量子アナログである。
• QFTは基底変換の一例である。
• 量子位相推定手順は、逆QFTと同様に、制御されたユニタリー演算からの位相キックバック機構に依存している。
• QFTとQPEは、どちらも多くの量子アルゴリズムで広く使われているサブルーチンである。

質問

「真」/「偽」

1. T/F 量子フーリエ変換は、古典的な離散フーリエ変換（DFT）の量子アナログである。
2. T/F QFTはハダマードゲートとCNOTゲートだけで実装できる。
3. T/F QFTはショーのアルゴリズムの重要な要素である。
4. T/F 量子位相推定の出力は、演算子の固有ベクトルを表す量子状態である。
5. T/F QPEでは、逆量子フーリエ変換（QFT $^\dag$ ）を使用する必要があります。
6. T/F QPEにおいて、位相 $\phi$ が $n$ ビットで正確に表現できる場合、アルゴリズムは確率1で正しい結果を与える。

短い回答

1. $2^n$、QFTを実行するのに必要な量子ビットの数は？
2. QFTは計算基底状態でない状態にも使えるのですか？ もしそうなら、どうなる？
3. QPEで使用される制御量子ビットの数は、結果として得られる位相推定の分解能にどのように影響しますか？

問題

1. 行列の乗算を使用して、QFT アルゴリズムのステップが本当に $\text{QFT}_4$ 行列になることを検証する：

(手でやる必要はない！）

課題問題

1. すべての奇数計算基底の等しい重ね合わせである4量子ビット状態を作る： $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$。次に、その状態に対してQFTを実行する。 その結果、どのような状態になるのか？ フーリエ変換の知識を用いて、あなたの結果がなぜ理にかなっているかを説明しなさい。