論文の概要: Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems
- arxiv url: http://arxiv.org/abs/2012.12347v1
- Date: Tue, 22 Dec 2020 20:41:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 21:46:59.331632
- Title: Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems
- Title(参考訳): 量子2局所ハミルトニアン問題の近似のためのビーティングランダムアサインメント
- Authors: Ojas Parekh and Kevin Thompson
- Abstract要約: k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の一般化である
極大絡み合いのインスタンスである厳密な二次インスタンスに対しては、古典的な 0.764 時間 0.764 近似を提供する。
これらは近似するのが最も難しい例であると推測する。
我々の研究は、最近開発されたCSPの古典近似解析技術を採用しており、量子情報科学者と古典計算機科学者の両方にアクセスできることを意図している。
- 参考スコア(独自算出の注目度): 3.553493344868414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum k-Local Hamiltonian problem is a natural generalization of
classical constraint satisfaction problems (k-CSP) and is complete for QMA, a
quantum analog of NP. Although the complexity of k-Local Hamiltonian problems
has been well studied, only a handful of approximation results are known. For
Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural
quantum generalization of classical Max 2-SAT, the best known approximation
algorithm was the trivial random assignment, yielding a 0.75-approximation. We
present the first approximation algorithm beating this bound, a classical
polynomial-time 0.764-approximation. For strictly quadratic instances, which
are maximally entangled instances, we provide a 0.801 approximation algorithm,
and numerically demonstrate that our algorithm is likely a 0.821-approximation.
We conjecture these are the hardest instances to approximate. We also give
improved approximations for quantum generalizations of other related classical
2-CSPs. Finally, we exploit quantum connections to a generalization of the
Grothendieck problem to obtain a classical constant-factor approximation for
the physically relevant special case of strictly quadratic traceless 2-Local
Hamiltonians on bipartite interaction graphs, where a inverse logarithmic
approximation was the best previously known (for general interaction graphs).
Our work employs recently developed techniques for analyzing classical
approximations of CSPs and is intended to be accessible to both quantum
information scientists and classical computer scientists.
- Abstract(参考訳): 量子k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の自然な一般化であり、NPの量子アナログであるQMAに対して完備である。
k-ローカルハミルトニアン問題の複雑さはよく研究されているが、近似結果はほとんど知られていない。
各項がランク3プロジェクターであるマックス2-局所ハミルトニアンにとって、古典マックス2-SATの自然な量子一般化は、最もよく知られた近似アルゴリズムは自明なランダム代入であり、0.75近似となる。
この境界を破る最初の近似アルゴリズム, 古典多項式時間 0.764 近似法を提案する。
厳密な二次的なインスタンスは、最大絡み合いのインスタンスであり、0.801近似アルゴリズムを提供し、我々のアルゴリズムが0.821近似である可能性を数値的に証明する。
これらを近似する最も難しい例と推測する。
また、他の関連する古典的2-CSPの量子一般化の近似も改善した。
最後に、Grothendieck問題の一般化への量子接続を利用して、2部相互作用グラフ上の厳密な二次トレースレス2-ローカルハミルトニアン(英語版)の物理的特殊ケースに対して古典的な定数係数近似を得る。
本研究は,cspsの古典近似を解析するための最近の手法を用いており,量子情報科学者と古典計算機科学者の両方が利用できることを意図している。
関連論文リスト
- Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
ハミルトン方程式は、コストテートとして知られる補助変数を通して最適性の解釈を提供する。
本稿では,前向きに作業することを目的とした,新しいニューラルベースによる最適制御手法を提案する。
論文 参考訳(メタデータ) (2023-12-14T19:29:37Z) - 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) - A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳(メタデータ) (2023-04-17T16:42:05Z) - Exponential quantum speedup in simulating coupled classical oscillators [1.9398245011675082]
本稿では,2n$結合発振器の古典力学に対する量子アルゴリズムを提案する。
我々のアプローチは、調和ポテンシャルに対するシュル「オーディンガー方程式」とニュートン方程式の間の写像を利用する。
提案手法は,古典的コンピュータ上での指数的高速化により,潜在的に実用的な応用を実現できることを示す。
論文 参考訳(メタデータ) (2023-03-23T03:24:03Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - An Improved Approximation Algorithm for Quantum Max-Cut [0.0]
我々は、SDP緩和を絡み合った量子状態に丸めることによって動作するQuantum Max-Cutの近似アルゴリズムを提案する。
EPRハミルトニアンに対しては、全てのグラフに対して近似比1/sqrt2$の近似アルゴリズムを与える。
論文 参考訳(メタデータ) (2022-09-06T15:45:04Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳(メタデータ) (2021-11-09T18:49:48Z) - On the complexity of quantum partition functions [2.6937287784482313]
局所ハミルトニアンの近似量の計算複雑性について検討する。
$mathrmpoly(n)$ の古典的アルゴリズムは与えられた 2$-局所ハミルトニアンの自由エネルギーを近似する。
論文 参考訳(メタデータ) (2021-10-29T00:05:25Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-11-26T18:22:21Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳(メタデータ) (2020-09-23T08:33:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。