論文の概要: Are uncloneable proof and advice states strictly necessary?

• arxiv url: http://arxiv.org/abs/2410.11827v1
• Date: Tue, 15 Oct 2024 17:53:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-16 14:01:49.407731
• Title: Are uncloneable proof and advice states strictly necessary?
• Title（参考訳）: 不当な証明とアドバイスは厳格に必要か?
• Authors: Rohit Chatterjee, Srijita Kundu, Supartha Podder,
• Abstract要約: 我々は、QMA、BQP/qpoly、FEQP/qpolyといった言語が、不可能な量子証明とアドバイスを必要とすることを示す。 われわれはQMAを、不可能な証明しか持たない言語と定義している。 また、Aaronson、Buhrman、Kretschmerによって使われている言語が、厳密に拘束不能なFEQP/qpolyであるようなオラクルを使わずに示す。
• 参考スコア（独自算出の注目度）: 0.14565169431855263
• License:
• Abstract: Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by $k$ separate polynomial-time verifiers, for arbitrary polynomial $k$. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.
• Abstract（参考訳）: そう、そうであるように示します。 我々は、必然的に不可避な量子証明とアドバイスを必要とする言語の研究を開始する。 クラス QMA, BQP/qpoly および FEQP/qpoly (これは多項式サイズの量子アドバイスと正確に解ける関係問題のクラスである) の厳密な非連結バージョンを定義する。 厳密に拘束不能なQMAは、QMAの言語のクラスとして定義されており、任意の証明状態の族が与えられた場合、多項式時間クローンアルゴリズムは、任意の多項式$k$に対して$k$別の多項式時間検証器で共同で使用可能な状態を生成することができない。 これは以前の研究で考慮されたものよりも厳密な証明とアドバイスという概念であり、それは従わない証明や助言の1つの族の存在しか必要としなかった。 量子オラクルモデルでは、厳密な拘束不能なQMAと厳密な拘束不能なBQP/qpolyに言語が存在することを示す。 厳密な独立性 QMA の言語はまた、Nehoran と Zhandry (2024) によって導入された QMA とクラスクローン性 QMA の間の量子オラクル分離を与える。 また、この言語がFEQP/qpolyとFBQP/polyを分離するためにAaronson, Buhrman, Kretschmer (2024) が使用したオラクルを使わずに示す。

関連論文リスト

• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• Can a Multichoice Dataset be Repurposed for Extractive Question Answering? [52.28197971066953]
  我々は,Multiple-choice Question answering (MCQA)のために設計されたBandarkar et al.(Bandarkar et al., 2023)を再利用した。 本稿では,英語と現代標準アラビア語(MSA)のためのガイドラインと並列EQAデータセットを提案する。 私たちの目標は、ベレベレにおける120以上の言語変異に対して、他者が私たちのアプローチを適応できるようにすることです。
  論文  参考訳（メタデータ） (2024-04-26T11:46:05Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• A Qubit, a Coin, and an Advice String Walk Into a Relational Problem [1.9260081982051918]
  PSPACE が NP/poly に含まれない限り, FBPP は FP/poly に含まれない。 この分離が「情報優位性」を示す実験の可能性をいかに高めるかについて議論する。 我々の証明はIP=PSPACEと時間境界コルモゴロフ複雑性を用いる。
  論文  参考訳（メタデータ） (2023-02-20T21:55:47Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Learn to Explain: Multimodal Reasoning via Thought Chains for Science Question Answering [124.16250115608604]
  本稿では,SQA(Science Question Answering)について紹介する。SQA(Science Question Answering)は,21万のマルチモーダルな複数選択質問と多様な科学トピックと,それに対応する講義や説明による回答の注釈からなる新しいベンチマークである。 また,SQAでは,数ショットのGPT-3では1.20%,微調整のUnifiedQAでは3.99%の改善が見られた。 我々の分析は、人間に似た言語モデルは、より少ないデータから学習し、わずか40%のデータで同じパフォーマンスを達成するのに、説明の恩恵を受けることを示している。
  論文  参考訳（メタデータ） (2022-09-20T07:04:24Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  量子計算のための古典的簡潔な対話的引数(BQP)を構築する。 我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
  論文  参考訳（メタデータ） (2022-06-29T22:19:12Z)
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle [0.0]
  最近の研究は、量子信号処理(QSP)とそのマルチキュービットリフトバージョン、量子特異値変換(QSVT)を示している。 QSVTは、ほとんどの量子アルゴリズムの表現を変換し改善する。
  論文  参考訳（メタデータ） (2022-05-12T17:58:59Z)
• 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 Büchi Automata [4.998632546280976]
  QBAが認識する$omega$-Languagesのクラスを、ほぼ確実に、厳密で非制限しきい値セマンティクスで紹介する。 QBAによって認識される$omega$-Languageの少なくとも4つの実質的に異なるクラスしか存在しないことが示されている(数えきれないほど無限である)。 従来の$omega$-LanguagesとQBAsの関係は,ポンプ補題を用いて明らかにした。
  論文  参考訳（メタデータ） (2018-04-24T12:23:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。