論文の概要: Entropic barriers as a reason for hardness in both classical and quantum
algorithms
- arxiv url: http://arxiv.org/abs/2102.00182v2
- Date: Wed, 24 Feb 2021 14:22:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 06:53:08.854014
- Title: Entropic barriers as a reason for hardness in both classical and quantum
algorithms
- Title(参考訳): 古典的および量子的アルゴリズムにおける硬さの理由としてのエントロピー障壁
- Authors: Matteo Bellitti, Federico Ricci-Tersenghi and Antonello Scardicchio
- Abstract要約: 古典的および量子的アルゴリズムを用いて3つの規則ランダムグラフ上の3-XORSATという難解な最適化問題を解く。
大規模なエネルギー障壁を乗り越えることができない新しい準グレーディアルゴリズムを導入することにより、問題硬度は主にエントロピー障壁によるものであることを示す。
- 参考スコア(独自算出の注目度): 2.062593640149623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study both classical and quantum algorithms to solve a hard optimization
problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new
quasi-greedy algorithm that is not allowed to jump over large energy barriers,
we show that the problem hardness is mainly due to entropic barriers. We study,
both analytically and numerically, several optimization algorithms, finding
that entropic barriers affect in a similar way classical local algorithms and
quantum annealing. For the adiabatic algorithm, the difficulty we identify is
distinct from that of tunnelling under large barriers, but does, nonetheless,
give rise to exponential running (annealing) times.
- Abstract(参考訳): 古典的および量子的アルゴリズムを用いて3つの規則ランダムグラフ上の3-XORSATという難解な最適化問題を解く。
大きなエネルギー障壁を飛び越えることができない新しい準欲望アルゴリズムを導入することで、問題の難しさは主にエントロピー障壁によるものであることを示した。
解析的および数値的に、いくつかの最適化アルゴリズムを研究し、エントロピー障壁が古典的局所アルゴリズムや量子アニーリングのように影響することを示した。
断熱アルゴリズムでは、大きな障壁の下でトンネルを掘ることは困難であるが、それでも指数的なランニング(アニーリング)の時間が発生する。
関連論文リスト
- On the approximability of random-hypergraph MAX-3-XORSAT problems with
quantum algorithms [0.0]
ハミルトン時間進化に基づく量子アルゴリズムにおける近似硬さの直感的なメカニズムはよく理解されていない。
これらの問題に支障を来さない新しいスペクトル畳み込み最適化法を提案する。
エネルギーを$E = N_unsat-N_sat$と定義すれば、スペクトル的に折り畳まれた量子最適化はエネルギー$E leq Aを持つ状態を返す。
論文 参考訳(メタデータ) (2023-12-11T04:15:55Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。
我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。
最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文 参考訳(メタデータ) (2023-05-17T18:00:06Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum algorithms and the power of forgetting [1.5791732557395555]
本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。
このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
論文 参考訳(メタデータ) (2022-11-22T18:04:10Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Comparing the hardness of MAX 2-SAT problem instances for quantum and
classical algorithms [1.0499611180329804]
特定の問題に対するアルゴリズムは、固定された入力サイズであっても、問題のいくつかの例がより簡単であり、解決が困難である可能性がある。
我々は, MAX 2-SAT問題インスタンスの相対的硬度を, 連続時間量子アルゴリズムと同等の古典的アルゴリズムに対して数値解析する。
論文 参考訳(メタデータ) (2022-06-14T14:23:47Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳(メタデータ) (2021-08-18T09:26:17Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳(メタデータ) (2021-01-18T19:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。