量子ビザンチン協定

ビザンチンフォールトトレラント プロトコルは、分散アルゴリズムにおける任意のタイプの障害に対して堅牢なアルゴリズムです。ビザンチン合意プロトコルはこのタスクの重要な部分です。ビザンチンプロトコルの定数時間量子バージョン^[1]については以下で説明します。

ビザンチン協定 プロトコルは、分散コンピューティングのプロトコルです。このプロトコルの名前は、1982 年に Lamport、Shostak、Pease によって定式化された問題に由来しています。 ^[2]この問題自体は歴史的な問題への言及です。ビザンチン軍は師団に分かれており、各師団は以下の特性を持つ将軍によって率いられていました。

• 各将軍はビザンチン国家に忠誠を誓う者か、あるいは裏切り者かのいずれかである。
• すべての将軍はメッセージを送受信することで通信します。
• コマンドは攻撃と撤退の 2 つだけです。
• 忠実な将軍たちは全員、攻撃か撤退かという同じ行動計画に同意するはずです。
• 悪い将軍のごくわずかな割合がプロトコルの失敗を引き起こすことはありません (割合未満)。${\displaystyle {\tfrac {1}{3}}}$

（不可能性の証明については^[3]を参照）。この問題は通常、指揮官である将軍と忠実な中尉の形で同等に言い換えられ、将軍は忠実か裏切り者であり、中尉については以下の特性がある。

• 忠実な中尉たちは全員同じ命令を実行します。
• 指揮官である将軍が忠実であれば、忠実な中尉は皆、将軍の命令に従います。
• 指揮官を含む少数は裏切り者です。${\displaystyle {\tfrac {1}{3}}}$

アルゴリズムまたはプロトコルの障害は、主に次の 3 つのタイプに分類できます。

1. アルゴリズム内の別の実行ステップを実行できないこと: これは通常、「フェールストップ」障害と呼ばれます。
2. 正しく実行されないランダムな障害: これは「ランダム障害」または「ランダム ビザンチン」障害と呼ばれます。
3. アルゴリズムが手順を正しく実行できないという任意の障害 (通常は、アルゴリズム全体を失敗させるような巧妙な方法で攻撃者が実行します) で、前の 2 種類の障害も含みます。これは「ビザンチン障害」と呼ばれます。

ビザンチン耐性またはビザンチンフォールトトレラントプロトコルまたはアルゴリズムは、上記のすべての種類の障害に対して堅牢なアルゴリズムです。たとえば、複数の冗長プロセッサを備えたスペースシャトルの場合、プロセッサが矛盾するデータを出力した場合、どのプロセッサまたはプロセッサセットを信頼すればよいでしょうか。このソリューションは、ビザンチンフォールトトレラントプロトコルとして定式化できます。

ここでは非同期アルゴリズム^[1]の概要を説明します。 アルゴリズムは2つのフェーズで動作します。

• フェーズ 1 (コミュニケーション フェーズ):

すべてのメッセージはこのラウンドで送受信されます。

コイン投げプロトコルは、互いに信頼関係のない 2 つの当事者 A と B がコインを投げて特定のオブジェクトを獲得できるようにする手順です。

コイン投げプロトコルには 2 つの種類があります。

• 弱いコイン投げプロトコル: ^[4] 2人のプレイヤーAとBは最初は何も入力せずに開始し、何らかの値を計算し、誰かが不正行為をしていると非難できるようにします。AとBが結果に同意すればプロトコルは成功です。結果0はAの勝利、1はBの勝利と定義されます。プロトコルには次の特性があります。 ${\displaystyle c_{A},c_{B}\in [0,1]}$
  • 両方のプレイヤーが正直であれば（プロトコルに従う場合）、 についてプロトコルの結果に同意します。${\displaystyle c_{A}=c_{B}}$${\displaystyle Pr(c_{A}=c_{B}=b)={\tfrac {1}{2}}}$${\displaystyle a,b\in \{0,1\}}$
  • プレイヤーの 1 人が正直である場合 (つまり、他のプレイヤーがローカル計算でプロトコルから任意に逸脱する可能性がある)、最大 の確率でもう一方のプレイヤーが勝ちます。言い換えると、B が不正直であれば であり、A が不正直であれば です。${\displaystyle {\tfrac {1}{2}}+\epsilon }$${\displaystyle Pr(c_{A}=c_{B}=1)\leq {\tfrac {1}{2}}+\epsilon }$${\displaystyle Pr(c_{A}=c_{B}=0)\leq {\tfrac {1}{2}}+\epsilon }$
