論文の概要: Complexity Theory for Quantum Promise Problems
- arxiv url: http://arxiv.org/abs/2411.03716v1
- Date: Wed, 06 Nov 2024 07:29:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-07 19:22:34.874306
- Title: Complexity Theory for Quantum Promise Problems
- Title（参考訳）: 量子約束問題に対する複素性理論
- Authors: Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih,
- Abstract要約: 本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
- 参考スコア（独自算出の注目度）: 5.049812996253858
- License:
- Abstract: Quantum computing introduces many problems rooted in physics, asking to compute information from input quantum states. Determining the complexity of these problems has implications for both computer science and physics. However, as existing complexity theory primarily addresses problems with classical inputs and outputs, it lacks the framework to fully capture the complexity of quantum-input problems. This gap is relevant when studying the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework, as characterizing the security of quantum cryptographic primitives requires complexity classes for problems involving quantum inputs. To bridge this gap, we examine the complexity theory of quantum promise problems, which determine if input quantum states have certain properties. We focus on complexity classes p/mBQP, p/mQ(C)MA, $\mathrm{p/mQSZK_{hv}}$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states corresponding to any classical class C. We establish structural results, including complete problems, search-to-decision reductions, and relationships between classes. Notably, our findings reveal differences from classical counterparts, such as p/mQIP $\neq$ p/mPSPACE and $\mathrm{mcoQSZK_{hv}} \neq \mathrm{mQSZK_{hv}}$. As an application, we apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or $\mathrm{mQSZK_{hv}}$. We also show that the average-case hardness of $\mathrm{pQCZK_{hv}}$ implies the existence of EFI. These results provide new insights into Impagliazzo's worlds, establishing a connection between quantum cryptography and quantum promise complexity theory. We also extend our findings to quantum property testing and unitary synthesis, highlighting further applications of this new framework.
- Abstract（参考訳）: 量子コンピューティングは物理学に根ざした多くの問題を導入し、入力量子状態から情報を計算するよう要求する。
これらの問題の複雑さを決定することは、コンピュータ科学と物理学の両方に影響を及ぼす。
しかし、既存の複雑性理論は主に古典的な入力と出力の問題に対処するので、量子インプット問題の複雑さを完全に捉えるための枠組みが欠如している。
このギャップは、量子暗号と複雑性理論の関係を研究する際に、特にImpagliazzoの5つの世界の枠組みにおいて、量子暗号プリミティブのセキュリティを特徴づけるためには、量子入力に関わる問題に対する複雑性クラスが必要である。
このギャップを埋めるために、入力量子状態が特定の性質を持つかどうかを決定する量子約束問題の複雑性理論について検討する。
p/mQP, p/mQ(C)MA, $\mathrm{p/mQSZK_{hv}}$, p/mQIP, p/mPSPACE ここでは、「p/mC」は任意の古典クラスCに対応する純粋(p)または混合(m)状態のクラスを表す。
特に, p/mQIP $\neq$ p/mPSPACE や $\mathrm{mcoQSZK_{hv}} \neq \mathrm{mQSZK_{hv}}$ など, 古典的なものとは異なっている。
アプリケーションとして、このフレームワークを暗号化に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAまたは$\mathrm{mQSZK_{hv}}$でバウンドされていることを示す。
また、$\mathrm{pQCZK_{hv}}$の平均ケース硬さは、EFIの存在を意味することを示す。
これらの結果は、Impagliazzoの世界に対する新たな洞察を与え、量子暗号と量子約束複雑性理論の結びつきを確立した。
我々はまた、この新たなフレームワークのさらなる応用を強調しながら、量子特性テストとユニタリ合成にも研究結果を拡張した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。