論文の概要: A distribution testing oracle separation between QMA and QCMA
- arxiv url: http://arxiv.org/abs/2210.15380v4
- Date: Sun, 31 Dec 2023 21:57:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 03:10:40.455930
- Title: A distribution testing oracle separation between QMA and QCMA
- Title（参考訳）: QMAとQCMAの分配試験オラクル分離
- Authors: Anand Natarajan and Chinmay Nirkhe
- Abstract要約: 量子複雑性理論において、$textitnon-deterministic$ 量子計算の定義が量子証人を必要とするかどうかという長い議論である。
本稿では,各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより,この問題を進展させる。
- 参考スコア（独自算出の注目度）: 0.6906005491572401
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: It is a long-standing open question in quantum complexity theory whether the
definition of $\textit{non-deterministic}$ quantum computation requires quantum
witnesses $(\textsf{QMA})$ or if classical witnesses suffice $(\textsf{QCMA})$.
We make progress on this question by constructing a randomized classical oracle
separating the respective computational complexity classes. Previous
separations [Aaronson-Kuperberg (CCC'07), Fefferman-Kimmel (MFCS'18)] required
a quantum unitary oracle. The separating problem is deciding whether a
distribution supported on regular un-directed graphs either consists of
multiple connected components (yes instances) or consists of one expanding
connected component (no instances) where the graph is given in an
adjacency-list format by the oracle. Therefore, the oracle is a distribution
over $n$-bit boolean functions.
- Abstract（参考訳）: 量子複雑性理論では、$\textit{non-deterministic}$の量子計算の定義が量子証人$(\textsf{QMA})$、または古典的目撃者がsuffice$(\textsf{QCMA})$を必要としているかどうかという長い問題である。
各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより、この問題を進展させる。
以前の分離 (Aaronson-Kuperberg (CCC'07), Fefferman-Kimmel (MFCS'18)) は量子ユニタリオラクルを必要とした。
分離問題は、正規の非方向グラフでサポートされている分布が複数の連結成分(yesインスタンス)で構成されているか、または1つの拡張連結成分(noインスタンス)で構成されているかを決定することである。
したがって oracle は $n$-bit boolean 関数上のディストリビューションである。
関連論文リスト
- 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - An optimal oracle separation of classical and quantum hybrid schemes [0.0]
任意の深さパラメータ$d$に対して、計算時間古典が許されるとき、量子深さ$d$と2d+1$を分離するオラクルが存在することを示す。
これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
論文 参考訳（メタデータ） (2022-05-10T02:31:19Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - 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) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳（メタデータ） (2021-11-04T16:52:58Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。