論文の概要: Improved approximation algorithms for bounded-degree local Hamiltonians
- arxiv url: http://arxiv.org/abs/2105.01193v1
- Date: Mon, 3 May 2021 22:23:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-01 17:29:55.418299
- Title: Improved approximation algorithms for bounded-degree local Hamiltonians
- Title（参考訳）: 境界次局所ハミルトニアンの近似アルゴリズムの改良
- Authors: Anurag Anshu, David Gosset, Karen J. Morenz Korol, Mehdi Soleimanifar
- Abstract要約: 与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。
結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
- 参考スコア（独自算出の注目度）: 12.961180148172197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the task of approximating the ground state energy of two-local
quantum Hamiltonians on bounded-degree graphs. Most existing algorithms
optimize the energy over the set of product states. Here we describe a family
of shallow quantum circuits that can be used to improve the approximation ratio
achieved by a given product state. The algorithm takes as input an $n$-qubit
product state $|v\rangle$ with mean energy $e_0=\langle v|H|v\rangle$ and
variance $\mathrm{Var}=\langle v|(H-e_0)^2|v\rangle$, and outputs a state with
an energy that is lower than $e_0$ by an amount proportional to
$\mathrm{Var}^2/n$. In a typical case, we have $\mathrm{Var}=\Omega(n)$ and the
energy improvement is proportional to the number of edges in the graph. When
applied to an initial random product state, we recover and generalize the
performance guarantees of known algorithms for bounded-occurrence classical
constraint satisfaction problems. We extend our results to $k$-local
Hamiltonians and entangled initial states.
- Abstract（参考訳）: 有界次グラフ上の2局所量子ハミルトニアンの基底状態エネルギーを近似するタスクを考える。
既存のアルゴリズムのほとんどは、製品状態の集合よりもエネルギーを最適化する。
ここでは、与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。
このアルゴリズムは平均エネルギー $e_0=\langle v|H|v\rangle$ と variance $\mathrm{Var}=\langle v|(H-e_0)^2|v\rangle$ を入力とし、$\mathrm{Var}^2/n$ に比例して e_0$ 以下のエネルギーの状態を出力する。
典型的な場合、$\mathrm{Var}=\Omega(n)$ を持ち、エネルギー改善はグラフの辺の数に比例する。
初期ランダムな積状態に適用すると、有界古典的制約満足問題に対する既知のアルゴリズムの性能保証を回復し、一般化する。
結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-04T17:58:01Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳（メタデータ） (2023-09-15T14:01:13Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。