Fugu-MT 論文翻訳(概要): A Linearly Convergent Algorithm for Computing the Petz-Augustin Information

論文の概要: A Linearly Convergent Algorithm for Computing the Petz-Augustin Information

arxiv url: http://arxiv.org/abs/2502.06399v1
Date: Mon, 10 Feb 2025 12:37:10 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-11 14:29:21.257821
Title: A Linearly Convergent Algorithm for Computing the Petz-Augustin Information
Title（参考訳）: Petz-Augustin情報計算のための線形収束アルゴリズム
Authors: Chun-Neng Chu, Wei-Fu Tseng, Yen-Huan Li,
Abstract要約: 次数$alphain (1/2,1)cup (1,infty)$のPetz-Augustin情報を計算するための反復アルゴリズムを提案する。最適化エラーは$Oleft(vert 1-1/alpha vertTright)$で収束することが保証されている。我々の知る限りでは、これはペッツ=アウグスティンの情報を非漸近収束保証で計算する最初のアルゴリズムである。
参考スコア（独自算出の注目度）: 2.059931105362387
License:
Abstract: We propose an iterative algorithm for computing the Petz-Augustin information of order $\alpha\in(1/2,1)\cup(1,\infty)$. The optimization error is guaranteed to converge at a rate of $O\left(\vert 1-1/\alpha \vert^T\right)$, where $T$ is the number of iterations. Let $n$ denote the cardinality of the input alphabet of the classical-quantum channel, and $d$ the dimension of the quantum states. The algorithm has an initialization time complexity of $O\left(n d^{3}\right)$ and a per-iteration time complexity of $O\left(n d^{2}+d^3\right)$. To the best of our knowledge, this is the first algorithm for computing the Petz-Augustin information with a non-asymptotic convergence guarantee.
Abstract（参考訳）: 本稿では,ペッツ=アウグスティンの次数$\alpha\in(1/2,1)\cup(1,\infty)$の反復アルゴリズムを提案する。最適化誤差は$O\left(\vert 1-1/\alpha \vert^T\right)$で収束することが保証される。古典量子チャネルの入力アルファベットの濃度を$n$とし、量子状態の次元を$d$とする。このアルゴリズムは初期化時間の複雑さを$O\left(n d^{3}\right)$とし、時間単位の複雑性を$O\left(n d^{2}+d^3\right)$とする。我々の知る限りでは、これはペッツ=アウグスティンの情報を非漸近収束保証で計算する最初のアルゴリズムである。

関連論文リスト

Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-07-04T11:03:48Z)
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)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文参考訳（メタデータ） (2023-06-05T12:22:46Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
A (simple) classical algorithm for estimating Betti numbers [1.8749305679160366]
経路積分モンテカルロ法を用いて、$k$-th正規化ベッチ数を$n$要素上の単純複素数として推定する簡単なアルゴリズムを記述する。一般の単純複素数に対して、我々のアルゴリズムの実行時間は$nOleft(frac1sqrtgammalogfrac1varepsilonright)$で、加法精度は (0,$1) のラプラシアンとヴァレプシロンのスペクトルギャップを測定する$gamma$である。
論文参考訳（メタデータ） (2022-11-17T16:10:47Z)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文参考訳（メタデータ） (2020-06-21T06:57:59Z)
Improved quantum algorithm for A-optimal projection [4.248054546466641]
本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
論文参考訳（メタデータ） (2020-06-10T09:31:53Z)

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