量子アルゴリズム入門: Daniel Simon 本人と読み解く Simon のアルゴリズム

本ブログは 2021 年 10 月 11 日に公開された AWS Blog “Exploring Simon’s Algorithm with Daniel Simon” を翻訳したものです。

はじめに

量子コンピューティングに取り組み始めたお客様は、基礎を学ぶときや新しいサービスを評価するときに、既知のアルゴリズムを活用することがよくあります。Amazon Braket では、そうしたアルゴリズムを SDK とマネージドノートブックに多数用意しています。この記事では、最初期に考案された量子アルゴリズムの 1 つであり、Amazon Braket のサンプルとして公開されている Simon のアルゴリズムを取り上げます。まずアルゴリズムの背景にある理論を説明し、続いて Amazon Braket を使って Simon のアルゴリズムをエンドツーエンドで実装します。さらに、Simon のアルゴリズムの考案者で AWS Cryptography の Principal Security Engineer である Daniel Simon が、自身の名を冠したアルゴリズムについて当時の背景や着想を語ります。

この記事は、Simon のアルゴリズムのサンプル Jupyter Notebook を補足するものです。このノートブックは、Amazon Braket のマネージドノートブックインスタンスを起動してサンプルノートブックのセクションを開くか、オープンソースの amazon-braket-examples GitHub リポジトリを参照することで入手できます。より詳しい内容はノートブックをご覧ください。Amazon Braket サンプル GitHub リポジトリには、他の重要な量子アルゴリズムの実装も公開されています。

Simon のアルゴリズム

Simon のアルゴリズムは、量子コンピュータで特定の問題を解くことにより、既知の最良の古典アルゴリズムに対して指数関数的な高速化を達成した最初の例です。1994 年に発表されたこのアルゴリズムは、よく知られた Shor の素因数分解アルゴリズムの先駆けとなり、その後の量子計算分野における多くの重要な研究に着想を与えました。

Daniel Simon: 「少し面白い経緯をお話しします。私は自分のアルゴリズムを理論計算機科学の学会 (STOC 1993) に投稿しましたが、採択されませんでした。しかし、その学会のプログラム委員会に Peter Shor がいて、同じアルゴリズム構造を素因数分解や離散対数といった具体的な問題に応用できる可能性 (正直に言えば、私はまったく気付いていませんでした) をすぐに見抜いたのです。Shor は私の論文を採択するよう委員会を説得しようとしましたが叶わず、そこで自身の研究に取り組み、次の主要な理論計算機科学の学会 (FOCS 1993) に投稿しました。私も同時に再投稿しました。実は、Shor の論文だけが採択された場合は 2 つの論文を統合することで合意していたのですが、さいわいにも委員会は両方を採択し、結果として得られた成果について、それぞれの貢献分を私たち双方に認めてくれました」

Simon の問題

Simon のアルゴリズムは、次の数学的問題を解くために設計されました。
ビット文字列をビット文字列に写す関数 f:{0,1}ⁿ→{0,1}ⁿ が与えられたとします。さらに、関数 f について、次のいずれかが成り立つという約束 (promise) が与えられます。すなわち、入力ごとに異なる出力に写すか、あるいは異なる 2 つの入力を同じ 1 つの出力に写すかです。ただし、どちらであるかは知らされません。数学的には、f が 1 対 1 (単射) か 2 対 1 のどちらかであり、次の約束が成り立つことを意味します。

$Simon's problem promise: for all x and y in {0,1}^n, f(x)=f(y) if and only if x=y oplus s$

これは、ある未知の n ビットの文字列 s∈{0,1}ⁿ に対して成り立ちます。ここで ⊕ は、ビットごとの mod 2 加算を表します。

別の言い方をすると、ある未知の文字列 s が存在し、すべての入力文字列 x に対して f(x)=f(x⊕s) が成り立ちます。s がゼロでない場合、この関数が取る各出力値にちょうど 2 つの入力が写るため、2 対 1 になります。s がゼロ文字列の場合は 1 対 1 になります。

Simon のアルゴリズムの目的は f が 1 対 1 か 2 対 1 かを判定することであり、そのために秘密の文字列 s を直接求めます。実際、ここで考えているオラクルの設定では、s を見つけることが元の問題を解くことと数学的に等価だと示せます。

