論文の概要: Quantum Constraint Problems can be complete for $\mathsf{BQP}$,
$\mathsf{QCMA}$, and more
- arxiv url: http://arxiv.org/abs/2101.08381v3
- Date: Wed, 21 Jul 2021 00:08:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-14 08:44:15.938169
- Title: Quantum Constraint Problems can be complete for $\mathsf{BQP}$,
$\mathsf{QCMA}$, and more
- Title（参考訳）: 量子制約問題は$\mathsf{BQP}$、$\mathsf{QCMA}$などに対して完備することができる。
- Authors: Alex Meiburg
- Abstract要約: 量子制約問題はすべて、古典的制約問題と共有されない性質である量子ビット上で実現可能であることを示す。
結果は、量子制約問題に存在するクラスの顕著な多様性を示唆している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A quantum constraint problem is a frustration-free Hamiltonian problem: given
a collection of local operators, is there a state that is in the ground state
of each operator simultaneously? It has previously been shown that these
problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this
list has not been shown to be exhaustive. We present three quantum constraint
problems, that are (1) BQP_1-complete (also known as coRQP), (2)
QCMA_1-complete and (3) coRP-complete. This provides the first natural complete
problem for BQP_1. We also show that all quantum constraint problems can be
realized on qubits, a trait not shared with classical constraint problems.
These results suggest a significant diversity of complexity classes present in
quantum constraint problems.
- Abstract（参考訳）: 量子制約問題はフラストレーションのないハミルトニアン問題である: 局所作用素の集合が与えられたとき、各作用素の基底状態にある状態は存在するか?
これらの問題は、P、NP-完全、MA-完全、QMA_1-完全と示されているが、このリストは完全ではない。
1) BQP_1-完全(coRQPとも呼ばれる)、(2) QCMA_1-完全、(3) coRP-完全である。
これはbqp_1に対する最初の自然完全問題である。
また,量子制約問題はすべて,古典制約問題と共有しない特性である量子ビット上で実現可能であることを示した。
これらの結果は、量子制約問題に存在する複雑性クラスにかなりの多様性があることを示唆する。
関連論文リスト
- Bosonic Quantum Computational Complexity [0.0]
私たちはそのような研究計画の基礎をつくった。
本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。
ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
論文 参考訳（メタデータ） (2024-10-05T19:43:41Z) - A Quantum Unique Games Conjecture [0.0]
本稿では,ラベル・コーバーとユニク・ラベル・コーヴァーの量子拡張の定義を紹介する。
これらの問題は、古典的な設定で行うように、量子制約満足度問題の非近似性を研究する上でも同様に重要な役割を果たすことを示す。
論文 参考訳（メタデータ） (2024-09-30T07:34:41Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Four Related Combinatorial Problems [0.0]
量子測度$mu$が次数2の加算条件を満たすことを示す。
そして、これが元の量子測度問題を解くことを示す。
論文 参考訳（メタデータ） (2023-11-13T19:57:12Z) - 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) - Quantum Programming of the Satisfiability Problem with Rydberg Atom
Graphs [1.2179548969182574]
実験では、リドベルク原子を用いて(すなわち、満足度(3-SAT)の問題をプログラムし、解を求める)。
論文 参考訳（メタデータ） (2023-02-28T07:49:10Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。