はまやんはまやんはまやん

hamayanhamayan's blog

2020年のうちに量子プログラミング入門しといた

量子プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

2020年のうちに量子プログラミング入門しといた

年末ちょっとだけ時間ができたので、やろうやろうと思っていた量子プログラミングを入門しておいたので、その記録。
今年のAdvent Calenderの記事を雑に仕上げてしまったので、その埋め合わせになればと思います（この記事も雑ですが）。
目標はCodeforcesでやってるQ#コンテストのWarmupを解いて理解すること。
以下に色々書いているけど、だいぶ適当な記述になってる。気が向いたら直す。

読書記録

とりあえず、何も分からなかったので、本をかき集めて読んだ。
以下、読んだ順と個人的感想。

[1] 絵で見てわかる量子コンピュータの仕組み

最初に読んだ本だったが、とてもよかった。出てくるキーワードも丁寧に解説されており、予備知識なしで読めた。

[2] よくわかる最新 量子コンピュータの基本と仕組み

プロが書いた本じゃないので、記載内容に怪しい部分も散見される。
（間違っているというより、筆者の主観っぽいのが理由もなく書いてあるだけとか、そういったこと）。
だが、とても広い範囲について紹介されておりキーワードが沢山出てくるので、辞書的な使い方ができる可能性がある。
色々なヒントや関連情報が得られるので、2冊目以降にいい。ここで得られた情報をもとに自分で調べること。
一本目に読むとキーワードだけ得られる（キーワードの意味や量子コンピュータの意味はわからない）。にしても、地力がある人にはお勧めしない。

[3] 量子コンピュータがわかる本

歴史的な観点と、数学的な観点を網羅している。
数学についてもちゃんと説明しているので高校数学レベルがあれば読める（読めるだけで理解できるかというと…）
理論を数式を見て追っていきたいけど、ガチなやつはきついなら最適な本。

[4] 驚異の量子コンピュータ

量子コンピュータの歴史、仕組み（概念的なレベル）、実情、これからについて書かれた本。
全体を通してとても読みやすく、説明も明快であるため、かなりわかりやすい。
最初に[1]を読んだが、[4]を読んでから[1]でも良かったかもしれない。
賢い人は文才にも富むのだろうか。

[5] シュレーディンガーの猫、量子コンピュータになる。

計算機の始まりから量子コンピュータの最新（といっても2013年の本だが）までを網羅した本。
情報の詰まり方がすごく、歴史をなぞるような本。
ただ、書いてある内容が結構難しく、かつ、計算機の始まりから量子コンピュータの最新までをなぞりながら、関連情報をこれまでかと詰め込んであるので、
簡潔に理解しようとする本ではないことに注意。

　
　
とりあえずここまで読んでCodeforcesのQ#コンテストWarmupをやった。
これだけ詰め込んでからやったら、割とすんなり入れた。
あと、読んでないけど、絶対読んだ方がよさそうな雰囲気を出している本
[6] 量子コンピューティング 基本アルゴリズムから量子機械学習まで

量子プログラミングのために

量子プログラミングをするにあたって特に理解が必要なことについて以下に箇条書きにしておく。
解説してるわけじゃないので、キーワードだけ、雰囲気だけ感じ取って。
あと、ぶっつけWarmup本番でも大丈夫そう。

量子コンピュータの種類

  • 実はいくつかあって、ちょっと違うから注意
  • 量子ゲート
    • Q#が対象としてるのはコレ。こっち側しかちゃんと勉強してない
  • 量子アニーリング

量子ビット、量子ゲート

  • ブロッホ球、ブラケット記法、量子ゲートとユニタリ計算
    • この辺が特に大事。Q#でも量子ゲートを通していくが、この辺が分かってないとイメージが全然わかない
  • 重ね合わせ状態と測定、量子もつれ
    • コード上に全く表れてこないので、別途ちゃんと勉強しないと全然分からないと思う
    • 雰囲気でしか理解してないが、最重要知識の1つ
  • 可逆計算
    • 結構大事な考え方だと思う

