量子誤り訂正入門 - 物理学科 Advent Calendar - Physics Lab. 2022

量子誤り訂正入門 - 物理学科 Advent Calendar - Physics Lab. 2022 物理学科 Advent Calendar 2021 物理学科アドカレ2021 | 17 日目 量子誤り訂正入門 量子コンピュータのうち、最終的な目標となる誤り耐性量子コンピュータの実現には量子誤り訂正の技術が不可欠です。量子誤り訂正をちょとだけ紹介します。情報系の人にもお勧めです。 ⚠記事の内容は学生個人の見解であり、所属する学科組織を代表するものではありません。 Twitterで共有 この記事は Physics Lab. 2022 Advent Calendar 17日目の記事です。 $$ \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}} $$ 0. はじめに はじめまして！Physics Lab. 2022 副統括、幾何班・量子物理学班所属のシャーペンといいます。 最初にPhysics Lab. 2022の宣伝を… Physics Lab. 2022は物理学科有志による五月祭企画（5/14(土), 15(日)）で、オンライン（virtual 会場）と対面の両方で開催される予定です。 様々な方にきっと物理の面白さを感じて頂けるようなものを準備してお待ちしておりますのでぜひお越しください！ さて、今回、Advent Calendarの記事として量子誤り訂正の気持ち的な所を簡単に紹介したいと思います。では、さっそく本編に入っていきましょう！ 1.目的 今回は量子コンピュータの具体的な物理的実装や量子計算の厳密な定式化などは避けて、数学パズルとしてどういったことをやっているかを説明したいと思います. 流れとしては、 2. 準備(量子状態と測定) 古典誤り訂正 量子誤り訂正の基本(メイン) となります. なお、線形代数の基礎的な所(基底, 次元, 部分空間, 射影等)を前提知識として仮定しています。 これは個人的な考え方ですが、記事や参考書には少なからず著者の解釈や物事を見る角度というものが反映されると思うので、同じテーマについても様々な教科書・記事を読んでみることをお勧めします。 そのため、参考文献に挙げているようなものや、量子誤り訂正についての教材もぜひ参考にしてみてください。 本記事も量子誤り訂正についての理解の一助となれば幸いです。 2.準備 2.1 qubitの状態 量子コンピュータの状態や測定についてはIBMなどが提供している教材等のほか、インターネット上にも多くの記事が充実しているため、細かい説明はそちらに譲って、必要なものだけ定義していきます。 まず、量子コンピュータの情報の基本単位はqubitです。 これは古典コンピュータのビットに対応しています。 古典コンピュータのビットは\(\hspace{0.2em}0\hspace{0.2em}\)または\(\hspace{0.2em}1\hspace{0.2em}\)の状態しかとる事が出来ませんが、 qubitは\(\hspace{0.2em}\ket{0}\hspace{0.2em}\)と\(\hspace{0.2em}\ket{1}\hspace{0.2em}\)を基底とした\(\hspace{0.2em}2\hspace{0.2em}\)次元複素数空間の単位球面上、すなわち $$ \{ \alpha\ket{0}+\beta\ket{1},\qquad \bigl(\alpha,\beta\in\mathbb{C},\quad \lvert\alpha\rvert^2+\lvert\beta\rvert^2=1 \bigr) \} $$ と書かれる状態すべてを取る事が出来ます。ただし、絶対値が\(\hspace{0.2em}1\hspace{0.2em}\)の複素数をかけて一致するものは同一の状態とみなされます。すなわち、\(\ket{\psi}\sim c\ket{\psi}\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}(|c|=1, c\in\mathbb{C})\hspace{0.2em}\)です。 なお, 厳密には物理的に取る状態は古典的な混合状態と合わせて密度行列と\(\hspace{0.2em}1\hspace{0.2em}\)対\(\hspace{0.2em}1\hspace{0.2em}\)に対応し、上記のような形で書かれるものは純粋状態と言われます。\(\ket{0}\hspace{0.2em}\)と\(\hspace{0.2em}\ket{1}\hspace{0.2em}\)で張られる空間を\(\hspace{0.2em}1\hspace{0.2em}\)qubitの状態空間と呼びます。 次に、\(n\hspace{-0.2em}\hspace{0.2em}\) qubit \(\hspace{-0.2em}\hspace{0.2em}(n\geq 2)\hspace{0.2em}\)の状態空間はこれらのテンソル積空間で表され、取り得る状態はその単位球面上になります。テンソル積を知らなくてもこの場合は有限次元ですし直感的に理解は難しくありません。\(n\hspace{0.2em}\)桁のビット列としてあり得る\(\hspace{0.2em}2^n\hspace{0.2em}\)個それぞれに対応する基底が存在してどの\(\hspace{0.2em}2\hspace{0.2em}\)つも互いに直交するとし、それらによって張られる空間の事です。例えば、\(n=2\hspace{0.2em}\)ならばあり得る状態は $$ \{ \alpha\ket{00}+\beta\ket{01}+\gamma\ket{10}+\delta\ket{11},\qquad \bigl(\alpha,\beta,\gamma,\delta\in\mathbb{C},\quad \lvert\alpha\rvert^2+\lvert\beta\rvert^2+\lvert\gamma\rvert^2+\lvert\delta\rvert^2=1 \bigr) \} $$ と書く事が出来ますし、\(n=3\hspace{0.2em}\)ならば状態空間は\(\hspace{0.2em}\ket{000}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{001}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{010}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{011}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{100}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{101}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{110}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{111}\hspace{0.2em}\)の\(\hspace{0.2em}2^3=8\hspace{0.2em}\)つの基底によって張られる\(\hspace{0.2em}8\hspace{0.2em}\)次元の空間です。 2.2 測定 次に測定についてです。今回はZ測定とX測定およびそれらを複数ビットにわたって測定するもののみを考えます。これはパウリ測定と呼ばれるものの一部です。測定についても測定型量子計算など様々な面白い話があるのですが、今回は割愛します。 まず、最初にZ基底, X基底とはそれぞれパウリXゲート, パウリZゲートの固有状態で、具体的には\(\hspace{0.2em}\ket{0}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{1}\hspace{0.2em}\)をZ基底, \(\hspace{-0.2em}\hspace{0.2em}\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\hspace{0.2em}\)をX基底とよびます。Z測定, X測定はそれぞれの基底についての射影測定です。これは次のようなものをさします。 \(\hspace{0.2em}\ket{\psi}=\alpha\ket{0}+\beta\ket{1}\hspace{0.2em}\)とZ基底を用いて表されるとします。 これをZ測定すると, \(\hspace{-0.2em}\hspace{0.2em}\lvert\alpha\rvert^2\hspace{0.2em}\)の確率で\(\hspace{0.2em}0\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\lvert\beta\rvert^2\hspace{0.2em}\)の確率で\(\hspace{0.2em}1\hspace{0.2em}\)が結果として得られます。確率は測定結果をみたす空間に射影したときのノルムの\(\hspace{0.2em}2\hspace{0.2em}\)乗値と一致します。ここで大事なのは、測定後に状態が射影\(\hspace{0.2em}\to\hspace{-0.2em}\hspace{0.2em}\) 正規化される事です。つまり、\(0\hspace{0.2em}\)を結果として得たならば、元々\(\hspace{0.2em}\ket{\psi}\hspace{0.2em}\)だった状態は\(\hspace{0.2em}\ket{0}\hspace{0.2em}\)に、\(1\hspace{0.2em}\)を結果として得たならば\(\hspace{0.2em}\ket{1}\hspace{0.2em}\)へと変化します。測定も状態に影響を与えるというこの性質は量子コンピュータ特有のものです。 X測定は上の\(\hspace{0.2em}\ket{0}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{1}\hspace{0.2em}\)を\(\hspace{0.2em}\ket{+}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{-}\hspace{0.2em}\)に変換したものです。得られる測定結果は\(\hspace{0.2em}\ket{+}\hspace{0.2em}\)に\(\hspace{0.2em}0\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{-}\hspace{0.2em}\)に\(\hspace{0.2em}1\hspace{0.2em}\)が対応し、X測定においても\(\hspace{0.2em}0\hspace{0.2em}\)または\(\hspace{0.2em}1\hspace{0.2em}\)の測定結果を得ます。 ここで簡単な練習問題です。\(\ket{\psi}=\frac{\sqrt{3}}{2}\ket{0}+\frac{1}{2}\ket{1}\hspace{0.2em}\)をX測定するとどうなるでしょうか? まず, \(\hspace{-0.2em}\hspace{0.2em}\ket{\psi}=\frac{\sqrt{6}+\sqrt{2}}{4}\ket{+}+\frac{\sqrt{6}-\sqrt{2}}{4}\ket{-}\hspace{0.2em}\)と書けます。これは上の\(\hspace{0.2em}\ket{+}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{-}\hspace{0.2em}\)を代入すれば分かります。これより、 \(\hspace{-0.2em}\left\lvert\frac{\sqrt{6}+\sqrt{2}}{4}\right\rvert^2=\frac{2+\sqrt{3}}{4}\hspace{0.2em}\)の確率で\(\hspace{0.2em}0\hspace{0.2em}\)を結果として得て、その後の状態は\(\hspace{0.2em}\ket{+}\hspace{0.2em}\)となります。また、\(\left\lvert\frac{\sqrt{6}-\sqrt{2}}{4}\right\rvert^2=\frac{2-\sqrt{3}}{4}\hspace{0.2em}\)の確率で\(\hspace{0.2em}1\hspace{0.2em}\)を結果として得て、その後の状態は\(\hspace{0.2em}\ket{-}\hspace{0.2em}\)となります。 複数のqubitの場合は測定した結果のxorを得ることができます。ここでxorとは排他的論理和のことをさし、\(0 xor 0= 1 xor 1=0\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}0 xor 1=1 xor 0=1\hspace{0.2em}\)となります。例えば、次のようになります。 $$ \{ \alpha\ket{00}+\beta\ket{01}+\gamma\ket{10}+\delta\ket{11}\} $$ と書かれた状態に対して、\(Z_1Z_2\hspace{0.2em}\)測定を行う事を考えます。 \(\hspace{0.2em}Z_1Z_2\hspace{0.2em}\)とは\(\hspace{0.2em}1\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}2\hspace{0.2em}\)qubitに対してZ測定を行うという事です。これは\(\hspace{0.2em}1\hspace{0.2em}\)回の測定でxorした後の結果だけ得られ、個別に測定してあとでxorをとったものとは意味合いが全く異なる事に注意してください。得られる結果の確率分布は同じですが、測定後の状態が異なります。このような場合、測定として異なると考えます。 測定結果が\(\hspace{0.2em}0\hspace{0.2em}\)となる状態は\(\hspace{0.2em}\ket{00}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{11}\hspace{0.2em}\)の\(\hspace{0.2em}2\hspace{0.2em}\)つの状態で張られた空間の状態です。 すなわちその確率は \(\hspace{-0.2em}\hspace{0.2em}\sqrt{\lvert\alpha\rvert^2+\lvert\delta\rvert^2}\hspace{-0.2em}\hspace{0.2em}\) であり, 測定後の状態は射影ですから、\(\ket{\psi}^0_{after}\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}=\frac{\alpha}{\sqrt{\alpha^2+\delta^2}}\ket{00}\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}+\frac{\delta}{\sqrt{\alpha^2+\delta^2}}\ket{11}\hspace{0.2em}\)となります。 同様に測定結果が\(\hspace{0.2em}1\hspace{0.2em}\)となる確率は\(\hspace{0.2em}\sqrt{\beta^2+\gamma^2}\hspace{0.2em}\)であり測定後の状態は\(\hspace{0.2em}\ket{\psi}^1_{after}\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}=\frac{\beta}{\sqrt{\beta^2+\gamma^2}}\ket{01}\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}+\frac{\gamma}{\sqrt{\beta^2+\gamma^2}}\ket{10}\hspace{0.2em}\)となります。 \(\hspace{0.2em}1\hspace{0.2em}\)qubitのときとの違いとして、\(1\hspace{-0.2em}\hspace{0.2em}\) qubitのときは次元が\(\hspace{0.2em}2\hspace{0.2em}\)に対してあり得る状態の次元を\(\hspace{0.2em}2\hspace{0.2em}\)分の\(\hspace{0.2em}1\hspace{0.2em}\)に絞った事により測定後の状態が完全に\(\hspace{0.2em}\ket{0}\hspace{0.2em}\)か\(\hspace{0.2em}\ket{1}\)(または\(\hspace{0.2em}\ket{+}\hspace{0.2em}\)か\(\hspace{0.2em}\ket{-}\hspace{0.2em}\))と定まってしまい, \(\hspace{-0.2em}\hspace{0.2em}\alpha\hspace{0.2em}\)や\(\hspace{0.2em}\beta\hspace{0.2em}\)が消えてしまったのに対して、今回は次元が\(\hspace{0.2em}4\hspace{0.2em}\)に対して\(\hspace{0.2em}2\hspace{0.2em}\)つずつの基底からなる空間に分けたため、比の形で部分的に測定前の情報が残っているというのが分かると思います。 ここで、注記ですが、\(\ket{0}\hspace{0.2em}\), \(\hspace{-0.2em}\hspace{0.2em}\ket{1}\hspace{0.2em}\)はZゲートに対する固有状態 \(\hspace{-0.2em}\hspace{0.2em}(Z\ket{0}=\ket{0},Z\ket{1}=-\ket{1})\hspace{-0.2em}\hspace{0.2em}\) であって、\(\ket{0}\leftrightarrow \ket{1}\hspace{-0.2em}\hspace{0.2em}\) の変換が起きるのは X ゲートを作用させた時ということに注意してください。 3.古典誤り訂正 3.1 誤り訂正とは 古典誤り訂正についても、必要な部分だけ触れていきます。 ビットとqubit の性質や測定の違いから、古典誤り訂正を量子誤り訂正にほぼそのままに適用することはできませんが、考え方や用語等多くのものを共有しています。そのため、量子誤り訂正について知るために古典誤り訂正を学ぶことは価値があると言えます。 まず、そもそも誤り訂正とは、アルゴリズム起因などで入るものではありません。 コンピュータに物理的な実在がある以上、ビット(量子コンピュータであればqubit)の情報の担い手であるものが何らかの理由(ゆらぎや、他にも(二次)宇宙線の衝突など)によって想定外の挙動をしてしまう事が考えられます。こういう時にそのエラーが 計算結果に影響を与える確率を抑えて 実用上問題無いようにしようというのが誤り訂正です。ここで、例えば確率を\(\hspace{0.2em}10^{-30}\hspace{0.2em}\)とかにしようと言っているのであって、\(0\hspace{0.2em}\)にすると言っているわけでは無い事に注意してください。 たとえ、どんなに注意して状態を分けたとしても、（それこそ猿がシェイクスピアの作品を打ち出すくらいの）ものすごい低確率で一方から他方に移り合う事が出来てしまうはずです。 3.2 多数決 さて、その具体的な手法を紹介しましょう。 とてもシンプルな例としては多数決があります。 これは計算前のビットをコピーして\(\hspace{0.2em}3\hspace{0.2em}\)つに分け, それぞれについて計算を行います。 そして得られた結果のうち多いものを結果として採用します。 各ビットのエラー率を \(\hspace{-0.2em}\hspace{0.2em}p\hspace{-0.2em}\hspace{0.2em}\) \(\hspace{-0.2em}\hspace{0.2em}(p\ll 1)\hspace{0.2em}\)とすると、前者であればエラーの起きる確率は\(\hspace{0.2em}1-p\hspace{0.2em}\)になります。後者であれば\(\hspace{0.2em}1-3p^2+2p^3\hspace{0.2em}\)となります。この時、\(p\ll 1\hspace{0.2em}\)から、\(3p^2-2p^3 < p\hspace{0.2em}\)となります。 例えば\(\hspace{0.2em}p\sim 10^{-5}\hspace{0.2em}\)であれば、前者では\(\hspace{0.2em}\sim 10^{-5}\hspace{0.2em}\)ですが、後者では\(\hspace{0.2em}\sim 10^{-10}\hspace{0.2em}\)となります。 このようにして、 \(\hspace{-0.2em}1\hspace{-0.2em}\hspace{0.2em}\) つ \(\hspace{-0.2em}\hspace{0.2em}1\hspace{-0.2em}\hspace{0.2em}\) つのビットのエラー率より最終的な計算結果が誤ったものになる確率を落とす技術が誤り訂正の技術です。 ここで、この訂正は計算中に何度でも行えることが大事です。もし、複雑な計算を行う際、最後にだけこの訂正を行おうとした時、（現在の古典ビットではすでにそこまで精度は低くないのですが、）それまでに起きるエラーの確率は大きかったとするとすでに手遅れ、すなわち、\(0\hspace{-0.2em}\hspace{0.2em}\) と \(\hspace{-0.2em}\hspace{0.2em}1\hspace{-0.2em}\hspace{0.2em}\) がランダムに混ざり合った状態になってしまいます。しかし、\(1\hspace{-0.2em}\hspace{0.2em}\) ステップ計算を行うたびに訂正を行えば、それぞれの段階でエラーが起きているビットの数は少なく、最終的なエラー率は小さくなり