How to run quantum circuits on the development platform Qiskit

[Abstract] IBM Qiskit is used as a typical development environment for quantum computing. Its version is frequently updated, and some parts are soon deprecated, which can be confusing. The description of quantum gates and quantum circuits remains almost the same, but there are frequent changes in simulations and execution methods on actual machines. Here, I would like to note three typical execution methods at the present time (2024-11-10).

🔴Example: Quantum computation part of Shor's prime factorization algorithm

Here, we will focus only on running the order finding quantum circuit, which is the main part of Shor's algorithm. Fig.1 shows the prime factorization of the very small integer 15 (15 = 3 × 5) for demonstration purposes. We will not explain the relationship between the entire Shor algorithm and the quantum circuit in Fig.1 this time, so if necessary, please refer to the following past articles.

• Shorの素因数分解に親しむためのスマホアプリ
• Shor's Algorithm：量子コンピューティングの学びの最高峰
• Developing a mobilephone app to demonstrate Shor's prime factorization

🔴[1] Simulation with Qiskit Sampler (run on local PC)

Qiskit Sampler is the most common simulator for running a quantum circuit (name: qc) like the one in Fig.1 (including measuring the lower three qubits). The main points of its use are as follows. The results of this simulation (measurement results of 1,000 shots) are shown in Fig.2.

# Running the Simulation
from qiskit_aer.primitives import Sampler
sampler = Sampler()
result = sampler.run(qc, shots=1000).result()

# Extraction and visualization of measurement results
quasi_dists = result.quasi_dists
binary_quasi_dist = quasi_dists[0].binary_probabilities()
counts_dict = quasi_dists[0].binary_probabilities()
counts = Counts(counts_dict)
plot_histogram（counts)

🔴[2] Simulation incorporating a noise model of the actual machine (run on a local PC)

In the above, the simulation results (Fig.2) show that the counts corresponding to the four bases are approximately 25% each, and the counts of the other bases are zero as expected because there is no noise. In addition to using a normal sampler like this, it is also possible to perform simulations that reflect the noise generated by the actual quantum computer.

Fig. 3 shows the result of incorporating a noise model generated by a real machine (127-qubits) named ibm_sherbrooke into AerSimulator and running it. Indeed, the effects of noise that did not occur in Fig. 2 are apparent. This may be useful for preliminary examination before running on a real machine.

# important imports

from qiskit_aer import AerSimulator

from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2 as Sampler

# Set the noise model of the real machine

real_backend = service.backend("ibm_sherbrooke")

aer = AerSimulator.from_backend(real_backend)

pm = generate_preset_pass_manager(backend=aer, optimization_level=1)

isa_qc = pm.run(qc) # transpile for the real machine

sampler = Sampler(mode=aer)

result = sampler.run([isa_qc],shots=1000).result() # execution

# Extraction and visualization of measurement results

pub_result = result[0]

counts = pub_result.data.c.get_counts() # Note the 'c' !

plot_histogram(counts)

🔴[3] Execution on an actual IBM Quantum machine (submitting a job via the web)

Next, the job was submitted to an actual IBM Quantum machine via the web and executed. The machine was ibm_sherbrooke, the same as that given in the noise model above. The job was executed in batch mode, so the execution results were retrieved via the web after it was completed. This is shown in Fig. 4, and it was found to be almost identical to the simulation results shown in Fig. 3, which reflect the above noise model.

# Automatically select machines with low load

from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService(channel="ibm_quantum", token= "***")

be = service.least_busy(simulator=False, operational=True)

print(f"QPU backend：{be}")

# Transpile for real machine and submit the job

pm = generate_preset_pass_manager(optimization_level=1, backend=be)

ic = pm.run(qc) # Transpiled circuit

job = Sampler(be).run([ic], shots= 1000)

print(f"job ID: {job.job_id()}")

print(f"job statusI: {job.status()}")

# After execution, the results are retrieved and displayed

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService(

    channel='ibm_quantum',

    instance='ibm-q/open/main',

    token='token for the job'

)

job = service.job('jab ID')

job_result = job.result()

counts = job.result()[0].data.c.get_counts()

plot_histogram(counts)

The execution status is shown in Fig. 5. Usage = 2 sec. Free users are limited to 10 minutes of usage per month. This is sufficient for testing simple quantum circuits, but caution is required when testing slightly more complex quantum circuits, as this can result in unexpectedly high usage. At present, there are three models of actual machines available for free use, as shown in Fig. 6. For paid users, eight more models of actual machines can be used in addition to these.

🔴 Differences between the results of a real machine and a simulator

Currently, quantum computers generate various noises, which causes errors. For example, the difference between the results of a pure simulator (Fig. 2) and the results of a real machine (Fig. 4) shows this. Although it cannot be said in general, errors that occur on a real machine can have a large impact on the necessary calculations. However, in the case of this example problem, due to the nature of probabilistically searching for an order, it can be said that the difference between Fig. 2 and Fig. 4 is almost no problem.

量子コンピューティング開発環境Qiskitでの実行方法

