Fugu-MT 論文翻訳(概要): Polynomial speedup in Torontonian calculation by a scalable recursive algorithm

論文の概要: Polynomial speedup in Torontonian calculation by a scalable recursive algorithm

arxiv url: http://arxiv.org/abs/2109.04528v3
Date: Tue, 15 Nov 2022 11:47:56 GMT
ステータス: 処理完了
システム内更新日: 2023-03-15 18:07:26.195111
Title: Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
Title（参考訳）: スケーラブル再帰アルゴリズムによるトロントの計算における多項式高速化
Authors: \'Agoston Kaposi, Zolt\'an Kolarovszki, Tam\'as Kozsik, Zolt\'an Zimbor\'as, P\'eter Rakyta
Abstract要約: トロント関数は、しきい値検出を伴うガウスボソンサンプリング(GBS)のシミュレーションにおいて中心的な計算課題である。本稿では,トロントの正確な計算を,最先端のアルゴリズムと比較して高速化する再帰的アルゴリズムを提案する。このアルゴリズムは,大規模計算能力を必要とせずに,しきい値GBSを最大35～40ドルでシミュレーションできるようなユースケースに拡張可能であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: Evaluating the Torontonian function is a central computational challenge in the simulation of Gaussian Boson Sampling (GBS) with threshold detection. In this work, we propose a recursive algorithm providing a polynomial speedup in the exact calculation of the Torontonian compared to state-of-the-art algorithms. According to our numerical analysis the complexity of the algorithm is proportional to $N^{1.0691}2^{N/2}$ with $N$ being the size of the problem. We also show that the recursive algorithm can be scaled up to HPC use cases making feasible the simulation of threshold GBS up to $35-40$ photon clicks without the needs of large-scale computational capacities.
Abstract（参考訳）: トロント関数の評価はガウスボソンサンプリング(GBS)のしきい値検出における中心的な計算課題である。本研究では,トロントの精度計算における多項式の高速化を,最先端のアルゴリズムと比較した再帰的アルゴリズムを提案する。我々の数値解析によると、アルゴリズムの複雑さは、問題のサイズが$N$である$N^{1.0691}2^{N/2}$に比例する。また、この再帰的アルゴリズムは、大規模計算能力の必要なしに、しきい値GBSのシミュレーションを最大35〜40ドルの光子クリックで実現可能なHPCユースケースまで拡張可能であることを示す。

関連論文リスト

A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文参考訳（メタデータ） (2024-09-07T06:37:23Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
論文参考訳（メタデータ） (2023-10-23T04:19:35Z)
Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
論文参考訳（メタデータ） (2023-10-01T03:57:13Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文参考訳（メタデータ） (2021-09-23T07:46:20Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。私たちの後悔の限界はエピソードの数とは無関係です。
論文参考訳（メタデータ） (2020-11-09T18:32:22Z)
Quadratic speedup for simulating Gaussian boson sampling [0.9236074230806577]
本稿では,ガウスボソンサンプリングの古典的シミュレーションのためのアルゴリズムを提案する。アルゴリズムの複雑さは、検出された光子対の数において指数関数的であり、光子の数ではない。改良されたループハフニアンアルゴリズムはスーパーコンピュータを必要とせずに純粋状態確率を計算することができることを示す。
論文参考訳（メタデータ） (2020-10-29T13:53:30Z)
On Thompson Sampling with Langevin Algorithms [106.78254564840844]
多武装バンディット問題に対するトンプソンサンプリングは理論と実践の両方において良好な性能を享受する。計算上のかなりの制限に悩まされており、反復ごとに後続分布からのサンプルを必要とする。本稿では,この問題に対処するために,トンプソンサンプリングに適した2つのマルコフ連鎖モンテカルロ法を提案する。
論文参考訳（メタデータ） (2020-02-23T22:35:29Z)
Quantum Relief Algorithm [12.599184944451833]
リリーフアルゴリズム(Relief algorithm)は、Kira と Rendell によって提案された二項分類における特徴選択アルゴリズムである。 Reliefアルゴリズム(quantum Relief algorithm)と呼ばれるReliefアルゴリズムに基づく量子特徴選択アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-01T10:18:34Z)

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