とても強い計算量クラスのコンピュータとその実現方法

この記事は武蔵野アドベントカレンダー19日目の記事です。

物理のステートメントはだいぶ雑ですが、計算のステートメントには一応正確さに気を使って書いているつもりです。何か誤りがあった場合は、@iKodackまでご連絡いただけると幸いです。

(2018/12/22に「宇宙破壊コンピュータはセールスマン巡回問題の最適化問題を解けるか？ 」「時間遡行コンピュータで無限ループすると何が起きるか？」を記事末尾に追加しました。)

(2018/12/28に「宇宙破壊コンピュータは答えが無い場合に全ての宇宙を破壊する？」について記事末尾に追加しました。)

前書き

より速い計算機が欲しい、という欲求は全ソフトウェアエンジニア共通であることが知られています。
最近、業務において500GBのSSDや16GBのメモリを最低水準にするべきではないか、という議論がネットで活発になされていますが、生産性を限界まで高める限界性能の計算機については今までtwitterで十分な議論がなされてきませんでした。

この記事では従来の水準を大幅に超える計算機の仕組みがいかにプログラマの生産性を向上させるかを、ソースコードとともに具体的に解説します。さらに、こうした計算機をどのようにして調達するかについても議論します。

量子コンピュータ

量子コンピュータは名だたる大企業が欲しがっているので、大規模な量子コンピュータを個々人に支給すればソフトウェアエンジニアとして最低限の人権は少なくとも保証されていると言ってよいでしょう。

量子コンピュータは量子コンピュータにしかできない操作を用いて、いくつかの問題を高速に解くことができます。一番有名な例はShorのアルゴリズムという量子アルゴリズムを用いた高速な素因数分解です。

• https://en.wikipedia.org/wiki/Shor%27s_algorithm

Shorのアルゴリズムは位相推定アルゴリズムというアルゴリズムの応用になります。位相推定アルゴリズムは他にも様々な応用があり、例えば線型方程式を条件付きで解いたり、これを用いた種々の量子機械学習アルゴリズムなどが提案されています。Shorの素因数分解以外を含む代表的な量子アルゴリズムをほぼ網羅したQuantum Algorithm Zooという記事があります。

• https://math.nist.gov/quantum/zoo/

その日本訳はここにあります。

• https://www.qmedia.jp/algorithm-zoo/

現状の量子計算機はこうした高級なアルゴリズムを動かすにはまだまだ未熟なため、実際に手を動かして学ぶことが難しく、習得のハードルが高いといえます。量子計算に関しては今年はアドベントカレンダーがたくさんあるので是非興味がある人は読んでみてください。

• https://qiita.com/advent-calendar/2018/quantum
• https://qiita.com/advent-calendar/2018/quantum2

Shorのアルゴリズムなどの実現にはまだまだ時間はかかると思われますが、ソフトウェアエンジニアを数十年程度コールドスリープさせてやることで、目覚めたころにはその時の最先端の計算機では素因数分解できない数を因数分解する量子計算機を提供できるかもしれません。

宇宙破壊コンピュータ

量子力学の解釈の一形態として、所定の操作によりある観測をすると、宇宙は観測Aをした宇宙と観測Bをした宇宙という相互作用のない二つの世界線に分岐するという考え方があります(参考)。かなり電波なステートメントから始まりましたが、まずはこれを固く信じることから始めましょう。（記事全体でこの文が一番専門家に殴られそうで怖い。）

この世界観において、計算機が問題を解く過程で何らかの真性乱数（例えば量子乱数）を振るたび、世界はそれぞれの値を得た世界に分岐します。そして、気にくわない計算結果を得た場合に自身のいる宇宙を破壊することで、自身が生存する世界線においては常に計算が成功していることが保証できます。つまり、自身により観測されうるあらゆる計算結果は常に成功していると言えます。

このことを利用してより生産性の高いソフトウェアを開発しましょう。この計算機で具体的に何ができるのかはコードを見ながら解説します。

概ねこの宇宙破壊コンピュータの破壊的性能はSFなどの文脈で議論されており（筆者調べ）、その応用として最も有名なのは与えられた数列arrayをボゴソートでソートする例です。ボゴソートとは、数列がソートされるまで数列をランダムにシャッフルし続けるというアルゴリズムです。

def sort(array):
    np.random.shuffle(array)
    if not is_sorted(array):
        suicide()
    return array

suicideが実行されるとその宇宙は破壊されます。従ってrandom.shuffleで$n!$に分岐した世界線のうち、開発者が生きている世界線のみが生き残るため、残存した宇宙では必ず数列がソートされています。もしあなたが消滅する宇宙に存在していた場合、潔くソフトウェアの高速化のために職に殉じましょう。

このコンピュータは明らかにSSDやメモリの容量を追加するよりも質的な高速化が得られているように見えます！実際、上記のソートに要する時間は$O(n)$でクイックソートなどより高速ですし、必要なメモリも$O(n)$で、実装もクイックソートより簡潔です。宇宙の破壊は物理的にも可能なので、以降紹介するコンピュータと異なり実現性についても申し分ないと言えます。完璧なコンピュータですね。

ただ、ソートはクイックソートなどでも$O(n\log n)$で出来てしまうため、$\log n$倍の高速化のために実行のたびに$(n!-1)/(n!)$の確率で自身の宇宙が消滅の危機に瀕するのは許容できないという人もいるかもしれません。そんな彼らのために、さらに難しい問題である素因数分解を高速に解くことで説得を試みましょう。

def factoring(N):
    p = np.random.randint(2,N)
    if N%p != 0:
        suicide()
    return p

数々の数学者が挑み解けなかった素因数分解がたった5行で解けてしまいました！これは圧倒的生産性が期待できますね。

しかし、慎重な研究者は「素因数分解は証明されていないだけで実は普通のコンピュータでも簡単に解けるかもしれない」と文句をつけるかもしれません。また、量子コンピュータでも素因数分解は高速に解けるので、宇宙消失のリスクを取るより数十年のコールドスリープを選択する人も多いでしょう。この意見に反論するため、量子コンピュータで解けない可能性が高いと考えられているNP完全な問題の一つである、セールスマン巡回問題を考えます。