English version here
【要旨】量子コンピューティングの代表的な開発環境として、IBM Qiskitを利用している。そのバージョンアップは頻繁になされて、すぐにdeprecated（非推奨、または廃止）となる部分が多く、困惑する場合がある。量子ゲートや量子回路の記述などはほとんど変わらないが、シミュレータ、および実機での実行方法などの変更が多発する。ここでは、現時点（2024-11-10）での典型的な実行方法３つをメモして置きたい。

🔴例題：Shorの素因数分解アルゴリズムの量子計算部分
　ここでは、Shorのアルゴリズムの主要部である位数計算（order finding）量子回路を動かすことだけに注目する。Fig.1は、デモとして動かすための、極く小さな整数15の素因数分解（15 = 3 × 5）の場合である。Shorのアルゴリズム全体とFIg.1の量子回路との関係などは今回は説明しないので、例えば以下のような過去記事をご覧いただきたい。

• ショアの素因数分解に親しむためのスマホアプリ
• Shor's Algorithm：量子コンピューティングの学びの最高峰
• Developing a mobilephone app to demonstrate Shor's prime factorization

🔴[1]Qiskit Samplerによるシミュレーション（ローカルPCで実行）
　Fig.1のような量子回路（名称：qc）の実行（下位３量子ビットの測定を含む）を行うための最も一般的なシミュレータとして、Qiskit Samplerがある。その利用の要点は以下のとおりである。このシミュレーションの結果（1,000 shotsの測定結果）をFig.2に示す。

# シミュレーションの実行
from qiskit_aer.primitives import Sampler
sampler = Sampler()
result = sampler.run(qc, shots=1000).result()

# 測定結果の取り出しと図示
quasi_dists = result.quasi_dists
binary_quasi_dist = quasi_dists[0].binary_probabilities()
counts_dict = quasi_dists[0].binary_probabilities()
counts = Counts(counts_dict)
plot_histogram（counts)

🔴[2]実機のノイズモデルを組み込んだシミュレーション（ローカルPCで実行）
　上記では、シミュレーション結果（Fig.2）として、４つの基底に対応するカウントがほぼ25%づつで、それ以外の基底のカウントは、ノイズがないので、理論通りゼロとなった。このような通常のSamplerによる以外に、量子コンピュータ実機で発生するノイズを反映させたシミュレーションを行うこともできる。
　Fig.3は、ibm_sherbrookeという名の実機（127-qubits）で発生するノイズモデルを、AerSimulatorに組み込んで実行した結果である。確かに、Fig.2では発生しなかったノイズによる影響が出ている。実機で実行する前の事前検討などに有用であろう。

# 重要なimport

from qiskit_aer import AerSimulator

from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2 as Sampler

# リアルマシンのノイズモデルをセット

real_backend = service.backend("ibm_sherbrooke")

aer = AerSimulator.from_backend(real_backend)

pm = generate_preset_pass_manager(backend=aer, optimization_level=1)

isa_qc = pm.run(qc) # 実マシン向けのtranspile

sampler = Sampler(mode=aer)

result = sampler.run([isa_qc],shots=1000).result() # 実行

# 測定結果の取り出しと図示

pub_result = result[0]

counts = pub_result.data.c.get_counts() # 'c'を指定することに注意！

plot_histogram(counts)

🔴[3]IBM Quantumマシン実機での実行（web経由でジョブを投入）

　次に、IBM Quantumマシン実機へweb経由でジョブを投入し、実行を行った。マシンは、上記のノイズモデルで与えたものと同じibm_sherbrookeである。ジョブはバッチ形式で実行されるので、その終了後にWeb経由で実行結果を取り出す。それを表示したものがFig.4である。上記のノイズモデルを反映したシミュレーション結果Fig.3とほぼ同一であることが確認できた。

# 負荷の少なそうなマシンを自動選択

from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService(channel="ibm_quantum", token= "***")

be = service.least_busy(simulator=False, operational=True)

print(f"QPUバックエンド：{be}")

# 実マシン向けのtranspileを行い、Jobを投入

pm = generate_preset_pass_manager(optimization_level=1, backend=be)

ic = pm.run(qc) # Transpile結果

job = Sampler(be).run([ic], shots= 1000)

print(f"ジョブID: {job.job_id()}")

print(f"ジョブI状態: {job.status()}")

# 実行終了後に、結果を取り出し、表示。

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService(

    channel='ibm_quantum',

    instance='ibm-q/open/main',

    token='jobに対応するトークン'

)

job = service.job('jab ID')

job_result = job.result()

counts = job.result()[0].data.c.get_counts()

plot_histogram(counts)

　この実行の状況をFig.5に示した。Usage = 2 secとなっている。無償ユーザは、毎月10分までのUsageという制約がある。簡単な量子回路の試験には十分であるが、少し複雑な量子回路になると想定外に多くのUsageを使うことになるので、注意が必要である。なお、現時点では、無償で使える実機はFig.6に示すとおり、３機種であった。有償の場合は、これらの他にさらに８機種の実機が利用できる。

🔴実マシンとシミュレータの結果の相違について

