GitHub Repository: quantum-kittens/platypus
Path: blob/main/translations/ja/ch-states/case-for-quantum.ipynb
⁴⁰⁶⁵ views

Kernel: Python 3

量子コンピューターの場合

1. 足し算の複雑さ

単純に述べると、量子コンピューターは古典コンピューターでは解くことができなかった問題を解くことができます。この理由を理解するために、最初にその問題を解くために必要な計算量を考える必要があります。

まず、最初の章で検討したアルゴリズム(2つの数値の足し算)を再度考えます。

   9213
+  1854
=  ????

２つの $n$ 桁の数の足し算は、それぞれが2つの1桁の数字を足すシンプルな演算子で計算することができます。過程の複雑さを分析すると、これらの数の足し算が要求されている計算量やこれがどのように $n$ に依存するかを考えることができます。この数を $c(n)$ と呼びます。

最も簡単なケースは、繰り上がりのない足し算で、 $n$ 回の基本的な足し算が要求されます。最悪なケースは、 $n$ 回の繰り上がりの足し算を実行する必要がある場合です。それぞれの位に基本的な足し算が必要になります。これらの考えから、計算に必要な回数は $n \leq c(n) \leq 2n$ と結論づけられます。

2. O記法（ビッグ・オー記法）

この結果は、 $c(n)$ が $n$ とともに線形に増加するということができます。より一般的には、 $n$ が大きい場合に $c(n)$ の上限として機能する $n$ の線形関数を見つけることができると言えます。これは言葉にすると長くなる上、毎回説明したくもないので、代わりに、これをより簡潔に「O記法(ビッグ・オー記法)」と表現します。

備忘

9213

1854 = ????

ビッグ・オー記法は、特定のプラットフォームやアルゴリズムの実装に関係なく、アルゴリズムに必要なリソース/ランタイムが入力サイズとどのようにスケールするかを比較できるので便利です。以下に、入力サイズ $n$ の関数としてのランタイム $N$ の一般的なスケーリング係数の例を示します。問題のサイズが十分に大きい場合、 $a$ と $b$ が一定である時、 $O(a^n)$ のアルゴリズムの実行時間が $O(n^b)$ のアルゴリズムの実行時間を超えることは明らかです。

この記法を使うことで、上記の性質は単純に $c(n) = O(n)$ として表されます。これにより、詳細にこだわる必要なく線形な振る舞いを捉えています。したがって、 $c(n) = n$ 、 $c(n) = 2n$ 、またその他であろうと、 $c(n) = O(n)$ と簡単に表現できます。

これまで検討してきたことには、隠れた仮定があります。桁数について話す際に、特定の数記法を使うことを前提としています。しかし、桁数は、10 進数、2進数、またはその他の、どの数記法を使っているかによって変わるでしょう。例えば、数を表すのに必要なビット数 $n_2$ は、以下の式によって同じ数を示すのに必要な 10 進数の桁数 $n_{10}$ と関係しています。

$n_2 = \left\lceil \frac{\log 10}{ \log 2} , n_{10} \right\rceil \approx 3.3 , n_{10}.$

これも線形な関係なので、ビッグ・オー記法を使用して複雑さを表現する方法は変わりません。 $c(n_2) = O(n_2)$ 、 $c(n_{10}) = O(n_{10})$ 、さらには $c(n_{10}) = O(n_{2})$ は同等と言えます。私達が使用する記数法を指定せずともよく単に桁数 $n$ と話すことができるのはこのためです。

3. 複雑性理論

複雑性理論は、任意のアルゴリズムを実行するために必要な計算量の研究のことです。ある問題を解くための最適なアルゴリズムを考慮することによって、その問題を解く時の固有の計算量を研究することができます。さらに、最適なアルゴリズムはすでに分かっているので、 $O(n)$ の複雑さの問題でもあることが分かっています。

掛け算はそれほどシンプルではありません。2つの $𝑛$ 桁の数値を掛け算する時に、学校で学んだアルゴリズムでは、1 桁の加算や乗算など、 $O(n^2)$ の基本的な操作が必要になります。漸近的な複雑さの低いアルゴリズムが見つかっていますが、 $O(n)$ の複雑さで掛け算を実行することは不可能であると広く考えられています。

