2023年4月現在、
量子コンピュータはGoogleやIBMを筆頭とした海外企業からだけでなく、日本国内の理化学研究所からも製造・公開が始まっています。
世界で初めて量子超越(量子コンピュータを使って古典コンピュータよりも高速に計算)Googleの量子コンピュータチップ"Sycamore"[1]
量子コンピュータの使用分野は材料計算、探索、暗号などが主として挙げられていますが、最も大きなインパクトを与え、世界の研究を加速させたのは暗号分野でしょう。
その暗号分野において今なおスタンダードとされるアルゴリズムが"Shorのアルゴリズム"であり、これ自体は素因数分解を行うものとして知られています。素因数分解はそれ自体が現在主流となっている暗号の解読にものすごく密接に関わっているため、Shorのアルゴリズムが暗号領域に革命を起こすアルゴリズムとして知られているわけです。
Shorのアルゴリズム自体は1994年にピーター・ショア(Peter Shor)によって開発されたものであり、現在はその発展・応用形があることは間違いないでしょうが、このブログではそのスタート地点となるShorのアルゴリズムが提案された論文[2]"Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer"からじっくり見ていくつもりなので興味のある方はご一緒していただければ幸いです。
この記事では、論文内のabstractに限定して読んでいきます。難しい数式は本記事では登場しませんがこれから必要になる重要な用語がピックアップできるはずです。
abstractを和訳すると
以下のようになりました。分かりやすいようにそれぞれの文頭に番号を振ります。
①デジタルコンピュータは一般的に効率的な普遍的な計算装置であると考えられており、つまり、計算時間が多項式の因子によって増加する最大値で、任意の物理的な計算装置をシミュレートできると信じられています。 ②ただし、量子力学が考慮される場合、これが真実でない場合があります。 ③この論文では、一般的に古典的なコンピュータ上で困難であると考えられている2つの問題、整数の因数分解と離散対数を求めることについて検討します。 ④これらの問題は、いくつかの提案された暗号システムの基礎として使用されています。 ⑤仮想的な量子コンピュータ上でこれらの2つの問題に対して、効率的なランダム化アルゴリズムが与えられます。 ⑥これらのアルゴリズムは、入力サイズ（例えば、因数分解する整数の桁数）に多項式ステップを必要とします。
それぞれの番号に分けて読んでいきます。
①については言葉は難しいですが計算複雑性理論(computational complexity theory)に基づいた一般的な言及であり、簡単に言えばデジタルコンピュータ(以下コンピュータ)の計算速度には限界が設定されているということです。
例えばあるコンピュータAがある問題を解くのに必要な時間が$O(N^4)$であった場合、それを$O(N^k)$(例えばk=8)でシミュレートして解くことができるコンピュータがあるということを表しています。これは現在のコンピュータを考えるうえで基本的なルールでした。極端な話、スマホとスーパーコンピュータもこの関係の内である。
$O()$はランダウ表記という表記方法で、Nに関わらずカッコ内の任意の定数倍以下の数となることを表しています。例:$3N^3+2N+1=O(N^3)$
Nは問題のサイズを表していると考えてよいです。
より詳しいランダウ表記の解説(興味ない方は飛ばしてください):
ランダウ表記は、アルゴリズムの計算時間や空間利用量など、計算理論におけるアルゴリズムの効率を表現するための表記方法です。この表記法は、大きな入力サイズに対してアルゴリズムの増加量を表すために使用されます。
具体的には、O記法（ビッグオー記法）がよく使用されます。この表記法では、アルゴリズムの計算時間や空間利用量が、入力サイズの増加に伴ってどのように増加するかを表現します。O記法は、アルゴリズムの最悪の場合の増加量を表すために使用されます。例えば、O(n)は、入力サイズがnの場合、アルゴリズムが最悪の場合にnのオーダーで増加することを表します。
他にも、Ω記法（ビッグオメガ記法）やθ記法（ビッグシータ記法）などがあります。Ω記法は、アルゴリズムの最良の場合の増加量を表現するために使用され、θ記法は、アルゴリズムの平均的な場合の増加量を表現するために使用されます。
ランダウ表記は、アルゴリズムの効率性を評価するために広く使用されており、アルゴリズムの設計や比較に役立ちます。
②について、①の内容を否定しています。量子力学的には①は成り立たないときがあるということです。言い方は聞きなれないかもしれませんが、ここでまさに量子コンピュータには優位性があるといっているわけです。
量子コンピュータで$O(N^k)$で解ける問題であっても古典コンピュータ、つまり従来のコンピュータでは$O(N^l)$で解けるとは限らず、問題によっては$O(m^N)$になってしまうということです。ここで$O(m^N)$は問題サイズに対して指数的な計算量が必要であることを指し、$O(N^k)$よりもずっと大きいこと理解できます。
③では2つの数学問題が②を満たす問題として挙げられています。
1.整数の因数分解 (factoring integers)
2.離散対数を求める (finding discrete logarithms)
因数分解は素因数分解より広い範囲を指す言葉ですが、整数の因数分解というとこれは素因数分解のことといえると思います。離散対数を求めることも②を満たす、古典コンピュータでは難しく、量子コンピュータでは解きやすい問題だということです。
素因数分解だけが世間で注目されているので、離散対数というワードを知ることができたのは苦労して大元の論文を読んだ甲斐があったというものです。後の文章でこの離散対数に関する新たな発見があることに期待できます。
④より、素因数分解、離散対数の発見どちらも暗号分野の重要な要素だと述べられています。
⑤で、これら2つのアルゴリズムに対し、効率的なアルゴリズムを提案すると書かれています。ランダム化というのはランダム要素を含んだアルゴリズムということでしょう。つまりいつも計算時間が同じになるわけではなくランダム性があるということです。これを意外に思う方もいるかと思いますがアルゴリズムの世界ではランダム性を入れることで全体として効率化することはよくあることです。
仮想的な量子コンピュータ(hypothetical quantum computer)というのは気になる言い方ですね。現実の量子コンピュータができていない時期の論文なので、"あくまで机上の"のいう意図を含んでいるのかもしれません。
⑥について、これら2つの問題を多項式時間で解くことができると言及してアブストラクトを締めています。古典コンピュータではこれらの問題は指数時間かかるのに対し、量子コンピュータでは多項式時間$O(N^k)$で解けるというわけですね。
分かったこととして
以下が挙げられます。
- 取り扱う計算問題は2つ。素因数分解と離散対数の発見。
- 上の2つの問題は暗号分野の基礎部分で使用されている。
- 古典コンピュータでは上2つの計算は指数時間かかるが、仮想的な量子コンピュータでは多項式時間で済む。
次回は来週2023/4/9更新予定です。
論文の内容に踏み込んでいきます。リアクション頂けるとやる気が出ます。
[1]https://www.nature.com/articles/s41586-019-1666-5
[2]https://arxiv.org/pdf/quant-ph/9508027.pdf