Fugu-MT 論文翻訳(概要): A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity

論文の概要: A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity

arxiv url: http://arxiv.org/abs/2609.11664v1
Date: Thu, 10 Sep 2026 15:04:28 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-11 23:53:35.41002
Title: A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity
Title（参考訳）: 証明書複雑度と量子クエリ複雑度との近似的分離
Abstract要約: 合計ブール関数$f$, $Q(f) = widetildeO(sqrt[4]C(f))$, $Q(f)$は有界エラー量子クエリ複雑性を示し、$C(f)$は証明複雑性を表す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We construct a total Boolean function $f$ for which $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.
Abstract（参考訳）: 合計ブール関数 $f$, $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, $Q(f)$ は有界エラー量子クエリ複雑性を示し、$C(f)$ は証明複雑性を表す。これは長年のオープンな疑問を解決し、対数的要因に強く依存する。

関連論文リスト

Randomized query complexity can beat certificate complexity [1.7889544416325804]
R(f) = O(sqrtC(f)) の関数を構成する。同じ関数はまた、$Q(f) = O(C(f)1/4) を持ち、Q(f) は f の有界エラー量子クエリ複雑性である。
論文参考訳（メタデータ） (2026-09-14T05:29:42Z)
Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
for general max-k-XORSAT with $k geq 3$, no-time algorithm can be significantly better than random guessing on worst-case instance。この接続を明示的にし、任意の有限体上の有界次数$D$および有界次数$E$k$-LINSAT$(q,r)$にハードネスを拡張する。
論文参考訳（メタデータ） (2026-06-11T16:59:12Z)
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
正規化トレース 2-nTr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。 f(x)$ が近似次数 $(rm poly(n))$ の連続関数であれば、2-nTr[f(A)]$ を定数加法誤差まで見積もる。
論文参考訳（メタデータ） (2026-04-02T01:15:12Z)
Quantum State-Aware Query Complexity: Krylov Compression and Polynomial Query Duality [0.0]
この状態認識の観点は、量子クエリによるKrylov/Favard近似という最悪のケース境界を洗練させ、状態依存のスペクトル構造が均一な設計よりも大幅に節約できるかを説明している。
論文参考訳（メタデータ） (2025-10-13T18:00:03Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
本稿では,2つのパリンドロムを結合した文脈自由言語を認識するための量子特性試験アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-17T07:19:20Z)
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
論文参考訳（メタデータ） (2023-01-22T22:08:28Z)
Quantum divide and conquer [6.527258283771695]
Divide-and-conquerフレームワークは、古典的なアルゴリズム設計で広く使われている。 C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ の類似反復関係を生じる量子分割・量子化フレームワークについて述べる。
論文参考訳（メタデータ） (2022-10-12T17:14:28Z)
Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
時間複雑性に対して$widetildeOleft(n3/4-1/4(2k-1)right)の新たな上限を与える。この新しい手法を用いて,$O(n)$クエリと$O(n2)$タイムで溶接木を解く方法を示す。
論文参考訳（メタデータ） (2022-08-29T10:51:56Z)
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)
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)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)

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