それでも、掛け算は最も複雑な問題ではありません。はるかに複雑な問題の例は、因数分解です: $n$ 桁の数を取り、その素因数を見つけることです。この素因数分解の最もよく知られているアルゴリズムの計算量は、 $O\left(e^{n^{1/3}}\right)$ よりも悪いです。ここで、指数が含まれていることはとても急速に複雑性が増幅し、指数関数はその因数分解を解くため問題がハードになっていくことを示します。

実際の計算時間を使用してこの点を示すために、最近の例を取り上げます。 $^{1}$ 次の829桁の数値について考えてみます。

In [1]:

rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

このサイズの数値の掛け算や足し算をするために、あなたのコンピューターを使うと、瞬時に問題を解くことができることがわかるでしょう。コンピューターが持つプロセッサの数にコア秒数を取得するために必要な秒数を掛け算すると、 1 コア秒よりもはるかに少ないコア秒数が必要であることを確認してください。

しかしながら、この数の因数分解の実行で以下の2つの因数を生成する計算では、スーパーコンピューターで約2700コア年もの実行時間を必要とします。

In [2]:

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
p*q

Out[2]:

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

より大きな数の因数分解では、スーパーコンピューターが天文学的な数字を実行する必要があるポイントに簡単に到達します。明らかにそのような問題は実践的に解くことは不可能です。

これまでは、 $n$ 桁の数字に対する数学的演算だけを考えてきましたが、その複雑さは、単純な一桁の演算の数で表されます。しかしながら、複雑性理論は、データーベースの探索やグラフを描いたり、ダイナミクスをシミュレーションしたり、ゼルダの伝説のダンジョンの移動など、あらゆる種類の問題の計算方法を分析できます。いずれの場合も、入力サイズとして機能する、パラメーター、またはパラメーターのセットを見つけ、O記法を用いて入力サイズの観点から計算量を表現することができます。例えば、 $N$ の要素のデータベースを探索する場合、その計算量は $O(N)$ です。

正式には、アルゴリズムの計算量の定義は、使っている計算の正確な理論モデルに依存します。各モデルには、プリミティブ演算と呼ばれる一連の基本演算があり、これを使用して任意のアルゴリズムを表現できます。ブール回路の場合、1章で検討したように、プリミティブ演算は論理ゲートです。アラン・チューリングによって提唱された、架空のコンピューターの形式である、チューリングマシーンの場合、テープに保存された情報をステップスルーして操作する装置を想定します。RAM モデルには、より複雑なプリミティブ操作のセットがあり、私たちが毎日使うコンピューターの理想的な形として機能しています。これら全てのことが、離散値の離散された操作の基本となるデジタル方式のモデルです。それぞれ異なって見えるかもしれませんが、それぞれが他をシミュレートするのは非常に簡単であることがわかります。これは、ほとんどの場合、計算の複雑性は、これらのモデルでどのモデルを使うかに大きく依存ないことを意味します。したがって、RAM モデルやチューリングマシーンに特化して計算量を述べるのではなく、デジタルコンピューターの計算量をシンプルに述べることができます。

4.デジタル計算を越すもの

デジタルコンピューターは今優勢なものですが、計算の形式はデジタルコンピューターだけではありません。アナログコンピューターもまた、過去に広く使われ、研究されてきました。デジタルコンピューターの離散的な値とは異なり、アナログコンピューターは連続的に変化する変数の精密な操作に基づいています。このアナログコンピューター・デバイスが、デジタルコンピューターで処理しにくい問題を迅速に解くことができると主張されることがあります。しかし、そのような主張は実現しませんでした。アナログコンピューターの大きな障害は、任意に高精度なデバイスを構築できないことです。デジタルコンピューターでは、誤差を目立たせるために比較的大きく離散化し、エラーを検出して修正する方法を実装できます。しかし、アナログコンピューターでは、誤差は任意に小さくて検出できないことがあり、またその影響が積み重なって計算を台無しにしてしまうことがあります。

