論文の概要: Query-optimal estimation of unitary channels in diamond distance
- arxiv url: http://arxiv.org/abs/2302.14066v2
- Date: Mon, 29 Jul 2024 20:16:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-31 23:09:12.656618
- Title: Query-optimal estimation of unitary channels in diamond distance
- Title（参考訳）: ダイヤモンド距離における一元チャネルのクエリ-最適推定
- Authors: Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang,
- Abstract要約: 単一量子チャネルのプロセストモグラフィーについて考察する。
我々は、ダイヤモンドノルムの未知のユニタリに$varepsilon$-closeのユニタリの古典的な記述を出力する。
- 参考スコア（独自算出の注目度）: 3.087385668501741
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a $\textsf{d}$-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O(\textsf{d}^2/\varepsilon)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O(\textsf{d}^3/\varepsilon^2)$ [via standard process tomography] or $O(\textsf{d}^{2.5}/\varepsilon)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to "bootstrap" an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega(\textsf{d}^2/\varepsilon)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.
- Abstract（参考訳）: 単一量子チャネルのプロセストモグラフィーについて考察する。
未知のユニタリチャネルが$\textsf{d}$-dimensional quditに作用することを考えると、ダイヤモンドノルムの未知ユニタリに$\varepsilon$-closeのユニタリの古典的な記述を出力することを目指している。
我々は、未知のチャネルと1つのquditしか適用しない$O(\textsf{d}^2/\varepsilon)$を使ってエラーを発生させるアルゴリズムを設計する。
これは以前の結果よりも改善され、$O(\textsf{d}^3/\varepsilon^2)$[標準プロセストモグラフィ]または$O(\textsf{d}^{2.5}/\varepsilon)$[Yang, Renner, Chiribella, PRL 2020]アプリケーションを使用する。
この結果を示すために、Heisenbergスケールで$\varepsilon$-error推定を生成できるアルゴリズムを「ブートストラップ」する簡単な手法を導入する。
最後に、未知のユニタリの逆あるいは制御されたバージョンにアクセスしても、推定に$\Omega(\textsf{d}^2/\varepsilon)$アプリケーションが必要であることを示す補完的な下界を証明する。
このことから,本アルゴリズムは問合せの複雑さと空間の複雑さの両立を図っている。
関連論文リスト
- Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
2つの敵が同時に存在するときの疎線形回帰を効率的に計算可能な推定器を設計する手法を開発した。
2つの敵が存在する場合の重み付き設計に適した重み付きハマー損失の新しい解析法を提案する。
論文 参考訳（メタデータ） (2024-10-31T13:51:59Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。
直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T12:24:14Z) - 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) - Replicability in Reinforcement Learning [46.89386344741442]
生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。
ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
論文 参考訳（メタデータ） (2023-05-31T05:16:23Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳（メタデータ） (2022-12-19T09:36:33Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。