A semi-definite programming formulation of the device-dependent guessing probability

本論文は、完全に特性化された準備・測定量子セットアップにおいて、固有のランダム性と攻撃者の推測確率を精密に推定するための半正定値計画法の定式化を導入し、それが厳密な証明可能なランダム性を決定できる能力を持つこと、およびもつれが攻撃者の予測能力を厳密に増大させることを明らかにしている。

要約

あなたは、帽子からウサギを取り出す手品を行っているところだと想像してください。量子力学の世界では、この「ウサギ」とは、微小な粒子を測定することで生成される乱数です。セキュリティの専門家にとっての大きな疑問は、**「このウサギは、どれほど真にランダムなのか？」**ということです。ずる賢い手品師（エヴァという名の攻撃者）が、トリックが行われる前に、帽子やウサギを細工して、次に何が出てくるかを正確に知ることができるのでしょうか？

この論文は、最も単純な種類の量子マジック（「準備と測定」の設定として知られるもの）に対して、その問いに答えるための、強力で新しい数学的ツールを紹介しています。

以下は、簡単な比喩を用いた、この論文の知見の解説です。

1. 問題点：「ブラックボックス」の謎

現実の世界では、私たちの量子デバイス（帽子とウサギ）は完璧ではありません。それらは、ノイズの混じったラジオのように、ノイズを含んでいます。

• 設定: アリス（正直なユーザー）は、特定の量子状態（ウサギ）を準備し、それを測定する（ウサギを取り出す）デバイスを持っています。彼女は、デバイスが「本来どうあるべきか」を知っています。
• 脅威: エヴァ（ハッカー）は、アリスよりも多くのことを知っている可能性があります。彼女は秘密の「カンニングペーパー」を持っていたり、デバイスとの隠れた接続を持っていたりして、結果を予測できるかもしれません。
• 困難さ: これまでは、エヴァがどれだけ予測できるかを正確に計算することは、形を変え続ける迷路を解くようなものでした。特にデバイスにノイズがある場合、一般的で簡単な方法で答えを見つけることはできませんでした。

2. 解決策：「魔法の計算機」（半正定値計画法）

著者らは、**半正定値計画法（SDP）**と呼ばれる新しい数学的なレシピを作成しました。

• 比喩: 霧に包まれた山脈の中で、最も高い地点を探そうとしていると想像してください。以前は、勘に頼って登るしかなく、頂上だと思っていても小さな谷に捕まってしまうことがありました。新しいSDP法は、山脈全体を一望できるドローンのようなもので、瞬時に正確な最高峰を教えてくれます。
• 役割: これは、量子デバイスの乱雑でノイズの多い現実を、クリーンで解ける数学の問題へと変換します。これにより、科学者は単なる「最善の推測」による上限ではなく、エヴァから守られていることが保証された「正確な」ランダム性を計算できるようになります。

3. 彼らが発見したこと（3つのテスト）

著者らは、自分たちの新しい計算機がどのように機能するかを確認するために、3つの異なるシナリオでテストを行いました。

• テストA：ノイズの混じった鏡
  ウサギと帽子（デポラリゼーション・ノイズ）の両方が「静電気（スタティック）」に覆われているシナリオを調査しました。

  • 結果: 彼らの計算機は、このセットアップのランダム性に関する以前の数学的な推測が、実は完璧であったことを確認しました。つまり、以前の推測が絶対的な限界であったことを証明したのです。

• テストB：漏れのある検出器
  検出器（ウサギを取り出す手）が時々怠慢であったり、効率が悪かったりする設定を調査しました。

  • 結果: 以前の手法では、「漏れ」は特定の単純な方法で行われると想定されていました。しかし、新しい計算機は、もしエヴァがより複雑な「漏れ」を利用できるほど巧妙であれば、以前の方法が考えていたよりも少し上手く予測できてしまうことを示しました。これは、以前の推定値が安全性を楽観的に見積もりすぎていた（安全性を過大評価していた）ことを意味します。

