論文の概要: Complexity Theory for Quantum Promise Problems
- arxiv url: http://arxiv.org/abs/2411.03716v2
- Date: Mon, 07 Apr 2025 03:05:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-08 17:32:55.581337
- Title: Complexity Theory for Quantum Promise Problems
- Title（参考訳）: 量子約束問題に対する複素性理論
- Authors: Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih,
- Abstract要約: p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, p/mPSPACEの構造結果を示す。
驚いたことに、我々の発見は、彼らの古典的な類推から分岐する関係を明らかにした。
応用においては、量子暗号、量子特性試験、およびユニタリ合成における興味深い問題に対処する。
- 参考スコア（独自算出の注目度）: 5.049812996253858
- License:
- Abstract: We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, $\text{p/mQSZK}_{\text{hv}}$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE. This includes identifying complete problems, as well as proving containment and separation results among these classes. Here, p/mC denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C. Surprisingly, our findings uncover relationships that diverge from their classical analogues -- specifically, we show unconditionally that p/mQIP$\neq$p/mPSPACE and p/mBQP/qpoly$\neq$p/mBQP/poly. This starkly contrasts the classical setting, where QIP$=$PSPACE and separations such as BQP/qpoly$\neq$BQP/poly are only known relative to oracles. For applications, we address interesting questions in quantum cryptography, quantum property testing, and unitary synthesis using this new framework. In particular, we show the first unconditional secure auxiliary-input quantum commitment with statistical hiding, solving an open question in [Qia24,MNY24], and demonstrate the first pure quantum state property testing problem that only needs exponentially fewer samples and runtime in the interactive model than the single-party model, which is analogous to Chiesa and Gur [CG18] studying interactive mode for distribution testing. Also, our works offer new insights into Impagliazzo's five worlds view. Roughly, by substituting classical complexity classes in Pessiland, Heuristica, and Algorithmica with mBQP and mQCMA or $\text{mQSZK}_\text{hv}$, we establish a natural connection between quantum cryptography and quantum promise complexity theory.
- Abstract（参考訳）: p/mBQP, p/mQ(C)MA, $\text{p/mQSZK}_{\text{hv}}$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, p/mPSPACE。
これには、完全な問題を特定することや、これらのクラス間での包含と分離の結果を証明することが含まれる。
特に、p/mQIP$\neq$p/mPSPACE と p/mBQP/qpoly$\neq$p/mBQP/poly が無条件であることを示す。
QIP$=$PSPACE や BQP/qpoly$\neq$BQP/poly のような分離は、オラクルに対してのみ知られている古典的な設定とは対照的である。
アプリケーションでは、量子暗号、量子プロパティテスト、およびこの新しいフレームワークを用いたユニタリ合成に関する興味深い疑問に対処する。
特に, 統計的隠蔽による最初の無条件安全な補助入力量子コミットメントを示し, [Qia24,MNY24] のオープン質問を解くとともに, 分散テストのインタラクティブモードを研究するChiesa と Gur [CG18] に類似した, 対話モデルにおいて指数関数的に少ないサンプルと実行時間しか必要としない最初の純粋量子状態特性試験問題を実証する。
また、Impagliazzoの5つの世界観に関する新たな洞察も提供しています。
概して、ペシランド、ヒューリスティック、アルゴリズムの古典的複雑性クラスを mBQP と mQCMA または $\text{mQSZK}_\text{hv}$ で置換することにより、量子暗号と量子約束複雑性理論の間の自然な関係を確立する。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - 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 algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文 参考訳（メタデータ） (2023-09-28T13:30:20Z) - QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
我々は、ニューラルネットワークの量子対する最も有望な候補として登場した変分量子回路(VQC)に注目した。
有望な結果を示す一方で、バレン高原、重みの周期性、アーキテクチャの選択など、さまざまな問題のために、VQCのトレーニングは困難である。
本稿では,VQCの重みとアーキテクチャの両方を最適化するために,自然進化にインスパイアされた勾配のないアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-14T08:03:20Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
クラスNP合成における状態合成法について検討した。
我々は、最も自然な候補者の1つであるUQMA目撃者の家族が国家QMAであることを確認した。
状態QCMAが完全性を達成することを実証する。
論文 参考訳（メタデータ） (2023-03-03T12:14:07Z) - stateQIP = statePSPACE [0.15229257192293197]
本研究では,SDPPSPACEと状態QIPの2つの状態クラスの関係について検討する。
私たちの主な結果は、リバースインクルージョン、stateQIP $subseteq$ statePSPACEです。
また、一般的な量子対話プロトコルの最適証明戦略を量子空間で実装できることも示している。
論文 参考訳（メタデータ） (2023-01-18T19:00:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Computational Complexity -- From Quantum Information to Black
Holes and Back [0.0]
ホログラフィック辞書の新しいエントリとして量子計算の複雑さが提案された。
汎用量子システムの複雑性を定義するためにどのように使用できるかを示す。
カオスシステムにおける複雑性、カオス、スクランブルの関係を強調します。
論文 参考訳（メタデータ） (2021-10-27T18:00:12Z) - Quantum Meets the Minimum Circuit Size Problem [3.199102917243584]
量子環境における最小回路サイズ問題(MCSP)について検討する。
MCSPはブール関数の回路複雑性を計算する問題である。
これらの問題はNPではなくQCMA(あるいはQCMAプロトコル)にあることを示す。
論文 参考訳（メタデータ） (2021-08-06T15:34:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。