　現状では、量子コンピュータは種々のノイズが発生するので誤りが起こる。例えば、純粋のシミュレータの結果Fig.2と、実マシンによる結果Fig.4の相違がそれを示している。一概には言えないが、実機で起こる誤りが、必要な計算に与える影響は大きい場合がある。だが、本例題に限って言えば、確率的に位数（order）を探すという性質上、Fig.2とFig.4の差はほとんど問題にならないと言える。

自作モバイル量子回路シミュレータのテスト

【要旨】本稿は、これまでに自作したモバイル量子回路シミュレータQsim_multiの適用性をテストするものである。例題として、最近発刊されたある書籍に載っている、逆量子フーリエ変換と位数発見問題を取り上げた。これらは、Shorの素因数分解アルゴリズムの根幹を成している。結論として、自作シミュレータQsim_multiがこれらを正常に処理できることを確認できた。

🔴 A new book on quantum computing

　最近、Nivio Dos Santos著の新刊（FIg.1）を購入した。タイトルは、"How to code for Quantum Computers"となっているが、いわゆるハウツー本ではなく、基本概念がコンパクトにまとめられている。本を開いたとたんに、何か楽しいことが書いてある、という雰囲気がある。後半には、量子フーリエ変換、量子位相推定、Shorのアルゴリズムの計算が詳細に説明されている。だから、初級から中級レベルの本だと言える。

　本文には、プログラムコードはほとんど出てこないが、Google Cirq環境用のPythonコード（Jupyter Notebook）がWeb上に公開されているので重宝する。

　この本に掲載されている以下の二つの例題を、私の自作モバイル量子シミュレータで稼働させるのである。だが、ここで重要なことに気づいた。それは、量子ビットの並べ順である。私のシミュレータは、IBM Qiskitなどと同じだが、Cirqでは、それが逆順になっているのである。したがって、それを逆転させる必要があった。しかし、そうしても、例えば、量子フーリエ変換の結果などは、各基底の確率は同一になっても、位相は異なるだろう。それを踏まえて扱えば問題ない。

🔴 Example1: Using Inverse-QFT

　まず、逆量子フーリエ変換を使う例である。Fig.2はこの書籍で説明されている回路図と16個の基底からなる量子状態である。逆量子フーリエ変換invQFTは展開形で示されている。それぞれの円内の塗り潰した小さな円は確率を示し、赤い直線の傾きは位相を示す。

　これを私のシミュレータ用に変換して実行した結果をFig.3に示す。このシミュレータには、逆量子フーリエ変換IQFTを内蔵しているので、それをそのまま使った。量子状態をFig.2と比較すると、確率は同じであり、位相は鏡像反転している。この結果から、私のシミュレータは、正常に稼働していることが分かる。

🔴 Example2: Finding the order of [g^k mod N = 1]

　次に、Shorのアルゴリズムで重要な位数発見問題である。ここでは、具体例「7^k mod 15 = 1」の位数、すなわち、この式を満たす最小の整数kを求める。

　量子回路と位数発見結果を以下に示す。Fig.4はCirq環境であり、Fig.5は私のシミュレータによる。「7^k mod 15 」とinvQFTの適用後の測定結果は、3-qubitシステムにおいて、両者で一致した。すなわち、８個の可能性のうち、010、100、000、110の四つだけが、それぞれ等しい確率で測定される。その結果を有理数近似して1/4が得られ、位数が４であることがわかった。なぜそう言えるのかの詳細と、Shorのアルゴリズムとの関係は以下に示されている：

　2024年7月9日火曜日

　Shor's Algorithm：量子コンピューティングの学びの最高峰

　https://sparse-dense.blogspot.com/2024/07/shors-algorithm.html

　Fig.4では、測定結果は、1000回試行おける出現頻度で示してあり、Fog.5では確率計算結果として示している。

　なお、Fig.5の私のシミュレータでは、測定した4ケース（3-qubit）の値が、それぞれ四つに分かれている。これは少し見にくいので、Fig4.のようにまとめた方が良い。次回のバージョンアップの際に対処したい。

🔴結論

　逆量子フーリエ変換と位数発見問題の簡単な場合について、私のモバイル量子回路シミュレータは、Google Cirq環境で実行されたのと同一の結果を与えた。一定の適用性を確認できたと考える。

Developing a mobilephone app to demonstrate Shor's prime factorization

[Abstract] I have written several articles about Shor's prime factorization, one of the pinnacles of quantum algorithms. The mobilephone app I developed this time is an all-in-one app that includes both classical processing and quantum algorithms. However, I did not create the quantum algorithm part myself, but used the quantum circuit simulator Quirk. Quirk does not provide an API, so the necessary parameters for linking the classical and quantum parts are passed manually. The significance of this app is that it allows you to complete the execution of the entire Shor's algorithm on a single screen (although it is limited to small integers). In practice, this method of manually passing the necessary parameters (not a fully automated process) while checking the results of the quantum circuit simulation is useful for deepening your understanding. I would like to demonstrate this in detail below.

🔴Details of Shor's Factoring Algorithm

The theory and calculation details of Shor's algorithm are written in this article. Also, the most important part, finding order, is an application of quantum phase estimation, and this is also explained in detail in this article. Therefore, this article only describes the overview and usage of the app developed this time.

🔴All-in-one app for Shor's algorithm

