量子フーリエ変換(QFT)再訪

　前報では、正規直交基底ベクトルの組に対して、少しづつ位相を変化させることで位相の波を起こし、それをビジュアル化して楽しんだ。ここでは、もっと先を見据えて、それを量子フーリエ変換で行ってみた。

🔴過去の記事
　量子フーリエ変換に関しては、これまでに断片的であるが以下のような短い記事を書いてきた。今回はその復習にもなっている。

    ⚪︎スマホのアプリで量子フーリエ変換をデモする
    ⚪︎Running quantum Fourier transform on my mobile simulator
    ⚪︎量子フーリエ変換：QFT(|ψ⟩+|φ⟩)=QFT|ψ⟩+QFT|φ⟩

🔴量子フーリエ変換の回路とその実行
　一例として、４個の量子ビット（4-qubit）の場合を考える。それに対する量子フーリエ変換QFTの回路をFig.1の上段に示した。qft4q_coreとなっているが、このcoreとは、swapを含まないQFTのコア部分という意味である。それを3-qubitの場合のQFTコアqft3q_coreを使って作っている。このような、カスタムゲート機能をIBM Quantum Composerで使うことができる。この図からも推測される通り、1-qubit、すなわち２次元のQFTはアダマール変換Hそのものである。

　このqft4q_coreの前段に、全てのqubitの順序を逆転させるswapを施している。そして、入力状態として、|0010>、すなわち、|2>を与えてこの回路を実行させた結果をFig.1の下段に示した。（注：qubitの縦の並びの上位を２進ビット列の下位に対応させている。）このカラーの配置から、正規直交基底ベクトルの並び順に従って、π/4づつ位相が反時計回りに回転していることがわかる。すなわち、生成された位相の波の周波数は２である。
　なお、QFTは、Fig.2のように、量子ビット重ね合わせ状態に対しも働くのが特徴的である。

🔴量子フーリエ変換の計算式
　上図の回路は、Fig.3に示すQFTの計算式に基づいて作られている。確かに、その位相項を見ると位相の回転の様子がFig.1のようになることが推定できる。しかし、Fig.3の数式が正確にFig.1に反映されているのを確かめるには（特に、位相変換ゲートPが制御付きとなっている点など）、少し複雑な計算をしないといけないようである。だが、その計算の詳細は参考文献[1]の第5章に示されているので、必要であれば参照願いたい。

　ここで、|x>は、正規直交基底ベクトルであり、xは10進数である。例えば、3-qubitの場合、|5>は|101>を意味する。一般の状態ベクトル|ψ>は、正規直交基底ベクトルの重ね合わせなので、QFT(|ψ>)はQFTの線形性から、上図の計算式を使って計算できる。

🔴逆量子フーリエ変換IQFT
　この記事では詳細は略すが、QFTの逆変換となるIQFTもよく利用される。IQFTは、以下のように作ればよい。
（１）QFTを構成するゲートを逆順に配置する。
（２）各位相変換ゲートでの位相角の符号を反転させる。（QFTの場合に対して）
（３）最後に、全てのqubitの並び順を逆転させるためのswapを施す。

🔴まとめ
　量子フーリエ変換 (QFT) は、n-qubitからなる量子状態を周波数領域に変換する操作である。入力の量子状態が一つの整数に対応していると考えられる場合は、QFTの結果は、その整数値を周波数とする位相の波を出力すると言える。
　逆量子フーリエ変換 (IQFT) は QFT の逆変換であり、量子状態にエンコードされた位相情報を元の振幅情報に戻す。言い換えると、QFT によって位相の回転としてエンコードされた周波数情報を、IQFT によって元の振幅分布に変換する。

参考文献

[1] 宮野健次郎、古澤明：量子コンピュータ入門第２版、日本評論社、2019(第2版第3刷).

Illustrating Shor's algorithm with my quantum circuit simulator