計算の理想モデルを提唱する場合、デジタルコンピューターの頑健性とアナログコンピューターの繊細な操作を結びつけることを探索するかもしれません。量子ビットが離散的な出力0と1を持つシステムであるが、連続パラメーターによってのみ記述できる状態で存在できることはすでに見てきました。これは、量子システムに典型的な「波と粒子」の二重性としてよく知られた概念の特定の例です。量子ビットは、離散的または連続的のどちらかでは、完全に表現することができず、むしろその2つの組み合わせとして表現することができます。アインシュタインは以下 $^{2}$ の言葉を残しています。

「時には一方の理論を使い、時には他方の理論を使わなければいけない場合もあれば、どちらかを使用する場合もあるようです。私たちは新しい種類の困難に直面しています。私たちは現実について2つの矛盾した写真を持っています。どちらも別々には現象を完全に説明してくれないが、一緒になら説明してくれます。」

それ故、プリミティブ演算が量子ビットに適用されるゲートである量子コンピューターは、アナログでもデジタルでもなく、何かユニークなものです。次の章では、このユニークな性質がもたらす結果を探っていきます。量子コンピューターはデジタルコンピューターとは根本的に異なった計算複雑性の問題を解くことができます。実際、量子コンピューティングは特定のタスクで、古典コンピューターよりも指数関数的に速くなることができる唯一の技術として、知られています。計算時間を数年から数分に短縮できる可能性があります。量子誤り訂正が欠陥の影響をどのように取り除くことができるかもまた、私たちは探求します。

5. 量子コンピューターを使う最適なケース

量子ビットと量子ゲートでは、デジタルやアナログの古典的なアルゴリズムと根本的に異なった新しいアルゴリズムを設計することができます。このような方法で、古典コンピューターで解くことができなかった問題の解法を見つけることを期待しています。

これを行う一つの方法は、全体的な特性を決定したい関数を持っている時です。例えば、もし関数𝑓(𝑥)が最小値の時の変数𝑥の値を知りたい場合、または、関数𝑓(𝑥)が周期的な関数であれば、その関数の周期を知りたい場合です。デジタルコンピューターのアルゴリズムは、全体的な特性についての十分な情報を得るために、さまざまな異なる入力に対して、 $f(x)$ を計算するプロセスを使用することがあります。しかし、量子コンピューターでは、重ね合わせ状態を作り出すことができる現象が、関数をたくさんの可能な入力に同時に適用できることを意味します。そのような状態を測定すると、単に1つの結果を得られるだけなので、これは、全ての可能な出力にアクセスできるという意味ではありません。しかし、代わりに量子の干渉の結果に帰納することができ、これにより、私たちが知りたい全体的な特性が明らかになります。

この典型的な記述は、たくさんの既に発見された量子アルゴリズムの機能を説明します。代表的な例として、Groverのアルゴリズムがあります。このアルゴリズムは、 $N$ のデータを探索する複雑さを $O(N)$ から $O(N^{1/2})$ に減らします。この2次の速度の向上は、機械学習や最適化問題のような非構造化探索として表現できるタスクを使用する多くのアプリケーションで役立つ可能性があります。

In [ ]:

# このコードは相互作用するグラフを作るものです。
from bokeh.layouts import column
from bokeh.models import ColumnDataSource, CustomJS, Slider
from bokeh.plotting import figure, show
from bokeh.embed import file_html
from bokeh.resources import CDN
import numpy as np
import IPython

x = np.arange(0,500)
y_linear = x
y_sqrt = 7.5*np.sqrt(x)

linear_source = ColumnDataSource(data=dict(x=x, y=y_linear))
sqrt_source = ColumnDataSource(data=dict(x=x, y=y_sqrt))

plot = figure(
              plot_height=400, 
              plot_width=800,
              sizing_mode="scale_width",
              tools="reset,save",
              x_range=[0, 500], y_range=[0, 500], 
              x_axis_label="Size of Problem",
              y_axis_label="Time Taken to Find Solution")
