Quantum Lambda Calculus を OCaml で実装した

$$
\newcommand{\bra}[1]{\left\langle #1 \right|}
\newcommand{\ket}[1]{\left|#1 \right\rangle}
\newcommand{\bracket}[2]{\left\langle #1 \middle|#2 \right\rangle}
$$

はじめに

Selinger らの Quantum Lambda Calculus [1][2] を実装したので、それについてかなり雑に書きます。

Quantum Lambda Calculus とは?

量子計算のためのラムダ計算の体系です。
量子計算においては古典の世界では存在しなかった様々な制約があるため、量子ラムダ計算を定式化することには意味があります。

特徴

linear types

先程述べた制約の1つに、量子ビットは No-cloning theorem によって複製ができないというものが存在します。
例えば、量子ビット  q_0 があったとして

$$
\begin{align*}
(\lambda x . (x, x)) ~q_0
\end{align*}
$$

などと書くことは許されません。このようなたかだか1度しか消費できない型を表現するのに線形型が用いられています。

quantum closure

計算を進めるに従って、プログラムが持つデータの量子状態が変化していきますが、それを管理するのが quantum closure です。

quantum closure とは 3-tuple  [Q, L, M] であって、それぞれ以下を指します。

  •  Q:規格化された空間  \bigotimes^n \mathbb{C}^2
  •  L M に含まれる量子ビットの自由変数の列  \ket{x_1 \ldots x_n}
  •  M:ラムダ項

 M の計算が進むにつれて  Q, L も変化していきます。

制御フローは古典的

評価導出を見るとわかるのですが、いわゆる量子的分岐などといったプログラム自体が重ね合わせにあるような体系ではありません。扱っているデータが量子的であるだけです。

量子的フローのプログラムを設計するのはかなり骨が折れる上、意味論も難しいのでしばらくは "古典的フロー+量子的データ" なプログラミングが主流になるのではと思っています。

量子的フローに関してもう少し触れられているラムダ計算の論文としては
https://arxiv.org/pdf/quant-ph/0307150.pdf
あたりが有名かと思います。

ソースコード

github.com

実は評価部分の実装は間違えており、 \bigotimes^n \mathbb{R}^2 になっています。
理由は型システムの実装をやりたかったのでそっちが終わって満足し、位相をいじるゲートを導入していないからですが、単なる怠慢ですね…。

型推論の実装

論文でも触れられているのですが、線形型の上に subtyping が導入されています。
この subtyping がやっかいで、principal type (つまり、その項が取りうる型で最も一般的な型)が存在しないことがあります*1

それでも型推論自体は可能で、自分は以下のようにやっています。

  1. 線形性は無視してとりあえず simply typed な体系で型推論する。
  2. 1. がうまく行けば線形性だけ考える。このとき、各型に線形かどうかの変数を割り当てるがこれは最終的に「linear でなければならない」「どちらでもよい」「non-linear でなければならない」のどれかになる。量子ビット型は linear に確定させ、複製があれば non-linear に確定させる。
  3. 2. と同時に subtyping relation だけかき集めておく
  4. 3 で集めた relation でもって確定できるところを確定させる
  5. 最終的に「どちらでもよい」のままになった変数をすべて linear に置き換える

まとめ

  • Quantum Lambda Calculus とは量子計算用のラムダ計算体系
  • 線形型によって No-cloning theorem に反しないことを保証
  • プログラムと量子状態は quantum closure によって表現
  • 扱うデータは量子的だが制御フロー自体は古典的
  • 型推論システムが備わっている

最後に&思ったこととか

今現在の状況として、様々な量子プログラミング言語が設計され提案されている段階でなかなか熱いものがあります。

例えば量子プログラムを書くのに使われている言語として Qiskit (Python)、Quipper や Q# などが主流だと思いますが、今のところは今回紹介した論文だけで多くをカバーできる程度しか実装されていないのではないでしょうか(Quipper は Haskell の表現力でいろいろできますが…)。特に Qiskit なんかは Python ですから大変です。
そういう意味では最初にこの論文を読む価値はかなり高いと思います。

最後になりましたが、自分で書いておいてかなり雑になってしまい申し訳ないです。

量子プログラミング言語に興味のある人は是非元論文を読んでいただければと思います。

もし詳しい人がいらっしゃったら、僕の周りにやってる人が全然いないので仲間に入れてください。お願いします。

References

[1] P. Selinger and B. Valiron. A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science, pages 527--552, 2006.
[2] P. Selinger and B. Valiron. Quantum lambda calculus. In S. Gay and I. Mackie, editors, Semantic Techniques in Quantum Computation, pages 135--172. Cambridge University Press, 2009.

*1:実は捉え方によっては存在するということもできるのですが、そこらへんの話は "Once upon a type" という論文を読むとよいです

ICPC Asia Yokohama Regional 2019 参加記

はじめに

参加記です。はてなブログが乗っ取られていて書くのが遅れました…。

Day1

朝から横浜に出発します。早速乗るはずだった新幹線を逃しました。

ちなみに偶然 TigerSone*1と同じ新幹線だったのですが、

  • etonagosa が予定の新幹線に乗り遅れそうになる
  • チームメイトが気を利かせて1本あとのに乗ることに
  • etonagesa がギリギリ間に合ったが、あとのに乗ることを知らずに乗車
  • 待ってくれたチームメイトがおいていかれる
  • 代わりに乗り遅れた僕が合流する

というよくわからないことになっていました。

昼はみなとみらい駅の麻婆豆腐専門店で食べました。ここのはかなりおいしい。

f:id:Suikaba:20191127180011j:plain

ラクティスは、割と適当にやりました。基本的に日本のオンサイトでジャッジを疑う必要はないと思います。

夜は京大の他のチームと中華街に繰り出してご飯を食べました。(よく考えなくても京大チーム固まり過ぎでは?

その後 ABC に出ました。終わった後 TL を眺めてたらコドフォ div2 があることを知り手が滑って出てしまいました(あとでチームメイトに怒られました)。

Day2

コンテスト本番ですが、冷えたので書くことがほとんどありません。

  • とりあえず CLion を立ち上げて A を読む
  • なんか雑にやれば間に合う系やろと思って書き始める(実装担当やめろ
  • よく考えたら間に合わないので、ちゃんと考察する
  • 先に B をやってもらう -> B が通る
  • A は max を決め打ちすると貪欲になることがわかったので書く -> AC
    • これ A にしては若干難しくないですか?頭が寝ていたので破滅しました
  • その後 H が kazuma によって通される
  • E, G, I を nakano から聞くと G がたしかにやるだけに見える。I は実装が大変なだけ。
  • G を書き始める
  • kazuma と nakano が E を頑張って詰める
  • G が TLE。雑に文字列とかでやっていたのでそれはそう
  • 文字列パートを早くして投げる -> TLE
  • やべー
  • ダイクストラパートの log がやばい?と思って辺の重みがたかだか 15 とかであることを利用して log を外す -> TLE
  • G が謎すぎるので I を書き始めたりする(落ち着きはどこへ…
  • この間 kazuma が E を書いていたが、終了ちょっと前に本質的な遷移が抜けていることに気がついたらしい :innocent:
  • G について、ここらへんでそもそもノードが多すぎるのでは?ということに気がつく
    • 手元でノードやら辺の初期化パートが最悪ケースで早かったので全く考慮していなかった
  • これがほとんど終了間際で、どうしようもなく終わり…

結果は 3完32位で、3年間で最も低い順位を取った。

でも企業賞がもらえました。やったー(何)。opt さんありがとうございます!!

感想

なんともまあ残念な結果でしたが、院試前からほとんどずっと競プロをしていないことを踏まえると、今の実力通りの結果が出たという感じでしょうか。

C, E, G, I の解法自体はすぐに出ていたので、実装力が地に落ちているということがわかりました。ここらへんはバチャとかで訓練すればましになるかなと思っています。

横浜大会は終わりましたが、まだ Danang にも出場します。京大から3チーム(!?)も出場するらしいです。そっちではもうちょっとまともな順位を取ろうと思います。

*1:ところでTigerSone のチーム名の由来を知っていますか?僕は知っています

動的計画法入門 1

はじめに

大学内の KCPC という競プロ同好会において、初心者向けに動的計画法のスライドを書いたので公開しておきます。

スライド


ちなみに(スライド内容とは関係ないです)

とある先輩に「知見は共有して欲しい」と言われたのが公開の動機だったりします。
今後も発表した場合は公開しようと思います。

ABC 137 F - Polynomial Construction

解法

想定解はかなり頭がいいが、今回は汎用的なラグランジュ補間で解く。
今 \(n\) 次の多項式 \(P(x)\) が \(P(x_i) = y_i ~(i = 0, \ldots, n)\) を満たすとする。このとき、$$P(x) = \sum_{i = 0}^n y_i \frac{\prod_{k \neq i} (x - x_k)}{\prod_{k \neq i} (x_i - x_k)}$$ が成り立つ。$$Q_i = \frac{y_i}{\prod_{k \neq i} (x_i - x_k)}$$ と置いておく。
各 \(i\) に対して \(Q_i\) を求めるのは \(O(n)\) で可能。
\(\prod_{k \neq i} (x - x_k)\) については、予め $$\prod_{k=0}^n (x - x_k) = x^{n+1} + c_nx^n + \ldots + c_1x + c_0$$ を求めておく。
\(c_i\) は、\(\prod_k^m (x - x_k)\) を計算して係数を求めた後、\((x - x_{m + 1})\) を掛けると係数が簡単な漸化式で表せるので、\(O(n^2)\) で求められる。
各 \(i\) について考えるときは \((x - x_i)\) で割る必要があるが、高次のほうから $$ c_n^\prime = c_{n+1} (= 1) \\ c_j^\prime = c_{j+1} + x_ic_{j + 1}^\prime$$ と計算できる。
漸化式の意味は、\(c_j^\prime\) が \(\{x_0, \ldots, x_{i - 1}, x_{i + 1}, \ldots, x_n\}\) から \(n - j\) 個選んでかけ合わせたものの総和、ということを考えると、理解できると思う。
こうして $$\prod_{k \neq i} (x - x_k) = c_n^\prime x^n + \ldots + c_1^\prime x + c_0^\prime$$ が求まったので、これに \(Q_i\) をかけたものを各 \(i\) について足し合わせればOK。

以上より、\(O(n^2)\) でこの問題が解けた。

ソースコード

#include <bits/stdc++.h>

using ll = long long;

ll modpow(ll x, ll n, const ll mod) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        n >>= 1;
    }
    return res;
}
ll inverse(ll x, const ll mod) {
    return modpow(x, mod - 2, mod);
}

std::vector<ll> lagrange_interpolation(std::vector<ll> xs, std::vector<ll> ys, const int m) {
    const int n = xs.size();
    for(int i = 0; i < n; ++i) {
        xs[i] %= m;
        ys[i] %= m;
    }
    std::vector<ll> all_c(n + 1);
    all_c[0] = 1;
    for(int i = 0; i < n; ++i) {
        std::vector<ll> nxt(n + 1);
        for(int j = 0; j < n; ++j) {
            nxt[j + 1] = all_c[j];
        }
        for(int j = 0; j < n; ++j) {
            nxt[j] = (m + nxt[j] - xs[i] * all_c[j] % m) % m;
        }
        all_c = std::move(nxt);
    }

    std::vector<ll> c(n);
    for(int i = 0; i < n; ++i) {
        ll qi = 1;
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            qi = qi * (m + xs[i] - xs[j]) % m;
        }
        qi = inverse(qi, m) * ys[i] % m;

        auto tmp_c = all_c;
        for(int j = n - 1; j >= 0; --j) {
            c[j] = (c[j] + qi * tmp_c[j + 1]) % m;
            tmp_c[j] = (tmp_c[j] + tmp_c[j + 1] * xs[i]) % m;
        }
    }
    return c;
}

using namespace std;

int main() {
    int p; cin >> p;
    vector<ll> xs(p), ys(p);
    for(int i = 0; i < p; ++i) {
        xs[i] = i;
        cin >> ys[i];
    }
    auto res = lagrange_interpolation(xs, ys, p);
    for(int i = 0; i < p; ++i) {
        cout << res[i] << " \n"[i + 1 == p];
    }
}

感想

係数求めるやつは初めて書いたのでちょっと混乱した。

ICPC 2019 国内予選 参加記

はじめに

7/12 に行われた国内予選に SleepingDragon で出ました。
チームメイトはいつもの kazuma, nakano です。

コンテスト内容

  • 問題を読む前に bashrc に alias の設定だけする
  • A を読むとはいなので書く
    • 入力形式を見間違えていてサンプルが合わなかった
    • すぐ気がついたので直して AC (0:05:11)
  • B を kazuma が書いてる間に C を聞く
    • やるだけなので終わったら書くことに
    • B が AC (0:14:05) したので適当に書いて AC (0:24:37)
    • C の FA らしい。謎すぎる。
  • D を kazuma に投げられてしまう
    • nakano から解法を聞く
    • 理解できなかったが自信ありそうだったので理解しないまま書く
    • 理解しないまま書いたので無事破滅する
    • 理解していないのでデバッグができないため nakano に丸投げする (Fを考える
    • nakano が直す箇所を教えてくれて直して AC (1:32:28)
  • E を kazuma が裏で頑張ってくれていたので AC (1:44:48)
  • F をみんなで考える
    • (使う頂点集合、使わない頂点集合) の二部グラフを考えると、色が変わるのはカット辺だけになるから見通しがいいかなと思った
    • 無限に悩む
    • コンテスト終了(は???)

結果

5完で全体6位、大学内3位で予選通過。

感想

さすがに今年は仕事しなさすぎでびっくりした。
D で虚無ったのはまあ反省で、それ以上に F が解けなかったのがかなりつらい。
僕が提示した指針を引きずりすぎた(しみんなも引きずってた)ので戦犯といえば戦犯、仕方ないといえば仕方ない。
院試が終わったら精進再開したいね。
京大から4チーム通過したのは多分初めてっぽいので、めでたい。アジアでは倒す。

AOJ 1387 - String Puzzle

解法

各分割区間と一致する場所が、「より左にある」という制約が重要で、これにちゃんと気がつけば解ける。
これによって

 文字列のある位置の文字と別の位置の文字が、与えられた条件によって等しい
 ⇔ それぞれの位置について、条件をたどって等しいことが言える位置集合のなかで、最も左の位置が等しい

が成り立つ。
したがって、最初に与えられた文字を最も左端に寄せた時にどこに対応するかを計算すれば、各クエリに対して答えるのは簡単(そのクエリの位置を左端に寄せていって、対応する位置の文字を読むだけ)。

左端への寄せ方だが、雑にやると TLE する。
ある区間に一致する区間が、その区間とかなり overlap していると、対応する位置に細かく移していくと O(n) になるからである。
これの解決は簡単で、overlap の場合は一気に飛ばすようにすれば良いだけである。
愚直に一回のステップで左に動く大きさが \(y[i] - h[i]\) なので、これが今見ている区間を追い越すギリギリを求めれば良い。
すなわち、今の位置を \(p\) として、\(p\) が乗っている区間を \(i\) とすれば $$p = p - \left(\left\lfloor\frac{p - y[i]}{y[i] - h[i]}\right\rfloor + 1\right) \times (y[i] - h[i])$$ と更新すると良い。

これで O((a + q)b) で解ける。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, a, b, q; cin >> n >> a >> b >> q;
    vector<int> x(a);
    vector<char> c(a);
    for(int i = 0; i < a; ++i) {
        cin >> x[i] >> c[i];
    }
    vector<int> y(b), h(b);
    for(int i = 0; i < b; ++i) {
        cin >> y[i] >> h[i];
    }

    auto find_left_most_pos = [&] (int p) {
        while(true) {
            const int i = upper_bound(begin(y), end(y), p) - begin(y) - 1;
            if(i < 0 || h[i] == 0) break;
            p -= ((p - y[i]) / (y[i] - h[i]) + 1) * (y[i] - h[i]);
        }
        return p;
    };
    map<int, char> ans;
    for(int i = 0; i < a; ++i) {
        ans[find_left_most_pos(x[i])] = c[i];
    }

    while(q--) {
        int z; cin >> z;
        z = find_left_most_pos(z);
        cout << (ans.count(z) ? ans[z] : '?');
    }
    cout << endl;
}

感想

こんなに簡単なのに本番だと解かれないんだから本当に怖い。
参加してたときも Standings みてかなりビビって手を付けなかった気がする。

ゼッケンドルフの定理と全探索

はじめに

友人と会話してて得られた知見で、共有したいと思います。

ゼッケンドルフの定理

ゼッケンドルフの定理は

任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できる

というものです。
これを使うと、全探索がオーダーレベルで効率良く行えることがあります。

全探索

たとえば、一般的にこういう問題を考えます。

\(N\) 個のデータが順序ついて並んでいて、その部分集合であって、ある性質を満たすものを求める。

もしこの「ある性質」が、連続する2つのデータを取り出すと成り立たないようなものであれば、ゼッケンドルフの定理からオーダーが改善できます。
(成り立たないは直接的ですが、最小化問題などのときに、2連続は考えなくてもよい、みたいな状況もありえそうです。)

\(N\) 個の点を \(N\) ビットで表現するとすると、連続2点をえらばないので、
これはゼッケンドルフ表現と捉えることができます。
このような選び方が自然数と一対一対応するので、例えば \(N \leq 40\) だとすると、大体 \(F_{40} = 10^8\) 程度の部分集合しかないことがわかります。
なので、全探索が間に合う(かもしれない)ということですね。

最後に

結局考えてた問題ではこの性質は使わずに解きました(というか、こんな性質はなかったので使えなかった、悲しい)。