論文の概要: Quantum Lower Bounds by Sample-to-Query Lifting
- arxiv url: http://arxiv.org/abs/2308.01794v2
- Date: Wed, 26 Jun 2024 13:11:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 19:53:52.991282
- Title: Quantum Lower Bounds by Sample-to-Query Lifting
- Title（参考訳）: サンプル・ツー・クエリ・リフティングによる量子下界の研究
- Authors: Qisheng Wang, Zhicheng Zhang,
- Abstract要約: 本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
- 参考スコア（独自算出の注目度）: 7.319050391449301
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998) and the adversary method by Ambainis (STOC 2000) have been shown to be powerful in proving quantum query lower bounds for a wide variety of problems. In this paper, we propose an arguably new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem, which is from an information theory perspective. Using this method, we obtain the following new results: 1. A quadratic relation between quantum sample and query complexities regarding quantum property testing, which is optimal and saturated by quantum state discrimination. 2. A matching lower bound $\widetilde \Omega(\beta)$ for quantum Gibbs sampling at inverse temperature $\beta$, showing that the quantum Gibbs sampler by Gily\'en, Su, Low, and Wiebe (STOC 2019) is optimal. 3. A new lower bound $\widetilde \Omega(1/\sqrt{\Delta})$ for the entanglement entropy problem with gap $\Delta$, which was recently studied by She and Yuen (ITCS 2023). 4. A series of quantum query lower bounds for matrix spectrum testing, based on the sample lower bounds for quantum state spectrum testing by O'Donnell and Wright (STOC 2015). In addition, we also provide unified proofs for some known lower bounds that have been proven previously via different techniques, including those for phase/amplitude estimation and Hamiltonian simulation.
- Abstract（参考訳）: Beals, Buhrman, Cleve, Mosca, de Wolf (FOCS 1998) の多項式法と Ambainis (STOC 2000) の逆法は、様々な問題に対する量子クエリの下界の証明に強力であることが示されている。
本稿では,情報理論の観点から,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。
1) 量子状態の判別により最適かつ飽和な量子特性試験に関する,量子サンプルとクエリ複雑性の2次関係を求める。
2. 逆温度$\beta$における量子ギブズサンプリングの値に一致する$\widetilde \Omega(\beta)$は、Gily\'en, Su, Low, Wiebe (STOC 2019) による量子ギブズサンプリングが最適であることを示す。
3. 新しい下界$\widetilde \Omega(1/\sqrt{\Delta})$は、最近She and Yuen (ITCS 2023) によって研究されたギャップ$\Delta$で絡み合うエントロピー問題に対するものである。
4. O'Donnell and Wright (STOC 2015) による量子状態スペクトル検定のためのサンプル下界に基づく,行列スペクトル検定のための一連の量子クエリ下界。
さらに、位相/振幅推定やハミルトニアンシミュレーションなど、これまで異なる手法で証明されてきたいくつかの既知の下界に対する統一的な証明も提供する。
関連論文リスト
- The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels [53.253900735220796]
不等式はボゾン量子モードの最も一般的な線形混合の出力の最小条件フォン・ノイマンエントロピーを決定する。
ボソニック量子系は、量子状態における電磁放射の数学的モデルを構成する。
論文 参考訳（メタデータ） (2024-10-18T13:59:50Z) - Hidden-State Proofs of Quantumness [1.0878040851638]
量子性の実験的暗号的証明は、量子情報科学の進歩における重要なマイルストーンとなる。
このようなテストを実装する上で、エラー寛容は永続的な課題である。
本稿では、(Brakerski et al)と同じ回路構造を維持する量子性の証明を示す。
論文 参考訳（メタデータ） (2024-10-08T21:04:53Z) - Spontaneous symmetry breaking in a $SO(3)$ non-Abelian lattice gauge theory in $2+1$D with quantum algorithms [0.0]
量子アルゴリズムによる非アベリア系非アベリア系SO(3)$格子ゲージ理論における基底状態の生成能力について, 2+1$Dで検討する。
ゲージ場のヒルベルト空間を扱うために、量子リンク作用素のリドン表現における非アベリアガウス法則の正確な仮定が、自由度を著しく減少させることを示す。
論文 参考訳（メタデータ） (2024-09-11T08:55:59Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。
すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。
我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
論文 参考訳（メタデータ） (2024-01-15T19:00:36Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Heavy-tailed Bandits [36.458771174473924]
重み付き報酬と量子報酬を用いたマルチアーム・バンディット(MAB)とリニア・バンディット(SLB)について検討した。
まず,量子モンテカルロ推定器に基づく重み付き分布に対する新しい量子平均推定器を提案する。
量子平均推定器に基づき、量子重み付きMABとSLBに着目し、上信頼境界(UCB)フレームワークに基づく量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-23T19:23:10Z) - Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。
次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。
量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
論文 参考訳（メタデータ） (2023-01-05T18:55:04Z) - Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs.
Coded Systems [69.33243249411113]
パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。
我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
論文 参考訳（メタデータ） (2020-12-15T15:51:27Z) - Quantum Statistical Complexity Measure as a Signalling of Correlation
Transitions [55.41644538483948]
本稿では, 量子情報理論の文脈において, 統計的複雑性尺度の量子バージョンを導入し, 量子次数-次数遷移のシグナル伝達関数として利用する。
我々はこの測度を2つの正確に解けるハミルトンモデル、すなわち1D$量子イジングモデルとハイゼンベルクXXZスピン-1/2$チェーンに適用する。
また、考察されたモデルに対して、この測度を1量子および2量子の還元状態に対して計算し、その挙動を有限系のサイズと熱力学的限界に対して解析する。
論文 参考訳（メタデータ） (2020-02-05T00:45:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。