論文の概要: The Acrobatics of BQP
- arxiv url: http://arxiv.org/abs/2111.10409v3
- Date: Fri, 7 Oct 2022 18:33:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 09:52:49.169779
- Title: The Acrobatics of BQP
- Title（参考訳）: BQPのアクロバティックス
- Authors: Scott Aaronson, DeVon Ingram, William Kretschmer
- Abstract要約: 量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
- 参考スコア（独自算出の注目度）: 3.9747898273716697
- 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}}}$には含まれない。
-ランダムなオラクルと比較すると、$k$ ごとに$\mathsf{\sigma}_{k+1}^\mathsf{p}\not\subset\mathsf{bqp}^{\mathsf{\sigma}_{k}^\mathsf{p}}$ となる。
-\mathsf{bqp}=\mathsf{p^{\# p}}$でありながら$\mathsf{ph}$が無限であるオラクルの相対関係が存在する。
-その関係は、$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$である。
これらの結果を達成するために、oracle の raz と tal による 2018 年の成果に基づいて、$\mathsf{bqp}\not \subset \mathsf{ph}$ と関連する forrelation 問題に関する結果を構築します。
また、独立した関心を持つ可能性のある新しいツールも導入します。
これにはランダム制限法の「量子認識」バージョン、$\mathsf{ac^0}$回路のブロック感度の集中定理、スパースオラクルに対するaaronson-ambainis予想の(証明可能な)類似性が含まれる。
関連論文リスト
- On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
局所密度行列(mathsfPureCLDM$)および純$N$-representability(mathsfPure$-$N$-$mathsfRepresentability$)問題の純粋整合性について検討する。
この新しいクラスには$mathsfPure$-$N$-$mathsfRepresentability$と$mathsfPureCLDM$の両方が完了していることを証明します。
論文 参考訳（メタデータ） (2024-11-05T13:43:21Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する
私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。
我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
論文 参考訳（メタデータ） (2024-01-08T10:55:41Z) - 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) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。