First, the overall image of the developed app is shown in Fig.1. This screen shows an example of decomposing 221, given as the product of two prime numbers 13 and 17, into the original two prime numbers. It consists of a classical calculation part and a quantum calculation part.

This app was created with MIT App Inventor. The classical part verifies the order (period) candidates obtained from the quantum part, and if they are valid, prime factorization is performed immediately. If they are not, a parameter (called A here) is changed appropriately and the process is retried. Meanwhile, the quantum part calls the quantum circuit simulator Quirk to obtain order candidates. The Quirk screen is crowded, but you can use your finger to zoom in on the parts you need.

🔴How to use the app

Please see Fig.2 below. Give two prime numbers p and q, and press the blue button "setup R" to obtain the desired integer R. Next, turn on the switch with red characters "Quirk Q Sim". Then, manually give this integer R as an input to the displayed Quirk simulator. Give another (randomly selected) integer A to Quirk in the same way. This Quirk quantum circuit is designed to find candidates for the order (i.e., period) of f(x) = A^x mod R. This simulation consists of a total of 14 qubits. (8 qubits for problem setting, 6 qubits for solution)

Next, as shown in Fig. 3, the results of the Quirk simulation (measurement results) show that out of 256 (=2⁸) bases, only four appeared with a probability of 25% each. If you enlarge the screen, you can see that one of the bases, |010000⟩, is a candidate for giving the order. Set this as the binary bit string "010000" in the window at the top of the screen.

Next, press the round "Shor" button as shown in Fig. 4. This binary bit string is then converted into a decimal, and then converted into a rational number (fraction s/r) using the continued fraction approximation method. The denominator r becomes a candidate for the order. In this example (N=221, A=18), s=1 and r=4. The validity of the order can be confirmed, and as mentioned earlier, we get GCD(A^r/2+1, R)=13 and GCD(A^r/2-1, R)=17, completing the prime factorization!

Although it is not a fully automated process, it is impressive that the entire Shor prime factorization can be demonstrated on a single screen in this app!

🔴Shor's Algorithm is Probabilistic

So far we have seen the whole picture of Shor's algorithm. It is a probabilistic algorithm. In fact, another result executed under the above conditions did not give a valid order, and the prime factorization ultimately failed. Such an example is shown in Fig. 5.

However, when executed using a fully quantum computer, the correct answer can be obtained with a sufficiently small number of attempts! The details are described in Nielsen & Chuang [1].

[Additional Notes]

MIT App Inventor was once again very useful. It was great to be able to call the external quantum circuit simulator Quirk easily using the WebViewer. On the other hand, if all the processing related to "f(x) = A^x mod R" was created in App Inventor, the number of blocks would increase, making it difficult to manage. Furthermore, it was necessary to use the Modular Exponentiation Method to prevent the calculation from overflowing. Therefore, this time, most of these were created in JavaScript and called from App Inventor. This kind of integration with JavaScript is also useful.

In creating this app, I referred to the chapter II-5 of Nielsen & Chuang [1], the chapter 7 of Wong [2] and the chapter 9 of Burd[3]. I would like to express my gratitude.

Reference

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

[2] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

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

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

ショアの素因数分解をデモするためのスマホアプリの開発

【要旨】量子アルゴリズムの頂点の一つ、ショアの素因数分解については、何度か記事を書いてきた。今回開発したスマホアプリは、その古典的処理と量子アルゴリズムの両方を包含したall-in-oneとなっている。ただし、量子アルゴリズム部分は自作ではなく、量子回路シミュレータQuirkを利用した。QuirkではAPIが提供されていないため、古典的部分と量子部分の連携では、必要なパラメータは人手で授受した。このアプリにより、（対象は小さな整数に限定されるが）一つの画面でショアのアルゴリズム全体の実行を完結できることに意味がある。実際に行ってみると、量子回路シミュレーション結果を確認しながら、人手で必要なパラメータを渡す（完全自動処理ではない）この方法は、理解を深める上で有用な面がある。以下に、それを具体的に示したい。

🔴Shor's Factoring Algorithmの詳細

　ショアのアルゴリズムの理論と計算の詳細はこの記事に書いた。また、その最も重要な部分である位数発見（finding order）は、量子位相推定の応用であるが、これに関してもこちらの記事に詳細を示した。従って、本記事では、今回開発のアプリの概要と使い方についてのみ述べる。

🔴ショアのアルゴリズムのAll-in-oneアプリ

　まず、開発したアプリの全体像をFig.1に示す。この画面は、２つの素数13と17の積として与えた221を、元の２つの素数に分解した例である。古典的計算部分と量子計算部分から成る。

　このアプリはMIT App Inventorで作られた。古典的部分では、量子部分から得た位数（周期）の候補を検証し、妥当であれば、直ちに素因数分解を行うことができる。そうでなければパラメータ（ここではAという名称）を適宜変更して再試行する。

　一方、量子部分では、位数の候補を得るため、量子回路シミュレータQuirkが呼び出される。Quirkの画面は込み入っているが、必要な箇所を指で拡大して見ることができる。
　

🔴アプリの操作手順