• 強力なコイン投げプロトコル: 強力なコイン投げプロトコルでは、特定の値 0 または 1 から偏ったランダム ビットを生成することが目標です。明らかに、偏りのある強力なコイン投げプロトコルは、同じ偏りのある弱いコイン投げにつながります。${\displaystyle \epsilon }$

• 検証可能な秘密共有プロトコル: (n,k)秘密共有プロトコルでは、n 人のプレーヤーが秘密を共有し、k 人以上のプレーヤーの定足数だけが秘密を発見できるようにします。秘密を共有 (秘密のピースを配布) するプレーヤーは、通常、ディーラーと呼ばれます。検証可能な秘密共有プロトコルは、悪意のあるディーラーが存在する場合でも、プレーヤーが自分の共有が一貫していることを検証できるという点で、基本的な秘密共有プロトコルとは異なります。

1. ラウンド1では、量子ビット上にGHZ状態を 生成し、その一部を保持したまま、番目の量子ビットを番目のプレイヤーに送信する。${\displaystyle |\mathrm {コイン} _{i}\rangle ={\tfrac {1}{\sqrt {2}}}|0,0,\ldots ,0\rangle +{\tfrac {1}{\sqrt {2}}}|1,1,\ldots ,1\rangle }$${\displaystyle n}$ ${\displaystyle k}$${\displaystyle k}$
2. 1から までの数字の均等な重ね合わせである量子ビット（複数の量子ビットで構成される量子コンピューティングコンポーネント）上の状態を生成する。量子ビットをすべてのプレイヤーに分配する^[1]${\displaystyle |\mathrm {Leader} _{i}\rangle ={\tfrac {1}{n^{3/2}}}\sum \nolimits _{a=1}^{n^{3}}|a,a,\ldots ,a\rangle }$${\displaystyle n}$${\displaystyle n^{3}}$${\displaystyle n}$
3. すべてのプレイヤーから量子メッセージを受信し、次の通信ラウンドを待機して、どのメッセージが渡されたかを敵に選択させます。
4. ラウンド 2: ラウンド 1 で受信したすべての量子ビットを(標準ベースで) 測定します。最高のリーダー値を持つプレーヤー (同点の場合は任意に決定) をそのラウンドの「リーダー」として選択します。リーダーのコインを標準ベースで測定します。${\displaystyle \mathrm {Leader} _{j}}$
5. QuantumCoinFlip プロトコルの出力を設定します: = リーダーのコインの測定結果。${\displaystyle v_{i}}$

ランダムなコインを生成するには、各プレイヤーに [0,n-1] の範囲の整数を割り当てます。各プレイヤーは他のすべてのプレイヤーに対してランダムな番号を選択し、検証可能な秘密共有スキームを使用してこれを配布するため、各プレイヤーは独自のランダム ID を選択することはできません。 ${\displaystyle P_{k}}$${\displaystyle s{_{k}^{i}}}$${\displaystyle P_{i}}$

このフェーズの最後に、プレイヤーはどの秘密が適切に共有されたかについて合意し、秘密が公開され、各プレイヤーに値が割り当てられます。 ${\displaystyle P_{i}}$

${\displaystyle s_{i}=\sum \,{s_{k}^{i}}{\text{for all secrets properly shared}}\mod n}$

