本記事は、何であって、何ではないか
何であるか：誤り訂正符号がわからない人、量子コンピュータがわからない人に向けた、量子削除誤り訂正符号の背景の説明
何ではないか：深淵な量子削除誤り訂正符号の数学的説明や厳密な説明ではない
ちゃんとした議論は、千葉大の萩原先生の資料を見てください。
https://www.jstage.jst.go.jp/article/transfun/advpub/0/advpub_2024TAI0001/_article
量子コンピュータにおける誤り訂正の必要性
量子コンピュータは、古典コンピュータでは到底実行できない大規模な計算を高速に解けることが期待されています。
このような高速なコンピュータとしては、アナログコンピュータと呼ばれる、物理法則を利用して時間発展させることで解を得る方法もあります。
しかしアナログコンピュータは、一般には、誤り訂正を実現できないため、スケールしないという問題があります。
量子コンピュータは、アナログコンピュータに似ていながらも、誤り訂正(冗長化と確実な誤り検出）を実現できる「デジタル性」を併せ持ちます。
これにより、デバイス単位では誤りを起こしたとしても、誤り訂正を用いることで大規模な計算を実行可能となります。
例えば$10^{-2}$の誤り率であっても、十分巨大な冗長化を行えば、その誤り訂正後の誤り率は$10^{-10}$まで落とすことも可能です。
つまり量子コンピュータの実現は、誤り訂正が大前提ということになります。
そうでなければ、ほかのアナログコンピュータと同じように、計算がスケールすることはなく、したがって古典コンピュータで実行できる程度の問題しか扱えなくなってしまうからです。
量子コンピュータにおける誤り
誤り訂正のための冗長化と誤り検出の手法(つまり符号設計)は、どのように誤るかの影響を強く受けます。
例えば、誤る頻度だけでも
- ほぼランダムに誤る
- 集中的に誤る(バーストエラー)
が考えられます。例えば、QRコードにおけるコーヒーの染みは、バーストエラーとなります。
あるいは、通信プロトコルにおける同期はずれや、逐次処理において初っ端で「コケる」場合は、バーストエラーが生じがちです。
バーストエラー対策としては、事前にビットを拡散しておくインターリーブが基本的ですが、それでも訂正できない場合にバーストエラー訂正に強い符号を用いることが重要です。
そのようなものとしては、リードソロモン符号と呼ばれる多元符号が知られており、QRコードや、一部の通信方式に採用されています。
加えて、誤り方 でもいろいろ考えられます。
例えばデジタル通信0,1,0,1...の場合、ビット反転誤り0→1, 1→0 はすぐ思いつきますね。
量子コンピュータでもこのような誤り方は存在します。
でも、0か1か判別できない状態(例えば何も受信できなかった場合)は"?"に化けてしまうことも考えられます。
(これはパンクチャリングと呼ばれる符号化のテクニックでも登場します）
0でも1でもないような状態、例えば"2"に化けてしまうことも考えられます。
これは量子コンピュータではlekage errorと呼ばれるエラーです。
さて、まだ面白い誤りパターンが考えられます。
それは、bitが消えてしまい、かつ消えてしまった位置が短縮されてしまった場合です！
例えば "0110" に対して、上から2番目のbitが削除(Deletion)したとすると、"010"となります。
消えたぶん詰められているので、bit長が変わってしまっています。
これを削除誤りといいます。
削除誤りの場合、「どこが消えてもいいように符号を作って起き、必ず元に戻せる」ということが重要です。
つまり、上記の例だと、「どこが消えたかわからない3桁のbitが与えられ、そこから正確に元の4桁のbitに戻せる」ことが必要となります。
そのような符号は削除誤り訂正符号と呼ばれ、VT符号などの例があるそうです。
消失と対になる概念として、挿入誤りがあります。
例えば "0110" に対して、上位1番目に新たなbit 1 が挿入;Insertionしたとすると、"10110"となります。
このような削除誤りや挿入誤りがどのようなシステムで重要となるかは、ビット反転誤りほど自明ではないと思われますが、いくつかの適用先が検討されているようです。
さてさて、削除誤り（や挿入誤り）が量子コンピュータで起きた場合、それは訂正可能でしょうか？
つまり量子削除誤り訂正符号は構成可能でしょうか？
量子削除誤り訂正符号は構築可能である
この問いに、（少なくとも第一歩となる）答えを与えたのが萩原先生です。
量子削除誤りの場合、量子ビットが”消失"することになります。
これは、その量子ビットが「見ても仕方がない」ような状態になったことに相当していて、量子情報の言葉では「部分トレース」に相当します。
この表現をうまく使うことで、例えば1量子ビットが"消失"する誤りに対して、それがどの量子ビット位置であったとしても、もとに戻せるような符号の存在と、その構成が具体的に構築されました。
めでたしめでたし
未解決問題
・・・というわけがなくて、未解決問題が無数にあります。
その中には、古典的な削除誤り訂正符号でみられるものの量子対応もありますし、量子ならではのものもあるでしょう。
まずは萩原先生の解説から抜粋していきます。
訳が間違っているかもしれないので、詳細は資料を見てください。
論文で提案されている未解決問題
(古典符号では、削除誤り訂正符号と挿入誤り訂正符号の等価性が知られている。量子でも同じ原理が成り立つのか？）
(量子削除誤り訂正符号と量子挿入誤り訂正符号の理論フレームワーク(一般論)を構築せよ)
(量子削除誤り訂正符号を設計するための代数的な方法論を記述できるか)
(量子削除誤り訂正符号の限界を与えよ）
(並び替え不変な1量子ビット削除誤りを訂正できる、4量子ビットの符号は存在するか?)
ここで、限界 は「その符号(あるいは同類の符号が)満たす不等式」とされています。
例えば、1量子ビット削除誤り訂正を実現できる符号のうち、最も冗長度の小さいものは何か？という問題が考えられます。少なくとも4量子ビットへの冗長化は必要だそうです。これを一般化すると難しそうですね。。
(大きな系の部分系で削除誤りが起きた時、部分系の削除誤り訂正を行いながら、全体系に影響を与えないような方法は存在するか？）
(部分系へ削除誤り訂正を適用する前に、それと相互作用があるかもしれない外部系へ量子操作を行ってしまった場合でも、部分系の削除誤り訂正は機能させられるか？)
つまり、削除誤り訂正符号は、それと相互作用（量子もつれなど）する系と”独立”させられるか ということですね。
僕の思う面白い問題
まだまだ面白い問題が考えられそうです。
思うに、量子ビット反転誤りのような符号で要求される仕様を、削除誤り訂正符号は満たせるのか？という観点があります。
量子ビット削除誤り訂正符号化をしたまま、論理ゲート操作をする方法は存在するか?それは量子コンピュータの高速性を失うことなく効率的に行えるか?
ビット反転誤りでは、スタビライザ符号と、論理ゲートとしてクリフォードゲートだけを許せば、誤り訂正符号化したまま演算ができることが知られています。それの対応物です。トランスバーサル性を満たせるか？とかも難問そうですね。
そのような論理ゲートだけで、万能計算ができるか?
ビット反転誤りの場合、非クリフォードゲートが難問になるわけです（魔法状態を使うことで回避する）
隣接量子ビット間のCNOT演算のみで、量子削除誤り訂正符号は構成できるか?
表面符号の対応物です。
誤り訂正操作を、量子ゲートではなく、古典事後処理に置換できる条件は存在するか？
Pauli frameの対応物です。実用上、重要と考えています。
訂正操作を効率的に（指数時間ではなく）確定できるか?
誤り訂正に必要な操作の列を求める問題です。表面符号だと最小重みマッチングかな。
確率的に起きる削除誤りに対して、訂正性能はどうなるか?
必ず1量子ビットが削除されるのではなく、確率的に、1個(以上)の量子ビットが削除されてしまうような状況です。
誤り訂正操作を求める処理または復号操作を並列化できるか?
並列できると処理時間が減らせるのでうれしいことが多いですね。
軟復号は存在するか?有効か?
削除が軟値(削除"度合い")ってよく意味わかんないですけど。。
まとめ
量子削除誤り訂正符号はブルーオーシャン！