　下図のFig.2をご覧いただきたい。２つの素数p,qを与えて、青いボタン「setup R」を押すと目的の整数Rが得られる。次に、赤字のスイッチ「Quirk Q Sim」をonにする。そして、この整数Rを、表示されたQuirkシミュレータへの入力として（手動で）与える。もう一つの（ランダムに選んだ）整数Aも同様にQuirkに与える。このQuirkの量子回路は、f(x) = A^x mod Rの位数（すなわち、周期）の候補を見つけるように作られている。全部で14-qubitの構成（問題設定用に8-qubit、解答用に6-qubit）である。

　次に、Fig.3に示すように、Quirkシミュレーションの結果（測定結果）として、2⁸= 256個の基底のうち、4個だけがそれぞれ25%の確率で出現した。画面を拡大して見ると、その一つの基底 |010000⟩が、位数を与える候補であることが分かる。それを２進ビット列"010000"として、画面上部の窓に設定する。

　続けて、Fig.4に示すように丸い「Shor」ボタンを押す。するとこの２進ビット列が10進小数に変換され、さらに、連分数近似法により有理数（分数s/r）に変換される。その分母rが位数の候補となる。この例（N=221, A=18）では、s=1、r=4であった。位数としての妥当性が確認できるので、すでに述べた通り、 GCD(A^r/2+1, R)=13とGCD(A^r/2-1, R)=17が得られて、素因数分解完了！

　完全自動処理ではないが、このアプリの一つの画面だけで、ショアの素因数分解の全体をデモできることは意味があるのではないか！

🔴Shor's Algorithmは確率的

　ここまでにショアのアルゴリズムの全貌を見た。これは確率的アルゴリズムである。実際、上記の条件で実行された別の結果は、妥当な位数を与えず、最終的に素因数分解が失敗した。そのような例をFig.5に示す。

　しかし、完全な量子コンピュータを使った実行においては、十分に少ない試行で正解が得られるという事実がある。その詳細は、Nielsen & Chuang [1]に叙述されている。

【補足】

　今回もMIT App Inventorをとても有効に利用できた。外部の量子回路シミュレータQuirkをWebViewerから簡単に呼び出せることは素晴らしい。一方、f(x) = A^x mod R に関係する処理を全てApp Inventorで作るとブロック数が増えて見通しが悪くなる。計算がオーバーフローしないように、Modular Exponentiation Methodを使う必要もある。そこで、今回は、これらの大部分をJavascripで作成し、それをApp Inventorから呼び出している。このような、Javascriptとの連携機能も有用である。

　このアプリの作成にあたっては、Wong[2]の第７章「Quantum Algorithms」とBurd[3]の第９章を参考にさせていただいた。感謝申し上げる。

References

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

[2] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

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

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

Shor's Algorithm：量子コンピューティングの学びの最高峰

【要旨】前回、ショアの素因数分解アルゴリズムに親しむための記事をここに書いた。そこでは、概要をつかむのが主目的であったので、最も肝心な位数計算（order-finding）と呼ばれる処理を、ナイーブな古典的計算で済ませた。だが、この位数計算の量子版の理解無しには、ショアを理解したことにはならない。逆に、これを完全に理解できれば、量子コンピューティングの学びの最高峰に達すると言える。なぜなら、そこには、量子計算の重要な要素（量子状態重ね合わせ、量子もつれ、量子位相キックバック、量子フーリエ変換、量子位相推定、測定による波束の収縮、等々）が凝縮されているからである。本記事は、そこへの到達を目指す。

🔴Shor's Algorithmを理解するための参考資料
　まず、知識の源泉がある。解説書は多数あるが、私の場合は、Fig.1に示した６点である。このうち、Nielsen & Chuang[1]は、精緻な叙述で世界的に著名な大作（全676頁）である。Shor's algorithmの発表は1994年だが、本書の第１版は2000年（10周年記念版は2010年）である。その第5章「量子フーリエ変換とその応用」で、位相推定や位数計算が丁寧に説明されている。他にも、随所に計算基礎論に基づく知見が散りばめられている。まさにバイブルである。
　宮野&古澤[2]でも、第５章「ショアのアルゴリズム」の説明が丁寧であり、複雑そうに見える理論計算と具体例の計算をフォローしやすい。厳密に計算を追求したい読者には最適である。
　Bernhardt[3]は、私が量子コンピューティングの基礎を掴むのに徹底して読んだ最初の本である。そこには、ショアのアルゴリズムの詳細は無いのだが、それに大きな影響を与えたと言われるSimon'sアルゴリズムが、厳密かつ簡潔に叙述されていて、感銘を受けたのでここに含めた。

　Wong [4]は、量子アルゴリズムの基礎を幅広く優しく、かなり綿密に解説している。随所に、Niesen & Chuang[1]を参照しながらも、独特の平易な解説に徹している。量子回路シミュレータとして、主に、ビジュアルに優れるQuirkを利用している。
　Barry [5]は、独特の図解で、"why"よりも"how"に重きをおいて説明している。最初に、量子フーリエ変換から入って、coprime power sequenceの周期を求めている。その後、位相推定（および位数計算）を使う方法も説明している。主要な例題の量子回路は、Qiskitコードで示されており、シミュレーションを実行できる。
　最後のFrankharkins [6]は、Shor's factoring（全過程）に特化したQiskitコードの解説である。Jupyter notebook形式になっているので、一歩ずつ理解しながら、シミュレーションを進めることができる。（ただし、これらのコードは、Qiskit 0.x版に準拠している。現在のQiskit 1.x版ではいくつかのエラーが発生して動かなかったが、移行ドキュメントに従い、Qiskit 1.0版用に変換することができた。）