Shor's algorithm is mathematically quite difficult, so many books on quantum computing often only briefly mention it. On the other hand, when an explanation is given, it is difficult to understand because it is a list of many mathematical formulas. In this context, the book by Prof. Barry Burd [1] is surprisingly easy to understand and explains the basics. Chapter 9 of this book takes 40 pages to thoroughly explain the essence of Shor's algorithm. Using a concrete example, he explains that if you can find the period (frequency) in a coprime powers sequence, you can factorize the public key number. He then demonstrated quantum Fourier transform (QFT) to find that frequency, expressed it in Qiskit code, and ran it on IBM Quantum Lab. This is fantastic! With this, I was able to grasp the heart of Shor's algorithm!

I have so far developed my own quantum circuit simulator for 3-qubit as a mobile phone app with MIT App Inventor. The outline is shown in Fig.1.

This time, I was able to use my simulator to identify frequencies using quantum Fourier transform, following the instructions in this book. The results matched those from IBM Quantum Lab. In other words, using just a mobile phone, they were able to perform a quantum Fourier transform and obtain the results, just like a scientific calculator. The situation is shown in Fig.2 and Fig.3.

(Notes)

As of 02/23/2024, the execution environment of Qiskit (IBM Quantum Lab) has changed, so it is necessary to modify the original Python code (for example, Chapter09.ipynb) to run it.

●Here is how to fix it:

---------------------------------------------

(A)change libraries:

from qiskit import QuantumCircuit, Aer, execute

from qiskit.tools.visualization import plot_histogram

  ↓

from qiskit.primitives import Sampler

from qiskit.visualization import plot_histogram

---------------------------------------------

(B)use 'Sampler' instead of 'Aer' as follows:

sampler = Sampler()

result = sampler.run(circ, shots=1000).result()

print("result: ", result)

quasi_dists = result.quasi_dists

print("quasi_dists: ", quasi_dists) 

display(plot_histogram(quasi_dists))

---------------------------------------------

●More details here:

Migration examples

https://docs.quantum.ibm.com/api/migration-guides/qiskit-runtime-examples

---------------------------------------------

Reference

[1] Barry Burd, Quantum Computing Algorithms -Discover how a little math goes a long way, Packt Publishing, 2023.

https://users.drew.edu/bburd/quantum/

量子フーリエ変換：QFT(|ψ⟩+|φ⟩)=QFT|ψ⟩+QFT|φ⟩

　前報で、独自のモバイル量子回路シミュレータを用いて、3量子ビットシステムのbasis vector（|000⟩, |001⟩, |010⟩, ... ,|111⟩）それぞれに対して量子フーリエ変換QFTを行った。だが、QFTは、量子重ね合わせ（SuperPosition）に対して適用できる点に大きな特徴があるといえる。そこで、今回、私のシミュレータでのGUIを以下の図に見られるように若干変更して、これを実験してみた。以下の図から、実用上非常に重要なQFTの線形性を確認でき、位相の波の干渉による増幅/減衰（高め合い/弱め合い）の状況が分かる。

●QFT(|000⟩+|001⟩)=QFT|000⟩+QFT|001⟩

　前回までにQFTを見てきたので、あまり説明は必要ないと思われる。Fig.1に、2

つの状態の重ね合わせ |000⟩+|001⟩ に対するQFTの結果を示した。

　(a)はQFT|000⟩、(b)はQFT|001⟩であり、(c)は両者の加算となっている。同じ位相の場合は確率（塗りつぶした赤い円の面積）が倍増しており、位相が180度逆転している場合は確率がゼロとなっていることが分かる。

●QFT(|000⟩+|100⟩)=QFT|000⟩+QFT|100⟩

　もう一例見てみよう。Fig.2は、2つの状態の重ね合わせ |000⟩+|100⟩ に対するQFTの結果を示した。

　(d)はQFT|000⟩、(e)はQFT|100⟩であり、(c)は両者の加算となっている。今度は、|100⟩の位相が、(d)と(e)で完全に逆転しているので、(f)にてその確率はゼロとなる。赤い円の塗り潰しは無くなった。そして、その前後で、両者の位相が次第に近づくに従って、位相が揃ってきて増幅され、確率が増加する（赤い円の塗り潰しが大きくなる）ことが分かる。緩やかな波が見えてくる！

