論文の概要: A Separation Between Types of Quantum Oracle Separations

• arxiv url: http://arxiv.org/abs/2609.38704v1
• Date: Wed, 30 Sep 2026 00:33:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:26.877784
• Title: A Separation Between Types of Quantum Oracle Separations
• Title（参考訳）: 量子Oracle分離のタイプ別分離
• Abstract要約: 最近の研究は、量子オラクルが微妙な振舞いを持つことを示した。 これらの研究に触発されて、量子相対論のメタ複雑性の概念を導入する。
• 参考スコア（独自算出の注目度）: 3.142615022616392
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.
• Abstract（参考訳）: 近年の研究では、逆、共役、制御されたクエリへのアクセスは、特定のタスクのクエリの複雑さを指数関数的に変化させる可能性があるため、量子オラクルが微妙な振る舞いを持つことを示した。 これらの研究に触発されて、量子相対論のメタ複雑性の概念を導入する。 量子オラクルの「型」が等しいか、分離しているかという2つの量子複雑性クラスについて、我々は問う。 オラクルの異なるパンテオン(または量子オラクル型、例えばユニタリ対状態、多対超多次元)は、複雑性クラスを分離する力に基づく部分順序集合を形成する。 さらに、2つのオラクル・パンテオン A と B は、パンテオン A からオラクルの下に分離されているが、複雑性類がパンテオン B から全てのオークルの下で同値であるときに分離される。我々は、このメタ複雑度が、この論文で定義されたオラクル・パンテオンの族の中で完全な分類を与えることによって非自明であることを示し、このモデルが複雑性類 $\mathsf{PostBQP}$ と $\mathsf{PreciseBQP}$ を分離することができる。 どちらのクラスも非相対的な設定で$\mathsf{PP}$と等しい。 我々の分類学では、それらは実または多項式次元のユニタリオラクルと同等であり、逆アクセスや共役アクセスが供給されるときは常に等しい。 対照的に、スーパーポリノミカル次元の前方のみの複素対角ユニタリに対する分離と、単一量子状態準備オラクルに対する分離を与える。 我々はこれを、量子複雑性クラスの相対化に固有の微妙さを裏付けるオラクルのメタ複雑度のテストケースと見なしている。

関連論文リスト

• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
  量子暗号プリミティブの最初のメタ複雑性のキャラクタリゼーションを証明した。 片方向パズルが存在することは、カルモゴロフ複雑性を近似することが困難であるような二進弦の量子サンプリング可能な分布が存在する場合に限る。
  論文  参考訳（メタデータ） (2024-10-07T12:29:27Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。 この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。 すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
  論文  参考訳（メタデータ） (2023-12-28T18:53:21Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• 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)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  OTOC-RE定理(OTOC-RE theorem)は、作用素の完備な基底にまとめられたOTOCを第二レニイエントロピー(Renyi entropy)に関連付ける定理である。 関係作用素の小さな集合に対する和は、エントロピーの非常によい近似を得るのに十分であることを示す。 逆に、これは複雑性の別の自然な指標、すなわち時間と関連する演算子の数のスケーリングを提供する。
  論文  参考訳（メタデータ） (2020-07-31T19:23:26Z)

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

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