論文の概要: Entanglement is Necessary for Optimal Quantum Property Testing
- arxiv url: http://arxiv.org/abs/2004.07869v1
- Date: Thu, 16 Apr 2020 18:28:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 06:28:41.258763
- Title: Entanglement is Necessary for Optimal Quantum Property Testing
- Title（参考訳）: 量子特性試験におけるエンタングルメントの必要性
- Authors: Sebastien Bubeck, Sitan Chen, Jerry Li
- Abstract要約: 独立測定では,$Omega(d4/3/epsilon2)$を適応的に選択しても,$Omega(d4/3/epsilon2)$が必須であることを示す。
古典的一様性テストのためのパニンスキーの下界のチェーンルル型証明を含む,いくつかの新しい手法を開発した。
- 参考スコア（独自算出の注目度）: 15.58122727889318
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There has been a surge of progress in recent years in developing algorithms
for testing and learning quantum states that achieve optimal copy complexity.
Unfortunately, they require the use of entangled measurements across many
copies of the underlying state and thus remain outside the realm of what is
currently experimentally feasible. A natural question is whether one can match
the copy complexity of such algorithms using only independent---but possibly
adaptively chosen---measurements on individual copies.
We answer this in the negative for arguably the most basic quantum testing
problem: deciding whether a given $d$-dimensional quantum state is equal to or
$\epsilon$-far in trace distance from the maximally mixed state. While it is
known how to achieve optimal $O(d/\epsilon^2)$ copy complexity using entangled
measurements, we show that with independent measurements,
$\Omega(d^{4/3}/\epsilon^2)$ is necessary, even if the measurements are chosen
adaptively. This resolves a question of Wright. To obtain this lower bound, we
develop several new techniques, including a chain-rule style proof of
Paninski's lower bound for classical uniformity testing, which may be of
independent interest.
- Abstract（参考訳）: 近年、最適なコピー複雑性を達成する量子状態のテストと学習のためのアルゴリズムの開発が進んでいる。
残念なことに、それらは基底状態の多くのコピーに絡み合った測定を使わなければならないため、現在実験可能な領域の外にとどまる。
自然な疑問は、独立した-しかし、おそらく適応的に選択された-- 個々のコピーを計測することで、そのようなアルゴリズムのコピー複雑性にマッチできるかどうかである。
与えられた$d$次元の量子状態が最大混合状態からトレース距離において$\epsilon$-farと等しいかどうかを決定する。
エンタングル測定を用いて最適な$O(d/\epsilon^2)$コピー複雑性を実現する方法が知られているが、独立測定では、$\Omega(d^{4/3}/\epsilon^2)$が適応的に選択されても必要であることを示す。
これはライトの問題を解く。
この下限を得るために、パニンスキーの古典的一様性テストに対する下限のチェーンルル型証明を含むいくつかの新しい手法を開発した。
関連論文リスト
- Time-Efficient Quantum Entropy Estimator via Samplizer [8.646488471216262]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。
我々は、フォン・ノイマンエントロピー$S(rho)$とR'enyi entropy$S_alpha(rho)$を推定するための時間効率のよい量子アプローチを導入する。
論文 参考訳（メタデータ） (2024-01-18T12:50:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - 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) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Lower bounds for learning quantum states with single-copy measurements [3.2590610391507444]
量子トモグラフィーとシャドウトモグラフィーの問題点を,未知の$d$次元状態の個々のコピーを用いて測定した。
特に、この手法は、その複雑さの観点から、フォークロアのパウリ・トモグラフィー(Pauli tomography)アルゴリズムの最適性を厳格に確立する。
論文 参考訳（メタデータ） (2022-07-29T02:26:08Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Tight Bounds for Quantum State Certification with Incoherent
Measurements [18.566266990940374]
$sigma$ が最大混合状態 $frac1d I_d$ である場合、これは混合性テストとして知られている。
我々は、非コヒーレントな測定を使用するアルゴリズム、すなわち一度に$rho$のコピーを1つだけ測定するアルゴリズムに焦点を当てる。
論文 参考訳（メタデータ） (2022-04-14T17:59:31Z) - Distributed quantum inner product estimation [14.222887950206658]
2つの量子コンピュータ上で準備された状態の忠実度を推定することを目的とした、クロスプラットフォーム検証として知られるベンチマークタスクが提案されている。
ハードウェアの制約により、2つの物理プラットフォーム間で量子通信を行うことはできない。
サンプルの複雑さは、最強の設定でも少なくとも$Omega(max1/varepsilon2,sqrtd/varepsilon)$でなければならない。
論文 参考訳（メタデータ） (2021-11-05T05:35:03Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。