　最後に、逆量子フーリエ変換IQFTによって、この位相の波から、元の入力量子状態（すなわち、重ね合わせ状態）が復元される様子をFig.3に示す。

スマホのアプリで量子フーリエ変換をデモする

要旨：スマホ1台で稼働する量子回路シミュレータを開発している。現在、3-Qubitまでのアプリを動かすことができる。今回、これを用いて、量子フーリエ変換（QFT）、及びその逆変換（IQFT）の簡単なデモを実現できた。

●量子フーリエ変換(隠れた周期性の発見）

　ショアの因数分解アルゴリズムなどで重要な量子フーリエ変換（QFT）は、量子計算の代表例の一つである。QFTは、ある量子状態を入力すると、それに応じた周期性を有する量子状態（位相変化の波）を作り出す。また、逆量子フーリエ変換（IQFT）は、周期性を有する量子状態の隠れた周期を見つけることができる。

　ここでは、既存のシミュレータでQFTとIQFTを試すのではなく、量子回路シミュレータ自体をスマホ上に独自に構築した上で、QFTとIQFTを実験することに意義がある。そのため、以下の図にあるように、かなり多くの量子ゲートを実装することになった。

　IQFTでは、QFTを構成する量子ゲートを逆順に適用して行けば良いのであるが、実はその際、位相の回転方向を逆向き変更する必要があり、これが理由で実装量子ゲートが増えた面もある。

●QFTとIQFTの実行例

　詳しいことは略すが、実行例をいくつか示す。図１は、3量子ビットの状態ベクトル|100>を量子フーリエ変換に入力した場合である。

（注）本質的なことではないが、回路図上の量子ビットは上から下へ、q0q1q2と並んでいるが、図の下方にある円盤に付した状態ベクトルでは、慣例上、量子ビットは左から右へ、q2q1q0の順になっている。これ以降、状態ベクトルはこの「慣例」で表現する。

　図１では、(a)に示した量子ビット状態|100>を入力としてQFTを実行すると、(b)に示すような位相の波が得られた。すなわち、基底ベクトル|000>、|001>、... |111>の順に、位相が反時計回りに45度づつ変化し、8個の基底ベクトルで1周期の位相の波となる。

　続けて、IQFTを適用した結果を図２に示す。結果として、確率100%（円盤が全面塗り潰し）で|100>が測定された。これは元の入力そのものであり、回路図に戻って考えると古典ビットで"001"を得たことになる。すなわち、"１"周期の波であることが分かる。

　同様にして、入力量子状態|010>をQFTに与えると、今度は、２周期の位相の波（半時計周りに90度づつ進む）となり、さらにIQFTを実行すると元の入力量子状態が復元された。

　さらにもう一例、入力量子状態|001>をQFTに与えると、今度は、4周期の位相の波（半時計周りに180度づつ進む）となり、さらにIQFTを実行すると元の入力量子状態が復元された。

　図5に、逆量子フーリエ変換で位相の周期が分かる様子を再度掲載した。

●感想

　スマホで、電卓みたいな感覚で、簡単な量子回路シミュレータを作ろうとして始めたが、段々膨らんできて、３量子ビットの量子フーリエ変換ができるまでになった。まだまだ、初級レベルに留まるが、ちょっと嬉しくなる。ただ、スマホでは（性能上というよりも、画面設計やコード作成する上で）この位の規模が限界かもしれない。さらに高度なことは、QiskitやIBM Quantumで実行ということになろう。

　本記事内容を何かに生かすとしたら... 簡単なゲームが考えられる。３量子ビットで、何らかの周期性をもつビット列をプレイヤーに与えて、その周期を当ててもらう。あまり面白くないか。でも、量子アプリ作成の練習にはなるだろう。

　本記事内容を、整数の素因数分解に結びつけることは（たとえ15など小さな整数でも）非常に困難です。これを実現する量子回路を構成するには、より多くの知識と技術が必要です。私はまだその域に達していないようだ。特に、モジュラー指数関数を量子回路で実現する部分などです。