Fugu-MT 論文翻訳(概要): Distributed Grover's algorithm

論文の概要: Distributed Grover's algorithm

arxiv url: http://arxiv.org/abs/2204.10487v4
Date: Mon, 14 Nov 2022 15:30:40 GMT
ステータス: 処理完了
システム内更新日: 2023-02-16 01:15:52.465143
Title: Distributed Grover's algorithm
Title（参考訳）: 分散Groverのアルゴリズム
Authors: Daowen Qiu, Le Luo, Ligang Xiao
Abstract要約: 本稿では,より少ないクエリ時間と少ない入力ビット数で$f$の分散Groverのアルゴリズムを提案する。特に$a=1$の場合、分散Groverのアルゴリズムは$lfloor fracpi4sqrt2n-krceil+2t_a+1$しか必要としない。
参考スコア（独自算出の注目度）: 1.9551668880584971
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Let Boolean function $f:\{0,1\}^n\longrightarrow \{0,1\}$ where $|\{x\in\{0,1\}^n| f(x)=1\}|=a\geq 1$. To search for an $x\in\{0,1\}^n$ with $f(x)=1$, by Grover's algorithm we can get the objective with query times $\lfloor \frac{\pi}{4}\sqrt{\frac{2^n}{a}} \rfloor$. In this paper, we propose a distributed Grover's algorithm for computing $f$ with lower query times and smaller number of input bits. More exactly, for any $k$ with $n>k\geq 1$, we can decompose $f$ into $2^k$ subfunctions, each which has $n-k$ input bits, and then the objective can be found out by computing these subfunctions with query times at most $\sum_{i=1}^{r_i} \lfloor \frac{\pi}{4}\sqrt{\frac{2^{n-k}}{b_i}} \rfloor+\lceil\sqrt{2^{n-k}}\rceil+2t_a+1$ for some $1\leq b_i\leq a$ and $r_i\leq 2t_a+1$, where $t_a=\lceil 2\pi\sqrt{a}+11\rceil$. In particular, if $a=1$, then our distributed Grover's algorithm only needs $\lfloor \frac{\pi}{4}\sqrt{2^{n-k}} \rfloor$ queries, versus $\lfloor \frac{\pi}{4}\sqrt{2^{n}} \rfloor$ queries of Grover's algorithm. %When $n$ qubits belong to middle scale but still are a bit difficult to be processed in practice, $n-k$ qubits are likely feasible for appropriate $k$ in physical realizability. Finally, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF).
Abstract（参考訳）: ブール関数 $f:\{0,1\}^n\longrightarrow \{0,1\}$ ここで $|\{x\in\{0,1\}^n| f(x)=1\}|=a\geq 1$ とする。 Groverのアルゴリズムで$x\in\{0,1\}^n$を$f(x)=1$で検索するには、クエリ時間$\lfloor \frac{\pi}{4}\sqrt{\frac{2^n}{a}} \rfloor$が目的である。本稿では,少ないクエリ時間と少ない入力ビット数で$f$を計算する分散グローバーアルゴリズムを提案する。より正確には、$n>k\geq 1$の任意の$k$に対して、$f$を$n-k$の入力ビットを持つ$^k$のサブファンクションに分解することができ、その目的は、クエリ時間で最大$\sum_{i=1}^{r_i} \lfloor \frac {\pi}{4}\sqrt {\frac{2^{n-k}}{b_i}} \rfloor+\lceil\sqrt{2^{n-k}}\rceil+2t_a+1$ for some $1\leq b_i\leq a$と$r_i\leq 2t_a+1$$$$$$t=\lceil b_i\leq a$ and $r_i\leq 2t_a+1$$, $t=\lceil 2\sq 2\rceil+11$$$である。特に$a=1$の場合、分散Groverのアルゴリズムは$\lfloor \frac{\pi}{4}\sqrt{2^{n-k}} \rfloor$クエリしか必要とせず、$\lfloor \frac{\pi}{4}\sqrt{2^{n}} \rfloor$クエリはGroverのアルゴリズムのクエリである。 % $n$ qubits が中規模に属するが、実際には処理がやや難しい場合、$n-k$ qubits は物理的実現可能性において適切な$k$に対して実現可能である。最後に、共役正規形(CNF)を持つブール関数に対応するオラクルを実現するための量子回路を構築する効率的なアルゴリズムを提案する。

関連論文リスト

The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文参考訳（メタデータ） (2022-12-29T19:26:12Z)
Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
N]:=1,cdots,N$の整数列は、センサから受信される。目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
論文参考訳（メタデータ） (2022-03-06T17:07:56Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文参考訳（メタデータ） (2021-11-28T14:08:25Z)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文参考訳（メタデータ） (2021-09-21T13:19:04Z)
Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
2つの新しいアルゴリズムで加算誤差の上と下の境界における$n$の指数のギャップを埋める。局所的にプライベートな$k$-meansの問題を、定数係数乗算近似を持つ一定数のラウンドで解くことができる。
論文参考訳（メタデータ） (2021-05-31T14:41:40Z)
Query complexity of unitary operation discrimination [6.6802048869908965]
ユニタリ演算の識別は、量子計算と情報の基本である。所望の失敗確率が$epsilon$で、$U$と$V$の識別に必要となるクエリ数を示す。
論文参考訳（メタデータ） (2020-12-05T03:49:01Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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