論文の概要: Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes

• arxiv url: http://arxiv.org/abs/2408.16934v1
• Date: Thu, 29 Aug 2024 22:35:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-02 16:49:05.181792
• Title: Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
• Title（参考訳）: クリッド錯体のベッチ数推定のための量子および古典モンテカルロアルゴリズムの比較
• Authors: Ismail Yunus Akhalwaya, Ahmed Bhayat, Adam Connolly, Steven Herbert, Lior Horesh, Julien Sorci, Shashanka Ubaru,
• Abstract要約: クリプト錯体上のベッチ数推定(BNE)のための量子および古典モンテカルロアルゴリズムが最近提案されている。 我々はこれらのアルゴリズムをレビューし、新しいモジュラーフレームワーク内で共通のモンテカルロ構造を強調した。 異なるモジュールを再結合することにより、サンプルの複雑さに指数関数的に改善された依存を持つ新しい量子アルゴリズムを作成する。
• 参考スコア（独自算出の注目度）: 6.713479655907349
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. This framework allows us to directly compare these algorithms by calculating upper bounds on the minimum number of samples needed for convergence. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds.
• Abstract（参考訳）: クリプト錯体上のベッチ数推定(BNE)のためのいくつかの量子および古典モンテカルロアルゴリズムが最近提案されているが、それらの性能がどう比較されるかは定かではない。 我々はこれらのアルゴリズムをレビューし、新しいモジュラーフレームワーク内で共通のモンテカルロ構造を強調した。 このフレームワークにより、収束に必要なサンプルの最小値の上限を計算することで、これらのアルゴリズムを直接比較することができる。 異なるモジュールを再結合することにより、サンプルの複雑さに指数関数的に改善された依存を持つ新しい量子アルゴリズムを作成する。 古典的なシミュレーションを行ない、理論的境界内の収束を検証し、予測された指数的分離を観察する。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Approximation of group explainers with coalition structure using Monte Carlo sampling on the product space of coalitions and features [0.11184789007828977]
  我々は、与えられたMLモデルと予測ベクトルに基づく限界ゲームに対して、幅広い種類の線形ゲーム値と連立値に焦点を当てる。 我々はモンテカルロサンプリングアルゴリズムを設計し、背景データセットのサイズに線形に依存する複雑さを減らし、それらを推定する。
  論文  参考訳（メタデータ） (2023-03-17T19:17:06Z)
• Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for Max-cut Approximation: QAOA is not optimal [0.0]
  変分量子アニーリングと量子近似最適化(QAOA)にエミュレーションの概念を適用する。 我々の変分量子アニーリングスケジュールは、同じ物理成分を用いて、QAOAと同様の勾配のない方法で最適化できる新しいパラメータ化に基づいている。 アンス・アッツ型の性能を比較するため,モンテカルロ法の統計的概念を考案した。
  論文  参考訳（メタデータ） (2022-11-24T19:02:50Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Stochastic normalizing flows as non-equilibrium transformations [62.997667081978825]
  正規化フローは従来のモンテカルロシミュレーションよりも効率的に格子場理論をサンプリングするための経路を提供することを示す。 本稿では,この拡張された生成モデルの効率を最適化する戦略と応用例を示す。
  論文  参考訳（メタデータ） (2022-01-21T19:00:18Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Finite-Bit Quantization For Distributed Algorithms With Linear Convergence [6.293059137498172]
  量子化された通信対象のメッシュネットワーク上での(強い凸)複合最適化問題に対する分散アルゴリズムについて検討する。 通信効率のよい符号化方式と結合した新しい量子化器を提案し, バイアス圧縮(BC-)ルールを効率的に実装した。 数値計算により,提案手法を応用した分散アルゴリズムは,既存の量子化規則を用いたアルゴリズムよりも,通信の複雑さが高いことが示された。
  論文  参考訳（メタデータ） (2021-07-23T15:31:31Z)
• Sampling Permutations for Shapley Value Estimation [1.0323063834827415]
  Shapley値に基づくゲーム理論属性技術は、機械学習モデルの解釈に広く使用される。 シャプリー値の計算は置換集合上の和として表現できるので、近似のためのこれらの置換のサブセットをサンプリングする共通のアプローチである。 残念なことに、標準的なモンテカルロサンプリング法は遅い収束を示すことができ、より洗練された準モンテカルロ法は置換の空間でよく定義されていない。
  論文  参考訳（メタデータ） (2021-04-25T16:44:18Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Subgroup-based Rank-1 Lattice Quasi-Monte Carlo [51.877197074344586]
  グループ理論に基づく単純な閉形式ランク1格子構築法を提案する。 本手法は,ベンチマーク統合テスト問題とカーネル近似問題において,優れた近似性能を実現する。
  論文  参考訳（メタデータ） (2020-10-29T03:42:30Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。