論文の概要: Exact Quantum Algorithms for Composed Boolean Functions
- arxiv url: http://arxiv.org/abs/2611.16412v1
- Date: Thu, 12 Nov 2026 07:24:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.387194
- Title: Exact Quantum Algorithms for Composed Boolean Functions
- Title(参考訳): ブール関数合成のためのエクササイズ量子アルゴリズム
- Abstract要約: ブール関数全体のブロック合成に対する正確な量子アルゴリズムについて検討する。
Q_E(fcirc g)=O!left(mD+Q_E(f)Q_1/(4D)(g)right)を証明します。
また、異なる内部関数を許容し、量子通信において類似の定量的分離を与える。
- 参考スコア(独自算出の注目度): 0.06157382820537719
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\sqrt2)^{k(1+o(1))}$ queries asymptotically. More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}$ and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with $s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\ldots$. A second construction gives $R \ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. We also allow different inner functions and give analogous quantitative separations in quantum communication.
- Abstract(参考訳): ブール関数全体のブロック合成に対する正確な量子アルゴリズムについて検討する。
外部関数$f$の次数$D$と$m$ビット上の内関数$g$に対して、$Q_E(f\circ)を証明します。
g)=O\!
\left(mD+Q_E)
(f)Q_{1/(4D)}
(g)。
$$ このアルゴリズムは、近似内部評価と有限正確な補正を組み合わせる。
その2つのコストは外部関数の異なるパラメータによって支配される: 正確なクエリ複雑性はシミュレーションのコストを決定するが、多項式次数は補正に使用される内部ブロックの数を決定する。
まず、アリティ依存誤差しきい値を用いて構築を行い、次に上記の次数依存しきい値を得る。
再帰的三次不等式に対しては、$(3/\sqrt2)^{k(1+o(1))}$クエリを漸近的に使用する正確なアルゴリズムを与える。
より一般的には、固定された非定数全ガジェット$h$に対して、正確な再帰率を$\max\{\textrm{deg} と決定する。
(h)\operatorname{Adv}^{\pm}
(h)\}$を証明し、$Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$とする。
組成制限はまた、$Q_{\varepsilon}$と$°$から正確な量子クエリ複雑性への分離を、$Q_E$(Tal と Kulkarni 2016 Chicago Journal of Theory Computer Science の分数ブロック感度と似ている)に転送することができる。
我々は、$s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$でファミリを構築し、以前の指数である$.1527\ldots$を改善した。
2つ目の構成は、$R \ge Q_E^{2-o(1)}$を与え、以前の指数を3/2$に改善する。
また、異なる内部関数を許容し、量子通信において類似の定量的分離を与える。
関連論文リスト
- Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions [66.4427591916051]
oracle-interrogationアルゴリズムは、$n/2+O(sqrt n)$量子クエリを使って、有界誤差を持つすべての$n$ビットブール関数を計算する。
parityは$lceil n/2rceil$クエリを使って正確に計算できるが、単一のBoolean出力に対して$n/2$を超える追加のオーバーヘッドが必要かどうかは未定である。
論文 参考訳(メタデータ) (2026-11-06T17:58:16Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳(メタデータ) (2026-07-08T17:49:40Z) - On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。
格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。
$d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
論文 参考訳(メタデータ) (2026-04-27T10:23:24Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳(メタデータ) (2023-02-20T19:11:44Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳(メタデータ) (2021-04-29T14:50:03Z) - 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) - 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) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。