セールスマン巡回問題は$N$個の都市がある国で、$1$の都市から出発して$N-1$個の都市を巡回して$1$の都市に戻るルートのうち、総移動距離が$K$以下になる経路があるかを探す問題です。巡回路は$N-1$個の都市をどう回るのかの$(N-1)!$のパターンがあります。私は素因数分解したいと思ったことは日常ではCTFの時ぐらいしかないですが、経路を最小化したいことは割とあるのでこれはあるとより豊かな生活を送れそうですね。また、この問題は量子コンピュータを用いても、最悪ケースの場合には効率的に解くことは難しいと考えている人が多いです。

def travelling_salesman(N, compute_distance_func):
    path = np.random.permutation(N-1)+1
    if compute_distance_func(path) > K:
        suicide()
    return path

あのNP完全がたったの5行です！これほどの性能の計算機ともなると、これはもう導入を言い訳することはできないでしょう。

（2018/12/28 上記の手続きでは因数が無かったり$K$未満の距離のパスがない場合、すべての宇宙が破壊され答えを得ることができないのでは？と思うかもしれません。この周辺を正しく扱う方法については、記事末尾の「宇宙破壊コンピュータは答えが無い場合に全ての宇宙を破壊する？」をご覧ください。）

確率操作コンピュータ

計算機科学の進歩のために宇宙全体を危機にさらすのはコンプライアンスに反する、という向きもあるかもしれません。そこで、計算機ではなくそれを用いるソフトウェアエンジニアのサイキック能力を鍛えることでコンピュータの性能を上げるというアプローチを考えてみましょう。

具体的には新入社員に対してプログラミングではなく超能力開発の研修を行い、「確率的に行われた演算の結果、ある変数が0でない確率でTrueになっている場合、それを100%の確率でTrueだったことにできる」という能力を身につけさせます。研修を経たエンジニアが操ることができるコンピュータを確率操作コンピュータと呼ぶことにしましょう。こうした確率論の操作は主に漫画やライトノベルなどで一般的に行われています。

確率操作コンピュータは素因数分解を解けるでしょうか？

def factoring(N):
    p = np.random.randint(2,N)
    a = (N%p == 0)
    magic(a)
    return p

magic(a)の関数がコールされたタイミングで超能力者は計算機中のメモリに対して能力を発動することでaがTrueである確率を定数時間で100%にします。すると、処理が返った後の世界では3行目で$a={\rm True}$となるためにpはNの非自明な因数になっていなければいけません。つまり、上記のコードは$N$の非自明な因数を計算するコードになっています。

セールスマン巡回問題はどうでしょうか？

def travelling_salesman(N, compute_distance_func):
    path = np.random.permutation(N-1)+1
    a = (compute_distance_func(path) <= K)
    magic(a)
    return path

もう何でも解ける気がしてきました。解けない問題はあるでしょうか？オセロの最強AIを作ってみましょう。オセロに勝つにはこんな感じのプログラムでどうでしょうか？とりあえず自分が先手の場合を考えます。

def sugoi_othello_AI(put_enemy_hand_func):
    while not is_end(state):
        possible_hand_list = enumerate_possible_hand(state)
        if len(possible_hand_list) > 0:
            hand = np.random.choice(possible_hand_list)
            put(state,hand)
        if is_end(state):
            break
        put_enemy_hand_func(state)

    if win(state):
        a = True
    else:
        a = False
    magic(a)

うーん…これは相手がランダムに打ってくれて勝ち筋があるなら勝てますが、もしオセロが後手必勝で相手が最善手を打ち続けると、勝率が0になってしまうために超能力が使えず負けてしまいます。

オセロで先手と後手のどちらが必勝かが既知であればそれを選べばよいですが、残念ながら8*8でオセロが先手後手のどちらが必勝なのかはまだわかっていません。発想を転換して、確率操作コンピュータでオセロが先手必勝か後手必勝か判定しておき、必勝側の手を取れるようじゃんけんの手を確率操作するアプローチを考えましょう。このためには、オセロの必勝が先手か後手かを判定したいです。この判定は可能でしょうか？

実は既知の研究により、確率操作ではオセロは先手必勝か後手必勝かを効率的に判定できないことが証明されています。（正確にいえば、研究者の中で解けないだろうとかなり強く信じられています。）ついでに言うと、確率操作コンピュータと宇宙破壊コンピュータは計算能力が同じであることが示されています。実際、冷静に考えると宇宙破壊コンピュータとは確率操作により自身が生存する宇宙が実現する確率を100%にしていることのただの言い換えになっていることが分かると思います。つまり、超能力を身に着けるのと宇宙を破壊し世界線を選ぶのは物語のテイストとしてはだいぶ違いますが、計算機的には等価であることが分かります。もしあなたが能力モノの漫画作者で確率操作や宇宙破壊の能力者の扱いに困ったら、オセロの先手後手判定問題を解かせて混乱させているうちに倒すというアプローチがおすすめです。

（2018/12/22 宇宙破壊コンピュータでセールスマン巡回問題の最適化問題を解けるか？を追記しました。記事末尾をご覧ください。¹）

時間遡行コンピュータ

時間を巻き戻したいと思ったことはありますか？時間遡行はClosed timelike curve（CTC, 日本訳は時間的閉曲線らしい）という構造を使うことで実際に行うことができます。問題点としては、CTCは物理的には存在してもよい(らしい)がまだ発見されていないということぐらいでしょうか。まぁ重力波も検出されましたし、来年ぐらいには観測されると思えば些細な問題と言えるでしょう。近年では友人が魔法少女になったりCERNをハッキングしたり素数を数えて落ちつくことで比較的お手軽にCTCが口寄せされています。

CTCを得ると、「計算を行った結果、あるビットが1になっているなら、時間をワープしてメモリを引き継いだまま以前のある一つの時点から何度でも計算やりなおす」ことができるようになります（とします）。（より正確に言えば、$n$-bit入出力の論理回路を与えた時、その回路に対して定常状態となる$n$-bitの確率分布を$O(1)$で出力する能力を得ます。能力が定常分布を出力するという要請は時間遡行の結果が親殺しのパラドックスを生まないために必要らしいです。定常分布が複数ある場合、我々にとって最も好ましくないものが不思議な力で選ばれるとしておきます。）

