量子情報理論の基本：量子誤り訂正（Shorの符号） #Python - Qiita

量子情報理論の基本：量子誤り訂正（Shorの符号） #Python - Qiita 20 いいねしたユーザー一覧へ移動 8 X（Twitter）でシェアする Facebookでシェアする はてなブックマークに追加する more_horiz 記事を削除する close 一度削除した記事は復旧できません。 この記事の編集中の下書きも削除されます。 削除してよろしいですか？ キャンセル 削除する delete info この記事は最終更新日から3年以上が経過しています。 @ SamN 量子情報理論の基本：量子誤り訂正（Shorの符号） Python 量子コンピュータ 量子力学 量子計算 量子情報 20 最終更新日 2021年09月05日 投稿日 2020年02月10日 $$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$ はじめに 1980年代に量子計算の原理が明らかになった当初、古典的なデジタル処理で使われるような誤り訂正の理論がない、もしくはその理論確立が極めて困難なため、量子コンピュータなんていうものは現実的に実現不可能と考える人もいたらしいです。古典ビットの場合、ビットが反転するエラーだけを考えれば良いのに対し、量子ビットの場合、その変化は無限の自由度を持つので、無限のパターンのエラーを相手にする必要があります。ブロッホ球をイメージすると、量子状態のズレ方は無限にありますよね。そのズレた状態からもとの状態を正確に復元させることを考えないといけないです。さらに、量子状態は古典情報のように無邪気に複製できませんし、測定したら壊れてしまう代物です。といった諸々があり、難しさが半端ないと思われていたようです。それを最初に打破したのがPeter Shorです。このShorが提案した「Shorの符号(Shor code)」を使えば、1量子ビットに働く任意の誤りを訂正することができます。この「任意の」というところがスゴイところです。しかも、割と簡単な量子回路で実現できてしまいます。今回は、その理論を説明した後、量子計算シミュレータ qlazy で、その威力を実感してみたいと思います。 参考にさせていただいたのは、以下の文献です。 ニールセン、チャン「量子コンピュータと量子通信（３）」オーム社（2005年） 富田「量子情報工学」森北出版（2017年） 中山「量子アルゴリズム」技報堂出版（2014年） 理論の確認 古典的誤り訂正（繰り返し符号） 量子誤り訂正の話に突入する前の準備体操として、古典情報における誤り訂正の基本的な考え方をおさらいしておきます。いま、1ビットの情報を雑音のある古典チャネルを通して送信することを考えてみます。このチャネルにより、ビットは確率pで反転するとします。つまり、入力ビットが0だった場合、確率pでビットが1に反転し、確率1-pで0のまま維持されます。また、入力ビットが1だった場合、確率pでビットが0にに反転し、確率1-pで1のまま維持されます。このようなチャネルのことを「2値対称チャネル(binary symmetric channel)」と言います。何も考えず、このチャネルをそのまま使うと、当然ですが誤り率はpです。このチャンネルを前提に、何らかの処理を施すことによって、誤り率を減らすことができないでしょうか。 基本的で、よく知られたやり方は、ビットを複製してわざと冗長化しておく方法です。例えば、与えられた1ビットの情報を、以下のように3ビットに変換（符号化）しておきます。 \begin{align} 0 &\rightarrow 000 \\ 1 &\rightarrow 111 \\ \end{align} これを次々に古典チャネルを通して送信します。情報量は3倍になってしまいますが、誤り訂正のためには仕方ありません、という考え方です。雑音によって確率的にビットが反転するので、000というビット列は、受信側で010になっているかもしれません。が、これは真ん中のビットが反転したせいであり、本当は000のことだろうと推測するわけです。つまり多数決をとって、多いビットが元のビットだろうと見なす手法です。入力ビットを繰り返して符号化するので「繰り返し符号(repetition code)」と呼ばれています。容易にわかる通り、入力が000で雑音の結果110になってしまう可能性もなくはないです。が、トータルでの平均誤り率が小さければ良いと考えます。では、その平均誤り率は、具体的にどう計算されるでしょうか。0個もしくは1個のビット反転は訂正できるので、2個または3個のビットが反転してしまう確率だけを計算すれば、所望の誤り率になります。3個いっぺんに反転してしまう確率は$p^3$で、2個反転してしまう確率は3パターンあって$3p^2(1-p)$です。これを足すと、$p^3 + 3p^2(1-p) = 3p^2 - 2p^3$になります。何もやらない場合の誤り率は$p$だったので、誤り訂正をした方が誤り率が小さくなるという条件は、$p > 3p^2 - 2p^3$、すなわち、$p < 1/2$となります。つまり、$p$の値が$1/2$よりも小さい古典チャネルであれば、この繰り返し符号の効果が発揮されるというわけです。 ３量子ビットのビット反転符号 符号化 量子ビットの場合も、似たような考え方で符号化します。例えば、1量子ビットの状態が$\ket{\psi} = a \ket{0} + b \ket{1}$だったとして、それを$a \ket{000} + b \ket{111}$のように変換（符号化）できないかを考えます。簡単にわかると思いますが、以下のような量子回路を通せば実現できます。 |psi> --*--*-- ... | | |0> --X----- ... | |0> -----X-- ... この状態で、例えば一つのビットが反転して$\ket{000} \rightarrow \ket{010}$のように変化しても、元の状態を復元することができます。ということを、これから説明していきます（図中の点々部分は雑音チャネルであることを表すものとします。以下同様）。 誤り検出（シンドローム診断） まず、どのビットが反転したかを知る必要があります。この手続きのことを「誤り検出(error-detection)」とか「シンドローム診断(syndrome diagnosis)」と言います。3ビットの場合、以下のような射影演算を施せば、それがわかります。 \begin{align} P_0 &= \ket{000} \bra{000} + \ket{111} \bra{111} \\ P_1 &= \ket{100} \bra{100} + \ket{011} \bra{011} \\ P_2 &= \ket{010} \bra{010} + \ket{101} \bra{101} \\ P_3 &= \ket{001} \bra{001} + \ket{110} \bra{110} \tag{1} \end{align} $P_0$は何も誤りがないことを検出する測定に対応した射影演算子です。$P_1$は1番目のビットに誤りがあることを検出する射影測定です。以下、$P_2$は2番目、$P_3$は3番目のビットに誤りがあることを検出する射影測定です。雑音の結果、$a \ket{100} + b \ket{011}$となった場合、$\bra{\psi} P_1 \ket{\psi}$のみが1で、その他はすべて0になりますので、確かに$P_1$は1番目のビットの誤り検出のための演算子であるということがわかると思います。 この例以外にも、シンドローム診断のための射影測定があります。式(1)では4つの演算子を使いましたが、2つで済ますことができるスグレモノがあります。結論を先に言います。1番目、2番目、3番目の量子ビットに適用するパウリ$Z$演算子を各々$Z_1,Z_2,Z_3$としたときに、$Z_1 Z_2$および$Z_2 Z_3$というオブザーバブルを測定するやり方です。とイキナリ言われても「ん？」という状態かもしれないので、少し説明を加えます。 パウリ$Z$は$Z=\ket{0}\bra{0}-\ket{1}\bra{1}$と書けるので、 \begin{align} Z_1 Z_2 &= (\ket{0}_{1}\bra{0}_{1}-\ket{1}_{1}\bra{1}_{1})(\ket{0}_{2}\bra{0}_{2}-\ket{1}_{2}\bra{1}_{2}) \\ &= \ket{00}\bra{00} + \ket{11}\bra{11} - \ket{01}\bra{01} - \ket{10}\bra{10} \\ &= (\ket{00}\bra{00} + \ket{11}\bra{11}) \otimes I_3 - (\ket{01}\bra{01} + \ket{10}\bra{10}) \otimes I_3 \tag{2} \end{align} と展開できます。この式をじっと睨むとわかると思いますが、1番目と2番目の量子ビットが同じ場合（「偶パリティ」と言います）、このオブザーバブルを測定すると1を出力します。逆に、1番目と2番目の量子ビットが違う場合（「奇パリティ」と言います）、−1を出力します 1 。つまり、$Z_1 Z_2$の測定を行うと、1番目と2番目の量子ビットのパリティをチェックすることができます。同様に、$Z_2 Z_3$の測定によって、2番目と3番目の量子ビットのパリティがわかります。 表に整理すると、以下のようになります。 $Z_1 Z_2$の測定値（パリティ） $Z_2 Z_3$の測定値（パリティ） 反転しているビット +1（偶） +1（偶） なし +1（偶） -1（奇） 3番目 -1（奇） +1（偶） 1番目 -1（奇） -1（奇） 2番目 1行目は、1番目と2番目が偶パリティで、2番目と3番目が偶パリティということなので、反転しているビットがないと推定できそうです。 2行目は、1番目と2番目が偶パリティで、2番目と3番目が奇パリティということなので、3番目が反転していると推定できそうです。 3行目は、1番目と2番目が奇パリティで、2番目と3番目が偶パリティということなので、1番目が反転していそうです。 最後の4行目は、1番目と2番目が奇パリティで、2番目と3番目が奇パリティということなので、真ん中の2番目が反転している可能性が高そうです。 ということで、反転している量子ビットが何番目なのか、推定することができます。反転している量子ビットが、高々1個しかない場合は、反転ビットが何番目かを完全に特定することができます。 このシンドローム診断は、どのような量子回路で実現できるでしょうか。測定すれば良いだけなので、 |psi> --*--*-- ... --M-- | | |0> --X----- ... --M-- | |0> -----X-- ... --M-- としてしまうかもしれません。が、これでは駄目です。誤り訂正したい量子ビットを測定によって壊してしまっています。なので、誤り訂正したい量子状態を壊さないように、以下のように、補助量子ビット（アンシラ）を追加して、そちらに対象とする量子状態を逃してあげて、その状態を測定するようにしないといけません。 |psi> --*--*-- ... --*------------ | | | |0> --X----- ... -----*--*------ | | | | |0> -----X-- ... -----------*--- | | | | |0> --X--X--------M1 | | |0> --------X--X--M2 ここで、$Z_1 Z_2$の測定をM1、$Z_2 Z_3$の測定をM2と表しました 2 。 回復 シンドローム診断で、反転している量子ビットが特定できたので、次に、その量子ビットを再度反転して元に戻せば良いです。M1とM2の値に応じて、XゲートをON/OFFします。 |psi> --*--*-- ... --*------------X--- | | | || |0> --X----- ... -----*--*------X--- | | | | || |0> -----X-- ... -----------*---X--- | | | | || |0> --X--X---------M1 | | || |0> --------X--X---M2 測定結果に応じてゲートを制御することを二重の縦棒で表してみました（わかりにくく、かつ、正式な書き方でもないですが、気持ちを汲んでください、汗）。先程表で示したパターンで３つの量子ビットのどれかにXゲートをかけます。これで、元の状態に戻ることになります 3 。 測定結果に応じたゲート操作をする代わりに、CNOTとToffoliを使って同じことができます。 [雑音] |psi> --*--*-- ... --*-------------------X--X-- | | | | | |0> --X----- ... -----*--*----------------X-- | | | | | | |0> -----X-- ... -----------*-------X-----X-- | | | | | | | |0> --X--X----------------*--*-- | | | | |0> --------X--X-------*-----*-- [符号化] [シンドローム診断] [訂正] これはわかりますでしょうか。 シンドローム診断の段階で、1番目のアンシラが+1($\ket{0}$)で2番目のアンシラが+1($\ket{0}$)の場合、[訂正]と記載されている回路部の制御ビットはともに$\ket{0}$なので、何もしません。 1番目のアンシラが+1($\ket{0}$)で2番目のアンシラが-1($\ket{1}$)の場合、訂正回路の2番目のアンシラだけが$\ket{1}$になるので、3番目の量子ビットにXゲートがかかり反転します。 1番目のアンシラが-1($\ket{1}$)で2番目のアンシラが+1($\ket{0}$)の場合、訂正回路の1番目のアンシラだけが$\ket{1}$になるので、1番目の量子ビットにXゲートがかかり反転します。 1番目のアンシラが-1($\ket{1}$)で2番目のアンシラが-1($\ket{1}$)の場合、訂正回路の両方のアンシラが$\ket{1}$になるので、2番目の量子ビットにXゲートがかかり反転します。 ということで、これで、すべての誤りパターンに対してビットを回復することができました。 復号化 最後に、符号化の逆をやって、もともとあった状態に完全に戻します。 [雑音] |psi> --*--*-- ... --*-------------------X--X---*--*-- |psi> | | | | | | | |0> --X----- ... -----*--*----------------X------X-- |0> | | | | | | | |0> -----X-- ... -----------*-------X-----X---X----- |0> | | | | | | | |0> --X--X----------------*--*-- | | | | |0> --------X--X-------*-----*-- [符号化] [シンドローム診断] [訂正] [復号化] 以上で、1量子ビットの反転に対する誤り訂正回路が完成しました。 しかし、アンシラとして2量子ビット余分に必要になってしまうのが、よろしくないです。できればアンシラなしで済ませたいということで、考え出された回路を以下に示します。1番目の量子ビットだけ回復できれば良いので、2番目、3番目はもとに戻らなくても良いという考え方です。ただし、少なくとも1番目と他の量子ビットとの間にもつれが残らないようにします。 |psi> --*--*-- ... --*--*--X-- |psi> | | | | | |0> --X----- ... -----X--*-- | | | |0> -----X-- ... --X-----*-- どうでしょうか。かなりシンプルになっていますが、これで本当に誤り訂正できているのでしょうか。数式で確認してみます。入力する状態は$\ket{\psi} = a \ket{0} + b \ket{1}$とします。符号化した段階で状態は$a \ket{000} + b \ket{111}$となるのは明らかなので、その直後からの変化を見てみます。 反転する量子ビットがない場合、 \begin{align} a\ket{000} + b\ket{111} &\rightarrow a\ket{000} + b\ket{110} \rightarrow a\ket{000} + b\ket{100} \rightarrow a\ket{000} + b\ket{100} \\ &= (a\ket{0} + b\ket{1}) \otimes \ket{00} \tag{3} \end{align} 雑音により、1番目の量子ビットが反転した場合、 \begin{align} a\ket{100} + b\ket{011} &\rightarrow a\ket{101} + b\ket{011} \rightarrow a\ket{111} + b\ket{011} \rightarrow a\ket{011} + b\ket{111} \\ &= (a\ket{0} + b\ket{1}) \otimes \ket{11} \tag{4} \end{align} 雑音により、2番目の量子ビットが反転した場合、 \begin{align} a\ket{010} + b\ket{101} &\rightarrow a\ket{010} + b\ket{100} \rightarrow a\ket{010} + b\ket{110} \rightarrow a\ket{010} + b\ket{110} \\ &= (a\ket{0} + b\ket{1}) \otimes \ket{10} \tag{5} \end{align} 雑音により、3番目の量子ビットが反転した場合、 \begin{align} a\ket{001} + b\ket{110} &\rightarrow a\ket{001} + b\ket{111} \rightarrow a\ket{001} + b\ket{101} \rightarrow a\ket{001} + b\ket{101} \\ &= (a\ket{0} + b\ket{1}) \otimes \ket{01} \tag{6} \end{align} ということで、2番目と3番目の量子ビットは必ずしも$\ket{00}$に戻らないですが、少なくとも1番目の量子ビットはすべてのパターンで$\ket{\psi} = a\ket{0} + b\ket{1}$に戻っていて、かつ、他の量子ビットとはもつれていないです（＝積状態になっています）。 3量子ビットの位相反転符号 次に、1つの量子ビットに位相反転があった場合の誤り訂正についてです。ビット反転はXゲートで表現できますが、位相反転はZゲートの作用です。つまり、$a\ket{0}+b\ket{1} \rightarrow a\ket{0}-b\ket{1}$という変化です。この状態から回復したいわけですが、どうすれば良いでしょうか。実は簡単な処方箋があります。アダマールゲートをかければ良いです。アダマールゲートの作用は、 \begin{align} \ket{0} &\rightarrow \ket{+} = \frac{1}{2} (\ket{0} + \ket{1}) \\ \ket{1} &\rightarrow \ket{-} = \frac{1}{2} (\ket{0} - \ket{1}) \tag{7} \end{align} だったので、$a\ket{0}+b\ket{1} \rightarrow a\ket{0}-b\ket{1}$という位相反転は、 \begin{align} & \frac{1}{2} (a+b) \ket{+} \frac{1}{2} (a-b) \ket{-} \\ & \rightarrow \frac{1}{2} (a+b) \ket{-} \frac{1}{2} (a-b) \ket{+} \tag{8} \end{align} と表されます。つまり、位相反転は$\{ \ket{+}, \ket{-} \}$基底におけるビット反転に他なりません。したがって、先程のビット反転の回路において符号化の後にアダマールをかけてから、雑音チャネルに入れて、復号化の直前にアダマールをかけて元に戻すということをやれば良いです。 |psi> --*--*--H-- ... --H--*--*--X-- |psi> | | | | | |0> --X-----H-- ... --H-----X--*-- | | | |0> -----X--H-- ... --H--X-----*-- これで、位相反転に対する誤り訂正ができたことになります。 Shorの符号 「Shorの符号」は、ビット反転と位相反転の誤り訂正を同時に実現するものです。位相反転の誤り訂正では、初期状態の1量子ビットを3量子ビットに冗長化させ、各々にアダマールをかけます。その各量子ビットに対してビット反転の誤り訂正も実行するため、各々3量子ビットに冗長化します。その結果、合計で9量子ビット必要になります。回路図で表すと、 |psi> --*--*--H----*--*-- ... --*--*--X--H--*--*--X---- |psi> | | | | | | | | | | | | |0> --X----- ... -----X--*-- | | | | | | | | | | | | | | |0> -----X-- ... --X-----*-- | | | | | | | | |0> --X-----H----*--*-- ... --*--*--X--H-----X--*-- | | | | | | | | | |0> --X----- ... -----X--*-- | | | | | | | | | |0> -----X-- ... --X-----*-- | | | | | |0> -----X--H----*--*-- ... --*--*--X--H--X-----*-- | | | | | |0> --X----- ... -----X--*-- | | | |0> -----X-- ... --X-----*-- となります。これで、ビット反転と位相反転の誤りに対して元の状態を回復することができるようになります（もちろん、いま想定しているのは、どれか１つの量子ビットのみが雑音によって反転する場合です）。が、実は、このように構成されたShorの符号は、さらに強力な効果を持っています。ビット反転や位相反転のようなわ