論文の概要: Quantum Lower Bounds by Sample-to-Query Lifting
- arxiv url: http://arxiv.org/abs/2308.01794v1
- Date: Thu, 3 Aug 2023 14:41:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-04 13:48:50.067328
- Title: Quantum Lower Bounds by Sample-to-Query Lifting
- Title（参考訳）: サンプルからクエリへの浮揚による量子下限
- Authors: Qisheng Wang and Zhicheng Zhang
- Abstract要約: 本稿では,情報理論の観点から,量子クエリアルゴリズムの下位境界を証明するための新しい手法を提案する。
また、以前に異なる手法で証明されたいくつかの既知の下界に対する統一的な証明も提供する。
- 参考スコア（独自算出の注目度）: 4.523089386111081
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a quantum sample-to-query lifting theorem. It reveals a quadratic
relation between quantum sample and query complexities regarding quantum
property testing, which is optimal and saturated by quantum state
discrimination. Based on it, we provide a new method for proving lower bounds
on quantum query algorithms from an information theory perspective. Using this
method, we prove the following new results:
1. 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 (2019) is optimal.
2. 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 (2023).
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（参考訳）: 量子サンプル対クエリリフト定理を提案する。
これは、量子状態の識別によって最適かつ飽和される量子特性試験に関する量子サンプルとクエリの複雑度の間の二次関係を明らかにする。
そこで我々は,情報理論の観点から,量子クエリアルゴリズムの下位境界を証明するための新しい手法を提案する。
1) 逆温度での量子ギブズサンプリングに対して, 等価な下限値である$\widetilde \omega(\beta)$ は$\beta$ であり, gily\'en, su, low, wiebe (2019) による量子ギブズサンプリングが最適であることを示す。
2. 新しい下界$\widetilde \Omega(1/\sqrt{\Delta})$は、最近She and Yuen (2023) によって研究されたギャップ$\Delta$の絡み合いエントロピー問題に対するものである。
さらに,位相・振幅推定やハミルトニアンシミュレーションなど,これまで異なる手法で証明されてきた既知の下限の統一的な証明も提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。