論文の概要: An Optimal Quantum Linear Systems Algorithm

• arxiv url: http://arxiv.org/abs/2609.35660v1
• Date: Mon, 28 Sep 2026 17:22:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 19:49:58.479325
• Title: An Optimal Quantum Linear Systems Algorithm
• Title（参考訳）: 最適量子線形システムアルゴリズム
• Abstract要約: 量子線形システム問題(QLSP)では、条件番号$$$の$d$スパース$Ntimes N$Matrix$A$へのクエリアクセスが与えられる。 目標は、$vec x$ of $Avecx=vecb$に比例する量子状態に$$-approximationを出力することである。 行列エントリに対して$O(sqrt N)$クエリを使用して,任意の$Ntimes N$ユニタリを境界誤差で実装可能であることを示す。
• 参考スコア（独自算出の注目度）: 1.4903245304585715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.
• Abstract（参考訳）: 量子線形システム問題(QLSP)では、条件数$κ$の$d$スパース$N\times N$Matrix $A$と、ベクトル$\vec b$に比例する量子状態を作成することができる。 目標は、解の$\vec x$ of $A\vec{x}=\vec{b}$に比例する量子状態に$ε$-近似を出力することである。 長い研究の後、QLSPの最もよく知られた量子アルゴリズムは、クエリ複雑性$O(κd\log(1/ε))$と$κ\sqrt d(κd/ε)^{o(1)}$であり、最もよく知られた下界は$Ω(κ\log(1/ε))$と$Ω(κ\sqrt d)$である。 これらの境界を改良し、QLSPの複雑さが$(κ\sqrt d\log(1/ε))$であることを示す。 また、Berry と Childs のオープンな問題は、任意の$N\times N$ Unitary が、行列エントリへの$O(\sqrt N)$クエリを使って境界誤差で実装可能であることを示すことで解決する。

関連論文リスト

• Simultaneously Query-Optimal Quantum Linear-System Algorithm [2.8802622551493773]
  Oleft(logfrac1varepsilonright)$ query to $U_A$ and $Oleft(/sright)$ query to $U_b$。 すべての量子線型系アルゴリズムと全ての解ノルムスケールに対して、そのアルゴリズムは$(/s)$行列クエリと$(/s)$状態準備クエリの両方を必要とする単一のエルミートインスタンスが存在する。
  論文  参考訳（メタデータ） (2026-09-27T15:49:21Z)
• A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers [0.0]
  量子線形システム解法は、量子コンピューティングにおいて中心となるアルゴリズムプリミティブの1つを形成する。 $と$varepsilonへの依存はすでによく理解されています。 スパースアクセスモデルにおいて、完全関節下界$(sqrts)$を証明します。
  論文  参考訳（メタデータ） (2026-09-18T18:02:04Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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