ソフトウェアエンジニアたる我々はこの能力を使って馬券を買うなどの不純なことは当然考えず、高速なソフトウェアを書くことに専念することにします。時間遡行の能力にゆかりのある素因数分解をしてみましょう。

def factoring(N):
    p = 2
    time_leap:
    if N%p != 0:
        p+=1
        goto time_leap
    return p

goto文を実行するとメモリを維持したままtime_leapラベルの位置まで時間を巻き戻します。それを観測するソフトウェアエンジニアにとっては、if文に入る動作は見えないまま、高々$O(N)$巡程度した世界でreturn文に到達したという結果だけが見えます。従って、観測者にとって世界はif文に入ることなくいつの間にか因数が返されます。

セールスマン巡回問題を考えましょう。

def travelling_salesman(N, compute_distance_func):
    path = np.arange(N-1)+1
    time_leap:
    if compute_distance_func(path) > K:
        path = next_permutation(path)
        goto time_leap
    return path

そろそろNP完全な問題が解けるのも大したことないと思えてきました。次にオセロの先手後手を判定させましょう。

n = 8
cell = n*n
initial_set = 4

max_depth = cell - intital_set
state = [0]*max_depth # array of hand-ID
leaves_at_depth = []*max_depth
end = -1

def recursive_plus(depth,node):
    global state, leaves_at_depth, end
    if node != -1:
        leaves_at_depth[depth].append(node)
    state[depth] += 1
    if state[depth]==cell:
        if depth%2==0:
            parent_node = any(leaves_at_depth[depth])
        else:
            parent_node = all(leaves_at_depth[depth])
        leaves_at_depth[depth] = []
        state[depth] = 0
        if depth==0:
            end = parent_node
        else:
            recursive_plus(depth-1, parent_node)

time_leap:
if end == -1:
    # check_result returns any of {1:black_win, 0:black_lose, -1:invalid_history}
    result = check_result(state)
    recursive_plus(max_depth,result)
    goto time_leap

print(result)
# 動かしていないので自信ないけど多分こんな感じだと思う

長ったらしくなってしまいましたが、上記のコードは幅$n=8$のボードでオセロをやったとき、$(n^2)^{n^2} \sim 10^{115}$回の時間遡行により観測者にとっては実行は一瞬で終わります。$10^{115}$回時間遡行するのは凄い疲れそうですが、遡行するのは私ではなくコンピュータなので関係ないですね。

オセロは既存のAIもかなり強いらしいので、ここはAlpha Goのブームに乗っかり囲碁で先手後手判定をすることで、最強のAIであるAlpha Go超えを目指しましょう。しかしオセロで使った手法で囲碁の先手後手を判定しようとすると問題があることに気づきます。それは、囲碁は終わる手数が決まらないため、上記の再帰関数がスタックオーバーフローで死んでしまうという点です。囲碁は細かいルールあんま良く知らないんですが、ルール上は三つのコウを使えばゲームが無限にループをしていてよいらしいので、理論上は手数に限界はありません。また、アゲハマを無視して盤面の場合の数を考えても、盤面の場合の数は安直には$3^{19*19}\sim 10^{172}$です。宇宙の原子の数は$10^{80}$個らしい（Google調べ）ので、全宇宙の原子の2状態に0/1を割り振りスタックメモリにしても、時間遡行の途中でスタックオーバーフローしてしまうのです。悲しいですね。

実は囲碁の問題は時間をワープできても効率的に解けないことが証明されています。ラノベで敵に時間遡行者がいたら囲碁の勝負を挑んで相手の脳のスタックを爆破しましょう。

（2018/12/22 時間遡行コンピュータで無限ループすると何が起きるか？を追記しました。記事末尾をご覧ください。²）

超大容量コンピュータ

唐突に全宇宙の原子の数を提示することで読者を強引に納得させるというのはこの手の記事におけるポピュラーなマウント手法ですが、よく考えてみると原子の数はメモリ容量の限界とは何の関係ないことに気づきます。例えば、「原子の状態」ではなく「原子の位置」をメモリの情報として対応付けることができます。この場合、宇宙の大きさが1m立方で宇宙に一つしか原子が無くても、宇宙を1cm立方の小領域に分けることで、原子のいる区間から$10^6$の状態を表せます。もっと細かく区切れば、もっといっぱい状態を表せます。

現実には宇宙はもうちょっと大きく、原子の数もなかなか多いため、取りうる状態数は莫大になります。とはいえ、原子の位置が１光年離れていると相対論によりレイテンシが1yearと³かなり心もとない値になってしまうため、メモリチップという閉じた空間に全宇宙の原子を閉じ込めるシステムを開発したとしましょう。これでスタックオーバーフローのことを考えなくてもよい富豪プログラミングが可能になるでしょうか？

しかし、そうは事がうまく運びません。メモリにあまりに多くの情報を詰め込んでいくと、最終的には高密度さにメモリが耐えられずメモリがブラックホールを形成してしまいます。ブラックホールの体積当たりの質量やエントロピーは計算によって決まっており、このことから所定の体積に詰め込める情報の量には物理的な限界があります。こうした研究はすでに行われており、この限界はベッケンシュタイン境界と呼ばれます。

一方、希望が持てる事実として、上記の記事によれば、人間の脳の体積が保持できる状態数の限界は$10^{10^{41}}$らしいです。これは囲碁の状態数よりも多いですね。ブラックホールの生成と制御がコンピュータの未来を握っていることが分かりました。

36byteと8*8のオセロ ⁴

他の世界と同じことをしないようにするためには自身が何巡目の世界にいるかを認識する必要があり、仮に36byte整数としてそのIDを送ったとすると$2^{288}\sim 10^{86}$巡目までは自身の状態を認識できます。従って携帯電話にマイコンを取り付ければ$10^{86}$の探索は一瞬で行えますが、これは$10^{115}$には足りないですね。この場合、個々の世界で$10^{115}/10^{86}=10^{29}$程度の探索をすればIDがあふれることを防げますが、$10^{29}$の探索は各枝を1GHz程度つまり毎秒$10^9$個探索しても$10^{12}$年ほどかかるようです。宇宙の寿命は$10^{10}年$程らしいので、100並列ぐらいすれば何とかなるのかもしれません。

