論文の概要: QMA vs. QCMA and Pseudorandomness
- arxiv url: http://arxiv.org/abs/2411.14416v2
- Date: Fri, 22 Nov 2024 19:35:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 10:37:27.755183
- Title: QMA vs. QCMA and Pseudorandomness
- Title（参考訳）: QMA vs. QCMAと偽造
- Authors: Jiahui Liu, Saachi Mutreja, Henry Yuen,
- Abstract要約: そのようなオラクルは、ある量子擬ランダム性予想が成立するときに存在することを示す。
私たちの結果は、"Win-win"シナリオの確立と見なすことができます。
- 参考スコア（独自算出の注目度）: 5.483786291093505
- License:
- Abstract: We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating $\mathsf{QMA}$ from $\mathsf{QCMA}$. Settling this question in either direction would yield insight into the power of quantum proofs over classical proofs. We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Roughly speaking, the conjecture posits that quantum algorithms cannot, by making few queries, distinguish between the uniform distribution over permutations versus permutations drawn from so-called "dense" distributions. Our result can be viewed as establishing a "win-win" scenario: either there is a classical oracle separation of $\mathsf{QMA}$ from $\mathsf{QCMA}$, or there is quantum advantage in distinguishing pseudorandom distributions on permutations.
- Abstract（参考訳）: Aaronson と Kuperberg の長年にわたる疑問は、$\mathsf{QMA}$ と $\mathsf{QCMA}$ を分離する古典的なオラクルが存在するかどうかである。
この問題をどちらの方向にも設定すれば、古典的な証明に対する量子証明の力についての洞察が得られる。
そのようなオラクルは、ある量子擬ランダム性予想が成立するときに存在することを示す。
大まかに言うと、この予想は、量子アルゴリズムは、クエリをほとんど作ることによって、置換に関する均一分布といわゆる「密度」分布から引き出された置換との区別をできないと仮定している。
古典的なオラクル分離が$\mathsf{QMA}$から$\mathsf{QCMA}$から存在するか、あるいは置換上の擬似ランダム分布を区別する量子的優位性がある。
関連論文リスト
- Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。
この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
論文 参考訳（メタデータ） (2024-11-04T19:40:01Z) - Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。
我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2024-10-24T18:12:03Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Connecting classical finite exchangeability to quantum theory [69.62715388742298]
交換性は確率論と統計学の基本的な概念である。
有限交換可能な列に対するデ・フィネッティのような表現定理は、量子論と正式に等価な数学的表現を必要とすることを示す。
論文 参考訳（メタデータ） (2023-06-06T17:15:19Z) - Quantum Cryptography in Algorithmica [0.7524721345903025]
ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
論文 参考訳（メタデータ） (2022-12-01T21:33:38Z) - A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
量子複雑性理論において、$textitnon-deterministic$ 量子計算の定義が量子証人を必要とするかどうかという長い議論である。
本稿では,各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより,この問題を進展させる。
論文 参考訳（メタデータ） (2022-10-27T12:43:56Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Why we should interpret density matrices as moment matrices: the case of
(in)distinguishable particles and the emergence of classical reality [69.62715388742298]
一般確率論として量子論(QT)の定式化を導入するが、準観測作用素(QEOs)で表される。
区別不可能な粒子と識別不能な粒子の両方に対するQTをこの方法で定式化できることを示します。
古典的なダイスに対する有限交換可能な確率は、QTと同じくらい奇数であることを示す。
論文 参考訳（メタデータ） (2022-03-08T14:47:39Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳（メタデータ） (2021-03-16T20:54:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。