Daniel Simon: 「このアルゴリズムは『約束問題 (promise problem)』を解きます。つまり、特定の性質が約束されたオラクルの形で関数が与えられ、その約束が満たされている限り、アルゴリズムはその関数から関連する性質を引き出します。これは量子アルゴリズムにとって自然な対象です。『量子並列性』によって、指数関数的な大きさの入力空間にわたって関数を探索できるからです。量子アルゴリズムと古典アルゴリズムの差を示すこのアプローチを最初に提案したのは Deutsch と Jozsa でした。しかしこの試みは、決定論的な古典アルゴリズムと比べれば量子アルゴリズムが指数関数的に高速である一方、実際には古典的な確率的アルゴリズムで (指数関数的に小さい誤り確率で) 容易に解けてしまうものでした」

古典的な計算複雑性

Simon の問題を古典的に解くには、f(x)=f(y) となる異なる 2 つの入力 x と y を見つけるか、あるいは同じ出力を生成する入力の組が存在しないことを示す必要があります。前者が見つかれば s=x⊕y (加算はビットごとに mod 2 で行います) が求まります。

Daniel Simon: 「これは正しくないかもしれません。関数 f の計算の詳細を何らかの方法で掘り下げることで、文字列 s を常に効率的に見つけられる魔法のようなアルゴリズムが存在する可能性もあります。しかし f をオラクルとして表現すれば、そうした仮想的な解法 (見つかることはほとんどありませんが、不可能だと証明されることもほとんどありません) を抽象化して排除できます。その結果 s を見つける道は、同じ出力を持つ入力の組を実際に見つけることだけになります」

関数 f がブラックボックスとして与えられたとき、同じ出力に写る異なる 2 つの入力を見つけるのはどれほど難しいのでしょうか。n ビットの文字列の場合、考えられる入力は 2ⁿ とおりあります。したがって最悪の場合、同じ出力に写る組を見つけるには最大 2ⁿ 個の異なる入力を調べることになり、これが必要なクエリ複雑性の上限を与えます。では下限はどうでしょうか。古典的には Θ(2^n/2) 個の入力を調べる必要があることが示せますが、これも問題のサイズに対して指数関数的に増大します。この下限の直感的な理解は、(一般化された) 誕生日問題から得られます。ある集団の中で、2 人が同じ誕生日になる確率はどれくらいでしょうか。この問いを逆にして、「少なくとも 2 人が同じ誕生日である確率を一定の値より大きくするには、部屋に何人必要か」と考えることもできます。答えは、誕生日として考えられる日数 (つまり 365) の平方根程度の人数です。Simon の問題では、これは約 Θ(2^n/2) 個の入力を調べる必要があることに対応します。

Simon の問題に対する量子アルゴリズム

Simon のアルゴリズムは、指数関数的に少ない回数のクエリを関数 f に行うだけで、前述の問題を解く手法です。このアルゴリズムが機能するには、未知の関数 f を量子論理ゲートで実装できる必要があります。言い換えると、ユニタリ演算子 U_f によって、関数 f の作用を量子状態の変換としてエンコードする必要があります。具体的には次のようになります。

ここでの議論では、ユニタリ演算子 U_f はブラックボックス (「オラクル」) として与えられ、内部の仕組みはわからないものの、前述の変換を実装していることはわかっていると仮定して構いません。オラクルモデルの利点の 1 つは、オラクルの動作原理を知る必要はなく、正しく動作することを信頼すればよい点です。Simon のアルゴリズムのノートブックでは、f に対してよく使われるサンプルオラクルの実装を提供し、その仕組みと理由も詳しく説明しています。

量子回路

Daniel Simon: 「量子回路モデルと量子チューリングマシンモデルは等価ですが、このアルゴリズムを作った当時はそれを知らず、量子チューリングマシンの枠組みで考案しました。2 つのモデルの等価性は、その後すぐに Yao が示しています」

Simon のアルゴリズムは、量子的な部分と古典的な部分の両方から構成されます。量子部分はオラクルに効率的にクエリを実行するために使い、古典部分は測定結果を処理して隠された文字列 s を求めるために使います。量子部分の回路を次に示します。

Quantum circuit for Simon's algorithm. Hadamard gates are applied to the first n qubits, then the oracle unitary U_f is applied to all 2n qubits. Then another round of Hadamard gates to the first n qubits. Finally, the qubits are measured.

Daniel Simon: 「この回路で最も印象的なのは、その単純さです。実際、量子計算の能力を示す例として最初に提案された Deutsch-Jozsa 回路よりもさらに単純です。そもそも、この単純なアルゴリズムは対応する問題よりも先に生まれました。私は (おそらく少々無謀にも) 古典計算が量子計算をシミュレートできることを証明しようと試みることから始めました。そして、素直な方法では古典シミュレーションが難しい設計のうち、自分が見つけられた最も単純なものがこの回路だったのです。そこでその性質を探り始め、最終的にはこの回路を基に、シミュレーションされにくいという振る舞いに合わせた問題を構成したのです」