🔴Order finding (Period finding)の実際
　次に位数計算（Order finding）を具体的に検討する。【要旨】に述べた通り、Shor'sアルゴリズムの全体の流れはすでに分かったので、ここでは、Order findingのための量子コンピューティングに焦点を当てる。位数の候補が見つかれば、古典的アルゴリズムによって、目的の整数の素因数が（高い確率で）見つかるのである。

（１）量子位相推定（こちらとこちら）の応用として
　位数rの計算は、量子位相推定の応用であり、量子回路の構成もほぼ同じである。だが、入力とするユニタリ行列の固有状態の設定に注意する必要がある。ここで用いるユニタリ行列Uは以下の式(a)である。これは何なのか？例えば、a=3, N=35の場合、状態 |1⟩に対しては、Uの連続適用結果は、式(b)のようにrを周期として繰り返すことが分かる。ここでは、r=12である。実は式(c)が成り立つ。（証明は略）

　次に、式(d)に示すように、U^k|1⟩の重ね合わせ（superposition）である状態|u₀⟩を考えると、それはUの固有状態であり、その固有値は１であることが分かる。（証明は略すが、上記と同様に、具体的に展開すれば分かる。）
　同様に、式(e)に示す重ね合わせ |u₁⟩は、Uの固有状態であり、その固有値は、e^2πi/rである。さらに一般化した、式(f)に示す重ね合わせ |u_s⟩（sは整数）は、Uの固有状態であり、その固有値は、e^2πis/rである。

（２）量子位相推定回路へ入力する固有状態
　上記を理解できれば、すでに見た位相推定アルゴリズムQPE（Quantum Phase Estimation）によって、あるsについて位相s/rを測定によって得られそうである。しかしながら、それを実現する量子回路への入力となる |u_s⟩は、実はこの時点では作れないので困る。それを解消する方法がある。それは、sについて |u_s⟩の総和（すなわち、重ね合わせ）を取ると途中の位相がキャンセルされ、結果として式(g)の通り、状態が |1⟩になるという事実である！証明は略すが、これが重要！

　QPEへの入力として、この固有状態 |1⟩を与えると、QPEの前段の回路は、（位相）φ = s/rを量子フーリエ変換することになる。したがって、QPEの後段の逆量子フーリエ変換IQFTの結果を測定することで、s/rの近似値が得られる。具体的には、測定結果の古典ビット列（２進小数と見做される）を連分数アルゴリズム（continued fraction algorithm）によって有理数近似（分数表現）する。その分母として、rの候補が得られる。そのrが妥当な位数であれば採用し、そうでなければ、QPEの実行をやり直す。

🔴Order finding (Period finding)の量子回路と実行結果
　以上の検討に基づき、位数計算の量子回路を作り、その実行結果から、最終的に目的の整数を素因数分解することができる。ここでは、（多くの解説書で取り上げられている）極く小さな整数15の素因数分解（15 = 3 x 5）のデモを行う。そのための量子回路がFig.2である。

　この回路は確かに、既に示した位相推定回路とほとんど同じである。ただし、問題設定用のレジスタq₃q₄q₅q₆への入力が、上記式(g)の通り、 |1⟩となっていること、すなわち、量子ビットq₃に対してパウリXゲートが適用されていることに注目されたい。また、q₃q₄q₅q₆へ接続される３つの大きな回路は、以下の回路（7k mod 15）の繰り返しになっている。これは、上記式(a)(b)(c)のユニタリ操作Uに当てはめると考えやすい。

　そして、この回路の実行結果（1,000ショットの測定結果）をFig.3に示した。N=15は、素因数分解したい整数が15であることを意味する。整数a=7に設定しているが、このaはN以下でNと素な整数として選んだ。（最終的にうまく行かなければ、aの値を変更する。）

　この測定結果は、解答レジスタq₂q₁q₀が、４つの値000、010、100、110をほぼ等しい確率で取り、それ以外の値は取らないことを意味する。これらの値を2進小数にして、位相Phaseを計算することができる。（位相推定の場合と同じ方法による。）さらに、その位相を表す小数を、連分数アルゴリズムによって、有理数近似（分数で近似）する。その結果の分母が位数rの候補となる。その値rが妥当な位数であることが確認できれば、（こちらの記事で述べた通り）目的の整数15の素因数を得ることができる。以上の流れをFig.4に示した。

　この測定では、位数rの候補は1、4、２の３つであったが、r=1は妥当な位数ではなく失敗し、r=4の場合は成功している。

