Fugu-MT 論文翻訳(概要): Quantum Request-Answer Game with Buffer Model for Online Algorithms

論文の概要: Quantum Request-Answer Game with Buffer Model for Online Algorithms

arxiv url: http://arxiv.org/abs/2012.12321v1
Date: Tue, 22 Dec 2020 19:48:45 GMT
ステータス: 処理完了
システム内更新日: 2023-04-19 21:45:59.048431
Title: Quantum Request-Answer Game with Buffer Model for Online Algorithms
Title（参考訳）: オンラインアルゴリズムのためのバッファモデル付き量子要求応答ゲーム
Authors: Kamil Khadiev
Abstract要約: 相手は入力要求を生成し、オンラインアルゴリズムが答える。モデルに対する量子および古典的(決定論的またはランダム化)アルゴリズムについて検討する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider online algorithms as a request-answer game. An adversary that generates input requests, and an online algorithm answers. We consider a generalized version of the game that has a buffer of limited size. The adversary loads data to the buffer, and the algorithm has random access to elements of the buffer. We consider quantum and classical (deterministic or randomized) algorithms for the model. In the paper, we provide a specific problem (The Most Frequent Keyword Problem) and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm in terms of competitive ratio. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with buffer model.
Abstract（参考訳）: オンラインアルゴリズムを要求処理ゲームと捉えている。入力リクエストを生成する敵と、オンラインアルゴリズムが答える。サイズが制限されたバッファを持つゲームの一般化版を考える。敵はバッファにデータをロードし、アルゴリズムはバッファの要素にランダムにアクセスします。モデルに対する量子および古典的(決定論的またはランダム化)アルゴリズムを考える。本稿では、競合比の観点から、特定の問題(最も頻度の高いキーワード問題)と、どの古典的(決定論的またはランダム化)アルゴリズムよりも優れた量子アルゴリズムを提供する。同時に、標準モデルにおける古典的オンラインアルゴリズムはバッファモデルを用いた要求応答ゲームにおける古典的アルゴリズムと等価である。

関連論文リスト

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)
Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文参考訳（メタデータ） (2023-11-07T04:59:02Z)
Hybrid classical-quantum text search based on hashing [0.0]
非順序データベースにおける古典的な検索クエリの複雑さは、テキストの長さと与えられた値の長さにおいて線形であることが知られている。本稿ではGroverの検索を実装した古典量子ハイブリッドアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-11-02T13:16:07Z)
On Hitting Times for General Quantum Markov Processes [0.0]
我々は、古典的なウォークを直接一般化する量子マルコフ連鎖モデルを定義するために密度行列形式を用いる。打つ時間などの共通ツールを古典理論と同様の式で計算できることが示される。
論文参考訳（メタデータ） (2022-10-18T22:20:27Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文参考訳（メタデータ） (2022-05-26T20:32:36Z)
Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
論文参考訳（メタデータ） (2022-03-17T19:26:00Z)
Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文参考訳（メタデータ） (2022-02-23T11:43:17Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Quantum Inspired Adaptive Boosting [0.0]
量子アンサンブル法は古典的アルゴリズムに勝らないことを示す。本稿では,量子アンサンブル法と適応的なブースティングを組み合わせた手法を提案する。アルゴリズムはテストされ、公開データセット上のAdaBoostアルゴリズムに匹敵することがわかった。
論文参考訳（メタデータ） (2021-02-01T16:33:14Z)
Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。 ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
論文参考訳（メタデータ） (2020-11-17T13:12:43Z)
Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文参考訳（メタデータ） (2020-05-09T02:48:23Z)

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