論文の概要: Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

• arxiv url: http://arxiv.org/abs/2601.16697v1
• Date: Fri, 23 Jan 2026 12:27:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-26 14:27:27.677852
• Title: Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers
• Title（参考訳）: 量子線形系解の空間依存性複素度下界
• Authors: Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, Matthias Rosenkranz,
• Abstract要約: 量子線形システム (quantum linear system, QLS) は、潜在的な量子コンピューティングアプリケーションで使用される量子アルゴリズムの基本クラスである。 QLSソルバの複雑性を決定する主要なパラメータは、線形系の条件番号$$とsprsity$s$である。 一定の誤差でQLSを解く任意の量子アルゴリズムに対して、$(sqrts)$の低い境界を証明します。
• 参考スコア（独自算出の注目度）: 1.1666234644810893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $κ$ and sparsity $s$ of the linear system, and the target error $ε$. To date, the best known query-complexity lower bound is $Ω(κ\log(1/ε))$, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $Ω( κ\sqrt{s}\log(1/ε))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $κ,s,ε$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.
• Abstract（参考訳）: 量子線形システム (QLS) は、機械学習や微分方程式の解法など、多くの潜在的な量子コンピューティングアプリケーションで使用される量子アルゴリズムの基本クラスである。 量子アルゴリズムの性能は、しばしばクエリの複雑さによって測定され、入力にアクセスするのに必要なオラクル呼び出しの数を定量化する。 QLSソルバの複雑性を決定する主要なパラメータは、線形システムの条件番号$κ$とsprsity$s$、ターゲットエラー$ε$である。 現在知られているクエリ-複素性の下限は$Ω(κ\log(1/ε))$であり、最新のQLSソルバの最適性を確立している。 この下界の元々の証明は、ハローとコタリによるものであるが、結果は公表されていない。 さらに、線型系のスパーシティ$s$を含むより一般的な下界を論じるとき、$Ω( κ\sqrt{s}\log(1/ε))$と読むべきという民間伝承が生まれた。 本研究は,QLSの空間依存性を捕捉する厳密な下界を確立することを目的とする。 一定の誤差でQLSを解く任意の量子アルゴリズムに対して、$Ω(κ\sqrt{s})$の低い境界を証明する。 全てのパラメータに依存する$κ,s,ε$は未解決の問題であるが、我々の結果はQLS複雑性の完全な特徴づけに向けた決定的な一歩となる。

関連論文リスト

• Beyond asymptotic scaling: Comparing functional quantum linear solvers [0.0]
  多くの量子線形解法(QLS)が開発され、最も優れたオラクル最悪のケースの複雑性を達成するために競合している。 ほとんどのQLSはフォールトトレラントな量子コンピュータを前提としているため、実際のハードウェアでベンチマークを行うことはできない。 近似行列反転関数を直接実装する4つのよく知られたQVTアルゴリズムについて考察する。
  論文  参考訳（メタデータ） (2025-03-27T12:09:52Z)
• An Empirical Analysis on the Effectiveness of the Variational Quantum Linear Solver [10.562108865927005]
  変分量子線形ソルバー(VQLS)は、$Ax=b$という形の線形システムに対処する。 VQLSの主な利点は振幅符号化を使うことであり、これは線形システムサイズと対数的にスケールする多数のキュービットを必要とする。 本研究では,VQLSの適用範囲を,状態準備が非自明な問題を含む,より一般的な,より大きな問題インスタンスにまで拡張する。
  論文  参考訳（メタデータ） (2024-09-10T08:50:18Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number [0.0]
  量子線形系を解くことは、$A$が正定値であるとき、$kappa$のランタイム線形を必要とすることを示す。 2つの新しい量子アルゴリズムで、$kappa$の2次スピードアップを特徴とする。
  論文  参考訳（メタデータ） (2021-01-28T08:41:21Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。 リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
  論文  参考訳（メタデータ） (2019-09-12T17:28:09Z)

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

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