論文の概要: Unitarity estimation for quantum channels
- arxiv url: http://arxiv.org/abs/2212.09319v4
- Date: Tue, 9 May 2023 15:14:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 16:06:15.159579
- Title: Unitarity estimation for quantum channels
- Title(参考訳): 量子チャネルのユニタリ性推定
- Authors: Kean Chen, Qisheng Wang, Peixun Long, Mingsheng Ying
- Abstract要約: ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
- 参考スコア(独自算出の注目度): 7.323367190336826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Estimating the unitarity of an unknown quantum channel $\mathcal{E}$ provides
information on how much it is unitary, which is a basic and important problem
in quantum device certification and benchmarking. Unitarity estimation can be
performed with either coherent or incoherent access, where the former in
general leads to better query complexity while the latter allows more practical
implementations. In this paper, we provide a unified framework for unitarity
estimation, which induces ancilla-efficient algorithms that use
$O(\epsilon^{-2})$ and $O(\sqrt{d}\cdot\epsilon^{-2})$ calls to $\mathcal{E}$
with coherent and incoherent accesses, respectively, where $d$ is the dimension
of the system that $\mathcal{E}$ acts on and $\epsilon$ is the required
precision. We further show that both the $d$-dependence and
$\epsilon$-dependence of our algorithms are optimal. As part of our results, we
settle the query complexity of the distinguishing problem for depolarizing and
unitary channels with incoherent access by giving a matching lower bound
$\Omega(\sqrt{d})$, improving the prior best lower bound $\Omega(\sqrt[3]{d})$
by Aharonov et al. (Nat. Commun. 2022) and Chen et al. (FOCS 2021).
- Abstract(参考訳): 未知の量子チャネル $\mathcal{e}$ のユニタリ性の推定は、それがどの程度ユニタリであるかの情報を提供する。
ユニタリティ推定はコヒーレントアクセスまたは非コヒーレントアクセスで行うことができ、前者は一般にクエリの複雑さを向上し、後者はより実用的な実装を可能にする。
本稿では,コヒーレントおよび非コヒーレントアクセスを持つ$\mathcal{e}$ に対する$o(\epsilon^{-2})$ と $o(\sqrt{d}\cdot\epsilon^{-2})$ を,それぞれ $d$ が $\mathcal{e}$ が作用するシステムの次元である$\mathcal{e}$ と $\epsilon$ を必要な精度とする,ユニタリティ推定のための統一的なフレームワークを提案する。
さらに、我々のアルゴリズムの$d$-dependenceと$\epsilon$-dependenceの両方が最適であることを示す。
この結果の一環として,Aharonov et al. (Nat. Commun. 2022) と Chen et al. (FOCS 2021) により, 一致した下限の$\Omega(\sqrt{d})$, 前の最下限の$\Omega(\sqrt[3]{d})$を改良することにより, 不整合アクセスを持つ分極チャネルとユニタリチャネルの区別問題に対するクエリ複雑性を解決した。
関連論文リスト
- Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT [0.0]
本稿では、$k$-local quantum searchと呼ばれる、構造化量子探索アルゴリズムのファミリーを紹介する。
最大$k$-SSATは、平均ケース複雑性理論に基づく$m=Omega(n2+epsilon)$が平均であることを証明する。
論文 参考訳(メタデータ) (2024-03-05T15:03:47Z) - The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - 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) - Succinct quantum testers for closeness and $k$-wise uniformity of
probability distributions [1.7789870146290503]
我々は、近接性の性質をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
本稿では,クエリ複雑性を$Orbrasqrtnk/varepsilonで表した最初の量子アルゴリズムを提案する。
我々の量子アルゴリズムは、振幅推定のような基本的な量子サブルーチンのみを用いて、かなり単純で時間効率が高い。
論文 参考訳(メタデータ) (2023-04-25T15:32:37Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳(メタデータ) (2023-02-13T00:22:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。