論文の概要: Query complexity of unitary operation discrimination

• arxiv url: http://arxiv.org/abs/2012.02944v2
• Date: Tue, 22 Nov 2022 09:23:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-22 00:53:49.575061
• Title: Query complexity of unitary operation discrimination
• Title（参考訳）: ユニタリ操作判別の問合せ複雑性
• Authors: Xiaowei Huang and Lvzhou Li
• Abstract要約: ユニタリ演算の識別は、量子計算と情報の基本である。 所望の失敗確率が$epsilon$で、$U$と$V$の識別に必要となるクエリ数を示す。
• 参考スコア（独自算出の注目度）: 6.6802048869908965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known Deutsch-Jozsa algorithm, Simon's algorithm, and Grover's algorithm can essentially be regarded as discriminating among individual, or sets of unitary operations (oracle operators). The problem of discriminating between two unitary operations $U$ and $V$ can be described as: Given $X\in\{U, V\}$, determine which one $X$ is. If $X$ is given with multiple copies, then one can design an adaptive procedure that takes multiple queries to $X$ to output the identification result of $X$. In this paper, we consider the problem: How many queries are required for achieving a desired failure probability $\epsilon$ of discrimination between $U$ and $V$. We prove in a uniform framework: (i) if $U$ and $V$ are discriminated with bound error $\epsilon$ , then the number of queries $T$ must satisfy $T\geq \left\lceil\frac{2\sqrt{1-4\epsilon(1-\epsilon)}}{\Theta (U^\dagger V)}\right\rceil$, and (ii) if they are discriminated with one-sided error $\epsilon$, then there is $T\geq \left\lceil\frac{2\sqrt{1-\epsilon^2}}{\Theta (U^\dagger V)}\right\rceil$, where $\lceil k\rceil$ denotes the minimum integer not less than $k$ and $\Theta(W)$ denotes the length of the smallest arc containing all the eigenvalues of $W$ on the unit circle.
• Abstract（参考訳）: ユニタリ演算の識別は、量子計算と情報の基本である。 有名なdeutsch-jozsaアルゴリズム、simonのアルゴリズム、groverのアルゴリズムを含む多くの量子アルゴリズムは、本質的には個別あるいは一元演算の集合(oracle演算子)の識別と見なすことができる。 u$ と $v$ の2つのユニタリ演算を区別する問題は、次のように記述できる: $x\in\{u, v\}$ が与えられると、どれが$x$ であるかを決定する。 もし$X$が複数のコピーで与えられるなら、複数のクエリを$X$にすることで、識別結果を$X$に出力するアダプティブなプロシージャを設計できる。 所望の失敗確率を達成するために要求されるクエリ数は、$U$と$V$の区別の$\epsilon$である。 統一された枠組みで証明します (i)$U$と$V$が有界誤差$\epsilon$で判別された場合、$T$のクエリ数は$T\geq \left\lceil\frac{2\sqrt{1-4\epsilon(1-\epsilon)}}{\Theta (U^\dagger V)}\right\rceil$, and and (ii) 片面誤差$\epsilon$ で判別される場合、$t\geq \left\lceil\frac{2\sqrt{1-\epsilon^2}}{\theta (u^\dagger v)}\right\rceil$, ここで $\lceil k\rceil$ は単位円上の$w$ の固有値を含む最小の弧の長さを表す。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Differentially Private Approximate Pattern Matching [0.0]
  我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。 目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
  論文  参考訳（メタデータ） (2023-11-13T15:53:45Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。 一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
  論文  参考訳（メタデータ） (2020-12-16T17:58:45Z)
• 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)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• 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)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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