論文の概要: Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
- arxiv url: http://arxiv.org/abs/2602.04700v1
- Date: Wed, 04 Feb 2026 16:10:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-05 19:45:11.611448
- Title: Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
- Title（参考訳）: 決定木における量子アドバンテージ:重み付きグラフと$L_1$ノルムアプローチ
- Authors: Sebastian Alberto Grillo, Bernardo Daniel Dávalos, Rodney Fabian Franco Torres, Franklin de Lima Marquezino, Edgar López Pezoa,
- Abstract要約: 本稿では,重み付きグラフとして単一クエリ量子決定木の定式化を提案する。
量子決定木の出力のスペクトルノルムの高額なL_1$は、その古典的基準を上回るために必要な条件である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The analysis of the computational power of single-query quantum algorithms is important because they must extract maximal information from one oracle call, revealing fundamental limits of quantum advantage and enabling optimal, resource-efficient quantum computation. This paper proposes a formulation of single-query quantum decision trees as weighted graphs. This formulation has the advantage that it facilitates the analysis of the $L_1$ spectral norm of the algorithm output. This advantage is based on the fact that a high $L_1$ spectral norm of the output of a quantum decision tree is a necessary condition to outperform its classical counterpart. We propose heuristics for maximizing the $L_{1}$ spectral norm, show how to combine weighted graphs to generate sequences with strictly increasing norm, and present functions exhibiting exponential quantum advantage. Finally, we establish a necessary condition linking single-query quantum advantage to the asymptotic growth of measurement projector dimensions.
- Abstract（参考訳）: 単一クエリ量子アルゴリズムの計算能力の解析は、1つのオラクル呼び出しから最大情報を抽出し、量子優位性の基本的な限界を明らかにし、最適なリソース効率の量子計算を可能にするために重要である。
本稿では,重み付きグラフとして単一クエリ量子決定木の定式化を提案する。
この定式化は、アルゴリズム出力の$L_1$スペクトルノルムの分析を容易にするという利点がある。
この利点は、量子決定木の出力の高額なL_1$スペクトルノルムが古典的基準よりも上回る必要条件であるという事実に基づいている。
我々は、$L_{1}$スペクトルノルムを最大化するためのヒューリスティックスを提案し、重み付きグラフを組み合わせて、厳密に増加するノルムを持つシーケンスを生成する方法を示し、指数的量子優位性を示す関数を示す。
最後に、計測プロジェクター次元の漸近的成長に単一クエリの量子優位性をリンクさせる必要条件を確立する。
関連論文リスト
- Quantum Orthogonal Separable Physics-Informed Neural Networks [0.0]
本稿では、偏微分方程式を解くための新しいアーキテクチャであるQO-SPINN(Quantum Orthogonal Separable Physics-Informed Neural Networks)を紹介する。
量子アルゴリズムを用いて各層内の行列乗法を高速化し,$mathcal O(dlog d/2)$ complexity を達成する。
我々は、不確実性定量化(UQ)のための堅牢で効率的なフレームワークを提供しており、これは私たちの知る限り、分離可能なPINN用に特別に設計された最初のUQ手法である。
論文 参考訳（メタデータ） (2025-11-16T14:15:19Z) - Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。
結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
論文 参考訳（メタデータ） (2025-08-04T16:44:53Z) - QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
QAMA(Quantum Annealing Multi-Head Attention)は、エネルギーベースのハミルトン最適化問題として注目を集める新しいドロップイン演算子である。
この枠組みでは、トークン相互作用を二項二項項に符号化し、低エネルギー構成の探索に量子アニールを用いる。
経験的に、自然言語と視覚のベンチマークによる評価は、タスク全体にわたって、標準的なマルチヘッドの注意から少なくとも2.7ポイントの精度が低下していることを示している。
論文 参考訳（メタデータ） (2025-04-15T11:29:09Z) - Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
量子源からのエネルギー抽出は、量子電池のような新しい量子デバイスを開発するための重要なタスクである。
量子源からエネルギーを完全に抽出する主な問題は、任意のユニタリ演算をシステム上で行うことができるという仮定である。
本稿では,変分量子固有解法(VQE)アルゴリズムにインスパイアされた抽出可能エネルギーの最適化手法を提案する。
論文 参考訳（メタデータ） (2023-10-11T15:59:54Z) - Alleviating the quantum Big-$M$ problem [0.22615818641180715]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Quantum Dueling: an Efficient Solution for Combinatorial Optimization [3.7398607565670536]
量子デュエル(quantum dueling)と呼ぶ汎用最適化のための新しいアルゴリズムを提案する。
量子デュエルは、追加のqubitレジスタを統合することで革新的であり、2組のソリューションが競合するデュエルのシナリオを効果的に生成する。
我々の研究は、量子ビットの数を増やすことで、これまで考えられていなかったアルゴリズムの開発が可能になり、効率的な量子アルゴリズム設計の進歩の道を開くことを実証している。
論文 参考訳（メタデータ） (2023-02-20T18:33:55Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。