ただし、上のアルゴリズムでは探索の状況など自身の巡数以外も持ち帰る必要があり、これは多分64bit程度必要だと思われるため、実際には巡数のIDに使えるビット数はもっと小さいです。一方で、$10^{115}$という場合の数は毎回のターン全部のマスに石が置けうるとして計算されていますが、実際には64個すべてのマスに石が置ける状況はあり得ず、実現可能な盤面のうち最も選択肢が多い状況でも置ける場所の数は64マスよりはかなり少ないと予想されます。少なくとも、既に置いたマスには再度置けないことから、最初に置かれた4個を除いて置ける場所は60マス、59マス...と減っていくことは保証できるので、$60! \sim 10^{81}$程度にはなります。毎回の巡数の世界で$10^{14}$程度の場面の計算は頑張るとすると、必要な繰返しID数は$10^{67} \sim 2^{223}$程度となり、$65$ビットが残ります。このように、枝刈りを頑張れば探索状況の持ち帰り領域のことを加味しても解決可能と思われます。

時間停止コンピュータ

時間の遡行にはCTCが必要でありこれはまだ観測されていませんが、時間の流れを遅くするだけであれば、物質を光速に近い速度でぶん回すことで浦島効果によって可能になります。

これを利用し、計算機が計算している間、自分が光速で動くことで、体感的にはほぼ０秒で任意の計算を行うことが可能です。問題があるとすれば、時間を停止するには無限のエネルギーが必要であり、現代には無限のエネルギーがない、という点でしょうか。加速器の開発がソフトウェア高速化の観点から急務であることがよくわかります。

確率操作量子コンピュータ

速いCPUがあれば速いGPUは不要でしょうか？私はお金があればXeonもTeslaも欲しいです。同様の理由から、リッチなエンジニア環境を構築するには、上記の素晴らしい計算機を複数提供することが必須であると言えるでしょう。

この節では量子コンピュータの結果を確率操作するというコラボレーションを考えます。一見すると確率操作コンピュータは量子コンピュータが解けない問題を解いているので、確率操作コンピュータは量子コンピュータの上位互換のように見えます。

しかし、実は確率操作コンピュータでは効率的に解けないが、確率操作量子コンピュータでは効率的に解けると信じられている問題が知られています。例えばMAJSATがこれに該当する問題です。MAJSATとは、「n-bitを入力として、0か1を出力する、ある規則で作られた論理回路（というかSAT節）」に対し、$2^n$パターンの入力の中で1を吐かせる入力と0を吐かせる入力のどちらが多いかを求める、という問題です。

さらに驚くべきことに、確率操作が可能な状況を考える場面、与えられたコンピュータが完全な量子コンピュータより弱い量子コンピュータでも、確率操作が可能な人が通常のコンピュータを得た場合にはできない操作が可能になることが知られています。すなわち、エンジニアが確率操作可能であるなら、与える実機を量子の意味でチューリング完全な量子コンピュータから、一部の操作しかできない弱い量子コンピュータに変更しても、生産性に差異は無いということです。

例えば、ボソンという量子を使ってパチンコのようなことをする実験がこの「弱い量子コンピュータ」に該当し、これはボソンサンプリングと呼ばれています。この計算機は、「計算の結果、確率的にある可変長整数が得られるとき、その整数がある効率的に評価可能な条件を満たす確率が0でなければ、それを1にできる」という確率操作を拡張した能力を用いると⁵、確率操作量子コンピュータと同じ性能を得ることができます。上記の議論を論拠として、全世界の研究者が量子でパチンコを作りだしそれがトップ誌に掲載されるという恐ろしい時期がありました。このこじらせた発想のもと生まれた高速化の保証には量子超越性というこじらせた名前がついています。

ちなみに、確率操作量子コンピュータは時間遡行コンピュータよりちょっと弱いことが知られています。（ちょっと自信ないですが）確率操作量子コンピュータは固定サイズの（例えば8*8の）盤面のオセロの先手後手必勝を求めることができます。解けないと思われているようです⁶。

確率操作と量子コンピュータ

(予防線を張るとこの段落はあんまり自信がないです。)

上記で説明したボソンサンプリングは、確率操作を身に着けた人が利用した時、「確率的な普通の計算機」では解けなくて、「量子コンピュータ」では解けるような問題が作れるか、という疑問のなかで生まれ、比較的実験がやりやすい例として知られています。また、確率操作コンピュータは量子コンピュータでは解けないと思われるNP完全な問題を解くことができることも学びました。

では、「(古典)確率操作コンピュータでは解けなくて、量子コンピュータでは解ける問題」はあるでしょうか？少し前、問い合わせ回数を比べるという尺度のもとで、この比較で量子コンピュータしか解けないケースが作成できたということがニュースになりました。それは以下のような問題です。

• $2^n$個の$0,1$の値が入った箱が二つある。この箱に$1～2^n$の整数を入れると、入れた整数に対応した位置の$0,1$が帰ってくる。箱Bには箱Aのフーリエ変換(したようなもの)が入っているか、単にノイズが入っている。出来るだけ少ない回数の箱への問い合わせで、二つの箱の関係がフーリエ変換かノイズかを判定せよ。

私は二つの箱の関係がフーリエ変換とノイズのどちらかという判定をしたいと思ったことは人生で今のところありませんが、将来確率操作と量子計算が両方実現されその力を総動員して箱の中身がノイズかフーリエ変換の関係にあるかを判定したい場面が生じたとき、量子コンピュータは非常に有用であることが分かりました。

詳細はここを読んでください。

時間遡行量子コンピュータ

確率操作計算機と量子コンピュータのペアを考えることで、計算機の性能が向上することを前の節で学びました。ならば、量子コンピュータをCTCに叩き込み、時間遡行を繰り返しながら量子計算を行うことでさらに性能を上げられると期待したくなります。

