論文の概要: 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 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(textpoly(n) / mathsfqpoly$である。
我々は、$mathsfQMA(textpoly(n) / Mathsfqpoly notsupset に対して量子オラクルが存在することを示す。
論文 参考訳(メタデータ) (2024-01-15T19:00:36Z) - Quantum soft-covering lemma with applications to rate-distortion coding,
resolvability and identification via quantum channels [7.646713951724011]
量子シャノン理論からの切り離し技術を活用することで、スムーズなミンエントロピーの観点からワンショット量子被覆補題を証明した。
量子被覆補題のパワーは、追加の2つの応用によって実証される。
論文 参考訳(メタデータ) (2023-06-21T17:53:22Z) - 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) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。
このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
論文 参考訳(メタデータ) (2022-03-15T09:46:45Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Speeding up Learning Quantum States through Group Equivariant
Convolutional Quantum Ans\"atze [13.651587339535961]
我々はSU$(d)$対称性を持つ畳み込み量子回路の枠組みを開発する。
我々は、$nameSU(d)$と$S_n$ irrepbasesの同値性に関するHarrowの主張を証明する。
論文 参考訳(メタデータ) (2021-12-14T18:03:43Z) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。
我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
論文 参考訳(メタデータ) (2021-11-01T16:35:41Z) - Heisenberg-Limited Waveform Estimation with Solid-State Spins in Diamond [15.419555338671772]
任意の波形推定におけるハイゼンベルク極限はパラメータ推定とは全く異なる。
この量子限界を達成するために、多くのエキゾチックな量子絡み合った状態を生成することは、いまだに自明な挑戦である。
この研究は、連続した空間と時間における量子化構造認識を実現するための重要なステップを提供する。
論文 参考訳(メタデータ) (2021-05-13T01:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。