Q#

  • QuantumKatasという公式の学習教材があるので、これをちゃんとやるといいと思う（俺はやってない）
  • あまりなじみのない記法
    • UnitはVoidのこと
    • Adj+Ctlはoperationに対して属性を付けているイメージ
      • Adj: 逆演算（逆演算という言葉の正確性は自信がない）が可能である
      • Ctl: 制御ビットによる制御が可能
    • 内部状態のダンプをいくつかの方法で行える
      • DumpMachine, DumpRegisterで量子ビットの内容をダンプできる
      • ここのDumpUnitaryToFilesを使えば、operationを行列で表現したときの係数が得られる

Microsoft Q# Coding Contest

Codeforcesで開催されている。Warmupと本戦とがあるが、Warmupだけやった。
2020WarmupのDは、すこし面倒でやってない…
以下にACコードがあります。
qsharp-contests/QSharpContests at master · hamayanhamayan/qsharp-contests

Microsoft Q# Coding Contest - Summer 2018 - Warmup - Codeforces

  • A: 重ね合わせ状態として|+>と|->を作成する問題
    • |+>は|0>にHゲートを通せばいい
    • |->は|1>にHゲートを通せばいい。|1>は|0>にXゲートを通せば作れる
  • B: 4つのベル状態を作成する問題
    • [parity] 2005.02 keyword
      • 量子もつれ状態にあるビットは独立に考えるよりもまとめて考えてしまう方が自然であるため、量子もつれ状態になっているビットを一様にまとめたベル状態が考案されている
    • |Φ+> = 00と11の重ね合わせ状態 (|00> + |11>)/sqrt(2)
    • 以下3状態は、|->を作ったり、Xゲートで適当にひっくり返せば作れる
      • |Φ-> = 00と11の重ね合わせ状態 (|00> - |11>)/sqrt(2)
      • |ψ+> = 01と10の重ね合わせ状態 (|00> + |11>)/sqrt(2)
      • |ψ-> = 01と10の重ね合わせ状態 (|01> - |10>)/sqrt(2)
  • C: NビットのGHZ(:Greenberget-Horne-Zeilinger)状態を作成する
    • N=1のときは|+>、N=2のときは|Φ+>と同等になる
    • |Φ+>の作り方が分かっていればそれほど難しくない。どちらかというとQ#でのループの書き方の方が問題
  • D: |+>か|->が与えられるので、どっちが与えられたかを判断せよ
    • 測定してしまうと確率的に状況が確定してしまうので良くない
    • 測定前に適切に量子ゲートを通して、測定した結果を一意にすることで判断していく
    • 作り方を考えてみると、Hゲートを通せば|0>か|1>かになるので、測定してやればどちらであるかが分かる
  • E: ベル状態が与えられるので、どのベル状態であるかを判断せよ
    • 問題BでHゲートとCNOTゲートを使ったので、とりあえずをそれを逆順で噛ませてみる。
    • それで内部状態を見てみると、1つの状況に100%になっている
    • もうこれで測定した結果を出力すれば良い
  • F: ビット列の状態が2通り与えられるので、現在与えられてる量子ビットがどっちの状態であるかを答えよ
    • 量子ビットを測定して、その結果がどっちであるかを判定すればいい
  • G: k番目の量子ビットを抜き出す量子オラクルを作成せよ
    • yにx[k]を代入する関数f(x, y, k)を作る問題
      • 一般的なプログラミングでは代入するだけ問題のように見えるが、量子状態を単純にコピーすることはできない
      • 量子複製不可能定理
        • ここで持ってくるのが適切かは分かってない。
    • Quantum Oracle
      • Introduction to Quantum Oracles - Codeforces
      • 完全に理解したレベルまでにも達してないがとりあえずまとめる。上の英語を下に日本語でまとめる。あと、用語はがばがばだと思う。以下の文章は1%くらいの信用性しかない。
        • 入力と出力は量子計算では一定である必要があるが、関数としては入力N個で出力M個のようにN!=Mである場合もある
        • 量子（ゲート）計算であるユリタリ行列Oを持ってきたときに、f(x)=f(y)であったときにO|x>=O|y>であるが、倒置を使って消そうとするとOTO|x>!=OTO|y>となる。よってOのエルミート共役は無いが、オラクル内部は量子計算であるから可逆であるはずである。
        • これを解決するためM個の量子ビットを用意する
        • 後半は全然わかんねぇけど、とりあえず、Quantum Oracle的には、「入力変数+出力変数」を入力として、同様に出力させるような雰囲気と覚えた。
        • まあ、余剰ビットを用意することで上手い事やるんでしょう。どっかの本でもそんなもの見た気がする
    • 問題の意味 Implement a quantum oracle on N qubits witch implements a function f(x) = x_k
      • yにx[k]を代入せよという訳でもないのか、指定された条件の関数に対するquantum oracleと解釈すればいいのか？
        • 結果を満たすだけなら、SWAPでもしてやればいいと思ったが、これはWA
      • O(|x>×|y>) = |x>×|y xor f(x)>
      • これに照らし合わせると、×はベクトルをくっつけるイメージなので、後はxor部分
        • y xor f(x)ということは、y xor x[k]ということ。量子ゲートでxorはCNOTを使えばいいので、それを使えばいい
        • パッと見て量子複製不可能定理に反している気もするが、量子もつれが発生しているので大丈夫？（よくわからんね）
    • これのテストを書いてて思ったけど、Qubit型の比較関数がよくわからない
      • 量子状態の比較というのがそもそもナンセンスなのかもしれないけど、シミュレータ上で比較できそうな感じもする
      • using (q = Qubit()) { using (q2 = Qubit()) { q == q2 } }がfalseになる
      • q=qはtrueになる
      • 何か方法はありそうな気がするが…
      • CodeforcesのWA時のコンソール出力にはMicrosoft.Quantum.Intrinsic.Assertとあるので、QSharp上のUnitTestっぽい
  • H: 量子ビット列の1である個数 mod 2を答える量子オラクルを作成せよ
    • 単純にif文で測定して1ならX(y)とするループで答えたら誤答になった
    • なぜだろうと悩んでいたら可逆性を思い出す
      • if文を使ったら可逆的にするのが難しくなりそう
      • そもそも測定したら、可逆にはならんだろう
    • という訳で、測定とかif文とか使わない方法を考えてみると、パリティはXORすれば求まることを思い出す
      • CNOTはxorらしいので、全部CNOTすればOK
  • I: Deutsch-Jozsa algorithmを実装せよ
    • ドイチュ・ジョザのアルゴリズム（Deutsch-Jozsa algorithm）
      • 以下の2種類のどちらかであるオラクルが与えられるので、どっちの種類か判定せよ
      • constant: どんな入力であっても0か1を返す
      • balanced: 全ての入力できる状態について丁度半分については0を返し、もう半分については1を返す
      • かなり限定的な問題であるが、古典アルゴリズムよりも高速に動作する
    • アルゴリズム内容
      1. 初期状態
        • |x>|y> = |0>N|1> = |0...01>を用意する
      2. 全てのqubitにHゲートを適用する
        • H(|0...01>) = H(|0>N|1>) = H(|0>)N H(|1>) = |+>^N |->
      3. オラクルに通す
      4. もう一度すべてのqubitにHゲートを適用する
      5. 上位N桁に対してPauli Zを対角とする測定（普通の測定）をして、すべて|0>ならconstant、そうでないならbalanced
    • なぜそうなるかは全然理解していないのだけれど、実装するだけなら簡単

