論文の概要: Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
- arxiv url: http://arxiv.org/abs/2609.38403v1
- Date: Tue, 29 Sep 2026 19:00:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:26.620195
- Title: Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
- Title（参考訳）: 量子PAC学習におけるサンプル複雑化の利点は、状態準備単位への逆アクセスを必要とする
- Abstract要約: 予測規則の学習に必要な未知の確率分布からサンプリングしたデータ量を量子計算で削減できるかどうかを検討する。
このような量子データのコピーのみを用いて、最適な最悪のサンプルは、古典的なPAC学習と複雑に一致する。
前方のみのアクセスは、古典的なデータや量子データコピーから学習するよりも、クエリの複雑度に有利であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Whether quantum computation can reduce the amount of data sampled from an unknown probability distribution required to learn a prediction rule is a fundamental question in quantum machine learning. Quantum PAC learning studies this question using quantum data as a quantum state whose squared amplitudes encode the unknown distribution from which classical learning data are sampled. With only copies of such quantum data, the optimal worst-case sample complexity asymptotically matches that of classical PAC learning. In contrast, access to both a state-preparation unitary for this state and its inverse can improve the query-complexity dependence on the accuracy parameter in realizable learning. However, it has remained unclear whether forward-only access allows such an improvement. In this work, taking the worst case over compatible state-preparation unitaries and their finite ambient dimensions, we show that the optimal forward-only query complexities of realizable and agnostic learning are, respectively, $Θ((d+\log(1/δ))/\varepsilon)$ and $Θ((d+\log(1/δ))/\varepsilon^2)$, where $d$ is the VC dimension of the concept class, $\varepsilon$ the accuracy parameter, and $δ$ the failure probability. These bounds match the optimal sample complexities with classical data or quantum data copies. To prove them, we establish a reduction using $q$ copies of the prepared state to approximate the Haar-averaged output of any $q$-query forward-only algorithm. These results show that forward-only access cannot provide an asymptotic query-complexity advantage over learning from classical data or quantum data copies in this worst-case setting, and establish the essential role of inverse access in the known realizable-setting improvement. Our reduction also provides a new framework for analyzing limitations of forward state-preparation access via state-copy lower bounds.
- Abstract（参考訳）: 予測規則を学習するために必要な未知の確率分布からサンプリングされたデータ量を量子計算が削減できるかどうかは、量子機械学習の基本的な問題である。
量子PAC学習は、古典的な学習データがサンプリングされた未知の分布を符号化した2乗振幅を持つ量子状態として量子データを用いてこの問題を研究する。
このような量子データのコピーのみを用いて、最適な最悪のサンプルの複雑さは、古典的なPAC学習と漸近的に一致する。
対照的に、この状態に対する状態準備ユニタリとその逆の両方へのアクセスは、実現可能な学習における精度パラメータに対するクエリ複雑度依存性を改善することができる。
しかし、前方のみのアクセスがそのような改善を可能にするかどうかはまだ不明である。
本研究では、互換性のある状態準備ユニタリとその有限周囲次元に対して最悪の場合を考慮し、実現可能および不可知学習の最適な前方のみのクエリ複雑度が、それぞれ$((d+\log(1/δ))/\varepsilon)$と$((d+\log(1/δ))/\varepsilon^2)$であり、$d$は概念クラスのVC次元、$\varepsilon$は精度パラメータ、$δは失敗確率であることを示す。
これらの境界は、古典的なデータや量子データのコピーと最適なサンプル複雑度と一致する。
それらを証明するために、準備された状態の$q$コピーを用いて、任意の$q$-queryフォワードのみのアルゴリズムの平均出力を近似する減算を確立する。
これらの結果から, フォワードオンリーアクセスは, この最悪の状況下での古典的データや量子データコピーからの学習よりも, 漸近的なクエリ・複雑さの優位性を得られず, 既知の実現可能セットの改善において, 逆アクセスが不可欠な役割を担っていることが明らかとなった。
我々の削減はまた、状態コピーの下限を経由したフォワード状態準備アクセスの制限を分析するための新しいフレームワークも提供する。
関連論文リスト
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem [18.167418729752068]
本研究では、未知の量子状態の対称性を特定することを目的とする状態隠蔽部分群問題(State hidden subgroup problem, StateHSP)について検討する。
我々は、$O(log(|G/H|)/sqrt)$forward and inverse query を用いて時間効率の量子アルゴリズムを与え、一致する $(log(|G/H|)/sqrt)$ lower bound を証明する。
応用として、安定化群を学習し、絡み合いを突き止め、隠れた翻訳対称性を同定するための高速なアルゴリズムを得る。
論文 参考訳（メタデータ） (2026-09-28T17:21:41Z) - Towards Optimal Quantum Estimators for State Frame Potential [12.326210204717336]
本稿では, 3 つのより弱いアクセスモデルの下で, 次数 $t$ の状態フレームポテンシャルを付加誤差 $varepsilon$ に推定する問題について検討する。
クエリモデルでは、$widetilde(sqrtt/varepsilon)$のほぼ最適クエリ複雑性を確立します。
一般的なサンプルモデルでは、最適なサンプル複雑性を$(t/varepsilon2)$とする。
論文 参考訳（メタデータ） (2026-08-25T15:29:24Z) - Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound [0.0]
量子ランダムアクセスコード(QRAC)は、情報の圧縮性から限られた量子資源への基本的なトレードオフを具現化したものである。
明示的な演算子形式を用いて,$(n, n-1)$-QRACの解析的構成法を確立する。
導出された最適POVMを標準量子ゲートに分解する体系的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-01-27T04:43:43Z) - Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。
Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。
評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
論文 参考訳（メタデータ） (2024-04-30T23:55:03Z) - Learning Properties of Quantum States Without the I.I.D. Assumption [7.537220883022466]
我々は、独立かつ同一に分散された(d.d.)入力状態の仮定を超えた量子状態の性質を学習するためのフレームワークを開発する。
我々は厳密な量子情報理論を用いて、主要な結果を証明している。
論文 参考訳（メタデータ） (2024-01-30T11:45:38Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Explainable quantum regression algorithm with encoded data structure [0.0]
本稿では,最初の解釈可能な量子回帰アルゴリズムを構築する。
符号化されたデータ構造は回帰マップの計算の時間的複雑さを減少させる。
我々は、中性冷原子とイオンに実装されたマルチキュービットゲートを持つ潜在的な量子ユーティリティを想定する。
論文 参考訳（メタデータ） (2023-07-07T00:30:16Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。