• テストC：マルチアウトカム（多出力）のトリック
  デバイスが多くの異なる結果（例えば、ウサギ、ハト、あるいはハトの卵を取り出すなど）を生み出せるトリックを調査しました。

  • 結果: 以前の理論では、測定デバイスを完全に信頼できるのであれば、無限のランダム性を生成できると主張していました。しかし、新しい計算機は、もしエヴァが測定デバイスに対して秘密のリンクを持つことが許されるならば、結果の選択肢が3つまたは4つを超えた時点で、その「無限のランダム性」は消滅することを示しました。その安全性は、デバイスが完全に隔離されていると仮定したことによる錯覚だったのです。

4. 大きな驚き：エンタングルメント（量子もつれ）はスーパーパワーである

最も興味深い発見は、エンタングルメント（粒子間の不気味なつながり）に関するものです。

• 古い仮定: 多くのセキュリティモデルは、状態を準備するデバイスと、それを測定するデバイスは別々であり、古典的な情報（電話での会話のようなもの）のみを共有していると想定しています。
• 新しい発見: 著者らは、もし準備デバイスと測定デバイスがエンタングルメント（量子的なつながり）の状態にあるならば、エヴァの予測能力が厳密に増加することを証明しました。
• 比喩: 二人のスパイが秘密のコードを当てるゲームをしていると想像してください。もし彼らが電話で話しているだけなら（古典的な相関）、90%の確率で当てることができます。しかし、もし彼らがテレパシーのリンクを共有しているなら（エンタングルメント）、91%の確率で当てることができます。そのわずか1%の差が、ハイステークスなセキュリティにおいては極めて重要になります。これは、この量子的なつながりがハッカーに不当な優位性を与えることを示した、最も単純な例です。

まとめ

この論文は、量子的なランダム性を測定するための、より優れた、より正直な「定規」を提供しています。それは以下のことを示しています：

1. 私たちは今、単純な量子乱数生成器の正確な安全性を計算できます。
2. 以前の手法は、デバイスが実際よりも単純である、あるいはより隔離されていると想定することで、安全性を過大評価していました。
3. もしデバイスが量子的な接続（エンタングルメント）を共有しているならば、ハッカーの力は増大します。つまり、これらのデバイスを構築する際には、さらに注意深くある必要があるのです。

著者らは、他の人々が自身の量子デバイスをテストできるように、この「計算機」のコードも公開しています。

技術概要

技術要約：デバイス依存型推測確率の半正定値計画法による定式化

問題提起
量子力学において、状態が観測量の固有状態ではない場合に測定によって生成される本質的なランダムネスは、量子乱数生成器（QRNG）のための基本的なリソースである。最も単純なQRNGのシナリオは、完全に特性化された（デバイス依存の）準備・測定（PM）セットアップ——すなわち、既知の状態 $\rho_S$ が既知の正の演算子値測定（POVM）$\{M^a_S\}$ によって測定される場合——を伴うが、認証可能なランダムネスの正確な量を定量化することは依然として困難である。

ランダムネスの標準的な操作的指標は、条件付き最小エントロピー $H_{\min}(A|E)$ であり、これは（量子サイド情報を持つアドバーサリである）イブが、測定結果を推測できる最大確率（$P_{\text{guess}}$）から導かれる。デバイス依存のシナリオでは、イブは、システムと、測定のナイマルク拡張に関与するあらゆる補助系の間の結合状態の純化（purification）を保持していると仮定される。先行研究 [4] で指摘されているように、この推測確率の計算には、測定のあらゆるナイマルク拡張およびイブがデバイスと共有し得るあらゆる相関に関する非凸最適化問題が伴う。一般に、この非凸問題を厳密に解くための一般的な計算手順は存在せず、研究者はしばしば上界に頼るか、あるいは（準備デバイスと測定デバイスの間のエンタングルメントを仮定しないといった）制限的な仮定に頼らざなければならなかった。

手法
著者らは、デバイス依存の推測確率が半正定値計画法（SDP）として再定式化できることを証明することで、この計算上のギャップに対処する。

