Verifiable blind probabilistic error cancellation

あなたは、巨大で不可能なパズルを解こうとしていると想像してください。しかし、あなた自身にはそのピースもテーブルもありません。そこで、あなたは鍵のかかった部屋にいる見知らぬ人に、その作業を代行してもらうことにしました。これが「クラウド量子コンピューティング」の夢です。つまり、現在のマシンでは手に負えない問題を、強力で遠隔にある量子コンピュータに解かせることです。しかし、一つ問題があります。量子コンピュータは非常に壊れやすいのです。それはまるで繊細なガラスの彫刻のようで、強く見つめすぎたり、空気が乾燥していたりするだけで粉々に砕け散ってしまいます。この「ノイズ」はエラーを引き起こし、答えを信頼できないものにします。

これを解決するために、科学者たちは「確率的エラー打ち消し（Probabilistic Error Cancellation: PEC）」と呼ばれるトリックを開発しました。これは、数学におけるノイズキャンセリングヘッドホンのようなものです。もしノイズの正確なパターンを知っていれば、それを打ち消すための「逆の音」を再生して、クリアな信号を残すことができます。しかし、これは「逆の音」を作っている人物を信頼できる場合にのみ機能します。もし、鍵のかかった部屋にいる見知らぬ人がペテン師だったら、彼らはノイズを打ち消しているふりをして、実際にはあなたのパズルをめちゃくちゃにするかもしれません。あるいは、ノイズが何であるかについて嘘をつくかもしれません。これまで、その見知らぬ人が正直に作業を行い、実際にエラーを修正しているかどうかを確認する方法はありませんでした。この論文は、あなたが決して部屋の中を覗き見ることなく、その人物が正直であり、かつ実際にノイズを修正していることを保証する、超厳格で魔法のようなレフェリーとして機能する新しい手法を紹介しています。

---

問題点：信頼できない魔法の箱

例えば、あなたは量子コンピュータに「この新しい分子のエネルギーはいくらか？」といった質問をしたいとします。あなた自身のコンピュータでは十分な性能がないため、リモートサーバー（「サーバー」）に質問を送ります。しかし、そのサーバーは信頼できません。それは暴走したAIかもしれませんし、不具合のある機械かもしれません。あるいは、あなたを欺こうとしている悪意のある主体かもしれません。

これまでの科学者には、2つの対処法がありました：

1. ブラインド計算（Blind Computation）: あなたは指示を秘密のコードで送ることで、サーバーに何を計算しているのかを悟らせないようにできます。これにより、あなたの秘密は守られますが、もしサーバーが間違いを犯したり（あるいは嘘をついたり）した場合、それを知る術はありません。ただ、間違った答えを受け取るだけです。
2. エラー訂正（Error Correction）: ノイズを修正しようと試みることができます。しかし、標準的なエラー訂正には、現在のマシンには存在しない大量の「予備」の量子ビット（qubits）が必要です。

そこで登場したのが、**確率的エラー打ち消し（PEC）**です。これは巧妙なソフトウェアのトリックです。追加のハードウェアを必要とする代わりに、さまざまな「ノイズ打ち消し」の動きを混ぜながら、計算を何度も実行します。結果を平均化することで、数学的にノイズを差し引きます。問題は、PECはサーバーがノイズに対して正直であることを前提としている点です。もしサーバーが悪意を持っている場合、サーバーはノイズのパターンについて嘘をつくことができ、その結果、あなたの「打ち消し」はむしろ答えを「悪化」させてしまいます。サーバーがルールに従っていること、そして、それが打ち消しているノイズが本物であることを検証する方法が必要なのです。

解決策：VBPEC（魔法のレフェリー）

Bo Yang、Elham Kashefi、および Harold Ollivier の著者らは、**検証可能なブラインド確率的エラー打ち消し（Verifiable Blind Probabilistic Error Cancellation: VBPEC）**と呼ばれる新しいプロトコルを作成しました。これは、以下の3つを同時に実現する初めてのシステムです：

1. ブラインド性（Blindness）: サーバーはあなたが何を計算しているかを決して学習しません。
2. 検証可能性（Verification）: サーバーが不正を行わなかったことを数学的に証明できます。
3. エラー打ち消し（Error Cancellation）: サーバーは実際にノイズを修正し、より良い答えを提供します。

この魔法がどのように機能するかを、いくつかの比喩を使って説明します。

1. 量子の秘密を守る「ワンタイムパッド」

