論文の概要: Tight bounds for hybrid quantum-classical query algorithms

• arxiv url: http://arxiv.org/abs/2610.06803v1
• Date: Mon, 05 Oct 2026 17:53:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 22:37:35.527172
• Title: Tight bounds for hybrid quantum-classical query algorithms
• Title（参考訳）: ハイブリッド量子古典的クエリアルゴリズムのためのタイトバウンダリ
• Abstract要約: クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。 状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。
• 参考スコア（独自算出の注目度）: 0.45880283710344066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
• Abstract（参考訳）: クエリモデルにおけるハイブリッド量子古典アルゴリズムについて検討する。 計算は量子サブルーチンで構成され、最大$q$oracleクエリを生成する。 このモデルでは、いくつかの問題に対して上と下の境界が一致することを証明している。 (i) (Unbiased) 位相推定を精度$ε$まで推定するには、$(\frac{1}{q ε^2})$クエリが必要である。 (ii) (Unbiased) 精度の$ε$までの振幅推定には、$(\frac{p(1-p)}{q ε^2})$クエリが必要です。 (iii)$N$項目間の検索には、$s(\frac{N}{q})$クエリが必要である。 (iv) 2つのレベルAND-ORツリー(AND of $m$ ORs, with $n$ inputs to each OR)は、クエリーを$(\frac{nm}{q})で要求する。 これらの境界は、古典的複雑性に対応する1から1までのすべての$q$に対して、各問題の非制限量子クエリ複雑性である$Q(f)$まで最適である。 また、状態準備単位によって指定された2つの分布を区別するハイブリッドな下界を導出する。 特定の下位境界に加えて、ハイブリッド量子アルゴリズム(これはこれまで非常にアドホックだった)の下位境界を証明する方法の開発も重要な貢献である。 最初の2つの境界は共通の枠組みから従う: 測定書面上の確率分布を解析し、その識別性を捉える進捗測度をバウンドする。 AND-ORバウンダリはより繊細な議論を必要とし、アルゴリズムで利用可能な情報を古典的に、量子形式で追跡する2つの進歩測度を組み合わせる。

関連論文リスト

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Statistical Query Lower Bounds for Smoothed Agnostic Learning [42.71001191804269]
  我々は,最近導入されたCKKMS24によるスムーズな学習の複雑さについて検討した。 具体的には、滑らかなモデルにおいて、ガウス分布の下で半空間を不可知的に学習することに焦点を当てる。
  論文  参考訳（メタデータ） (2026-02-24T18:46:46Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。