関数 f が n ビットの文字列に作用する場合、上記の回路は 2n 量子ビットに作用します。これは U_f の定義に必要な数です。測定するのは最初の n 量子ビットだけで、残りの量子ビットは U_f を適用した後は使用しません。

数学的な詳細

この量子回路が、古典アルゴリズムよりも関数 f へのクエリ回数を指数関数的に少なく抑えて問題を解ける理由を理解するために、数学的な詳細にもう少し踏み込む必要があります。

Simon の問題を解くには、上記の量子回路を複数回実行します。回路を実行するたびに、最初の n 量子ビットの測定から出力ビット文字列が得られます。これを z と表します。

上記の回路を解析すると、各出力ビット文字列 z が次の条件を満たすことがわかります。

なぜこうなるのか、回路を段階的に解析して確認しましょう。各ステップの数学的な詳細は、付属のノートブックにすべて掲載されています。

1. すべての量子ビットを |0⟩ 状態に初期化します。
2. 最初の n 量子ビットのそれぞれにアダマールゲートを適用し、均等な重ね合わせ状態にします。
3. オラクル U_f を適用します。これにより関数 f の計算結果が後半の n 量子ビットに書き込まれます。
4. 後半の n 量子ビットを測定し、ランダムな結果 f(x) を得ます。f が 1 対 1 の場合、この f の出力は入力 x に対応します。f が 2 対 1 の場合、f の出力は入力 x または y=x+s のいずれかに対応します。ここで x と y は f への 2 つの異なる入力で、同じ出力 f(x)=f(y) を与えます。なお、測定結果自体は使わないためこのステップは厳密には不要ですが、解析をわかりやすくするために含めています。

Daniel Simon: 私は確かにこのステップを実行することを想定していました。この単純化がなければ、アルゴリズムを考え抜くのはずっと難しかったでしょう……

1. 最初の n 量子ビットのそれぞれにアダマールゲートを適用します。f が 1 対 1 の場合、状態 |x⟩ は次のように写ります。

$Applying Hadamard gates to the n qubit state ket x = square root of 1/2^n times sum over x in {0,1}^n of (-1)^(x dot z) ket z$

ここで x·z は、ベクトルとして表した 2 つの文字列の内積 (mod 2) です。

Daniel Simon: アダマールゲートが生み出す位相をこのように特徴づけられると気付くまでには、しばらく時間がかかりました。しかしこれが、アルゴリズムから興味深い情報を引き出す鍵になりました。論文発表前にバークレーで Ethan Bernstein と Umesh Vazirani へこのアルゴリズムを初めて説明したとき、私は誇らしげにこの重要な事実を指摘しました。すると Umesh はすぐにうなずいて「そうだね」と言い、あまりに当たり前のことを若手研究者に指摘された人特有の、うんざりした表情を浮かべたのです。2 人はこの事実にずっと前から気付いていて、単にそれをどう活用するかに思い至っていなかっただけなのは明らかでした。

同様に、f が 2 対 1 の場合、状態 (|x⟩+|y⟩)/√2 は次のように写ります。

$1/square root of 2^(n+1) times sum over x in {0,1}^n of [(-1)^(x dot z) + (-1)^(y dot z)] ket z$

1. 最初の n 量子ビットを測定します。
  f が 1 対 1 の場合、測定によってランダムなビット文字列 z が得られます。この文字列は {0,1}ⁿ から一様に選ばれます。
  f が 2 対 1 の場合、測定によってランダムなビット文字列 z が得られ、これは x·z=y·z mod 2 を満たします。そうでなければ振幅 (−1)^(x·z)+(−1)^(y·z) が打ち消し合ってしまうためです。Simon の問題の条件 (f(x)=f(y)⟹x=y⊕s) を使うと、次が得られます。

Series of equation manipulations showing the condition that s dot z = 0 mod 2

このように、どちらの場合も s·z=0 を満たすランダムなビット文字列 z が得られます。
したがって、上記の量子回路を実行するたびに、秘密の文字列 s と直交するビット文字列 z が 1 つ見つかります。

Daniel Simon: もともと私は、一般的な 1 対 1 の関数と 2 対 1 の関数を区別する方法を探していました。しかし、衝突する 2 つの入力の排他的論理和である s が、一般的な 2 対 1 の関数では任意に変化してしまうため行き詰まりました。最終的に、約束問題の「約束」として定義すれば s を関数全体で一定にできると思いつき、そこから結果が導かれたのです。

