why-quantum-computing.ipynb

Kernel: Python 3

なぜ量子コンピューティングなのか？

コンピューターとは何か？

このページにアクセスされた方は、コンピューターがどのようなものかをご存知でしょう。今日、コンピューターは、ノートパソコンや携帯電話から、信号機を制御するシステムまで、様々な形で利用されています。コンピューターは何でもできるようです。これらのシステムは非常に複雑で特殊なものですが、共通しているのは、コンピューターがある入力情報に対して一連の命令を実行し、何らかの新しい（出力）情報を与えてくれることです。

コンピューターに与える命令は、非常に具体的で曖昧さのないものである必要があります。このような命令の集合を「アルゴリズム」と呼び、コンピュータの研究の多くは、異なるアルゴリズムの挙動を研究しています。このコースでは、キーボードやマウス、画面は使わず、情報とアルゴリズムだけで構成される、最も単純なコンピューターについて考えます。

コンピューターのアルゴリズムの分類

従来のコンピューターの中で量子コンピューターが果たす役割を理解するためには、まず、さまざまなアルゴリズムの性能をどのように測定するかを知る必要があります。

コンピューターサイエンスでは、入力の大きさに応じて使用するリソースがどのように大きくなるかでアルゴリズムを分類します。これをアルゴリズムの複雑さと呼びます。例えば、ある数字が偶数かどうかを判断するアルゴリズムは、その数字の最後の一桁を見るだけでよいわけです。この場合、「入力」は数字で、「出力」は「偶数」か「奇数」のどちらかです。アルゴリズムが完了するまでの時間は、入力された数の大きさに依存しないので、これを定数時間アルゴリズムと呼びます。コンピューターによってこの結果を得るのにかかる時間は異なるかもしれませんが、それは他の要因によるもので、入力の長さによるものではありません。

別の例を見てみましょう。今回は、入力は同じ長さの2つの数で、問題はそれらを足すことです。この場合、出力は新しい数字になります。2つの複数桁の数字を足す場合、学校で習ったであろう一般的なアルゴリズムでは、それぞれの数字の右端の桁から始めて、それらを足し合わせます。そして、1桁左に移動して（結果が9より大きい場合は「1」を繰り越す）、この処理を繰り返します。コンピューターは、足すべき桁がなくなるまでこれを繰り返し、アルゴリズムを終了します。

足し算はどのくらい複雑なのか？

この足し算アルゴリズムが完了するまでにかかる時間は...

1. ...入力された数値の長さに線形に（比例して）増大する（線形時間）。

1. ...入力された数値の長さに影響されない（定数時間）

1. ...入力数の長さの2乗で大きくなる（2次時間）

繰り返しになりますが、コンピューターによってこのアルゴリズムの実行速度は異なります。ノートパソコンでは、人間の何百万倍もの速さで足し算を実行できます。しかし、1秒間に100万回の演算ができても、1回しかできなくても、増加率は同じです。

ここで最後に、私たちにとって非常に興味深い例を一つ紹介しましょう。秘密の番号（暗証番号など）を持っていて、それを当てるという問題があるとします。この場合、問題の大きさは番号の長さです。

答えが正しいかどうかを確認する唯一の方法が、キーパッドに数字を打ち込むことだとしましょう。その数字が何であるかについての情報はないので、この秘密の数字を見つけるための最適なアルゴリズムは「総当り」方式を使用します。つまり、巧妙なことは何もせず、単に可能な限りの数字を試してみるということです。

どれくらいの時間がかかるのでしょうか？さて、理論的には運が良ければ一回で答えを当てることができますが、これは非常に低い確率です。平均すると、可能な入力の約半分を試さなければならないので、アルゴリズムの実行時間は可能な組み合わせの数に比例します。そこで問題です。可能な組み合わせの数は、秘密番号の長さに応じてどのように増加するのでしょうか？

秘密の番号に桁を追加するごとに、可能な組み合わせの数が10倍されます。例えば、1桁の秘密の数字には10の可能性があり (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)、2桁の秘密の数字には100の可能性があるのです。各桁を当てるのにかかる時間が（長さに関係なく）同じだと仮定すると、次のように数学的に表すことができます。