しかし、大変残念なことながら、確率操作と異なり量子計算をタイムリープさせても能力が伸びないことが分かっています。そもそも時間遡行コンピュータは量子計算をシミュレートできることが知られているため、確率操作コンピュータの場合と異なり、量子コンピュータは時間遡行コンピュータの下位互換なのです。あなたがタイムリープできるなら、量子コンピュータはまるで意味がないことが分かります。

このことから、某タイムリープゲームに量子コンピュータが出てこない理由がうかがえます。あの世界ではSERNを中心として量子コンピュータの上位互換である時間遡行計算が可能であることが知られており、量子コンピュータの研究者は全員失業しているからです。

まとめ

色々な計算機を見てきましたがどうでしょうか？今回紹介した計算機は、量子計算を除いてまだ開発に取り掛かられてすらいないという残念な状況です。
しかし、我々の想像の中の計算機がどのような性能を持ち、身近な問題がどのような計算機によってはじめて高速に解けるのかを考えることで、「こういった問題はどの程度難しいのか」、「この問題を解くとは、どのような性能の計算機を作ると宣言することに等しいのか」といった考察が可能になります。実際に、上記のような考察が「量子計算で高速さを実証するために、最も技術的に簡単な課題は何か」などの、現実に需要のある議論にも結びついています。

あとネットで強さランキングを議論するのが好きな人はこういうの好きなんじゃないでしょうか。強さランキングっぽく書くと、今回の記事の内容は以下のようになります。

SSS : 囲碁 (EXPTIME)
SS : 時間遡行, オセロ (PSPACE)
S : 確率操作量子, MAJSAT (PP)
A : 確率操作、宇宙破壊 (PostBPP)
B : セールスマン巡回 (NP)
C : 素因数分解
D : 普通の計算機 (P, BPP)

ここからいくつかのことが言えます。

• SSSはDより真に強い(SSS>D)ことが証明されています。それ以外は全て「同格以上(>=)」であることしかわかっていません。
• RSA暗号の安全性はC>Dという仮定に依存しています。
• B>Dの証明はP≠NP問題と呼ばれていて、解くと賞金がいっぱいもらえて教科書に載ります。
• B=DならA=Dであることが知られています。
• 量子計算は上記のような一次元的な順序関係にはうまく載らないと考えられています。上と下を頑張って抑えると分かっているのはC<=量子<=Sだと思います。
• 「量子計算は計算量的に役に立たない」とは「量子=D」を意味します。これを仮定すると、C=DかつS=Aになります(SにAの量子版があるので)。対偶を取ると、C>DまたはS>Aなら、量子>Dです。
• 「S>Aならば自身の実験系>D」という証明手法がしばしば量子超越性(Quantum computational supremacy)という文脈で使われます。

興味のある計算モデルがあれば是非自分でも考えたり記事や論文を読んでみましょう。記事末尾に参照した文献もつけたので参考にしてください。

メモ

宇宙破壊コンピュータは${\rm BPP_{path}}$、確率操作コンピュータは${\rm PostBPP}$、CTCに関する計算量は${\rm P_{CTC}}$と${\rm BQP_{CTC}}$、確率操作量子コンピュータは${\rm PostBQP}$のつもりで解説しています。全体的に以下の理解で解説しています。

• ${\rm PostBPP}$は${\rm PH}$の三階に含まれ、${\rm NP}$を含む。
• ${\rm PostBPP}$と${\rm BPP_{path}}$は等しい。
• ${\rm P_{CTC}}$は${\rm PSPACE}$と等しい。${\rm PSPACE}$は${\rm PH}$を含む。
• ${\rm PostBQP}$は${\rm PP}$と等しい。${\rm PP}$は${\rm PSPACE}$に含まれる。${\rm P}^{\rm PP}$は${\rm PH}$を含む⁷。
• ${\rm BQP_{CTC}}$は${\rm PSPACE}$と等しい。したがって、${\rm P_{CTC}}$と差は無い。
• FACTORINGは${\rm BQP}$と${\rm NP}$の両方に含まれるが、${\rm BQP}$完全ではなく、${\rm NP}$完全でもないと信じられている。
• TSPは${\rm NP}$完全であり、${\rm BQP}$に含まれないと信じられている。
• OTHELLOは${\rm PSPACE}$完全である。定数サイズ$n$のOTHELLOは${\rm PH}$の$O(n^2)$階に含まれる。
• GOは${\rm EXPTIME}$完全である。${\rm EXPTIME}$は${\rm PSPACE}$を含み、${\rm P}$を真に含む。
• BOSONSAMPLINGは${\rm BQP}$であるが${\rm BQP}$完全ではない。
• PostBOSONSAMPLINGは${\rm PostBQP}$に等しい。
• 問い合わせ計算量で${\rm PH}$と${\rm BQP}$を分離するオラクルが存在する。

文献

話のかなりの部分はQuantum Computing since Democritusにて概ね似たノリの解説がなされており、それを参考にしています。この本は(色々な意味で)基礎的な部分から計算機の話を追うので、こうした話が好きな人はぜひ読んでみてください。講義録なので著者がネットで無料公開しています。

計算量クラスの確認のためにComplexity Zooを多用しました。

その他の文献としては以下の教科書や記事、論文を参考にしました。

• 計算量全般
  • Computational Complexity : A Modern Approach
• 量子計算全般
  • Quantum Computation and Quantum Information
• オセロと囲碁
  • The Othello game on an n × n board is PSPACE-complete
  • Robson's Proof that GO is EXP-time Hard
• メモリとブラックホール
  • I LIKE BIG BITS : Myth of RAM
• 多項式階層
  • Shtetl-Optimized: The relativized BQP vs. PH problem
  • [Cornell University lecture note: Polynomial Hierarchy] (http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture5.pdf)
  • Computational Complexity: BQP not in the Polynomial-Time Hierarchy in Relativized Worlds

最初にも書きましたが、何か変なことを言っていたら連絡をくれると幸いです。
読んでくれてありがとうございました。

追記

質問のあった内容の特に二点について、解説します。
後者は私の本文の書き方が悪かったです。すいません。

