論文の概要: On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$
- arxiv url: http://arxiv.org/abs/2303.10935v2
- Date: Tue, 21 Mar 2023 15:33:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-22 11:10:12.618425
- Title: On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$
- Title（参考訳）: $\text{MOD}_m^n$ と $\text{EXACT}_{k,l}^n$ の正確な量子クエリ複雑性について
- Authors: Zekun Ye
- Abstract要約: 我々は、$textMOD_mn$を計算するための最適量子アルゴリズムを提案する。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子的クエリ複雑性を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The query model has generated considerable interest in both classical and
quantum computing communities. Typically, quantum advantages are demonstrated
by showcasing a quantum algorithm with a better query complexity compared to
its classical counterpart. Exact quantum query algorithms play a pivotal role
in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm
demonstrated exponential quantum advantages over classical deterministic
algorithms. As an important complexity measure, exact quantum query complexity
describes the minimum number of queries required to solve a specific problem
exactly using a quantum algorithm.
In this paper, we consider the exact quantum query complexity of the
following two $n$-bit symmetric functions: $\text{MOD}_m^n(x) = |x| \bmod m$
and $$ \text{EXACT}_{k,l}^n(x) = \begin{cases} 1, &\text{if }|x| \in \{k,l\},
\\ 0, &\text{otherwise}, \end{cases} $$ where $|x|$ is the number of $1$'s in
$x$. Our results are as follows: i) We present an optimal quantum algorithm for
computing $\text{MOD}_m^n$, achieving a query complexity of $\lceil
n(1-\frac{1}{m}) \rceil$ for $1 < m \le n$. This settles a conjecture proposed
by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we
show the exact quantum query complexity of a broad class of symmetric functions
that map $\{0,1\}^n$ to a finite set $X$ is less than $n$. ii) When $l-k \ge
2$, we give an optimal exact quantum query algorithm to compute
$\text{EXACT}_{k,l}^n$ for the case $k=0$ or $k=1,l=n-1$. This resolves the
conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.
- Abstract（参考訳）: このクエリモデルは、古典的および量子コンピューティングのコミュニティに大きな関心を集めている。
通常、量子の利点は、従来のアルゴリズムに比べてクエリーの複雑さが良い量子アルゴリズムを示すことによって示される。
量子クエリーアルゴリズムは、量子アルゴリズムの開発において重要な役割を果たす。
例えば、deutsch-jozsaアルゴリズムは古典的決定論的アルゴリズムよりも指数関数的な量子効果を示した。
重要な複雑性尺度として、厳密な量子クエリ複雑性は、量子アルゴリズムを用いて特定の問題を解決するのに必要なクエリの最小数を記述する。
本稿では、以下の2つの$n$-bit対称関数の正確な量子クエリの複雑さを検討する。 $\text{mod}_m^n(x) = |x| \bmod m$ and $$ \text{exact}_{k,l}^n(x) = \begin{cases} 1, &\text{if }|x| \in \{k,l\}, \\0, &\text{otherwise}, \end{cases}$ ここで$|x|$は$x$の$$$$'sの数である。
結果は以下の通りである。
i)$\text{mod}_m^n$を計算するための最適な量子アルゴリズムを示し、$\lceil n(1-\frac{1}{m}) \rceil$を1 < m \le n$とする。
これは、cornelissen, mande, ozols and de wolf (2021) によって提案された予想を定めている。
このアルゴリズムに基づいて、$\{0,1\}^n$ から有限集合 $x$ への写像が $n$ 以下であるような対称関数の幅広いクラスにおける正確な量子クエリの複雑さを示す。
ii) $l-k \ge 2$ の場合、$k=0$ または $k=1,l=n-1$ に対して$\text{exact}_{k,l}^n$ を計算する最適な量子クエリアルゴリズムを与える。
ambainis, iraids, nagaj (2017) によって提案された予想を部分的に解決する。
関連論文リスト
- Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。
我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
論文 参考訳（メタデータ） (2024-01-18T12:50:20Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - 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) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。