論文の概要: QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more
- arxiv url: http://arxiv.org/abs/2309.16431v1
- Date: Thu, 28 Sep 2023 13:30:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 14:18:16.497815
- Title: QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more
- Title（参考訳）: qsethが再び攻撃:格子問題、強いシミュレーション、集合問題に対するより細かい量子下限
- Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian
Speelman
- Abstract要約: 現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
- 参考スコア（独自算出の注目度）: 5.69353915790503
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While seemingly undesirable, it is not a surprising fact that there are
certain problems for which quantum computers offer no computational advantage
over their respective classical counterparts. Moreover, there are problems for
which there is no `useful' computational advantage possible with the current
quantum hardware. This situation however can be beneficial if we don't want
quantum computers to solve certain problems fast - say problems relevant to
post-quantum cryptography. In such a situation, we would like to have evidence
that it is difficult to solve those problems on quantum computers; but what is
their exact complexity?
To do so one has to prove lower bounds, but proving unconditional time lower
bounds has never been easy. As a result, resorting to conditional lower bounds
has been quite popular in the classical community and is gaining momentum in
the quantum community. In this paper, by the use of the QSETH framework
[Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity
of a few natural variants of CNFSAT, such as parity-CNFSAT or counting-CNFSAT,
and also are able to comment on the non-trivial complexity of
approximate-#CNFSAT; both of these have interesting implications about the
complexity of (variations of) lattice problems, strong simulation and hitting
set problem, and more.
In the process, we explore the QSETH framework in greater detail than was
(required and) discussed in the original paper, thus also serving as a useful
guide on how to effectively use the QSETH framework.
- Abstract（参考訳）: 一見望ましくないように見えるが、量子コンピュータがそれぞれの古典的コンピュータに対して計算上の優位性がないという問題が存在することは驚くべき事実ではない。
さらに、現在の量子ハードウェアでは「有用な」計算上の優位性がないという問題がある。
しかし、量子コンピュータに特定の問題を素早く解決させたくなければ、この状況は有益である。
このような状況下では、量子コンピュータ上でこれらの問題を解決することが難しいという証拠を持ちたいと思いますが、その正確な複雑さは何ですか?
そのためには、下限を証明しなければならないが、無条件時間下限を証明するのは容易ではない。
その結果、条件付き下界へのアプローチは古典的なコミュニティでは非常に人気があり、量子コミュニティでは勢いが増している。
本稿では,QSETH フレームワーク [Buhrman-Patro-Speelman 2021] を用いて,パリティ-CNFSAT やカウント-CNFSAT などの CNFSAT の自然変種の量子複雑性を理解することができ,また近似#CNFSAT の非自明な複雑さについてコメントすることができる。
本プロセスでは,QSETHフレームワークを元の論文で論じられた(要求および要求)よりも詳細に検討し,QSETHフレームワークを効果的に利用する上で有用なガイドとして機能する。
関連論文リスト
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
論文 参考訳（メタデータ） (2024-11-06T07:29:52Z) - Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。
初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
論文 参考訳（メタデータ） (2024-03-25T15:47:35Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。
最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。
因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文 参考訳（メタデータ） (2023-07-18T13:12:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳（メタデータ） (2022-10-04T13:27:01Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。
この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。
GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-04-18T21:45:13Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Variational Quantum Algorithms [1.9486734911696273]
量子コンピュータは、大規模量子システムや大規模線形代数問題を解くなどの応用を解くことを約束する。
現在利用可能な量子デバイスには、量子ビット数の制限や回路深さを制限するノイズプロセスなど、深刻な制約がある。
パラメトリズド量子回路のトレーニングに古典的シミュレーションを用いる変分量子アルゴリズム(vqas)は、これらの制約に対処するための主要な戦略として登場した。
論文 参考訳（メタデータ） (2020-12-16T21:00:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。