論文の概要: Tight Bounds for State Tomography with Incoherent Measurements
- arxiv url: http://arxiv.org/abs/2206.05265v1
- Date: Fri, 10 Jun 2022 17:59:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-13 16:01:35.057861
- Title: Tight Bounds for State Tomography with Incoherent Measurements
- Title（参考訳）: 非コヒーレント測定による状態トモグラフィのタイト境界
- Authors: Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke
- Abstract要約: 非コヒーレントな測定を使用するプロトコルは、[Kueng-Rauhut-Terstiege '17]の上界と一致する$Omega(d3/varepsilon2)$コピーを必要とする。
- 参考スコア（独自算出の注目度）: 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}$
for which $\|\rho - \widehat{\rho}\|_{\mathsf{tr}} \le \varepsilon$. When one
is allowed to make coherent measurements entangled across all copies,
$\Theta(d^2/\varepsilon^2)$ copies are necessary and sufficient [Haah et al.
'17, O'Donnell-Wright '16]. Unfortunately, the protocols achieving this rate
incur large quantum memory overheads that preclude implementation on current or
near-term devices. On the other hand, the best known protocol using incoherent
(single-copy) measurements uses $O(d^3/\varepsilon^2)$ copies
[Kueng-Rauhut-Terstiege '17], 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/\varepsilon^2)$ copies, matching the upper bound of
[Kueng-Rauhut-Terstiege '17].
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.
- Abstract（参考訳）: 未知の量子状態のコピー $\rho\in\mathbb{c}^{d\times d}$ が与えられると、$\|\rho - \widehat{\rho}\|_{\mathsf{tr}} \le \varepsilon$ となるような出力$\widehat{\rho}$ が得られる。
すべてのコピーにコヒーレントな測定を絡ませることが許されると、$\Theta(d^2/\varepsilon^2)$コピーは必要で十分である [Haah et al. '17, O'Donnell-Wright '16]。
残念ながら、この速度を達成するプロトコルは、現在のデバイスや短期デバイスの実装を妨げる大きな量子メモリオーバーヘッドを引き起こす。
一方, incoherent (single-copy) 測定を用いた最もよく知られたプロトコルは,$o(d^3/\varepsilon^2)$ copy [kueng-rauhut-terstiege '17] を用いている。
そこで本研究では,不整合測定を用いたプロトコルが適応的に選択されたとしても,[Kueng-Rauhut-Terstiege '17] の上界に一致する$\Omega(d^3/\varepsilon^2)$コピーが必要であることを示すことにより,この問題を完全に解決する。
我々は、測定後の後方分布の「チルト」を直接束縛する新しい証明手法によって、この手法は、我々の下限の驚くほど短い証明となり、それが独立した関心事であると信じている。
関連論文リスト
- 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。