Fugu-MT 論文翻訳(概要): Entropic barriers as a reason for hardness in both classical and quantum algorithms

論文の概要: 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という難解な最適化問題を解く。大きなエネルギー障壁を飛び越えることができない新しい準欲望アルゴリズムを導入することで、問題の難しさは主にエントロピー障壁によるものであることを示した。解析的および数値的に、いくつかの最適化アルゴリズムを研究し、エントロピー障壁が古典的局所アルゴリズムや量子アニーリングのように影響することを示した。断熱アルゴリズムでは、大きな障壁の下でトンネルを掘ることは困難であるが、それでも指数的なランニング(アニーリング)の時間が発生する。

関連論文リスト

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)
Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
論文参考訳（メタデータ） (2024-07-10T14:08:58Z)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。