論文の概要: On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$

• arxiv url: http://arxiv.org/abs/2303.10935v5
• Date: Sun, 27 Oct 2024 04:18:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 16:01:07.287970
• 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: Penghui Yao, Zekun Ye,
• Abstract要約: 我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
• 参考スコア（独自算出の注目度）: 4.956977275061968
• License:
• 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:\{0,1\}^n \rightarrow \{0,...,m-1\}$ and $\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$, which are defined as $\text{MOD}_m^n(x) = |x| \bmod m$ and $ \text{EXACT}_{k,l}^n(x) = 1$ iff $|x| \in \{k,l\}$, 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:\{0,1\}^n \rightarrow \{0,...,m-1\}$と$\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$の正確な量子クエリ複雑性を、$\text{MOD}_m^n(x) = |x| \bmod m$と$ \text{EXACT}_{k,l}^n(x) = 1$ iff $|x| \in \{k,l\}$と定義する。 結果は以下の通りである。 i) $\lceil n(1-\frac{1}{m}) \rceil$ for $1 < m \le n$。 これは、コルネリセン、マンデ、オゾルズ、デ・ウルフによって提唱された予想(2021年)に決着をつける。 このアルゴリズムに基づいて、$\{0,1\}^n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。 i) $l-k \ge 2$ の場合、$k=0$ または $k=1,l=n-1$ の場合、$\text{EXACT}_{k,l}^n$ を計算するのに最適な正確な量子クエリアルゴリズムを与える。 これは、アンバイニス、イライド、ナガジ(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)

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

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