論文の概要: 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 18:44:18.408991
- 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Hidden-State Proofs of Quantumness [1.0878040851638]
量子性の実験的暗号的証明は、量子情報科学の進歩における重要なマイルストーンとなる。
このようなテストを実装する上で、エラー寛容は永続的な課題である。
本稿では、(Brakerski et al)と同じ回路構造を維持する量子性の証明を示す。
論文 参考訳（メタデータ） (2024-10-08T21:04:53Z) - Quantum property testing in sparse directed graphs [0.9624643581968987]
古典的な一方向モデルでは、$k$-star-freeness、より一般に$k$-source-subgraph-freenessをテストするという問題は、大きめの$k$にとってほとんど極端に難しい。
量子的にも線形なクエリ数が必要であることも示しています。
論文 参考訳（メタデータ） (2024-10-07T13:00:43Z) - 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) - Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
論文 参考訳（メタデータ） (2023-08-03T14:41:49Z) - 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) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。
偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-11-07T12:00:45Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Information-theoretic bounds on quantum advantage in machine learning [6.488575826304023]
物理実験結果の予測における古典的および量子機械学習(ML)モデルの性能について検討する。
任意の入力分布 $mathcalD(x)$ に対して、古典的な ML モデルは、最適量子 ML モデルに匹敵する回数 $mathcalE$ にアクセスすることで、平均で正確な予測を提供することができる。
論文 参考訳（メタデータ） (2021-01-07T10:10:09Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。