(I + 2iZ)/sqrt(5) というユニタリ変換を基本的なゲートで作る話

Q#というMS製の量子計算用言語の言語仕様 Q# statements | Microsoft Docs を読んでいたら、
(I+2iZ)/\sqrt{5} = \frac{1}{\sqrt{5}}\begin{pmatrix}1+2i & 0 \\ 0 & 1-2i\end{pmatrix} というゲートが、基本的なゲートたちと観測の組み合わせで正確に実現できるという話を見たので、調べてみました。

準備

状態|0>を\begin{pmatrix}1\\0\end{pmatrix}、状態|1>を\begin{pmatrix}0\\1\end{pmatrix}とします。状態ベクトルを複数並べた時の表示も、適切に定義されているものとします。例えば、
\displaystyle |00\rangle = \begin{pmatrix}1\\0\\0\\0\end{pmatrix},\displaystyle |01\rangle = \begin{pmatrix}0\\1\\0\\0\end{pmatrix},\displaystyle |10\rangle = \begin{pmatrix}0\\0\\1\\0\end{pmatrix},\displaystyle |11\rangle = \begin{pmatrix}0\\0\\0\\1\end{pmatrix}
です。

|+\rangle|-\rangleを、それぞれ|+\rangle:=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle),|-\rangle:=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)と定義します。

\langle 0|\langle 1|を、\langle i|j\rangle = \delta_{ij} が成り立つような線形写像とします。ここで\delta_{ij}クロネッカーのデルタです。2量子ビット以上の系についても、\langle ik|jl\rangle = \delta_{ij}\delta_{kl}などのように定義されているものとします。

ビットの位置は先頭が第0ビットであるものとします。0-indexedです。

以下の基本的なゲートたちの知識を仮定します。
X := \begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix} (Xゲート, X|0> = |1>, X|1> = |0>)
Z := \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix} (Zゲート, Z|0> = |0>, Z|1> = -|1>)
T := \begin{pmatrix}1 & 0 \\ 0 & e^{i\pi/4}\end{pmatrix} (Tゲート, Z|0> = |0>,  Z|1\rangle = e^{i\pi/4}|1\rangle)

CCNOT: (Toffoliゲート、CCNOT|11a> = |11(1-a)>, CCNOT|abc>=|abc> (a=0またはb=0のとき)
また、[1] に倣って、作りたいユニタリ変換にV_3という名前をつけます。
\displaystyle V_3 := (I+2iZ)/\sqrt{5} = \frac{1}{\sqrt{5}}\begin{pmatrix}1+2i & 0 \\ 0 & 1-2i\end{pmatrix}

Aがエルミート行列(A =A^\dagger)のとき、Aをオブザーバブルと呼びます。オブザーバブルAに関する観測とは、量子ビットをAの固有ベクトルの一つへと収縮させる行為を指します。量子ビット|\psi\rangleに対して、この量子ビットがAの固有ベクトル|v>へと収縮する確率は|\langle v|\psi \rangle|^2です。
例えば、Xゲートはエルミート行列ですが、Xに関してある量子ビット|\psi\rangleを観測すると、\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) または \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) のどちらかの状態に収縮します。前者に収縮する確率は|\frac{1}{\sqrt{2}}(\langle 0|+\langle 1|)|\psi\rangle|^2で、後者に収縮する確率は|\frac{1}{\sqrt{2}}(\langle 0|-\langle 1|)|\psi\rangle|^2です。

やり方

[1]のFigure 1.(a) の量子回路に即して説明します。この回路は、S=T^2ゲート1個と、Zゲート1個、およびXゲートに関する観測を2回行う回路です。この回路に量子ビット|\psi\rangleを入力すると、確率5/8でV_3|\psi\rangleに、確率3/8で|\psi\rangleになります。よって、平均8/5回でユニタリ変換V_3が実現できます。

