論文の概要: Coherence in Property Testing: Quantum-Classical Collapses and Separations

• arxiv url: http://arxiv.org/abs/2411.15148v1
• Date: Wed, 06 Nov 2024 19:52:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-01 05:39:26.354522
• Title: Coherence in Property Testing: Quantum-Classical Collapses and Separations
• Title（参考訳）: プロパティテストにおけるコヒーレンス:量子古典的崩壊と分離
• Authors: Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote, Pei Wu,
• Abstract要約: テスタが2n/8$のサブセット状態と2-Theta(n)$の確率で2n/4$のサブセット状態とを区別できないことを示す。 また、アンタングルおよび量子-量子変換の下界への接続を示す。
• 参考スコア（独自算出の注目度）: 42.44394412033434
• License:
• Abstract: Understanding the power and limitations of classical and quantum information and how they differ is a fundamental endeavor. In property testing of distributions, a tester is given samples over a typically large domain $\{0,1\}^n$. An important property is the support size both of distributions [Valiant and Valiant, STOC'11], as well, as of quantum states. Classically, even given $2^{n/16}$ samples, no tester can distinguish distributions of support size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-\Theta(n)}$, even promised they are flat. Quantum states can be in a coherent superposition of states of $\{0,1\}^n$, so one may ask if coherence can enhance property testing. Flat distributions naturally correspond to subset states, $|\phi_S \rangle=1/\sqrt{|S|}\sum_{i\in S}|i\rangle$. We show that coherence alone is not enough, Coherence limitations: Given $2^{n/16}$ copies, no tester can distinguish subset states of size $2^{n/8}$ from $2^{n/4}$ with probability better than $2^{-\Theta(n)}$. The hardness persists even with multiple public-coin AM provers, Classical hardness with provers: Given $2^{O(n)}$ samples from a distribution and $2^{O(n)}$ communication with AM provers, no tester can estimate the support size up to factors $2^{\Omega(n)}$ with probability better than $2^{-\Theta(n)}$. Our result is tight. In contrast, coherent subset state proofs suffice to improve testability exponentially, Quantum advantage with certificates: With poly-many copies and subset state proofs, a tester can approximate the support size of a subset state of arbitrary size. Some structural assumption on the quantum proofs is required since we show, Collapse of QMA: A general proof cannot improve testability of any quantum property whatsoever. We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
• Abstract（参考訳）: 古典的および量子的情報のパワーと制限を理解し、それらがどのように異なるかを理解することは、基本的な試みである。 分布のプロパティテストでは、テスターは典型的には大きな領域 $\{0,1\}^n$ 上のサンプルを与えられる。 重要な性質は、分布(Valiant と Valiant, STOC'11] と量子状態の両方のサポートサイズである。 古典的には、2^{n/16}$サンプルが与えられたとしても、2^{n/8}$と2^{n/4}$を区別することはできない。 量子状態は$\{0,1\}^n$のコヒーレントな状態の重ね合わせにすることができるので、コヒーレンスがプロパティテストを強化することができるかどうかを問うことができる。 フラット分布は自然に部分集合状態、$|\phi_S \rangle=1/\sqrt{|S|}\sum_{i\in S}|i\rangle$に対応する。 コヒーレンスだけでは十分ではないことを示す: 2^{n/16}$コピーが与えられたとき、テスターはサイズが 2^{n/8}$ のサブセット状態と 2^{n/4}$ の確率が 2^{n-\Theta(n)}$ より良い確率で区別できない。 分布から 2^{O(n)$ のサンプルと 2^{O(n)$ のプロバーとの通信が与えられたとき、テスターはサポートサイズを 2^{Omega(n)$ の確率で 2^{O-\Theta(n)$ まで見積もることができない。 私たちの結果はきつい。 対照的に、コヒーレントなサブセット状態証明は、テスト容易性を指数関数的に改善するのに十分である。 証明の量子的優位性: ポリマコピーとサブセット状態証明を使用することで、テスターは任意のサイズのサブセット状態のサポートサイズを近似することができる。 量子証明に関するいくつかの構造的仮定は、私たちが示すように、QMAの崩壊: 一般的な証明は、いかなる量子特性の試験性も改善できない。 また、アンタングルおよび量子-量子変換の下界への接続を示す。

関連論文リスト

• Testing classical properties from quantum data [0.0]
  古典的テスタをサンプルに制限する場合のスピードアップは,量子データを使用するテスタによって回復可能であることを示す。 単調性テストでは、古典的に必要とされる2Omega(sqrtn)$サンプルと比較して、$tildemathcalO(n2)$関数状態コピーを使用する量子アルゴリズムを提供する。 Omega(n1/4)$ および $Omega(n)$ の古典的下限と比較し,対称性と三角形自由度に関する $mathcalO(1)$-copy テスタも提示する。
  論文  参考訳（メタデータ） (2024-11-19T18:52:55Z)
• Nearly tight bounds for testing tree tensor network states [0.0]
  ツリーテンソルネットワーク状態(TTNS)は、シュミットランクが低いから多部量子状態を持つという概念を一般化する。 我々は、未知の純状態が、結合次元が最大$r$の$n$クォーディット上のTTNSであるかどうかをテストするタスクを研究する。 また,少数のコピーに対して一度に実施した測定値を用いて,テストの性能についても検討した。
  論文  参考訳（メタデータ） (2024-10-28T18:13:38Z)
• Experimental lower bounds on entanglement entropy without twin copy [0.0]
  断熱的に調製した地盤状態の実験的測定と関連するシャノンエントロピー$S_ABX$を計算した。 良い近似では$S_AvNpropto (2S_AX-S_ABX)$が1よりわずかに大きい例を示す。
  論文  参考訳（メタデータ） (2024-04-15T17:02:17Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。 固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
  論文  参考訳（メタデータ） (2023-12-23T15:52:46Z)
• Testing matrix product states [5.225550006603552]
  未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。 MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
  論文  参考訳（メタデータ） (2022-01-05T21:10:50Z)
• Distributed quantum inner product estimation [14.222887950206658]
  2つの量子コンピュータ上で準備された状態の忠実度を推定することを目的とした、クロスプラットフォーム検証として知られるベンチマークタスクが提案されている。 ハードウェアの制約により、2つの物理プラットフォーム間で量子通信を行うことはできない。 サンプルの複雑さは、最強の設定でも少なくとも$Omega(max1/varepsilon2,sqrtd/varepsilon)$でなければならない。
  論文  参考訳（メタデータ） (2021-11-05T05:35:03Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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