🔴感想
　以上の内容を示したことで、Shor'sアルゴリズムの全貌を（ほぼほぼ）把握できたと考える。今回の実行結果は、Qiskitのシミュレータによるものだが、極く小さな整数15の素因数分解に成功した。その要因は、位数計算に成功したことによる。
　しかし、現時点の量子コンピュータ実機では（ここにも示した様に）小規模な回路構成であっても、誤り発生のために、位相推定が、従って、位数計算がうまくできない。すなわち、大きな整数（semi prime）に対しては、現時点の実機ではShor'sをまともに動かせない。
　それにもかかわらず、Shor'sアルゴリズムは量子アルゴリズムの最高峰の一つであることに異論はないはずである。近い将来、完全な量子コンピュータが完成し、Shor'sアルゴリズムが真価を発揮することを期待したい。

🔴追加情報
　MITでは、量子コンピューティング基礎講座「QUANTUM COMPUTING FUNDAMENTALS」という4週間のオンラインコース（＄2,419)を定期的に開催している。その講師に、Prof. Peter Shorが入っている。彼が上記のShor's algorithmを発表したのは1994年（35才）だが、現在もMIT教授として活躍されているようだ。また、参考文献[1]の著者の一人、MITのProf. Isaac Chuangも同じくこのコースの講師となっている。私も受講を考えてはいるが...今回このブログ記事を書いたので、多分、講義内容には何とかついて行けそうな気はする。

References

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

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

[3] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.

https://www.chrisbernhardt.info/

[4] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

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

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

[6] Frank Harkins: Shor's Algorithm

https://github.com/Qiskit/textbook/blob/main/notebooks/ch-algorithms/shor.ipynb

Enjoy Shor's Prime Factorization with a Mobilephone App

This is the English translation of this article.
[Abstract] To fully execute the well-known Shor's Factoring Algorithm, a large-scale fault-tolerant quantum computer is required, and with current quantum computers, this is unlikely to happen. However, when an ideal quantum computer appears, it is believed that this algorithm will have a huge impact on cybersecurity. Here, we created an app to apply Shor's algorithm to small integers (products of two prime numbers). This will allow you to become familiar with Shor's algorithm and deepen your understanding.

🔴 Overview of Shor's Factoring
There are many explanations of Shor's algorithm, but I was drawn to the YouTube video by Elucyda shown in Fig. 1. It takes about 25 minutes, and he explains it clearly and step by step, using only a whiteboard and clearly handwritten. This is great!

Shor's algorithm is said to be difficult to understand, but the outline is on this one page (8 lines). It involves prime factorizing an integer N, which is the product of two prime numbers. If N is small, it is not difficult to create an original program on a classical computer by following the steps in this diagram. However, you should pay attention to the part surrounded by a red frame in Fig. 1, "Find MIN r>0 such that a^r=1 mod N". This finds the smallest integer r (order) such that a^r = 1 mod N when you bring in another integer a for the integer N you want to factorize. This is nothing more than finding the minimum period of the repeating wave of the value of a^r mod N.

For very large N, this order-finding is the core of Shor's algorithm, and this is where quantum computers come into play. (This article is only beginner level. Without a complete understanding of quantum algorithms for order finding, it cannot be called intermediate level or above. I would like to write about this in another article.) Since we are assuming a small N this time, we have realized the entire processing of Fig. 1 as a mobilephoe app. This will help you become familiar with Shor's algorithm, and will also serve as a preparation for creating quantum programs later.

🔴 Creating a mobile phone app

Originally, the search for the above order r would be performed as a quantum algorithm, but since we are creating a mobile phone app here, this part is also a primitive (naive) program that runs on a classical computer. Fig. 2 shows the order calculation function created with MIT App Inventor. It should be noted that there is a risk of overflow when calculating a^r, especially when the value of r becomes large. Therefore, in order to prevent this to a certain extent, we do not calculate a^r mod N directly, but instead use repeated calculations using a small r.

🔴 Review of execution results

Let's start by trying to prime factorize a small integer, for example N=247, with this app. (N is given as the product of two prime numbers p=19 and q=13.) Figure 3 shows two successful examples. In Figure (a), the integer a randomly set in Figure 1 happened to be GCD(q, a)>1, so factorization was completed immediately. This corresponds to Case 1 in Figure 1. On the other hand, Figure (b) corresponds to Case 2 in Figure 1, and factorization was successful as expected.

Figure 4 shows different cases of failure. In Figure 4(a), the order r for a random integer a could not be found within the preset range. Furthermore, in Figure 4(b), the random integer a and the order r were set successfully, but prime factorization failed. This corresponds to Case 3 in Figure 1. Shor's algorithm thus succeeds probabilistically (by heuristics). However, it is known that the success rate is quite high.

🔴Why can this algorithm be used for prime factorization?

This article focuses on how Shor's algorithm works, not on why it can be used for factorization. However, I would like to briefly explain the key points of why below. One of them, which may be surprising, is the following formula (junior high school math!):

      a² - 1 = (a + 1)(a - 1)

Using this, a^r-1 = 0 mod N in the explanation of Fig. 1 becomes (a^r/2 + 1)(a^r/2 - 1) = 0 mod N. In other words, the left side of = is divisible by N. Therefore, one of the prime numbers that make up N divides one of the factors on the left side. From this, GCD(N, a^r/2 + 1) and GCD(N, a^r/2 -1) should be prime factors of N. When we calculate the case of Fig.3(b) (a = 30, r = 6), we see that this is indeed the case, as shown below:

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