plot.line('x', 'y', source=linear_source, line_width=3, line_alpha=0.6, color="blue", legend_label="Classical Search O(N)")
plot.line('x', 'y', source=sqrt_source, line_width=3, line_alpha=0.6, color="red", legend_label="Quantum Search O(√N)")
plot.legend.location = "top_left"

callback = CustomJS(args=dict(source=sqrt_source), code="""
        var data = source.data;
        var f = (10-cb_obj.value)*2 + 3
        var x = data['x']
        var y = data['y']
        for (var i = 0; i < x.length; i++) {
            y[i] = f*Math.sqrt(x[i])
        }
        source.change.emit();
    """)

speed_slider = Slider(title="Relative Speed of Quantum Computer", value=7.5, start=1.0, end=10.0, step=0.1, show_value=False)
speed_slider.js_on_change('value', callback)

layout = column(plot, speed_slider)

caption = """
異なったプラットフォーム間でアルゴリズムのパフォーマンスを比較することは困難です。
O記法を通してわかることは、量子コンピューターと古典コンピューター間のスピードの違いがあるけれども、
十分に大きな問題の場合、量子探索アルゴリズムはいつも古典コンピューターで探索した結果よりも優れているということです。
"""

html_repr = file_html(layout, CDN)
html_fig = "<figure>{0}<figcaption>{1}</figcaption></figure>".format(html_repr, caption)
IPython.display.HTML(html_fig)

目覚ましい速度の向上は、素因数分解の問題を解く中心となる周期関数を分析するショアのアルゴリズムでも得られます。これにより、 $O(𝑛^3)$ の計算量で $𝑛$ 桁の数字を因数分解する量子ソリューションを得ることができます。これは、 $O\left(e^{n^{1/3}}\right)$ よりも悪い計算量を持つデジタルコンピューターと比べて超多項式の高速化となります。

量子アルゴリズムに対する別のアプローチは、量子問題を解決するために、量子コンピューターを使うことです。次のチャプターでわかるように、量子状態を表現するには、量子ビットの数に応じて指数関数的にスケールする情報が必要です。しかし、量子コンピューターでは、同じ仕事をするために、 $n$ 量子ビット必要なだけです。このように、量子状態を表現したり、操作したりする自然の特性があるため、分子や素粒子のような関心のある量子のシステムを研究し、よりよく理解することができるようになります。

したがって、さまざまな産業で量子アルゴリズムを適用し適応することで、ビジネスや科学の分野で破壊的なユースケースを可能にすると期待されています。これには、創薬、機械学習、材料発見、オプション価格設定、タンパク質の折りたたみ構造やサプライチェーンにおけるブレークスルーが含まれます。 $^{3}$ 特に有望なのは、古典アルゴリズムが固有のスケーリング限界に直面している問題であり、大きな古典的なデータセットをロードする必要がない問題です。量子優位性のために、与えられた問題の解答は量子力学がすべてのパスを通らなくても解が得られるような構造を持つ指数関数的に多くのエンタングルした自由度に強く依存する必要があります。しかし、量子コンピューターにとって「簡単な」問題(多項式時間で解ける問題)と他の複雑性理論クラスとの正確な関係は、まだ未解決な問題であることに留意してください。 $^{4}$

これは、量子アルゴリズムが特有の方法で計算を実行する方法のほんの一部です。これらのアプローチの詳細は後の章で扱います。しかし、まず複数量子ビットを学び、量子ゲートの完全なセットを理解することに時間を費やす必要があります。これについて、次の章で学びます。

6. 参考文献

https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html
Albert Einstein, Leopold Infeld (1938). The Evolution of Physics: The Growth of Ideas from Early Concepts to Relativity and Quanta. Cambridge University Press.
https://www.ibm.com/thought-leadership/institute-business-value/report/quantumstrategy
https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
Image: Cmglee / CC BY-SA (https://creativecommons.org/licenses/by-sa/4.0)

In [17]:

import qiskit.tools.jupyter
%qiskit_version_table

Out[17]: