論文の概要: Simultaneously Query-Optimal Quantum Linear-System Algorithm
- arxiv url: http://arxiv.org/abs/2609.33686v1
- Date: Sun, 27 Sep 2026 15:49:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-04 17:43:06.930594
- Title: Simultaneously Query-Optimal Quantum Linear-System Algorithm
- Title（参考訳）: 同時クエリ最適量子線形システムアルゴリズム
- Abstract要約: Oleft(logfrac1varepsilonright)$ query to $U_A$ and $Oleft(/sright)$ query to $U_b$。
すべての量子線型系アルゴリズムと全ての解ノルムスケールに対して、そのアルゴリズムは$(/s)$行列クエリと$(/s)$状態準備クエリの両方を必要とする単一のエルミートインスタンスが存在する。
- 参考スコア（独自算出の注目度）: 2.8802622551493773
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
- Abstract（参考訳）: 量子線形系アルゴリズムは、ブロック符号化オラクル$U_A$と状態準備オラクル$U_b$を介して右辺を介して係数行列にアクセスする。
O(κ\log(1/\varepsilon))$ query to $U_A$ と $O(κ/s)$ query to $U_b$ ここで$s=α\|A^{-1}b\|$。
一つのアルゴリズムが両方の境界を同時に達成できるかどうかは未定である。
私たちはこの問題を肯定的に解決する。
定数係数の$s$を仮定すると、正規化された解をエラーに準備する量子線形系アルゴリズムが与えられる: $ O\left(κ\log\frac1\varepsilon\right)$ query to $U_A$ and $O\left(κ/{s}\right)$ query to $U_b$。
このアルゴリズムは、状態準備を精度改善から切り離すため、マトリックス・クエリー数だけはターゲットの精度に依存する。
すべての量子線型系アルゴリズムと全ての解ノルムスケールに対して、そのアルゴリズムには$Ω(κ\log(1/\varepsilon))$行列クエリと$Ω(κ/s)$状態準備クエリの両方を必要とする単一のエルミートインスタンスが存在する。
したがって、2つのオラクル複体は同時に最適化でき、結果として得られる境界は共同で最適である。
関連論文リスト
- An Optimal Quantum Linear Systems Algorithm [1.4903245304585715]
量子線形システム問題(QLSP)では、条件番号$$$の$d$スパース$Ntimes N$Matrix$A$へのクエリアクセスが与えられる。
目標は、$vec x$ of $Avecx=vecb$に比例する量子状態に$$-approximationを出力することである。
行列エントリに対して$O(sqrt N)$クエリを使用して,任意の$Ntimes N$ユニタリを境界誤差で実装可能であることを示す。
論文 参考訳（メタデータ） (2026-09-28T17:22:14Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳（メタデータ） (2026-09-09T10:13:43Z) - Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳（メタデータ） (2022-08-14T02:49:26Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。