Open arxiv-quration-bot[bot] opened 4 months ago
量子もつれは量子力学の基本的な性質であり、量子計算や量子情報において重要な役割を果たしている。本研究では、複数のもつれない量子証明を持つNPクラスの量子一般化、いわゆるQMA(2)とその変種を考えることで、計算複雑度のレンズを通してもつれを研究する。QMA(2)の複雑性は長年の未解決問題であり、QMA $subseteq$ QMA(2) $subseteq$ NEXPという些細な境界のみが知られている。 本研究では、$text{QMA}^+(2)$と呼ぶ、非負振幅を持つ単一量子証明の力を研究する。この設定では、対数サイズの量子証明を使用し、「はい」インスタンスと「いいえ」インスタンスの区別に一定の確率ギャップを持つ問題に対する証明検証プロトコルを設計することができる。特に、小集団展開、一意ゲーム、PCP検証のための大域的プロトコルを設計する。その結果、一定のギャップを持つNP $subseteq \text{QMA}^+_{log}(2)$ が得られる。この新しい定数ギャップのおかげで、この結果を$text{QMA}^+(2)$にスケールアップすることができ、NEXPに対するPCPのより強い明示性を確立することにより、$text{QMA}^+(2)$=NEXPの完全な特徴を得る。 これらのプロトコルの重要な新規性の一つは、一定のギャップをもたらす大域的かつ首尾一貫した方法で量子証明を操作することです。これまでのプロトコル（一般的な振幅に対してのみ利用可能）は、局所的でギャップが非常に小さいか、量子証明を古典的な確率分布として扱い、多項式的に多くの証明を必要とするため、QMA(2)の非自明な境界を示唆するものではありませんでした。 最後に、QMA(2)は$text{QMA}^+(2)$と等しいが、後者のギャップが十分大きい定数であることを示す。特に、$text{QMA}^+(2)$がギャップ増幅を認めるなら、QMA(2)=NEXPである。
http://arxiv.org/abs/2402.18790v1 (ar5iv, pdf)
Fernando Granha Jeronimo, Pei Wu
2024/02/29
Summary (DeepL訳)
量子もつれは量子力学の基本的な性質であり、量子計算や量子情報において重要な役割を果たしている。本研究では、複数のもつれない量子証明を持つNPクラスの量子一般化、いわゆるQMA(2)とその変種を考えることで、計算複雑度のレンズを通してもつれを研究する。QMA(2)の複雑性は長年の未解決問題であり、QMA $subseteq$ QMA(2) $subseteq$ NEXPという些細な境界のみが知られている。 本研究では、$text{QMA}^+(2)$と呼ぶ、非負振幅を持つ単一量子証明の力を研究する。この設定では、対数サイズの量子証明を使用し、「はい」インスタンスと「いいえ」インスタンスの区別に一定の確率ギャップを持つ問題に対する証明検証プロトコルを設計することができる。特に、小集団展開、一意ゲーム、PCP検証のための大域的プロトコルを設計する。その結果、一定のギャップを持つNP $subseteq \text{QMA}^+_{log}(2)$ が得られる。この新しい定数ギャップのおかげで、この結果を$text{QMA}^+(2)$にスケールアップすることができ、NEXPに対するPCPのより強い明示性を確立することにより、$text{QMA}^+(2)$=NEXPの完全な特徴を得る。 これらのプロトコルの重要な新規性の一つは、一定のギャップをもたらす大域的かつ首尾一貫した方法で量子証明を操作することです。これまでのプロトコル（一般的な振幅に対してのみ利用可能）は、局所的でギャップが非常に小さいか、量子証明を古典的な確率分布として扱い、多項式的に多くの証明を必要とするため、QMA(2)の非自明な境界を示唆するものではありませんでした。 最後に、QMA(2)は$text{QMA}^+(2)$と等しいが、後者のギャップが十分大きい定数であることを示す。特に、$text{QMA}^+(2)$がギャップ増幅を認めるなら、QMA(2)=NEXPである。
Links
http://arxiv.org/abs/2402.18790v1 (ar5iv, pdf)
Authors
Fernando Granha Jeronimo, Pei Wu
Published
2024/02/29