これには秘密情報チャネルが必要なので、ランダムな秘密を重ね合わせに置き換えます。重ね合わせでは、状態は量子検証可能秘密共有プロトコル (QVSS) を使用してエンコードされます。^[5]悪質なプレイヤーが状態を崩壊させることができるため、状態を配布することはできません。悪質なプレイヤーによる崩壊を防ぐために、量子検証可能秘密共有 (QVSS) を使用して状態をエンコードし、各プレイヤーに秘密の一部を送信します。ここでも検証にはビザンチン合意が必要ですが、合意をグレードキャストプロトコルに置き換えるだけで十分です。^{[6] [7]}${\displaystyle |\phi \rangle ={\tfrac {1}{\sqrt {n}}}\sum \nolimits _{a=0}^{n-1}|a\rangle }$${\displaystyle |\phi ,\phi ,\ldots \phi \rangle }$

^{グレードキャストプロトコルは、 [6]}の定義を用いると以下の特性を持つ。 非公式には、グレードブロードキャストプロトコルは「ディーラー」（ブロードキャストする人）と呼ばれる指定されたプレーヤーを持つプロトコルであり、次のようなものである。

1. ディーラーが優秀であれば、すべてのプレイヤーに同じメッセージが送られます。
2. ディーラーが下手だったとしても、何人かの優秀なプレイヤーがメッセージを受け入れれば、優秀なプレイヤー全員が同じメッセージを受け取ります (ただし、受け入れるかどうかはわかりません)。

プロトコル P は、プロトコルの開始時に指定されたプレーヤー D (ディーラーと呼ばれる) が値 v を保持し、プロトコルの終了時にすべてのプレーヤーが次の特性が満たされるペアを出力する場合、段階的ブロードキャストを達成していると言われます。 ${\displaystyle P_{i}}$${\displaystyle (\mathrm {value} _{i},\mathrm {confidence} _{i})}$${\displaystyle (\forall i,\mathrm {confidence} _{i}\in \{0,1,2\})}$

1. D が正直であれば、すべての正直なプレイヤーに対して= vかつ = 2 となります。${\displaystyle \mathrm {value} _{i}}$${\displaystyle \mathrm {confidence} _{i}}$${\displaystyle P_{i}}$
2. 任意の 2 人の正直なプレイヤーとについて。${\displaystyle P_{i}}$${\displaystyle P_{j},}$ ${\displaystyle \vert \mathrm {confidence} _{i}-\mathrm {confidence} _{j}\vert \leq 1}$
3. (一貫性) 任意の 2 人の正直なプレイヤーとについて、およびであれば、 となります。${\displaystyle P_{i}}$${\displaystyle P_{j}}$${\displaystyle \mathrm {confidence} _{i}>0}$${\displaystyle \mathrm {confidence} _{j}>0}$${\displaystyle \mathrm {value} _{i}=\mathrm {value} _{j}}$

QVSS プロトコルの検証段階では、良いディーラーの場合は正しい状態がエンコードされ、不良ディーラーの場合はリカバリ段階で特定の状態が回復されることが保証されます。ビザンチン量子コイン投げプロトコルの目的上、回復段階ははるかに単純であることに注意してください。各プレーヤーは QVSS の自分のシェアを測定し、古典的な値を他のすべてのプレーヤーに送信します。検証段階では、最大で 100 人の不良プレーヤーが存在する場合でも、すべての良いプレーヤーが同じ古典的な値 (エンコードされた状態を直接測定した場合に得られる値と同じ値) を回復することが高い確率で保証されます。 ${\displaystyle t<{\tfrac {n}{4}}}$${\displaystyle t<{\tfrac {n}{4}}}$

2007年には、4光子偏光エンタングルメント状態を用いてビザンチン合意の量子プロトコルが実験的に実証されました^[8]。これは、古典的なビザンチン合意プロトコルの量子実装が実際に実現可能であることを示しています。