論文の概要: When Does Adaptivity Help for Quantum State Learning?

• arxiv url: http://arxiv.org/abs/2206.05265v2
• Date: Tue, 30 May 2023 13:20:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-01 02:55:43.100911
• Title: When Does Adaptivity Help for Quantum State Learning?
• Title（参考訳）: 適応性は量子状態学習にいつ役立つのか?
• Authors: Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
• Abstract要約: 非コヒーレントな測定を使用するプロトコルには$Omega(d3/epsilon2)$コピーが必要である。 不整合の測定に最適である$tildeO(d3/gamma)$コピーのみを用いて、不整合で$gamma$-closeの状態を$rho$に出力する適応アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 19.89243001385691
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the classic question of state tomography: given copies of an unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, output $\widehat{\rho}$ which is close to $\rho$ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, $\Theta(d^2/\epsilon^2)$ copies are necessary and sufficient to get trace distance $\epsilon$. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses $O(d^3/\epsilon^2)$ copies, and multiple papers have posed it as an open question to understand whether or not this rate is tight. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires $\Omega(d^3/\epsilon^2)$ copies, matching the best known upper bound. We do so by a new proof technique which directly bounds the ``tilt'' of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is $\gamma$-close in infidelity to $\rho$ using only $\tilde{O}(d^3/\gamma)$ copies, which is optimal for incoherent measurements. In contrast, it is known that any nonadaptive algorithm requires $\Omega(d^3/\gamma^2)$ copies. While it is folklore that in $2$ dimensions, one can achieve a scaling of $O(1/\gamma)$, to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.
• Abstract（参考訳）: 未知の量子状態のコピー$\rho\in\mathbb{c}^{d\times d}$が与えられたとき、出力$\widehat{\rho}$は何らかの意味で$\rho$に近い。 すべてのコピーでコヒーレントな測定を行うことができる場合、$\theta(d^2/\epsilon^2)$コピーが必要であり、トレース距離$\epsilon$を得るのに十分である。 残念なことに、この速度を達成するプロトコルは、短期デバイスの実装を妨げる大きな量子メモリオーバーヘッドを引き起こす。 一方、非コヒーレント(単一コピー)測定を用いた最もよく知られたプロトコルは、$O(d^3/\epsilon^2)$コピーを使用しており、複数の論文が、このレートがきついかどうかを理解するためのオープンな疑問として提案している。 本研究では,不整合測定を用いたプロトコルが,適応的に選択されたとしても,最もよく知られた上限値に一致する$\Omega(d^3/\epsilon^2)$コピーが必要であることを示すことにより,この問題を完全に解決する。 我々は、測定後の後続分布の `tilt'' を直接有界とする新しい証明手法により、我々の下限の驚くほど短い証明となり、我々は独立な興味を持つと考えている。 これは、適応性がトレース距離のトモグラフィーには役に立たないことを意味するが、実際には不確かさに関してトモグラフィーに役立っていることを示している。 非一貫性測定に最適である$\tilde{o}(d^3/\gamma)$コピーのみを使用して、$\gamma$-close in in infidelity の状態を$\rho$ に出力する適応アルゴリズムを与える。 対照的に、任意の非適応アルゴリズムは$\Omega(d^3/\gamma^2)$コピーを必要とすることが知られている。 2ドルの次元では、O(1/\gamma)$のスケーリングを私たちの知る限りで達成できるが、我々のアルゴリズムはすべての次元で最適なレートを達成した最初のアルゴリズムである。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• An optimal tradeoff between entanglement and copy complexity for state tomography [24.737530909081915]
  本研究では,1回に$t$のコピーを計測できる自然環境下でのトモグラフィーについて検討する。 これは量子学習タスクで知られている最初のスムーズなエンタングルメント・コピープロトコルである。 重要な洞察は、シュリロンワイルサンプリングを用いて$rho$のスペクトルを推定するのではなく、最大混合状態から$rho$の偏差を推定することである。
  論文  参考訳（メタデータ） (2024-02-26T07:18:57Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Quantum chi-squared tomography and mutual information testing [1.8416014644193066]
  ランク-$r$次元-$d$状態の量子状態トモグラフィーでは、$widetildeO(r.5d1.5/epsilon) leq widetildeO(d3/epsilon)$ copy suffice for accuracy$epsilon$ to the (Bures) $chi2$-divergence を示す。 我々はまた、相互情報テストの古典版における最もよく知られたサンプルの複雑さを$widetildeO(d)に改善する。
  論文  参考訳（メタデータ） (2023-05-29T18:00:02Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
  量子状態に対するシャドウトモグラフィーは、量子システムの特性を予測するためのサンプル効率の良いアプローチを提供する。 我々は,この問題を高い確率で解決するオンラインシャドウトモグラフィー手法を開発した。
  論文  参考訳（メタデータ） (2022-09-07T09:08:58Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。 状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。 我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-18T17:56:18Z)
• Tight Bounds for Quantum State Certification with Incoherent Measurements [18.566266990940374]
  $sigma$ が最大混合状態 $frac1d I_d$ である場合、これは混合性テストとして知られている。 我々は、非コヒーレントな測定を使用するアルゴリズム、すなわち一度に$rho$のコピーを1つだけ測定するアルゴリズムに焦点を当てる。
  論文  参考訳（メタデータ） (2022-04-14T17:59:31Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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