Microsoft Q# Coding Contest - Winter 2019 - Warmup - Codeforces

  • G1: AND演算をするオラクルを作成せよ
    • Controlled functorをサポートしている演算に対してControlledを付けることで、制御ビットで制御が可能になる
      • 具体的にはCNOT(x,y)はControlled X([x], y)のように書ける
      • 制御ビットを複数ビットにした場合はすべて1になれば、演算が実行される
    • よってANDで1になるのは全部1の場合になるので、入力をすべて制御ビットとして与えて、全部1ならXゲートを適用して反転すればいい
    • 実装テンプレを見るとadjoint autoが指定されている
    • adjointの設定はここにあるように、is Adjと書いてもいい
  • G2: OR演算をするオラクルを作成せよ
    • xを全部NOTしてANDしたら全部0なら1だし、それ以外なら0になる。ちょうど結果をNOTすればOR計算の結果と一致する
    • ここを見ると、ControllOnIntという便利なControlledもある
  • G3: 回文になっているビット列であるかを判定するオラクルを作成せよ
    • adjointであるが、計算用にビットを使用しても問題ないようだ
    • 回文の対応関係にある部分に対してXORをとると、同じなら0、そうでないなら1になる
    • あとは、全部0ならOKなので、全部のビットをXゲートでFlipしてからControlled Xゲートを通すと答えが得られる
    • usingで確保した後は量子ビットを0に戻す必要があるが、ResetAllはadjointの場合は使えない。逆計算をして0に戻しておこう
    • Palindrome checker oracle
      • 使えるプログラミング的な記法が紹介されている
  • U1: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する（2Nを一辺とする）行列である
      • 問題文にあるように逆対角（日本語正しい？）が10-5以上で、それ以外が10-5未満である
    • 一番単純な、逆対角が1で他が0であるようなユリタリを考えてみる
      • 書き下してみると、ちょうど全てのビットに対するSWAP操作を行うユリタリ行列となっている
  • U2: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する（2Nを一辺とする）行列である
      • 問題文にあるように2×2のEPS以上の係数がある部分が市松模様に配置されている
    • 小さい例から考えてみる
      • N=1
        • XX XXこれは全部一様になればいいからH(qs[0])でいい
        • んー、Hだけかければよさそう？
      • N=2
        • XX.. XX.. ..XX ..XXになればいい。00,01同士の遷移はある、10,11同士の遷移はある。だが、それ以外の遷移はない。よって2ビット目は変更無しだが、1ビット目については変更の可能性がある
        • H(qs[0]だけでいい
      • N=3
        • よくよく見ると、000,001,100,101間で遷移がある。010,011,110,111間で遷移がある。なので、2ビット目だけ変化がないみたい。
    • 2ビット目以外にHをかければ答え。
    • Chessboard unitary
      • さすが竹雄さんのサイトには、実験的な解法ではないちゃんとした解法が書かれている
  • U3: 以下条件を満たすunitaryを構築せよ
    • 条件
      • Nビットの量子ビットに対する（2Nを一辺とする）行列である
      • 問題文にあるように左上の領域は逆対角だけEPS以上で、右上と左下は全部EPS未満で、右下は全てEPS以上である
    • 条件が複雑で小さい例で考えるのがややこしいが考えてみる
      • N=1
      • N=2
        • .X.. X... ..XX ..XX
        • 00,01は相互変換、10,11は全部変換なので、2ビット目が0なら1ビット目はXゲートだし、2ビット目が1なら1ビット目はHゲート
        • もっと書くと、1ビット目をXゲートに通して、2ビット目が1なら1ビット目にHゲートを通すせば（CHゲート）よさそう

Microsoft Q# Coding Contest - Summer 2020 - Warmup - Codeforces

  • A1: 与えられたユニタリがIゲートかXゲートかを判定せよ
    • 量子ビットを1つ用意してユニタリに通して測定（普通にZ軸で測定）した結果を見れば分かる
  • A2: 与えられたユニタリがIゲートかZゲートかを判定せよ
    • |0>にZゲートをただ通しても変わらないので、工夫が必要
    • Hゲートをうまく使うことにしよう
      • |0>に対してHゲート→Iゲート→Hゲートをして測定すると|0>となる
      • |0>に対してHゲート→Zゲート→Hゲートをして測定すると|1>となる
  • A3: 与えられたユニタリがZゲートかSゲートかを判定せよ
    • ユニタリは丁度2回使う必要がある
    • Sゲートは位相を180度ずらすもの（要出典）
    • 今回は2回というのが特に怪しいので、Zゲートを2回、Sゲートを2回通したものを考えてみよう
      • 実はZ2=I, S2=Zとなる。これはユニタリ行列を実際に計算してみると分かる
    • これでA2に帰着できたので、あとはやるだけ
  • A4: 与えられたユニタリがI xor XかCNOTかを判定せよ
    • 1ビット目（判定ビット）が0であれば、I xor Xなら2ビット目はflipされるので測定したら1で、CNOTなら2ビット目はなにもしないので測定したら0になる
    • これで判定すればいい
  • A5: 与えられたユニタリがZか-Zかを判定せよ
    • -Zの意味合いが全く分からず、さっぱり分からなかった
    • Microsoft Q# Coding Contest – Summer 2020の復習(1) ユニタリーの識別 - 銀の光と碧い空
      • なるほど…というかなんというか…
      • |00>から1ビット目にHゲートを通すと、(|00>+|01>)/sqrt(2)になる
      • この状態で1ビット目を制御ビットとして2ビット目に対してControlledでユニタリを適用する
        • Controlled Zなら
          • |00>は|00>, |01>なら|01>になる
          • 結果は(|00>+|01>)/sqrt(2)
          • これにHゲートを更に通すと|00>
        • Controlled -Zなら
          • |00>は|00>, |01>なら-|01>になる
          • 結果は(|00>-|01>)/sqrt(2)
          • これにHゲートを更に通すと|01>
      • よってHゲート,Controlled unitary,Hゲートを通して1ビット目を測定すればどっちになるか分かる
    • Controlledのこのような使い方もあるのね…なるほど…
    • なんとなく行列とかで機械的に解けないもんだろうか
  • B1: インクリメントするオラクルを作成せよ
    • XゲートとControllを使えと書いてあるので、再帰しながら繰り上がりしていけばOK
    • LittleEndianの扱いが大変
  • B2: デクリメントするオラクルを作成せよ
    • B1をベースにして、繰り上がりを0の時に行うようにすればOK
  • C: (|01>+|10>+|11>)/sqrt(3)を作成せよ
    • 全然分からんし、問題制約でX,Y,Z,Hゲート（Controlled込み）と測定しか使っちゃダメか…
      • Hゲートでsqrt(2)が作れるのは分かるが、sqrt(3)は見たことないな
      • 試しにtatyamさんのSubmission #59576937 - Codeforcesを借りてきて改変したがダメ。Ryは使ってもいいって書いてないですよね…
    • Microsoft Q# Coding Contest – Summer 2020の復習(3) 状態の生成 - 銀の光と碧い空
      • 気持ちは分かる。00,01,10,11の重ね合わせ状態を作って、それを制御ビットにして、|0>の量子ビットにNOTゲートを通して測定したときに|0>になっていれば、制御ビットが00,01,10のどれかになっているはずなので、全体にXゲートを通せば11,10,01の重ね合わせになってるから答えであるということ
      • ancillaを測定したタイミングで量子もつれの関係で、ancillaの測定結果に沿った形でqsの量子状態が変化するのだろう
    • Microsoft Q# Coding Contest - Summer 2020 - Warmup - tutorial
      • ここも本質的にはやってることは変わらないが|00>を排除するようにControlledすることで一手減らしている
    • どちらも実装ではancillaと量子ビットに名前がついている。ふむ。Ancilla bit - Wikipedia
    • Q#にはrepeat構文というものが用意されているので、これを使って実装する
      • 「測定をすることで計算を進める」というのを何かの本で読んだ記憶があるが、このようにしてやるんだな…
  • D1,D2: 量子classificationをせよ。訓練データが与えられるので、学習をして、学習済みモデルを答える感じ
    • Microsoft Q# Coding Contest - Summer 2020 - Warmup - tutorial
      • 入力例をグラフ上で可視化してくれている。SVMとかで解けそうな感じ。
      • 学習させると、するとパラメタが出力されるので、それを使えば分類器が簡単に実装できますよということ。
    • 横着してやってない

まとめ

暇があれば、いつか本戦問題もやります。
量子プログラミングやってみた感想としては、かなりパズルっぽい感じですね。
競技プログラマーには適合性が高そうなので、皆さんも是非。

今年も界隈にはお世話になりました。（ほぼROM専で勝手にみてるだけ）
あと、会ったこともないのに書くのも恐れ多いのですが、rngさんこれまでお疲れさまでした。
今後も確実に活躍されると思うのでwatchしていきます。

来年もCTF比率が高くなりそうなのですが、来年もよろしくお願いいたします。
皆様、よいお年をお迎えください。

追記、というか自分用メモ