論文の概要: Efficient Quantum Agnostic Improper Learning of Decision Trees
- arxiv url: http://arxiv.org/abs/2210.00212v1
- Date: Sat, 1 Oct 2022 07:11:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 17:20:05.530916
- Title: Efficient Quantum Agnostic Improper Learning of Decision Trees
- Title（参考訳）: 決定木の効率的な量子非依存不適切な学習
- Authors: Debajyoti Bera and Sagnik Chatterjee
- Abstract要約: 我々はカライカナーデポテンシャル増強アルゴリズムの量子バージョンを提供する。
標準量子アルゴリズムを用いて量子弱学習器を構築する方法を示す。
- 参考スコア（独自算出の注目度）: 0.5584060970507505
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The agnostic setting is the hardest generalization of the PAC model since it
is akin to learning with adversarial noise. We study an open question on the
existence of efficient quantum boosting algorithms in this setting. We answer
this question in the affirmative by providing a quantum version of the
Kalai-Kanade potential boosting algorithm. This algorithm shows the standard
quadratic speedup in the VC dimension of the weak learner compared to the
classical case.
Using our boosting algorithm as a subroutine, we give a quantum algorithm for
agnostically learning decision trees in polynomial running time without using
membership queries. To the best of our knowledge, this is the first algorithm
(quantum or classical) to do so. Learning decision trees without membership
queries is hard (and an open problem) in the standard classical realizable
setting. In general, even coming up with weak learners in the agnostic setting
is a challenging task. We show how to construct a quantum agnostic weak learner
using standard quantum algorithms, which is of independent interest for
designing ensemble learning setups.
- Abstract（参考訳）: 不可知的な設定は、対向雑音による学習に似ているため、PACモデルの最も難しい一般化である。
本稿では,この設定における効率的な量子ブースティングアルゴリズムの存在について,オープンな考察を行う。
我々は、カライカナーデポテンシャル増強アルゴリズムの量子バージョンを提供することで、この疑問に肯定的な形で答える。
このアルゴリズムは、古典的な場合と比較して弱い学習者のVC次元の標準的な二次的スピードアップを示す。
昇降アルゴリズムをサブルーチンとして使用し,多項式実行時間における決定木を非依存的に学習する量子アルゴリズムを提案する。
私たちの知る限りでは、これは最初のアルゴリズム(量子または古典)である。
メンバシップクエリなしで決定木を学ぶことは、標準的な古典的実現可能な設定では難しい(そしてオープンな問題)。
一般的に、無知な設定で弱い学習者を見つけ出すのは難しい作業です。
本稿では,アンサンブル学習設定の設計に独立した関心を持つ標準量子アルゴリズムを用いて,量子非依存な弱い学習者を構築する方法を示す。
関連論文リスト
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。
量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
論文 参考訳（メタデータ） (2024-11-04T13:49:26Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
最適化問題を解くために反復量子最適化アルゴリズムを導入する。
72量子ビット以下のプログラム可能な超伝導量子系に量子アルゴリズムを実装した。
量子アルゴリズムは古典的な欲求よりも体系的に優れており、量子エンハンスメントのシグナルとなる。
論文 参考訳（メタデータ） (2023-03-09T18:59:37Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Bayes AI [1.7403133838762443]
量子ベイズAI(Quantum Bayesian AI, Q-B)は、量子コンピューティングで利用可能な計算ゲインを補う新興分野である。
我々は、古典的および量子的確率の双対性を提供して、後続の関心量の計算を行う。
本稿では,2つの単純な分類アルゴリズム上での量子アルゴリズムの挙動について述べる。
論文 参考訳（メタデータ） (2022-08-17T04:51:10Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Inspired Adaptive Boosting [0.0]
量子アンサンブル法は古典的アルゴリズムに勝らないことを示す。
本稿では,量子アンサンブル法と適応的なブースティングを組み合わせた手法を提案する。
アルゴリズムはテストされ、公開データセット上のAdaBoostアルゴリズムに匹敵することがわかった。
論文 参考訳（メタデータ） (2021-02-01T16:33:14Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。