論文の概要: A simple lower bound for the complexity of estimating partition functions on a quantum computer
- arxiv url: http://arxiv.org/abs/2404.02414v1
- Date: Wed, 3 Apr 2024 02:38:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 18:49:24.875246
- Title: A simple lower bound for the complexity of estimating partition functions on a quantum computer
- Title（参考訳）: 量子コンピュータ上の分割関数推定の複雑さに対する単純な下界
- Authors: Zherui Chen, Giacomo Nannicini,
- Abstract要約: 分割関数 $mathsfZ(beta)=sum_xinchi e-beta H(x)$ をハミルトニアン$H(x)$ で特徴づけられるギブス分布に対して推定する複雑性について検討する。
我々は、ギブス状態のコヒーレントな符号化を通して反射に依存することにより、この問題を解く量子アルゴリズムの単純で自然な下界を提供する。
- 参考スコア（独自算出の注目度）: 0.20718016474717196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of estimating the partition function ${\mathsf{Z}}(\beta)=\sum_{x\in\chi} e^{-\beta H(x)}$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a $\Omega(1/\epsilon)$ lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. We also prove a $\Omega(1/\epsilon^2)$ query lower bound for classical algorithms. The proofs are based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.
- Abstract（参考訳）: 分割関数 ${\mathsf{Z}}(\beta)=\sum_{x\in\chi} e^{-\beta H(x)}$ をハミルトニアン$H(x)$ で特徴づけられるギブス分布に対して推定する複雑性について検討する。
我々は、ギブス状態のコヒーレントな符号化を通して反射に依存することにより、この問題を解く量子アルゴリズムの単純で自然な下界を提供する。
我々の主な貢献は、量子アルゴリズムで分割関数を推定するために必要な反射数に対する$\Omega(1/\epsilon)$lowboundである。
また、古典アルゴリズムに対して$\Omega(1/\epsilon^2)$クエリローバウンドを証明します。
証明は未知の二進弦のハミング重みを推定する問題からの還元に基づいている。
関連論文リスト
- Partition function estimation with a quantum coin toss [0.0]
量子分割関数の推定は、様々な分野において重要な課題である。
本稿では,分割関数 $Z_beta$ を乗法誤差まで一般化したハミルトニアン$H$ の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-26T19:01:19Z) - Resource-efficient algorithm for estimating the trace of quantum state powers [1.5133368155322298]
量子状態のトレースを$textTr(rhok)$, for $k$等量子状態と見積もるのは基本的な課題である。
我々は、$mathcalO(tilder)$ qubitsと$mathcalO(tilder)$ multi-qubit gatesのみを必要とするアルゴリズムを導入する。
我々はアルゴリズムを任意のオブザーバブルに対して$textTr(rhok)$と$textTr(rhok)$の推定にまで拡張する。
論文 参考訳（メタデータ） (2024-08-01T06:23:52Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - 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) - A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。
我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
論文 参考訳（メタデータ） (2022-12-03T08:01:55Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-09T18:43:25Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
分割関数を推定するハイブリッド量子古典アルゴリズムを開発した。
我々のアルゴリズムは浅い$mathcalO(1)$-depth量子回路を必要とする。
浅層量子回路は、現在利用可能なNISQ(ノイズ中間スケール量子)デバイスにとって極めて重要であると考えられている。
論文 参考訳（メタデータ） (2021-09-22T02:03:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。