論文の概要: Improved Quantum Query Bounds for Boolean Matrix Product Verification

• arxiv url: http://arxiv.org/abs/2609.40180v2
• Date: Mon, 05 Oct 2026 17:46:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.479503
• Title: Improved Quantum Query Bounds for Boolean Matrix Product Verification
• Title（参考訳）: ブール行列製品検証のための量子クエリ境界の改善
• Abstract要約: ブール行列製品検証(mathsfBMPV$)の量子クエリ複雑性に対する最初の非自明な上限を証明する。 n$行列の$ntimes n$の上限は$widetilde O(n17/12)$であり、Bhrman と palek による Grover search を用いて得られる標準 $O(n3/2)$境界を改善する[SODA 2006]。 また、$mathsfBMPV$の変種に対して、厳密な$widetilde (n3/2)$boundを証明します。
• 参考スコア（独自算出の注目度）: 6.102000456192989
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.
• Abstract（参考訳）: 我々は、Boolean Matrix Product Verification(\mathsf{BMPV}$)の量子クエリ複雑性に対する最初の非自明な上限を証明する。 n$行列に対して、上界は$\widetilde O(n^{17/12})$で、標準の$O(n^{3/2})$バウンドを改善する。 この結果を補うために$Ω(n^{5/4})$ lower bound を示し、これは以前の最もよく知られた$\widetildeΩ(n^{19/18})$ by Childs, Kimmel, Kothari [ESA 2012] よりも改善される。 我々のアプローチはオルソゴンベクトル(英語版) (\mathsf{OV}$) との接続に集中しており、これは次元$n$のブールベクトルのインデックス付きリストが不連結なサポートを持つ2つのベクトルを含むかどうかを問うものである。 特に、$\mathsf{OV}$と$\mathsf{BMPV}$の等価性を証明し、$\mathsf{OV}$の上の有界性を確立する。 また、その積が与えられた行ベクトルを含むかどうかを問う、$\mathsf{BMPV}$の変種に対する厳密な$\widetilde >(n^{3/2})$バウンドも証明する。 これらの結果は、グラフが半径が 2 であるかどうかと、その直径が 2 であるかどうかを判定する量子クエリ複雑度の間の多項式分離を意味する。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• On the query complexity of connectivity with global queries [0.2538209532048867]
  グラフがグローバルクエリと結びついているかどうかを判断する際のクエリの複雑さについて検討する。 ゼロエラーランダム化アルゴリズムは接続性を解決するために,$Omega(n)$リニアクエリを生成する必要がある。
  論文  参考訳（メタデータ） (2021-09-05T16:22:55Z)
• 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)

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

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