論文の概要: Basic quantum subroutines: finding multiple marked elements and summing numbers

• arxiv url: http://arxiv.org/abs/2302.10244v1
• Date: Mon, 20 Feb 2023 19:11:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-22 17:18:00.099399
• Title: Basic quantum subroutines: finding multiple marked elements and summing numbers
• Title（参考訳）: 基本量子サブルーチン:複数の有マーク要素の発見と総和数
• Authors: Joran van Apeldoorn, Sander Gribling, Harold Nieuwboer
• Abstract要約: 量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(\sqrt{N k})$ of quantum queries and only a polylogarithmic overhead in the gate complexity, in the setting where one has a small quantum memory. Previous algorithms either incurred a factor $k$ overhead in the gate complexity, or had an extra factor $\log(k)$ in the query complexity. We then consider the problem of finding a multiplicative $\delta$-approximation of $s = \sum_{i=1}^N v_i$ where $v=(v_i) \in [0,1]^N$, given quantum query access to a binary description of $v$. We give an algorithm that does so, with probability at least $1-\rho$, using $O(\sqrt{N \log(1/\rho) / \delta})$ queries (under mild assumptions on $\rho$). This quadratically improves the dependence on $1/\delta$ and $\log(1/\rho)$ compared to a straightforward application of amplitude estimation. To obtain the improved $\log(1/\rho)$ dependence we use the first result.
• Abstract（参考訳）: 最小の量子メモリを持つ設定において、最適な数$O(\sqrt{Nk})$とゲート複雑性におけるポリ対数的オーバーヘッドのみを用いて、$k$マークされた要素を$N$の一覧で見つける方法を示す。 以前のアルゴリズムでは、ゲートの複雑さで$k$のオーバーヘッドを発生させたり、クエリの複雑さで$\log(k)$を増加させたりしていた。 次に、$s = \sum_{i=1}^N v_i$, $v=(v_i) \in [0,1]^N$の乗法的な$\delta$-approximationを求める問題を考える。 我々は、$O(\sqrt{N \log(1/\rho) / \delta})$クエリ($\rho$の穏やかな仮定の下で)を用いて、少なくとも1-\rho$の確率を持つアルゴリズムを与える。 これにより、1/\delta$ と $\log(1/\rho)$ への依存度は振幅推定の直接的な適用よりも向上する。 改良された$\log(1/\rho)$ 依存を得るには、最初の結果を使う。

関連論文リスト

• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。 最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。 2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
  論文  参考訳（メタデータ） (2024-04-08T02:13:40Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  量子状態 $varrho$ と量子化器 $cal E(varrho) が与えられたとき、$cal E(varrhootimes N)$ を決定するのは難しい。 本研究では, ある球対称状態の1発の蒸留可能な絡み合いを, このような拡張付加性によって定量的に近似できることを示す。
  論文  参考訳（メタデータ） (2022-07-31T00:23:10Z)
• 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)
• 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)
• Improved quantum data analysis [1.8416014644193066]
  我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。 また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
  論文  参考訳（メタデータ） (2020-11-22T01:22:37Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• 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)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。 ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。 本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
  論文  参考訳（メタデータ） (2019-12-31T14:52:36Z)

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

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