プロトコルがサーバーに対してブラインドであることを維持するために、「量子ワンタイムパッド（Quantum One-Time Pad）」と呼ばれるものを使用します。イメージとしては、メッセージをサーバーに送る際、すべての文字をランダムで解読不可能な封筒で包むようなものです。サーバーは封筒を開け、作業を行い、そして新しいランダムな封筒に入れて戻さなければなりません。封筒がランダムであるため、サーバーには単なる「意味不明な文字列」にしか見えません。サーバーは、それが分子のエネルギーを計算しているのか、単に10まで数えているのかさえ判別できません。これにより、完全なブラインド性が保証されます。

2. 混沌をサイコロ遊びに変える

著者らは素晴らしい発見をしました。ランダムな封筒（量子ワンタイムパッド）があるおかげで、サーバーが行おうとするいかなる間違いや不正も、特定の種類のランダムなエラーである「ストカスティック・パウリ・チャネル（stochastic Pauli channel）」へと書き換えられてしまうのです。
このように考えてみてください。もしサーバーがパズルのピースをねじ曲げることであなたを妨害しようとしても、ランダムな封筒によって、そのねじれは単純な「反転」（コインの表裏をひっくり返すようなもの）へと戻されてしまいます。サーバーはもう、凝ったことはできなくなります。サーバーができるのは、コインを投げる（反転させる）ことだけです。これは素晴らしいニュースです。なぜなら、コインの反転は追跡しやすく、打ち消しやすいからです。

3. 罠と統計テスト

では、嘘つきをどうやって捕まえるのでしょうか？ プロトコルは「罠（トラップ）」を使用します。イメージとしては、本物のパズルピースと、偽の「罠」のピースを混ぜてサーバーに送ります。罠のピースは、もしサーバーが正直であれば、特定の予測可能な場所に収まるように設計されています。もしサーバーが不正を行えば、罠は間違った場所に落ちます。

以前のプロトコルでは、単に罠がいくつ失敗したかを数えていました。もし失敗が多すぎれば、「ゲームオーバーだ、君は不正をした！」と判定していました。しかし、これは厳しすぎます。もしマシンが単に少しノイズが多いだけで（不正をしているのではなく）、そのせいでいくつかの罠が失敗した場合、正しい結果まで捨ててしまうことになるからです。

VBPECはゲームのルールを変えます。 単に失敗を数えるのではなく、罠の結果を使用して、ノイズがどれくらい発生しているかを正確に推定します。これは、シェフがスープを味見するようなものです。「塩辛すぎるから捨てろ」と言う代わりに、シェフは味を見て、「本来より10%塩分が高い」と判断します。そして、その知識を使ってレシピを調整します。

VBPECにおいて、クライアント（あなた）は罠の結果を使用して「ノイズマップ」を計算します。もしノイズマップがサーバーが行うべき内容と一致していれば、クライアントはその結果を受け入れます。もしノイズマップが奇妙な形（サーバーが嘘をついている状態）であれば、クライアントはそれを拒絶します。

大きな勝利：能動的なノイズキャンセリング

最もエキサイティングな部分は、サーバーが正直であるものの、マシンにノイズがある場合に起こります。

• 従来の方法: ノイズが高すぎると、プロトコルは結果を100%拒絶します。あなたは何も得られません。
• VBPECの方法: プロトコルはノイズを検知し、それが期待されるパターンと一致していることを確認した上で、能動的にそれを打ち消します。結果を受け入れ、修正された答えを提供します。

論文では、サーバーが正直であれば、より多くのラウンドを実行するにつれて、正しくノースキャンセルのされた答えを得られる確率がほぼ100%に達することを証明しています。たとえノイズモデルが完璧でなくても（例えば、マシンが想定とわずかに異なっていても）、その不一致が大きすぎない限り、プロトコルは十分に堅牢であり、動作し続けます。

これがあなたにとって何を意味するか

この論文は単に「これが機能する可能性がある」と言っているだけではありません。VBPECが**構成的に安全（composably secure）**であることを、厳密な数学的証明をもって示しています。これは、VBPECをより大きなシステムの構成要素として使用でき、そのセキュリティ保証が維持されることを意味します。

著者らは以下のことを示しています：

• 追加の量子ハードウェアを必要としません（「スペース・オーバーヘッド」なし）。
• コストは、計算を数回多く実行することだけです（これは新しいハードウェアを構築することに比べれば安価です）。
• あなたを騙そうとしているかもしれない見知らぬ人が所有するコンピュータであっても、その答えを信頼できます。

要約すると、VBPECは「信頼できない、ノイズの多い量子クラウド」を、リスクの高いギャンブルから、信頼できるツールへと変貌させます。これは、今日のノザイな量子コンピュータの現実と、暗号学の安全で完璧な世界との間の架け橋となります。これは、私たちが遠隔の量子コンピュータに世界で最も難しい問題を解かせるとき、その答えが真実であり、プライベートであり、かつ正しいものであると自信を持って確信できる時代への大きな一歩なのです。