1. 最適化の再定式化： 著者らは、$P_{\text{guess}}$ の定義を、システム・補助系空間上の射影測定（PVM）$\{\Pi^a_{SM}\}$ とイブの測定結果に関する最大化として開始する。サブノーマライズされた、イブの結果で条件付けられた状態を導入することにより、この問題は非可換多項式を含む形式へと再構成される。
2. SDPの構築： [5, 13] の手法を活用し、著者らは射影測定 $\{\Pi^a_{SM}\}$ を、システム・ヒルベルト空間の正規直交基底に関するブロック形式で表現する。これにより、一般化されたモーメント行列 $\Gamma_e$ の定義が可能となる。
3. 線形制約： 目的関数および物理的制約（既知の状態 $\rho_S$、既知のPOVM $\{M^a_S\}$、およびPVMの射影性・完全性との適合性）は、モーメント行列の係数の線形関数として表現される。
4. 完全性： 著者らは、このSDP緩和が単なる上界ではなく、推測確率の完全な特徴付けを与えることを証明する（定理1）。具体的には、SDPのいかなる実行可能解も、元の非凸問題の有効な物理的解に対応しており、したがって、このSDPは正確な最大推測確率を与える。

主な結果と応用
論文では、手法をベンチマークし、以前は上界しか分かっていなかった場面で正確なランダムネス値を決定するために、このSDP定式化を3つの特定のシナリオに適用している。

1. デポラライズされた状態と測定： 著者らは、量子ビット状態と測定の両方がデポラライジング・ノイズの影響を受けるセットアップを分析する。SDPの結果は [6] で導出された解析的な下界と一致しており、その解析的な下界がタイトであること、およびSDPが正確な認証可能ランダムネス量を正しく特定していることを確認している。
2. デポラライズされた状態と不完全な検出器： 量子コンピュータのための Berta と Brandão [7] によるスキームを再検討し、著者らは、特定の固定された拡張（[7] で行われているもの）を用いて推定されたランダムネスと、彼らのSDPによる無制限の最適化による比較を行う。彼らは、拡張を固定すると本質的なランダムネスがわずかに過大評価されることを見出し、あらゆる可能な拡張に対して最適化することの必要性を実証している。
3. 非特性化状態と等角測定： 著者らは、状態は非特性化されているが、測定は信頼された等角 $k$ 結果POVMである、ソース・デバイス独立スキーム [8] を調査する。著者らは、信頼された測定という仮定の下で $k > 3$ の場合に無制限のランダムネスが抽出可能であると [8] は主張しているが、もしイブが測定デバイスと相関を持つことが許される場合（すなわち、測定が完全には信頼されていない場合）、$k=4$ において認証可能なランダムネスは消失することを示す。これは、測定の信頼性の仮定が決定的な影響を与えることを浮き彫りにしている。

エンタングルメントと予測能力
この論文の重要な理論的貢献は、状態準備デバイスと測定デバイスの間のエンタングルメントが、イブの予測能力を厳密に高めることを示した点にある。

• 著者らは、推測確率 $P_{\text{guess}}$（システムと測定レジスタの間の可分状態に制約されない任意の相関を許容）と、$P^{\text{sep}}_{\text{guess}}$（可分状態に制約される）を比較している。
• 特定の量子ビット状態とバイナリ測定を用いて、$P_{\text{guess}} > P^{\text{sep}}_{\text{guess}}$ であることを示している。
• この結果は、準備デバイスと測定デバイスの間のエンタングルメントの不在を仮定すること（いくつかのフレームワークにおける一般的な簡略化）が、単一の量子ビットとバイナリ測定を含む最も初歩的なシナリオにおいてさえ、生成されるランダムネスを過大評価することにつながることを意味している。

意義と主張
本論文は、非凸最適化のヒューリスティックやデバイス相関に関する制限的な仮定に頼ることなく、デバイス依存のPMセットアップにおける本質的なランダムネスを推定するための、最初の一般的かつ計算効率の良い手法を提供すると主張している。

• 認証： SDPは、以前は上界のみが得られていたシナリオにおいて、認証可能なランダムネスの正確な決定を可能にする。
• 根本的な洞察： 本研究は、準備と測定の間のエンタングルメント支援が、アドバーサリの出力予測能力を高めるリソースであることを確立しており、これは単純なバイナリ測定のシナリオにおいても観察可能な結果である。
• 実用的な有用性： この手法は、ノイズの影響を受ける現実的な量子デバイスにおけるランダムネスを認証するための一般的なツールとして機能し、最も単純なデバイス依存型QRNGに対する厳密なレシピを提供する。

著者らは、彼らの定式化が、量子サイド情報が存在する中でのランダムネス生成の理解を進展させ、将来のランダムネス認証プロトコルのための堅牢なフレームワークを提供すると結論付けている。