論文の概要: 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)$コピーが必要であることを示すことにより,この問題を完全に解決する。
我々は、測定後の後方分布の「チルト」を直接束縛する新しい証明手法によって、この手法は、我々の下限の驚くほど短い証明となり、それが独立した関心事であると信じている。
関連論文リスト
- 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 [58.372148767703955]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳(メタデータ) (2024-02-14T13:44:16Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
量子状態に対するシャドウトモグラフィーは、量子システムの特性を予測するためのサンプル効率の良いアプローチを提供する。
我々は,この問題を高い確率で解決するオンラインシャドウトモグラフィー手法を開発した。
論文 参考訳(メタデータ) (2022-09-07T09:08:58Z) - Lower bounds for learning quantum states with single-copy measurements [3.2590610391507444]
量子トモグラフィーとシャドウトモグラフィーの問題点を,未知の$d$次元状態の個々のコピーを用いて測定した。
特に、この手法は、その複雑さの観点から、フォークロアのパウリ・トモグラフィー(Pauli tomography)アルゴリズムの最適性を厳格に確立する。
論文 参考訳(メタデータ) (2022-07-29T02:26:08Z) - 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 [77.57736777744934]
この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。
私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。