論文の概要: The Acrobatics of BQP
- arxiv url: http://arxiv.org/abs/2111.10409v4
- Date: Wed, 24 Apr 2024 20:05:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-27 00:45:56.921619
- Title: The Acrobatics of BQP
- Title(参考訳): BQPのアクロバティックス
- Authors: Scott Aaronson, DeVon Ingram, William Kretschmer,
- Abstract要約: 量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
- 参考スコア(独自算出の注目度): 1.7136832159667206
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically: -There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$. -Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$. -Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$. -Relative to a random oracle, $\mathsf{\Sigma}_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^\mathsf{P}}$ for every $k$. -There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite. -There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{PH}$, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
- Abstract(参考訳): ランダム化アルゴリズムが使用するランダム性を修正することができるが、量子性アルゴリズムが使用する量子性を修正するという類似概念は存在しない。
この基本的な違いを説明すれば、ブラックボックスの設定では、量子多項式時間($\mathsf{BQP}$)の振舞いは、$\mathsf{NP}$のような古典的な複雑性クラスと著しく分離できることが示される。
具体的には、–あるオラクルが存在し、$\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$は、フォーチュウの2005年の問題を解く。
圏として、$\mathsf{P}=\mathsf{NP}$であるが、$\mathsf{BQP}\neq\mathsf{QCMA}$であるようなオラクルが存在する。
逆に、$\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$であるようなオラクルが存在する。
-ランダムオラクルに対して、$\mathsf{PP}=\mathsf{PostBQP}$は "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$には含まれない。
-ランダムオラクルに対して、$\mathsf{\Sigma}_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^\mathsf{P}}$ for every $k$。
オラクルは、$\mathsf{BQP}=\mathsf{P^{\# P}}$ に対して、$\mathsf{PH}$ は無限である。
-その関係は、$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$である。
これらの結果を達成するために、Raz と Tal による2018 年のオラクルの業績を $\mathsf{BQP}\not \subset \mathsf{PH}$ と比較し、Forrelation 問題に関する関連する結果に基づける。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子認識」バージョン、$\mathsf{AC^0}$回路のブロック感度に対する濃度定理、スパースオラクルに対するアーロンソン・アンバイニス射影の(証明可能な)アナログを含む。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳(メタデータ) (2024-02-06T15:39:09Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳(メタデータ) (2024-01-03T09:12:25Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳(メタデータ) (2024-01-02T22:25:56Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳(メタデータ) (2023-11-22T20:27:05Z) - Quantum Cryptography in Algorithmica [0.7524721345903025]
ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
論文 参考訳(メタデータ) (2022-12-01T21:33:38Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳(メタデータ) (2022-06-23T16:23:59Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳(メタデータ) (2022-03-17T23:52:08Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - StoqMA meets distribution testing [0.0]
We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。
いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。
我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
論文 参考訳(メタデータ) (2020-11-11T12:30:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。