論文の概要: Testing classical properties from quantum data
- arxiv url: http://arxiv.org/abs/2411.12730v2
- Date: Tue, 18 Mar 2025 05:07:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-19 14:12:45.225922
- Title: Testing classical properties from quantum data
- Title（参考訳）: 量子データから古典的性質をテストする
- Authors: Matthias C. Caro, Preksha Naik, Joseph Slote,
- Abstract要約: 関数状態 $|frangle propto sum_x|x,f(x)rangle$ のコピーの形で、量子データからのみ$f$の特性をテストする量子アルゴリズムを導入する。
モノトニック性、対称性、三角形自由性の3つの確立された特性について、古典的テスタをサンプルデータに制限した場合のスピードアップは、量子データからのみ動作する量子アルゴリズムによって回復可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Properties of Boolean functions can often be tested much faster than the functions can be learned. However, this advantage usually disappears when testers are limited to random samples of a function $f$--a natural setting for data science--rather than queries. In this work we initiate the study of a quantum version of this "data science scenario": quantum algorithms that test properties of $f$ solely from quantum data in the form of copies of the function state $|f\rangle \propto \sum_x|x,f(x)\rangle$. $\bullet$ New tests. For three well-established properties--monotonicity, symmetry, and triangle-freeness--we show that the speedup lost when restricting classical testers to sampled data can be recovered by quantum algorithms operating solely from quantum data. $\bullet$ Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and we show that this necessary. In particular, there is no constant-complexity tester for symmetry relying solely on Fourier sampling and random classical samples. $\bullet$ Classical queries vs. quantum data. We exhibit a testing problem that can be solved from $O(1)$ classical queries but that requires $\Omega(2^{n/2})$ function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. $\bullet$ Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of Goldreich et al. (2000) and Black (2023), which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
- Abstract（参考訳）: ブール関数の性質は、学習できる関数よりもはるかに早くテストすることができる。
しかし、この利点は通常、テスタがクエリではなく、データサイエンスの自然な設定である関数のランダムなサンプルに制限されているときに消える。
この研究において、この「データサイエンスシナリオ」の量子バージョンの研究を開始する: 関数状態 $|f\rangle \propto \sum_x|x,f(x)\rangle$ のコピーの形で量子データのみから$f$のプロパティをテストする量子アルゴリズム。
$\bullet$ 新しいテスト。
モノトニック性、対称性、三角形自由性の3つの確立された特性について、古典的テスタをサンプルデータに制限した場合のスピードアップは、量子データからのみ動作する量子アルゴリズムによって回復可能であることを示す。
$\bullet$不適切なフーリエサンプリング。
新しいテスタは量子フーリエサンプリング以外のテクニックを使用します。
特に、フーリエサンプリングとランダム古典標本のみに依存する対称性に対する定数複素性テスターは存在しない。
$\bullet$ Classical query vs. Quantum data。
我々は、$O(1)$の古典的クエリから解けるテスト問題を示すが、$Omega(2^{n/2})$の関数状態コピーが必要である。
Forrelation問題は、逆方向の同じ大きさの分離を与えるので、量子データと古典的クエリは、テストのための"最大で互換性のない"リソースである、と結論付ける。
$\bullet$ 下位境界に向けて。
また、量子データからテストする際の下位境界の研究も開始する。
量子単調性試験では、古典的なサンプルベーステストにおいて指数的に低い境界を与えるGoldreich et al (2000) と Black (2023) のアンサンブルが、量子データからテストするための非自明な下限を生じさせないことを証明している。
このモデルでは、コピー複雑性の低い境界を証明するために、量子データに特有の新しい洞察が必要である。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
論文 参考訳（メタデータ） (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) - Testing matrix product states [5.225550006603552]
未知の状態$|psirangle$が特性試験モデルにおける行列積状態(MPS)かどうかをテストする。
MPS(英: MPS)は、量子多体系の研究で生じる物理関連量子状態のクラスである。
論文 参考訳（メタデータ） (2022-01-05T21:10:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。