論文の概要: Oracle separation of QMA and QCMA with bounded adaptivity
- arxiv url: http://arxiv.org/abs/2402.00298v1
- Date: Thu, 1 Feb 2024 03:18:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-02 16:50:14.193804
- Title: Oracle separation of QMA and QCMA with bounded adaptivity
- Title（参考訳）: 有界適応性を持つQMAとQCMAのOracle分離
- Authors: Shalev Ben-David and Srijita Kundu
- Abstract要約: 本稿では, 量子アルゴリズムにおけるQMAとQCMAのオラクル分離について述べる。
そこで本研究では,QMA と QCMA の完全古典的オラクル分離を行う上で有用な,Emphslipperiness という関係性を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give an oracle separation between QMA and QCMA for quantum algorithms that
have bounded adaptivity in their oracle queries; that is, the number of rounds
of oracle calls is small, though each round may involve polynomially many
queries in parallel. Our oracle construction is a simplified version of the
construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who
showed an oracle separation between QMA and QCMA when the quantum algorithms
are only allowed to access the oracle classically. To prove our results, we
introduce a property of relations called \emph{slipperiness}, which may be
useful for getting a fully general classical oracle separation between QMA and
QCMA.
- Abstract（参考訳）: 量子アルゴリズムにおけるQMAとQCMAの分離を、その量子アルゴリズムにおいて有界適応性を持つ場合、すなわち、各ラウンドは多項式的に多くのクエリを並列に含むが、オラクル呼び出しのラウンド数は小さくなる。
我々のオラクル構築は、最近Li, Liu, Pelecanos, Yamakawa (2023) が用いた、量子アルゴリズムが古典的にのみ、QMAとQCMAのオラクル分離を示した簡易版である。
この結果を証明するために,QMAとQCMAの完全古典的オラクル分離に有用な「emph{slipperiness}」という関係性を導入する。
関連論文リスト
- Toward Separating QMA from QCMA with a Classical Oracle [10.699704508276174]
QMAは効率的な量子検証器によって決定できる言語のクラスであり、QCMAは効率的な量子検証器が古典的な証人しか与えられない言語のクラスである。
量子クエリ複雑性における挑戦的な基本的なゴールは、これらのクラスに対する古典的なオラクル分離を見つけることである。
論文 参考訳（メタデータ） (2024-11-04T00:18:06Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Classical vs Quantum Advice and Proofs under Classically-Accessible
Oracle [10.063768056247591]
BQP/qpoly $neq$BQP/poly および QMA $neq$QCMA の古典的アクセス可能な古典的オラクルを構築する。
ここでは、古典的アクセス可能な古典的オラクルは、量子アルゴリズムでさえも古典的にのみアクセス可能なオラクルである。
論文 参考訳（メタデータ） (2023-03-08T00:30:07Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - 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) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - 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) - Verified Compilation of Quantum Oracles [10.942063551929914]
VQOは高保証量子プログラミングフレームワークである。
OQASMはオラクル量子アセンブリ言語である。
VQOのバージョンはクイッパーによって作られた(キュービット数とゲート数の両方で)オーラクルと同等かそれ以上であった。
論文 参考訳（メタデータ） (2021-12-13T14:36:36Z) - Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs.
Coded Systems [69.33243249411113]
パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。
我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
論文 参考訳（メタデータ） (2020-12-15T15:51:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。