f:id:koba-e964:20180708180243p:plain
[1]の Figure 1.(a)。Exp[T]=12.8というのは、平均でTゲートを実行する回数が12.8回という意味です。1個のToffoliゲートはTゲート4個で実現されています。(8/5)*2*4=12.8なので勘定があっています。

この事実を計算で示すのが、この記事の目標です。1ステップずつ見ていきましょう。

証明

 |\psi\rangle = a|0\rangle + b|1\rangleと置きます。aとbは|a|^2+|b|^2=1を満たす複素数であることに注意してください。
Ancilla bit (操作のために追加で足される量子ビット) たちも合わせた初期状態は

 |\Psi_0\rangle := \displaystyle |+\rangle \otimes |+\rangle \otimes |\psi\rangle= \frac{1}{2}(a|000\rangle + b|001\rangle+ a|010\rangle + b|011\rangle+ a|100\rangle + b|101\rangle+ a|110\rangle + b|111\rangle)
です。

これにToffoliゲートを適用すると、
\displaystyle |\Psi_1\rangle := \frac{1}{2}(a|000\rangle + b|001\rangle+ a|010\rangle + b|011\rangle+ a|100\rangle + b|101\rangle+ b|110\rangle + a|111\rangle)
になります。
これの第2ビット(ancilla bitではないビット)にSゲートを適用すると、
\displaystyle |\Psi_2\rangle := \frac{1}{2}(a|000\rangle + ib|001\rangle+ a|010\rangle + ib|011\rangle+ a|100\rangle + ib|101\rangle+ b|110\rangle + ia|111\rangle)
になります。

これにもう一度Toffoliゲートを適用すると、
\displaystyle |\Psi_3\rangle := \frac{1}{2}(a|000\rangle + ib|001\rangle+ a|010\rangle + ib|011\rangle+ a|100\rangle + ib|101\rangle+ ia|110\rangle + b|111\rangle)
になります。

これにZゲートを適用すると、
\displaystyle |\Psi_4\rangle := \frac{1}{2}(a|000\rangle - ib|001\rangle+ a|010\rangle - ib|011\rangle+ a|100\rangle - ib|101\rangle+ ia|110\rangle - b|111\rangle)
になります。

これのancilla bitたちをXに関して観測しましょう。両方のビットで|+>が観測されると第2ビットがV_3|\psi\rangleになるということだったので、それを確かめます。これが起こる確率は、|\langle++|\Psi_4\rangle|^2で与えられるので、計算します。ここで、\displaystyle\langle++|:=\frac{1}{\sqrt{2}}(\langle 0|+\langle 1|) \otimes \frac{1}{\sqrt{2}}(\langle 0|+\langle 1|) = \frac{1}{2}(\langle 00|+\langle 01|+\langle 10|+\langle 11|)です。
\displaystyle\langle++|\Psi_4\rangle=\frac{1}{4}((3+i)a|0 \rangle + (-1-3i)b|1\rangle)のため、
\displaystyle |\langle++|\Psi_4\rangle|^2=\frac{1}{16}(10|a|^2+10|b|^2)=\frac 58です。
観測後の第2ビットの状態は、\langle++|\Psi_4\rangleを規格化することで得られ、
\displaystyle|\psi'\rangle := \frac{1}{\sqrt{10}}((3+i)a|0 \rangle + (-1-3i)b|1\rangle)です。