宇宙破壊コンピュータはセールスマン巡回問題の最適化問題を解けるか？

本文では総経路が$K$より小さいかどうかの判定を行い、小さいものがある場合は経路を出力するというプログラムを書きました。しかし、通常の場合だと地図だけが与えられて最短路を求めよというケースが多いと思います。

この問題は、「生き残った世界が複数ある場合、実現される世界をその中から一様ランダムに選び確定させる」という操作をしてよいなら解けると思います。（理論的に言えば、PostBPPをオラクルとして利用して良いなら解けると思います。そうでない場合はちょっと考えましたが思いつきませんでした。）具体的には以下のようにして解きます。

都市の数を$n$個、出てくる距離は高々$n$ビット整数で表せる値だとします。$N=2^n$と定義しておきます。未知の知りたい最適値を$K^{*}$とします。まず、適当な近似アルゴリズムで少なくともこの値以下だ、という$K_{\rm max}$を計算します($K_{\rm max}<N$としておきます)。$K_{\rm min}=0$とします。すると、$K^{*}$は$K_{\rm min}$と$K_{\rm max}$の間にあります。このとき、以下のようなサブルーチンを考えます。

=====サブルーチン=====

1. $K_{\rm mid} = (K_{\rm max} + K_{\rm min})/2$を計算します。
2. $n+1$ビットの乱数を発生させます。乱数のうち、どれか一つでも$1$だったら3.を、そうでなければ4.を実行します。
3. $K_{\rm mid}$を引数にしてtravelling_salesman関数を呼び出し、$K_{\rm max} := K_{\rm mid}$ と代入します。5.に行きます。
4. $K_{\rm min} := K_{\rm mid}$と代入し、5.に行きます。
5. 生き残りの宇宙から一様ランダムに宇宙を選び、確定させます。

こうすると選ばれる宇宙は以下の性質を満たします。

• $K^{*} \leq K_{\rm mid}$だった場合
  乱数を発生させたお陰で、$K_{\rm mid}$を実行して$K_{\rm mid}$以下の総距離の経路を得た宇宙は、そうでない宇宙の少なくとも$N$倍あります。従って、「$K^{*}$は$K_{\rm mid}$以下だと判明した宇宙」が少なくとも $(1 - \frac{1}{N})$ の確率で選択されます。

• $K^{*} > K_{\rm mid}$だった場合
  travelling_salesmanを実行した宇宙は全て破壊されるので、残った宇宙は一つです。この宇宙が確率$1$で確定されます。

上記の操作のおかげで、サブルーチンの終わった後には、$K^{*}$は少なくとも$(1 - \frac{1}{N})$の確率で新たな$K_{\rm min}$と$K_{\rm max}$の間にあります。また、$K_{\rm max}-K_{\rm min}$は半分に縮まりました。$K_{\rm max}-K_{\rm min}$は高々$N=2^n$なので、このルーチンを$n$回繰り返し、すべてにおいて$(1-\frac{1}{N})$の場合が成立すれば区間は$1$となり正解が分かります。すべてに成功する確率は$(1-\frac{1}{N})^n$で、この値はある程度大きい$n$ではほぼ$1$です。不安であれば、乱数の数を増やすか、上記のすべてを何度も実行し、最小値を取ります。

より良い方法が分かったら是非教えてください。

時間遡行コンピュータで無限ループすると何が起きるか？

例えば時間遡行コンピュータにおいて

def func(N):
    p = 0
    time_leap:
    while True:
        goto time_leap
    return p

という関数を実行すると、私が定義したコンピュータでは一見すると宇宙は停止し、未来が未定義になってしまうように見えます。しかし、元々のCTCを用いた計算の定義は、こうした状況でも機能するように精巧に作られています。具体的には、上記の関数は$0$を返します。私はCTCを用いた計算の定義と等価な言い換えをしたつもりでしたが、言い換えが今考えるとあまりよくありませんでした。本来の計算能力より強くなっていることは無いとは思いますが、語弊がある言い方で申し訳ないです。この節では、より正確なCTCを用いた計算について書きます⁸。

CTCを得るとは、以下のような関数CTCが使えるようになることと等しいです。CTCは「$n$bitの二つの整数を引数とし、$n$bit整数二つを返す関数$f$」を引数とし、$n$bitの整数を出力する関数です⁹。関数$f$としては例えば、

def f(v,w):
    return v+w, v-w

などがその例になります。関数CTCは、まず与えられた関数$f$に対して以下に示すCausal Consistencyと呼ばれる条件を満たす、$n$ビット整数についての確率分布$\pi$を適当に一つ計算します。

以下のような$\pi$と$f$に関するmap1, map2という関数を考えます。pi.sampleとは$\pi$の確率分布から整数をサンプリングする操作を表します。

def map1(pi, f):
    v = pi.sampling()
    v,w = f(v,0)
    return v

def map2(pi,f):
    v = pi.sampling()
    return v

このとき、任意の$n$ビット整数$s$について、map1(pi,f)の結果として整数$s$を得る確率と、map2(pi,f)の結果として整数$s$を得る確率が等しい時、$\pi$はCausal Consistentであるといいます。Causal Consistentな分布が複数あるとき、Causal Consistentな分布のうち一つがランダムに選ばれます。与えられた関数$f$に対し、Causal Consistentなpiを得る関数をget_random_causal_consistentとします。

言い換えると、$\pi$がCausal Consistentであるとは「整数0と一緒に関数$f$を実行し、出力から追加したビットを外す（周辺化する）」という遷移行列$P$に対し、$\pi = P\pi$となるような定常分布になっているという意味です。一般に、定常分布は複数ありえますが、その場合は何らかの定常分布がランダムに得られるとしておきます。

このとき、関数CTCとは、以下のような操作を実行する関数です¹⁰。

def CTC(f):
    pi = get_random_causal_consistent(f)
    v = pi.sampling()
    v,w = f(v,0)
    return w

従って、例えば素因数分解を行う関数は正確には以下のようになります。

def factoring(N):
    def f(v,w):
        if v<=1 or v>=N:
            return ((v+1)%N,0)
        elif N%v != 0:
            return ((v+1)%N,0)
        else:
            return (v,v)
    answer = CTC(f)
    return answer