Incidentally, the algorithm for finding the underlying order r turns out to be roughly equivalent to the (precise) quantum phase estimation already described here and here, which makes Shor's algorithm more familiar.

ショアの素因数分解に親しむためのスマホアプリ

 【要旨】著名なShor's Factoring Algorithmの本格的な実行には、大規模な誤り耐性量子コンピュータが必要であり、現時点の量子コンピュータでは、その実現がほとんど望めない。だが、理想的な量子コンピュータが出現した時には、このアルゴリズムが与えるインパクトは、サイバーセキュリティ上、非常に大きいと考えられている。ここでは、小さな整数（２つの素数の積）に対して、このショアのアルゴリズムを適用するためのスマホアプリを作成した。それによって、Shor'sに親しみを持ち、理解を深めることができた。

🔴Shor's Factoringの概要
　ショアのアルゴリズムの解説は多数存在するが、私は、Fig.1に示したElucyda氏によるYoutubeビデオに注目した。約25分で、白板１枚だけを使って、鮮明に手書きしながら、分かりやすくstep by stepで説明している。これは上手、素晴らしい！

　難解と言われるショアのアルゴリムだが、概要はこの１枚（８行）である。２つの素数の積である整数Nを逆に素因数分解するのである。小さなNであれば、この図の手順に従って、パソコンなどで独自にプログラムを作って確かめることは難しくない。ただし、注意すべきは、Fig.1の赤枠で囲った部分、"Find MIN r>0 such that a^r=1 mod N"である。これは、因数分解したい整数Nに対して、別のある整数aをもってきた時に、a^r = 1 mod Nとなる最小の整数r（位数）を求めるのである。これは、a^r mod Nの値の繰り返しの最小周期を求めることに他ならない。

　非常に大きなNに対しては、この位数探索がショアのアルゴリズムの根幹であり、量子コンピュータの出番となるところなのである。（この記事は初級レベルに過ぎない。位数探索のための量子アルゴリズムの完全理解無しでは、中級レベル以上と言えないのである。）今回は、小さなNを想定するので、Fig.1の処理全体をスマホのアプリとして実現した。ショアのアルゴリズムに親しむとともに、この後の量子プログラム作成の準備ともなる。

🔴スマホアプリの作成
　本来は、量子アルゴリズムとして上記の位数rの探索を行うのだが、ここではスマホアプリとして作るので、この部分も古典コンピュータで動く原始的な（ナイーブな）プログラムとした。Fig.2は、MIT App Inventorで作った位数計算関数である。

　注意点として、a^rの計算で、特にrの値が大きくなるとオーバーフローを起こす恐れがある。そこで、一定程度それを抑止するため、a^r mod Nの計算をダイレクトに行わずに、小さなrを使った繰り返し計算で実現している。

🔴実行結果の検討
　早速だが、このスマホアプリで、小さな整数、例えばN=247を素因数分解してみる。（このNは２つの素数p=19とq=13の積として与えた。）成功した２例をFig.3に示す。このうち、図(a)は、Fig.1においてランダムに設定した整数aが、たまたまGCD(q, a)>1となったので、因数分解はすぐに完了した。Fig.1のCase1に該当する。また、図(b)の方はFig.1のCase2に該当し、正常に因数分解ができた。

　一方、失敗した場合をFig.4に示す。このうち図(a)は、当方で適宜設定した、ランダムな整数aと求める位数rの値の制限範囲内においては、値rの探索に失敗した場合である。また、図(b)の方は、ランダムな整数aと位数rは設定できたものの、素因数分解に失敗したケースである。これは、Fig.1でのCase3に該当する。Shorのアルゴリズムは、このように、確率的（発見的）に成功するものである。ただし、その成功確率はかなり高いことが分かっている。

🔴なぜこのアルゴリズムで素因数分解できるのか
　本記事は、なぜショアのアルゴリズムで因数分解できるのか、ではなく、どのように働いているのかを中心に述べている。とはいえ、whyについても以下にポイントを簡単に述べてみたい。意外かもしれないが、その一つは、以下の計算式（中学校数学）にあった。

a² - 1 = (a + 1)(a - 1)

　これを使うと、Fig.1の説明にある、a^r-1 = 0 mod Nは、(a^r/2 + 1)(a^r/2 - 1) = 0 mod Nとなる。すなわち、=の左辺は、Nで割り切れる。だから、Nを構成する一つの素数は左辺のどちらかの因子を割り切る。このことから、GCD(N, a^r/2 + 1)とGCD(N, a^r/2 -1)がNの素因数となるはずである。Fig.3(b)の場合（a = 30, r = 6）を計算してみると、以下の通り

確かにそうなる。

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

　ところで、根幹をなす位数rを見つけるアルゴリズム（finding the order）は、すでにこことここに述べた（精密な）量子位相推定とほぼ同等であることが分かっている。このことからも、Shor'sアルゴリズムへの親しみは増すのである。

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/