量子ビットの状態は、絶対値1の複素数倍を無視するので、これは
\displaystyle V_3|\psi\rangle=\frac{1}{\sqrt{5}}((1+2i)a|0\rangle+(1-2i)b|1\rangle)
と等価です。(V_3|\psi\rangle =\frac{1+i}{\sqrt{2}}|\psi'\rangleとなります。)

|\Psi_4\rangleのancilla bitたちの観測時に|++>以外が観測された場合には第2ビットが|\psi\rangleのままとなりますが、これの計算は読者への演習問題とします。 (訳: 疲れました)


References

[1] Paetznick, A., & Svore, K. M. (2013). Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries, 1–26. Retrieved from http://arxiv.org/abs/1311.1074f:id:koba-e964:20180708180243p:plain

AtCoder Grand Contest 024 E

問題文: ARC024 E Sequence Growing Hard

問題概要

0要素の数列がある。この数列に、以下の条件を満たすように、1要素ずつ挿入することをN回繰り返す。

  • 挿入後の数列は、挿入前より辞書順で大きい。

挿入の過程で同じ数列ができる操作は同じとみなす。操作の方法は何通りあるか。

自分の誤答

操作を逆から見ると、長さNの数列から要素を除去していく方法の総数を数えればよいことがわかる。除去できるのは、「広義単調増加のstreakの最後だけ」であることがわかる。しかしstreakの個数を状態として持つDPだと失敗する (除去した後のstreakの個数は同じか1個減るかだが、どちらかわからない)。

正解

挿入DPを行う。k=k'の結果が全てのnについて分かっている時、k=k'+1の時の結果を求めることを考える。k=k'の時の操作列にk'+1を挿入する操作を0個以上入れれば良いことがわかるが、うまく解析すると、k'+1を挿入する操作を入れる時刻を決めると、何個挿入しても場合分けの分岐の個数が一定であることがわかる (元の操作列における時刻にのみ依存する)。これを使って区間DPする。

感想

知識がなかった。挿入DPは1回だけ解いたことがあったので、それを活かしたかった。

AtCoder Regular Contest 097 F

問題文: ARC097 F Monochrome Cat

問題概要

N頂点の木が与えられる。各頂点には0または1が書かれている。好きな頂点を選び、そこに行き、以降以下の1.または2.の操作のいずれかを何回か行う。

  1. 隣接する頂点を一つ選び、移動し、移動先の頂点の数字を1->0または0->1に変更する。
  2. 現在いる頂点の数字を、1->0または0->1に変更する。

操作は任意の地点から始めることができ、また任意の地点で終えることができる。
全ての頂点に書かれた数字を0にしたい。操作回数の最小値を求めよ。

制約

N <= 100000

想定*誤答*

1が書かれた頂点だけを考えれば良い。操作の始点・終点は、1が書かれた頂点同士の間でもっとも遠いペアにすれば良い。それさえ決まれば、dfsでできる。

正解

まず、0が書かれた葉は関係ないので、全て削除する (queueで簡単)。この時残っている頂点のリストを作ると良い。
求める操作列は、Euler tour から単純パスを引いたものである。Euler tourについての操作列の長さは簡単。どのような単純パスを引けばいいかを考える。頂点vに書かれた数をc[v]とすると、単純パスを引くことによる操作回数への効用は、2 * #{v | c[v] xor (deg[v] % 2) } である(この値だけ操作回数が少なくなる)。これを最大化すればよい。最大化は木の直径を計算するのと同じアルゴリズムで、O(N)でできる。

感想

こういう難しい問題でも、数学的な分析ができるようになりたい。最初解く時に、始点と終点は最遠点同士だと決め打ちしたが、これにはなんの根拠もない。このような考察ミスをなくすのが大切。

おまけ

誤答 Submission #2531853 - AtCoder Regular Contest 097 は、c[v] = 0となる葉の削除にも手間取っている。「DFS をやってみて、c[v] = 1となる頂点に出会う前に元の頂点に戻ったら、そこより先はなかった扱いにする」ということをやっているが、これはやってはいけない。

解説をみた後の正答:
Submission #2532111 - AtCoder Regular Contest 097

チェス 2018/05/13

同じ相手と白黒入れ替えて2局指した。
少しチェスをやらない期間があると、すぐにblunderの鬼になってしまう…。

Daily Chess 2018/05/04

chess.comでdaily chessをやった。kobaは黒を持った。12...Nxe4がひどいblunderだったが咎められず、その後も最後まで白がはっきり有利だと思ったが、後で評価してみるとそうでもないようだった。