論文の概要: Sublinear quantum algorithms for estimating von Neumann entropy
- arxiv url: http://arxiv.org/abs/2111.11139v1
- Date: Mon, 22 Nov 2021 12:00:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 04:32:20.051111
- Title: Sublinear quantum algorithms for estimating von Neumann entropy
- Title（参考訳）: ノイマンエントロピー推定のための線形量子アルゴリズム
- Authors: Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
- Abstract要約: 我々は、確率分布のシャノンエントロピーと混合量子状態のフォン・ノイマンエントロピーの乗法係数$gamma>1$における推定値を得る問題を研究する。
我々は古典的確率分布と混合量子状態の両方を扱える量子純粋クエリーアクセスモデルに取り組んでおり、文献の中では最も一般的な入力モデルである。
- 参考スコア（独自算出の注目度）: 18.30551855632791
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Entropy is a fundamental property of both classical and quantum systems,
spanning myriad theoretical and practical applications in physics and computer
science. We study the problem of obtaining estimates to within a multiplicative
factor $\gamma>1$ of the Shannon entropy of probability distributions and the
von Neumann entropy of mixed quantum states. Our main results are:
$\quad\bullet$ an $\widetilde{\mathcal{O}}\left(
n^{\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a
$\gamma$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of
a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$;
$\quad\bullet$ an $\widetilde{\mathcal{O}}\left(
n^{\frac12+\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that
outputs a $\gamma$-multiplicative approximation of the von Neumann entropy
$S(\rho)$ of a density matrix $\rho\in\mathbb{C}^{n\times n}$.
In both cases, the input is assumed to have entropy bounded away from zero by
a quantity determined by the parameter $\eta>0$, since, as we prove, no
polynomial query algorithm can multiplicatively approximate the entropy of
distributions with arbitrarily low entropy. In addition, we provide
$\Omega\left(n^{\frac{1}{3\gamma^2}}\right)$ lower bounds on the query
complexity of $\gamma$-multiplicative estimation of Shannon and von Neumann
entropies.
We work with the quantum purified query access model, which can handle both
classical probability distributions and mixed quantum states, and is the most
general input model considered in the literature.
- Abstract（参考訳）: エントロピーは古典的および量子システムの基本的な性質であり、物理学と計算機科学における無数の理論的および実践的な応用にまたがる。
確率分布のシャノンエントロピーと混合量子状態のフォン・ノイマンエントロピーの乗法係数$\gamma>1$における推定値を得る問題について検討する。
Our main results are: $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$; $\quad\bullet$ an $\widetilde{\mathcal{O}}\left( n^{\frac12+\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the von Neumann entropy $S(\rho)$ of a density matrix $\rho\in\mathbb{C}^{n\times n}$.
いずれの場合においても、入力はパラメータ $\eta>0$ によって決定される量によってゼロから境界付けられたエントロピーを持つと仮定される。
さらに、シャノンとフォン・ノイマンのエントロピーの$\gamma$-乗算推定のクエリ複雑性について、$\omega\left(n^{\frac{1}{3\gamma^2}}\right)$下限を与える。
我々は古典的確率分布と混合量子状態の両方を扱える量子純粋クエリーアクセスモデルに取り組んでおり、文献の中では最も一般的な入力モデルである。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
半古典的状態におけるシュル・オーディンガーの方程式を考える。
このようなシュル・オーディンガー方程式はボルン=オッペンハイマーの分子動力学やエレンフェストの動力学など多くの応用を見出す。
論文 参考訳（メタデータ） (2021-12-25T20:01:54Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳（メタデータ） (2021-02-03T09:20:32Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。