Fugu-MT 論文翻訳(概要): A simple lower bound for the complexity of estimating partition functions on a quantum computer

論文の概要: 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)$クエリローバウンドを証明します。証明は未知の二進弦のハミング重みを推定する問題からの還元に基づいている。

関連論文リスト

Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文参考訳（メタデータ） (2024-11-06T22:51:27Z)
Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
同一の$k$密度行列のパワーのトレースを推定することは、多くのアプリケーションにとって重要なサブルーチンである。 The Newton-Girard method, we developed a algorithm that only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates。
論文参考訳（メタデータ） (2024-08-01T06:23:52Z)
Accelerated Quantum Amplitude Estimation without QFT [0.0]
我々は、現在利用可能なアプローチと比較して優れた性能(より低い量子計算複雑性と高速な古典計算部分)を実現する量子振幅推定アルゴリズムを提唱した。このアルゴリズムの正しさと量子計算複雑性に縛られる$O(frac1varepsilon)$は、正確な証明によって支持される。
論文参考訳（メタデータ） (2024-07-23T18:49:11Z)
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)

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