上記の関数$f$に対するCausal Consistentな分布がどのようなものかは、$N$が非自明な約数を持つかどうかによって変わります。

• $N$に非自明な約数がある場合、非自明な約数$p$について$(p,p)$だけが確率を持つ分布がCausal Consistent。
• $N$が素数である場合、$(0,0),(1,0),(2,0),(3,0)...(N-1,0)$の一様分布がCausal Consistent。

従って、どのような$N$を入れても、$N$が合成数なら非自明な約数$p$のどれかが、素数ならば$0$が出力されます。NP問題に対する基本的な戦略としては以下のようになります。

• $v$が解でないなら、$((v+1)%v_{\rm max} ,0)$を返します。
• $v$が解なら、$(v,v)$を返します。

このとき、$0...v_{\rm max}$の間に解があるなら、$(v,v)$は$(v,v)$にしか遷移せず、他はいつか$(v,v)$に到達するため、必ず解がCTCから出力されます。そうした解が無いなら、$w$の場所に$0$以外が来ることは無いので、$w=0$の何らかの分布が定常分布となり、$0$が出力されます。従って、$0$以外が出力されたらそれが解で、$0$が出力された場合は解が無いか$0$が答えかです。$0$が答えかどうかは容易にチェックできます。

同様にして、セールスマン巡回問題は以下のようになります。

def travelling_salesman(N, compute_distance_func):
    def f(v,w):
        permutation_id = v
        if permutation_id >= max_permutation:
            return (0,0)
        path = get_path_from_permutation_id(permutation_id)
        if compute_distance_func(path) > K:
            return ((v+1)%max_permutation,0)
        else:
            return (v,v)
    answer = CTC(f)
    path = get_path_from_permutation_id(answer)
    return path

内容は同様で、定常になりうる解は複数ありえますが、そこからサンプリングするどのようなpath(に対応するID)も、経路は$K$以下になっています。

オセロの判定は少しテクニカルになります。一見すると、オセロが先手必勝か後手必勝かを探索している状態(コードでいうとleaves_at_depthとstateのペア)を$v$として同じことをやればよいように見えますが、NP問題と違い、オセロでは$v$が「探索が終わり、先手必勝だった」を表す状態だったとして、それが探索の結果得られたのか、ランダムにいきなり与えられたのか区別することができません。後手が必勝だったにもかかわらず、ランダムにそのような$v$を与えられると、CTCは誤った結果を$w$に出力してしまいます。

そこで、戦略を以下のように変えます。探索の状況が初期化された$v$を$v_0$とします。

• $v$が「不正な状態」ならば$(v_0,0)$を返します。
• $v$が「探索中」ならば、次の探索状態を$v'$として、$(v',w)$を返します。
• $v$が「探索終わり、先手必勝」ならば、$(v_0,0)$を返します。
• $v$が「探索終わり、後手必勝」ならば、$(v_0,1)$を返します。

ここで重要なのは、探索が終わったら結果を格納するとともに探索の状態を初期状態に戻すことです。こうすることで、仮に後手必勝であるにもかかわらず「探索終わり、先手必勝」がランダムに与えられたとしても、その遷移先でもう一度探索が始まり、最終的に「探索終わり、後手必勝」に到達します。従って、Causal Consistentな定常分布は絶対に「探索終わり、先手必勝」を含まないことが分かります。一般のケースをコードにすると以下のような感じです。

def generic_pspace_problem():
    def f(v,w):
        search_state = v
        if is_accepted(search_state):
            return (initial_state, 0)
        elif is_rejected(search_state):
            return (initial_state, 1)
        else:
            next_search_state = get_next_search_state(search_state)
            return (next_search_state, w)
    result = CTC(f)
    return result

この戦略は、「初期状態(ループ開始時の探索状態に相当)を指定し、探索の状態をインクリメントしていき(ラベル間の計算に対応)、探索が終了したらループから抜け出してその状態を出力する($w$に結果を書き込む)」という本文の戦略を内包しています。したがって、本文の機能はサブセットになります（多分…）。本文の機能はPSPACE完全であるオセロを解いているので、計算力としては等価だと考えました（違ったらすいません）。

より正確かつちゃんとしたCTCに関する証明を読みたい場合については元論文を参照してください。

宇宙破壊コンピュータは答えが無い場合に全ての宇宙を破壊する？

本文中の宇宙破壊コンピュータのアルゴリズムは、問題の条件を満たす解答（因数や、長さK以下の経路）が無い場合に、必ず宇宙を破壊してしまいます。これは、NP完全な問題を解いたことにはなりません。宇宙破壊コンピュータが解答が無い場合を含めNP完全な問題を解くためには、より詳細な定義とアルゴリズムの修正が必要になります。この章では、より詳細な定義と解説をします。

まず、今回紹介した宇宙破壊計算機の計算量は、同じく乱数を用いる確率的な計算機で解ける計算量クラス(BPP)の拡張になっています。真正乱数は相対論と量子力学を用いれば現実に生成できるため、BPPは現実にも運用可能な計算量クラスです。

確率的な計算量で解ける判定問題とは、以下のようにして解くことができる効率的なアルゴリズムが存在する問題だと言い換えることができます。

1. 問題のサイズ$n$に対して${\rm poly}(n)$bitの乱数を振る。結果として、$2^{{\rm poly}(n)}$の分岐が生じる。
2. 上記の乱数をもとに、決定論的な計算を行う。
3. 計算の結果、全ての分岐はYesかNoかの判定を提出する。正しい判定を提出した分岐が、全分岐($2^{{\rm poly}(n)}$)のうち2/3以上の割合を占める。

BPPの本来の定義は「乱数を振りながら計算をし、2/3以上の確率で正解すること」となっていますが、「先に振りうる全部の乱数を振ってしまい、その乱数のうち2/3以上のパターンで正解する」と言い換えられ、このように言い換えたものが上記になります。

宇宙破壊計算機は上記の確率的な計算機の拡張になっています。宇宙破壊計算機において、「与えられた判定問題が解けた」ことの定義とは以下のような状態を指します。

