論文の概要: Testing classical properties from quantum data
- arxiv url: http://arxiv.org/abs/2411.12730v1
- Date: Tue, 19 Nov 2024 18:52:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-20 13:37:14.948728
- Title: Testing classical properties from quantum data
- Title（参考訳）: 量子データから古典的性質をテストする
- Authors: Matthias C. Caro, Preksha Naik, Joseph Slote,
- Abstract要約: 古典的テスタをサンプルに制限する場合のスピードアップは,量子データを使用するテスタによって回復可能であることを示す。
単調性テストでは、古典的に必要とされる2Omega(sqrtn)$サンプルと比較して、$tildemathcalO(n2)$関数状態コピーを使用する量子アルゴリズムを提供する。
Omega(n1/4)$ および $Omega(n)$ の古典的下限と比較し,対称性と三角形自由度に関する $mathcalO(1)$-copy テスタも提示する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Many properties of Boolean functions can be tested far more efficiently than the function can be learned. However, this advantage often disappears when testers are limited to random samples--a natural setting for data science--rather than queries. In this work we investigate the quantum version of this scenario: quantum algorithms that test properties of a function $f$ solely from quantum data in the form of copies of the function state for $f$. For three well-established properties, we show that the speedup lost when restricting classical testers to samples can be recovered by testers that use quantum data. For monotonicity testing, we give a quantum algorithm that uses $\tilde{\mathcal{O}}(n^2)$ function state copies as compared to the $2^{\Omega(\sqrt{n})}$ samples required classically. We also present $\mathcal{O}(1)$-copy testers for symmetry and triangle-freeness, comparing favorably to classical lower bounds of $\Omega(n^{1/4})$ and $\Omega(n)$ samples respectively. These algorithms are time-efficient and necessarily include techniques beyond the Fourier sampling approaches applied to earlier testing problems. These results make the case for a general study of the advantages afforded by quantum data for testing. We contribute to this project by complementing our upper bounds with a lower bound of $\Omega(1/\varepsilon)$ for monotonicity testing from quantum data in the proximity regime $\varepsilon\leq\mathcal{O}(n^{-3/2})$. This implies a strict separation between testing monotonicity from quantum data and from quantum queries--where $\tilde{\mathcal{O}}(n)$ queries suffice when $\varepsilon=\Theta(n^{-3/2})$. We also exhibit a testing problem that can be solved from $\mathcal{O}(1)$ classical queries but requires $\Omega(2^{n/2})$ function state copies, complementing a separation of the same magnitude in the opposite direction derived from the Forrelation problem.
- Abstract（参考訳）: ブール関数の多くの性質は、関数が学習できるよりもはるかに効率的にテストすることができる。
しかし、この利点は、テスタがランダムなサンプル(データサイエンスの自然な設定)に制限されている場合、クエリではなく、しばしば消える。
本研究では、このシナリオの量子バージョンについて検討する:関数の性質を量子データからのみテストする量子アルゴリズムで、関数状態のコピーを$f$でコピーする。
確立された3つの特性について、古典的テスタをサンプルに制限した場合のスピードアップが、量子データを使用するテスタによって回復可能であることを示す。
単調性試験では、$\tilde{\mathcal{O}}(n^2)$関数状態コピーを使用する量子アルゴリズムを、古典的に必要とされる2,^{\Omega(\sqrt{n})}$サンプルと比較する。
また、対称性と三角形自由度に関する $\mathcal{O}(1)$-copy テスタを、それぞれ $\Omega(n^{1/4})$ と $\Omega(n)$ の古典的下界と比較する。
これらのアルゴリズムは時間効率が高く、必ずしも初期のテスト問題に適用されたフーリエサンプリングアプローチを超えるテクニックを含んでいる。
これらの結果は、テストのための量子データによって得られる利点の一般的な研究である。
我々は、近接状態の量子データから単調性をテストするために、上界を$\Omega(1/\varepsilon)$で補うことでこのプロジェクトに貢献する。
これは、量子データからの単調性のテストと量子クエリとの厳密な分離を意味し、$\varepsilon=\Theta(n^{-3/2})$のとき、$\tilde{\mathcal{O}}(n)$クエリは十分である。
また、$\mathcal{O}(1)$古典的なクエリから解けるが、$\Omega(2^{n/2})$関数状態のコピーが必要であり、Forrelation問題から導かれる反対方向の同じ大きさの分離を補完する。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。
我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $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) - 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) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
独立測定では,$Omega(d4/3/epsilon2)$を適応的に選択しても,$Omega(d4/3/epsilon2)$が必須であることを示す。
古典的一様性テストのためのパニンスキーの下界のチェーンルル型証明を含む,いくつかの新しい手法を開発した。
論文 参考訳（メタデータ） (2020-04-16T18:28:39Z) - 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) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。