ParseError: KaTeX parse error: Undefined control sequence: \cssId at position 1: \̲c̲s̲s̲I̲d̲{T}{T} \cssId{p…

この式では桁数(d)が指数であることにお気づきでしょう。このように、これは指数時間アルゴリズムであり、実行時間は入力の長さに対して指数関数的に増加する、と言います。

なぜ、このようにアルゴリズムを測定するのか？

コンピューターによって得意分野が異なるため、あるコンピューター上では別のコンピューター上よりもある演算が速くなることがあります。入力サイズに対する時間の増加を研究することによって、アルゴリズムとコンピューターの特定の組み合わせではなく、デバイス固有の詳細を無視し、実際に「アルゴリズム」を測定することができます。重要なことは、アルゴリズムが入力サイズに対してどのように変化するかを知ることで、アルゴリズムが管理可能な大きさになるかどうかもわかるということです。

上で見た線形時間足し算のアルゴリズムについて考えてみましょう。10桁の数字を1秒につき2つ足すことができたとしたら、直線的な伸び率から、20桁の数字を2秒で足すことができるはずです。10桁増えるごとに、計算時間はおよそ1秒ずつ増えていくはずです。

一方、上記の指数時間探索アルゴリズムを使って、10桁の暗証番号を1秒で見つけることができたとします。これは、あなたのコンピューターが1秒間に ~5,000,000,000の組み合わせを試せるほど高速であることを意味します。このアルゴリズムを使ったコンピューターが20桁の暗証番号を見つけるには、およそ5,000,000,000秒（~150 年）かかると予想されます。さらに10桁増えると、約150,000,000,000年（宇宙の年齢の120倍）にもなります。指数関数時間のアルゴリズムは、わずかな入力桁数（この場合は ~30 桁）でも、実行するのが難しいどころか、文字通り不可能になってしまうのです。

この暗証番号探索問題は、できるだけ単純にするための人工的な例ですが、コンピューターサイエンスには、非効率なアルゴリズムしかない現実の問題が数多く存在します。今日のコンピューターは驚くほど高速ですが、これらの困難な問題は、最大のスーパーコンピューターでも難しすぎることがあります。

しかし、より効率的に時間増加するアルゴリズムが見つかれば、比較的遅いコンピューターや信頼性の低いコンピューターでも、これらの困難な問題を突然処理できるようになるかもしれません。そこで登場するのが、量子コンピューターです。

量子コンピューターはどのように役立つのか？

これまで、アルゴリズムというものを非常に抽象的に考えてきましたが、そのアルゴリズムを実行するコンピューターは現実の世界に存在しなければなりません。そのコンピューターが高性能なマイクロチップであろうと、紙とペンを持った人間であろうと、すべてのコンピューターは最終的に物理法則に支配されており、その演算によって私たちが作れるアルゴリズムが限定されてしまうのです。

物理学は、宇宙に存在するすべてのものが従う一連のルールを解明しようとするものです。20世紀初頭、実験室での繊細な実験を通して、物理学者たちは、現在の物理学では説明できないような奇妙な振る舞いを目にしました。このことは、物理法則が正確でないことを意味します。そこで彼らは、より完全な「量子」物理学を開発し、この挙動を非常にうまく説明することに成功しました。

物理学者は、これまで見たこともないような振る舞いを説明するために量子物理学を生み出し、コンピューター科学者は、新しく発見されたこの振る舞いを利用することで、より効率的なアルゴリズムが作成することが（理論的には）できることを発見したのです。その結果、従来のコンピューターでは解決不可能な問題でも、この振る舞いを利用できる「量子」コンピューターであれば解決できると考えられるものがあります。そのひとつが整数の因数分解です。

「$x$」と呼ぶ整数があるとします。因数分解アルゴリズムでは、$p×q = x$となるような整数 $p$ と $q$ を求めます。これは簡単な場合もあります。$2000 = 2 × 1000$と一目でわかりますが、$x$が2つの大きな素数の積の場合はこの問題は非常に難しくなります。整数の因数分解について語るとき、最も困難な（最悪の）シナリオを想定することになります。下のコードセルでは、変数xに250桁の数字を代入しています。

# pylint: disable=line-too-long, invalid-name
x = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

2020年に、研究者は古典的なスーパーコンピューターと~2700コア年の処理能力を用いてこの数を因数分解しました。これは大規模な作業であり、本稿執筆時点では記録破りである。彼らの結果は、以下のコードセルで確認することができます（幸運なことに、私たちには乗算の効率的なアルゴリズムがあります！）。

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

p*q == x  # 「True」と評価される

True

表示される出力は、セルの最終行の値です。この場合、p*q == xはTrueと評価されることがわかります。数学的に証明されているわけではありませんが、従来のコンピューターでこのような数の因数分解を行う効率的なアルゴリズムが存在しないことは確かです。実際、インターネットの暗号化の多くは、この問題が解決不可能であるという仮定に依存しており、617桁のRSA数の因数分解は不可能であるとされています。一方、量子コンピューターでは、十分な大きさの量子コンピューターができれば、1日以内にこれらの数字を因数分解することができると推定される効率的な因数分解アルゴリズムがわかっています。

今、私たちはどこにいるのか？

量子コンピューターは、より効率的なアルゴリズムを実行できることが分かっていますが、現在ある量子コンピューターは小さくて不安定なため、従来のコンピューターと比較して優位性を発揮することはできません。

量子コンピューターが解決できる問題の大きさを制限する要因は、ごく単純に考えても2つあります。1つ目は、量子コンピューターが保存・処理できるデータの量です。これは通常、量子ビットで測定されます。もし十分な量子ビットがなければ、あるサイズ以上の問題を保存・処理することはできません。2つ目は、量子コンピューターのエラーレートです。量子的な振る舞いは、実験室での繊細な実験でしか見ることができないため、量子コンピューターを作るのは繊細な作業です。今ある量子コンピューターはノイズが多いので、よく間違いますし、結果に「ノイズ」が入ります。ノイズが多すぎると、結果が意味のないものになってしまうのです！

今のところ、量子コンピューターは実験的なものです。量子ビットの数やエラーレートに制限があるため、現在解決できる最大の問題は、従来のコンピューターでも容易に解決できるものです。

未来のある時点で、これは変わるでしょう。量子コンピューターを使った方が、従来のコンピューターよりも経済的に有利に問題を解決できるという「量子アドバンテージ」に到達するのです。なぜそれがわかるのでしょうか？*なぜなら、私たちはアルゴリズムをその増加率で測っているからです！*量子コンピューターが順調に発展し続ける限り、いずれは古典的なコンピューターを追い抜くことが分かっているのです。

617桁のRSA数を1日以内に因数分解するには、~2,000万のノイズのある量子ビットが必要であるとされています。本稿執筆時点で、IBMは現在65量子ビットの量子コンピューターを保有しており、2023年までに1000量子ビットを超えるシステムの構築を目指しています。このマイルストーンのずっと前に、量子アドバンテージをもたらすと思われるアルゴリズムが他にもありますが、まだまだ先の話と思われるかもしれません。

以下のコードを使用すると、単純な量子プログラムを作成し、IBM Quantum に送信して、実際の量子コンピューターで実行できます。 IBM Quantum は、このプログラムを 4000 回実行します。このプログラムは確率論的であり、結果は半分が000 、残りの半分が 111 になるはずです。ご覧のとおり、これらは唯一の結果ではありません。ノイズのために他の出力を測定する可能性がわずかにあります。

# 1. '量子回路' と呼ばれるシンプルな量子プログラムを作成する
from qiskit import QuantumCircuit
qc = QuantumCircuit(3)
qc.h(0)
qc.cx(0, [1, 2])
qc.measure_all()

# 2. IBM Quantumに一番空いていてシミュレーターではないデバイスを問い合わせる
#    この例をローカルで実行している場合は、自分のIBM Quantumの
#    APIトークンを使って、アカウントをロードする必要がある
# IBMQ.save_account(token="XYZ")
# IBMQ.load_account()
from qiskit.providers.ibmq import IBMQ, least_busy
provider = IBMQ.get_provider('ibm-q')
device = least_busy(
            provider.backends(
                filters= lambda x: not x.configuration().simulator
            )
        )
print(f'Running on {device.name()}')

# 3. プログラムをデバイスで実行できる形に変換する
#    これは'トランスパイル'として知られている
from qiskit import transpile
transpiled_qc = transpile(qc, device)

# 4. 実機で実行しそのステータスをモニターするよう、
#    プログラムをIBM Quantumに送信する
from qiskit.tools import job_monitor
job = device.run(transpiled_qc)
job_monitor(job)

# 5. 結果をヒストグラムにプロットする
from qiskit.visualization import plot_histogram
plot_histogram(job.result().get_counts())

Running on ibm_geneva
Job Status: job has successfully run

従来のコンピューターがどこから来たのか、思い起こしてみる必要があります。下の写真は、1947年に作られた最初のトランジスターの写真です。トランジスターは、現代のコンピュータープロセッサーの構成要素です。

画像クレジット: 連邦職員リンク、パブリックドメイン。

それから70年、現代のコンピューターチップには、何十億というトランジスターが搭載されています。

このコースの残りの部分では、より効率的なアルゴリズムを作成することを可能にする量子効果を探ります。このコースの終わりには、ソフトウェアパッケージであるQiskitを使って、これらのアルゴリズムの1つを実行する量子コンピューターをプログラムすることができるようになるはずです。

クイッククイズ

量子コンピューターは、いずれ...

1. ...従来のコンピューターでは困難な計算を行うことができます。

1. ...従来のコンピューターに置き換わります。

1. ...従来のコンピューターの速度を向上させます。