論文の概要: Tight Bounds for Quantum State Certification with Incoherent
Measurements
- arxiv url: http://arxiv.org/abs/2204.07155v1
- Date: Thu, 14 Apr 2022 17:59:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-15 14:49:18.783062
- Title: Tight Bounds for Quantum State Certification with Incoherent
Measurements
- Title（参考訳）: 非コヒーレント測定による量子状態認証の厳密な境界
- Authors: Sitan Chen, Brice Huang, Jerry Li, Allen Liu
- Abstract要約: $sigma$ が最大混合状態 $frac1d I_d$ である場合、これは混合性テストとして知られている。
我々は、非コヒーレントな測定を使用するアルゴリズム、すなわち一度に$rho$のコピーを1つだけ測定するアルゴリズムに焦点を当てる。
- 参考スコア（独自算出の注目度）: 18.566266990940374
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of quantum state certification, where we are given
the description of a mixed state $\sigma \in \mathbb{C}^{d \times d}$, $n$
copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\varepsilon >
0$, and we are asked to determine whether $\rho = \sigma$ or whether $\| \rho -
\sigma \|_1 > \varepsilon$. When $\sigma$ is the maximally mixed state
$\frac{1}{d} I_d$, this is known as mixedness testing. We focus on algorithms
which use incoherent measurements, i.e. which only measure one copy of $\rho$
at a time. Unlike those that use entangled, multi-copy measurements, these can
be implemented without persistent quantum memory and thus represent a large
class of protocols that can be run on current or near-term devices.
For mixedness testing, there is a folklore algorithm which uses incoherent
measurements and only needs $O(d^{3/2} / \varepsilon^2)$ copies. The algorithm
is non-adaptive, that is, its measurements are fixed ahead of time, and is
known to be optimal for non-adaptive algorithms. However, when the algorithm
can make arbitrary incoherent measurements, the best known lower bound is only
$\Omega (d^{4/3} / \varepsilon^2)$ [Bubeck-Chen-Li '20], and it has been an
outstanding open problem to close this polynomial gap. In this work, 1) we
settle the copy complexity of mixedness testing with incoherent measurements
and show that $\Omega (d^{3/2} / \varepsilon^2)$ copies are necessary, and 2)
we show the instance-optimal bounds for state certification to general $\sigma$
first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also
hold for arbitrary incoherent measurements.
Qualitatively, our results say that adaptivity does not help at all for these
problems. Our results are based on new techniques that allow us to reduce the
problem to understanding certain matrix martingales, which we believe may be of
independent interest.
- Abstract（参考訳）: 我々は、混合状態 $\rho \in \mathbb{C}^{d \times d}$, $n$ copy of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\varepsilon > 0$ の問題を考察し、$\rho = \sigma$ と $\| \rho\sigma \|_1 > \varepsilon$ を判定する。
もし$\sigma$ が最大混合状態であるとき、$\frac{1}{d} i_d$ は混合性テストとして知られる。
非コヒーレントな測定を使用するアルゴリズム、すなわち、一度に$\rho$のコピーを1つだけ測定するアルゴリズムに焦点を当てる。
絡み合ったマルチコピー計測を使用するものとは異なり、これらは永続的な量子メモリなしで実装することができ、そのため現在または近い将来のデバイスで実行できる多数のプロトコルクラスを表現することができる。
混合性テストには、非コヒーレントな測定を使い、$O(d^{3/2} / \varepsilon^2)$コピーしか必要としないフォークロアアルゴリズムがある。
アルゴリズムは非適応であり、すなわち、その測定は時間前に固定され、非適応アルゴリズムに最適であることが知られている。
しかし、アルゴリズムが任意の非コヒーレントな測定を行うことができるとき、最もよく知られた下界は$\Omega (d^{4/3} / \varepsilon^2)$ [Bubeck-Chen-Li '20] でしかなく、この多項式ギャップを閉じることは未解決の問題である。
この作品では
1) 不整合測定による混合性試験のコピー複雑性を解決し,$\Omega (d^{3/2} / \varepsilon^2)$コピーが必要であることを示す。
2) 非適応測定における [Chen-Li-O'Donnell '21] が導出した一般$\sigma$に対する状態認証のインスタンス最適境界も任意の不整合測定に有効であることを示す。
質的に見れば、適応性はこれらの問題には全く役に立たない。
私たちの結果は、問題から特定の行列マーチンゲールを理解することを可能にする新しいテクニックに基づいています。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - The role of shared randomness in quantum state certification with
unentangled measurements [36.19846254657676]
非絡み合った量子測定を用いて量子状態認証を研究する。
$Theta(d2/varepsilon2)$コピーが必要である。
我々は固定化とランダム化の両方のための統一された下界フレームワークを開発する。
論文 参考訳（メタデータ） (2024-01-17T23:44:52Z) - 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) - Quantum Event Learning and Gentle Random Measurements [0.0]
我々は、ランダムに順序付けられた射影測定の列によって量子系に生じる期待された乱が、少なくとも1つの測定が受け入れる確率の平方根によって上界されていることを証明した。
また、未知の状態の$rho$へのサンプルアクセスが与えられ、受理確率の特性を推定する問題についても検討する。
論文 参考訳（メタデータ） (2022-10-17T15:00:58Z) - When Does Adaptivity Help for Quantum State Learning? [19.89243001385691]
非コヒーレントな測定を使用するプロトコルには$Omega(d3/epsilon2)$コピーが必要である。
不整合の測定に最適である$tildeO(d3/gamma)$コピーのみを用いて、不整合で$gamma$-closeの状態を$rho$に出力する適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-10T17:59:16Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Toward Instance-Optimal State Certification With Incoherent Measurements [17.107198714549515]
未知の混合状態 $rhoinmathbbCdtimes d$ が与えられたとき、$sigma = rho$ か $|sigma - rho|_mathsftr ge epsilon$ を判定する。
非適応的不整合測定による状態認証のコピー複雑性は、基本的に、$sigma$と最大混合状態の間の忠実度を混合性試験のコピー複雑性によって与えられる。
論文 参考訳（メタデータ） (2021-02-25T18:59:11Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
独立測定では,$Omega(d4/3/epsilon2)$を適応的に選択しても,$Omega(d4/3/epsilon2)$が必須であることを示す。
古典的一様性テストのためのパニンスキーの下界のチェーンルル型証明を含む,いくつかの新しい手法を開発した。
論文 参考訳（メタデータ） (2020-04-16T18:28:39Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。