古典的な後処理

測定結果 {z₁,…,z_k} から、連立方程式 {z_k·s=0 mod 2} を作れます。

set of equations z_j dot s = 0 mod 2 for j from 1 to k

方程式は k 個、未知数は n 個 (s の各要素) です。量子部分を十分な回数実行して n 個の独立した方程式が得られれば、これらを (例えばガウスの消去法で) 解いて秘密の文字列 s を復元できます。必要となる古典的な後処理はまさにこれで、上記で得た連立方程式を解いて文字列 s を復元します。さらに詳しい内容は、ノートブックの付録を参照してください。

量子的な計算複雑性

上記の量子回路を O(n) 回実行すれば、s を求めるのに使える n 個の線形独立な方程式が得られます。したがって Simon の問題は、O(n) 回のクエリを U_f に行うことで解けます。古典アルゴリズムには Ω(2^n/2) 回のクエリが必要なので、量子アルゴリズムによる指数関数的な高速化が示されます。

Amazon Braket での実装

まず、simons_oracle という、amazon-braket-examples リポジトリに実装されているメソッドをインポートします。このメソッドは、秘密の関数 f に対する特定の量子オラクルを実装したものです。この関数と量子実装の詳細は、ノートブックの付録で説明しています。simons_oracle メソッドは秘密の文字列 s を受け取ります。この文字列は最初に決めておき、同じ文字列 s を復元することが目標になります。

# Implemented in NBI / example notebook utils from simons_utils
import simons_oracle

s = '101011' # Secret string

n = len(s) 
circ = Circuit()
# Apply Hadamard gates to the first n qubits
circ.h(range(n))
# Apply the Oracle for f. See NBI / notebook for implementation
circ.simons_oracle(s)
# Apply Hadamard gates to the first n qubits 
circ.h(range(n))

print(circ)

このコードスニペットは、次の回路を生成します。

T   : |0|     1     | 2 |3|4|5|6|
                                 
q0  : -H-C-----------C---C-C-C-H-
         |           |   | | |   
q1  : -H-|-C---------|-H-|-|-|---
         | |         |   | | |   
q2  : -H-|-|-C-------|-H-|-|-|---
         | | |       |   | | |   
q3  : -H-|-|-|-C-----|-H-|-|-|---
         | | | |     |   | | |   
q4  : -H-|-|-|-|-C---|-H-|-|-|---
         | | | | |   |   | | |   
q5  : -H-|-|-|-|-|-C-|-H-|-|-|---
         | | | | | | |   | | |   
q6  : ---X-|-|-|-|-|-X---|-|-|---
           | | | | |     | | |   
q7  : -----X-|-|-|-|-----|-|-|---
             | | | |     | | |   
q8  : -------X-|-|-|-----X-|-|---
               | | |       | |   
q9  : ---------X-|-|-------|-|---
                 | |       | |   
q10 : -----------X-|-------X-|---
                   |         |   
q11 : -------------X---------X---

T   : |0|     1     | 2 |3|4|5|6|

次に、Amazon Braket のローカルシミュレーターでこの回路を 4n 回実行します。ショット数を 4n にすることで、s を求めるのに使える線形独立なサンプルを、高い確率で少なくとも n 個得られます。

# Sets the device to run the circuit on
device = LocalSimulator()
# Run the circuit 4n times, should be sufficient to get n independent bit strings
task = device.run(circ, shots=4*n)

これで完了です。残りの処理はすべて古典的なものです。前述の「古典的な後処理」セクションで説明したとおり、これらの測定結果が連立一次方程式を定義し、それを解くことで古典的な文字列 s を復元できます。この例をご自身で通して実行したい場合は、Simon のアルゴリズムのノートブックのコードを参照してください。このノートブックは Amazon Braket サンプルリポジトリで公開されています。リポジトリ内のサンプルは Amazon Braket のノートブックにもプリインストールされているため、すぐに使い始められます。

まとめ

Simon のアルゴリズムは、量子情報理論と量子計算の初期の基礎を築いた重要な成果です。今日では、実装が単純で 1 回の講義で扱えることから、量子情報理論を学ぶ学生に、コアカリキュラムの一部としてよく教えられています。しかし、このアルゴリズムには、その単純さからはうかがい知れない重要性があります。Simon のアルゴリズムで発見された概念は、今日の高度な量子アルゴリズムの多くにも見られます。

本ブログは Security Solutions Architect の中島章博が翻訳しました。

Amazon Web Services ブログ