論文の概要: Quantum lower bounds for convex optimization and real matrix-vector query problems
- arxiv url: http://arxiv.org/abs/2609.05679v1
- Date: Fri, 04 Sep 2026 19:23:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-12 12:54:46.065837
- Title: Quantum lower bounds for convex optimization and real matrix-vector query problems
- Title（参考訳）: 凸最適化と実行列ベクトルクエリ問題のための量子下界
- Abstract要約: 凸部分集合上の凸関数を最小化する量子クエリの複雑さは$tilde(n)$であり、最もよく知られた上界とほぼ一致する。
また、トレースの計算における量子クエリの複雑さ、行列式の符号、実行列の大きさについて、線形あるいはほぼ線形な下界を示す。
- 参考スコア（独自算出の注目度）: 1.4044759410670393
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of $\mathbb{R}^n$ with evaluation and membership queries is $\tildeΩ(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times n$ real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.
- Abstract（参考訳）: 私たち(著者とAIシステム)は、評価とメンバシップクエリで$\mathbb{R}^n$の凸部分集合上の凸関数を最小化する量子クエリの複雑さが$\tildeΩ(n)$であり、最もよく知られた上限値にほぼ一致することを示した。
特に、行列ベクトルクエリを用いて$n \times n$ real matrix を反転させるのと等価な二次最小化についても、これを示す。
また、トレースの計算における量子クエリの複雑さ、行列式の符号、行列ベクトルクエリモデルにおける実行列の行列式の大きさについて、線形あるいはほぼ線形な下界を示す。
我々は、フーリエ変換が低ランク行列上で消滅し、計算される関数とよく相関する証人を特定することによって、新しい量子下界法、決定的証人法を用いる。
関連論文リスト
- Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。
我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
論文 参考訳（メタデータ） (2026-07-14T18:42:40Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Optimal Quantization for Matrix Multiplication [29.75700570685703]
アルゴリズムにより,近似誤差を明確に保証したネスト格子に基づく普遍的量子化器を構築する。
我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
我々は,N-1(N-1)時間行列の行列式と逆行列を計算するために,純粋に量子的な量子アルゴリズムを提案する。
基本的な考え方は、行列の各行を量子系の純粋な状態にエンコードすることである。
論文 参考訳（メタデータ） (2024-01-29T23:23:27Z) - Exponential quantum advantages for practical non-Hermitian eigenproblems [9.59420259768862]
我々は一般の非エルミート固有値問題に対処する量子アルゴリズムを開発した。
本手法は,ファジィ量子固有値検出器と分別・対数戦略を組み合わせることで,関連する固有値の効率よく分離する。
自発的な$PT$対称性の破れの検出、リウヴィリアのギャップの推定、古典マルコフ過程の解析における幅広い応用について論じる。
論文 参考訳（メタデータ） (2024-01-22T16:29:08Z) - Quantum eigenvalue processing [0.0]
線形代数の問題は、非正規入力行列の固有値を処理して量子コンピュータ上で解くことができる。
ブロック符号化された非正規作用素の固有値に任意の変換を適用するための量子固有値変換(QEVT)フレームワークを提案する。
また,実スペクトルを持つ演算子に対する量子固有値推定(QEVE)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-11T19:49:31Z) - Bounding Real Tensor Optimizations via the Numerical Range [0.0]
行列の数値範囲は、実テンソル積ベクトル上での最適化問題の最適値の有界化にどのように利用できるかを示す。
我々の境界は固有値に基づく自明な境界よりも強く、半定プログラミング緩和によって得られる境界よりもはるかに高速に計算できる。
論文 参考訳（メタデータ） (2022-12-24T20:03:06Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-03-28T02:24:08Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - Symplectic decomposition from submatrix determinants [0.0]
ガウスの量子情報における重要な定理は、シンプレクティック変換によって任意のガウス状態の共分散行列を対角化できることを示している。
近年,ある部分行列からエルミート行列の固有ベクトルを求める手法に着想を得て,ある部分行列式からシンプレクティックを対角化する方法を考案した。
論文 参考訳（メタデータ） (2021-08-11T18:00:03Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Quantum query complexity with matrix-vector products [9.192149087264033]
入力ベクトル上での動作を返すクエリを用いて,行列の性質を学習する量子アルゴリズムについて検討する。
行列のトレース、行列式、階数などの様々な問題に対して、量子コンピュータは古典計算の高速化を提供していないことを示す。
論文 参考訳（メタデータ） (2021-02-22T20:42:17Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。