1. 問題のサイズ$n$に対して${\rm poly}(n)$bitの乱数を振る。結果として、$2^{{\rm poly}(n)}$の分岐が生じる。
2. 上記の乱数をもとに、決定論的な計算を行う。
3. 計算の結果、全ての分岐はYesかNoかUnknownの判定を提出する。
4. YesかNoかの判定を提出している分岐が一つ以上存在する。かつ、正しい判定を提出している分岐が、YesかNoの判定を提出している分岐のうち2/3以上を占める。

上記の計算では、Unknownの回答を提出することが「気にくわない結果なので宇宙を破壊し、最終的な分岐の分母から除外する」という行為に相当します。「全部の宇宙を破壊する」行為は4.の最初の条件に反するため、解けたとは呼びません。

上記のような定義では、以下の手続きで任意のNP完全問題を解くことができます。
まず、NP完全問題は前提として以下の特徴を持ちます。

• 真の答えがYesである場合、多項式長の文字列で表される「答えがYesである証拠」が1つ以上存在する。さらに、与えられた文字列が「答えがYesである証拠」かどうかを多項式時間で検証するアルゴリズムがある。
• 真の答えがNoである場合、上記の検証アルゴリズムを通過する偽の証拠は存在しないことが保障されている。

証拠の長さを$W$とし、かつ$W\geq1$としておきます。すると、証拠の文字列の場合の数は$2^W$になります。
この前提のもと、以下を行います。

1. $3W$ビットの乱数を振る。
2. 最初の$W$ビットを証拠の文字列と思うことにする。この証拠が「答えがYesである証拠」になっているかを多項式時間で検証する。検証の結果がTrueなら3.を、Falseなら4.を実行する。
3. Yesを提出する。
4. 残りの$2W$ビットがすべて0だったら、Noを提出する。それ以外の場合、Unknownを提出する。

上記の手続きを行うと、

• 判定の真の答えがYesの場合：

全部で$2^{3W}$の分岐が生じます。
このうち、$2^{2W}$の分岐は運よくYesの証拠を得て、Yesを提出します。
残りの$2^{3W}-2^{2W}$の分岐は正しくない証拠を得てしまいますが、殆どの分岐はUnknownを提出するため、Noを提出する分岐は$2^W - 1$です。
$W\geq1$より、$2^{2W}/(2^{2W}+2^{W}-1) > 2/3$なので、Yes/Noを提出した分岐のうち、2/3以上の分岐が正しい判定を提出しています。

• 判定の真の答えがNoの場合：

全部で$2^{3W}$の分岐が生じます。
最初の$W$ビットがどのような文字列だとしても、検証の結果がTrueになることはありません。従って、Yesを提出する分岐の数は$0$です。
$2^{W}$の分岐がNoを解答として提出します。Yes/Noを提出した分岐のうち、すべての分岐が正しい判定を提出しています。

従って、答えがYesの場合、Noの場合、どちらでも「与えられたNP完全な判定問題が解けた」と結論付けることができます。
言い換えれば、「宇宙を破壊する能力」とは、「乱数を振った後に、気にくわない乱数だった結果を条件に含めないよう、条件付けにして分母から排除する能力」と言えます。もし破壊を許さず分母にUnknownの場合を含めてしまうと(つまり現実に実現されているBPPだと)、上記の手続きでは真の答えがYesの場合にYesを提出している分岐の割合は$2^{-W}$となり、勘でYesの証拠を当たる非常に小さな確率になります。

1. 2018/12/22に追加 ↩

2. 2018/12/22に追加 ↩

3. 2018/12/28に修正 ↩

4. 2018/12/20に追加しました。
   上の節で無限のメモリを保持することが難しいことを学びましたが、過去に持ち出せるメモリが定数に限られていたらどうでしょうか？ここでは過去に情報を送れる携帯電話があったとして、過去に送信できる容量が仮に「全角18文字、半角36文字」、つまり288ビット(多分)だったとしましょう。この携帯電話にマイコンを付けることで、オセロの先手後手必勝が現実的な時間で求まるかを考えましょう。 ↩

5. 2018/12/21 指摘を受け修正：1ビットしか確率操作できない場合、BosonSamplingは確率操作量子コンピュータ(PostBQP)になりません。このためには複数のビットを確率操作(Post-selection)する必要があるため、本文の「bool変数(1bit)を操作」する能力では不十分です。このため、能力を拡張して「任意の数の出力ビットが、多項式時間で評価される条件を満たす確率を1二できる」と能力を拡張する必要があります。ちなみに、同じ弱い量子計算機でも、「殆どがノイジーな量子計算機」であるDQC1は1ビットののみの確率操作でも確率操作量子コンピュータと同じになります。 ↩

6. 2018/12/21に指摘を受け修正。確率操作量子コンピュータは${\rm PP}$と呼ばれる計算量に対応します。定数サイズのオセロは${\rm PH}$に含まれると思われますが、${\rm PH}$を含むのは${\rm P^{PP}}$であり、${\rm PP}$は${\rm PH}$を含みません。従って、確率操作量子コンピュータが定数サイズのオセロを解けるかは未解決問題であり、恐らく解けないだろうと信じられているようです。
   しかし、オセロの盤面が問題のサイズとしてどんどん大きくなっていくような問題の場合、先手後手の問題は時間遡行コンピュータでしか効率的に解くことができなくなります。 ↩

7. 2018/12/21に指摘を受け修正　元は${\rm PP}$が${\rm PH}$を含むと誤って書いていましたが、戸田の定理は表記の不等式が正しいです。 ↩

8. 厳密に書くとより長くなるので、気になる人は記事末尾に書いた元論文を読んで下さい。 ↩

9. ここでは$n$ビットと書きますが、$n$の多項式程度の大きさの領域は許されます。この関数は確率的な関数でも性能は一緒ですが、簡単のために乱数を使わない関数とします。また、決定問題では$m$ビットの1bit目のみが出力されるのですが、関数問題を扱うためにここでは$m$ビットが全て出るとしておきます。 ↩

10. 2019/02/15に指摘を受け修正 ↩