論文の概要: Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape
- arxiv url: http://arxiv.org/abs/2507.03692v1
- Date: Fri, 04 Jul 2025 16:21:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-08 15:46:34.838993
- Title: Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape
- Title（参考訳）: 相関測定による量子計算:複雑景観への示唆
- Authors: David Miloschewsky, Supartha Podder,
- Abstract要約: 私たちは$mathsfCorrBQP$が$mathsfBPPmathsfPP$と全く同じであることを示す。
また、$mathsfCorrBQP$は古典的なクエリに関して自己低であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In 2004, Aaronson introduced the complexity class $\mathsf{PostBQP}$ ($\mathsf{BQP}$ with postselection) and showed that it is equal to $\mathsf{PP}$. In this paper, we define a new complexity class, $\mathsf{CorrBQP}$, a modification of $\mathsf{BQP}$ which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. We show that $\mathsf{CorrBQP}$ is exactly equal to $\mathsf{BPP}^{\mathsf{PP}}$, placing it "just above" $\mathsf{PP}$. In fact, we show that other metaphysical modifications of $\mathsf{BQP}$, such as $\mathsf{CBQP}$ (i.e. $\mathsf{BQP}$ with the ability to clone arbitrary quantum states), are also equal to $\mathsf{BPP}^{\mathsf{PP}}$. Furthermore, we show that $\mathsf{CorrBQP}$ is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy ($\mathsf{CH}$) would collapse to $\mathsf{BPP}^{\mathsf{PP}}$. Finally, we introduce a variant of rational degree that lower-bounds the query complexity of $\mathsf{BPP}^{\mathsf{PP}}$.
- Abstract（参考訳）: 2004年、アーロンソンは複雑性クラス $\mathsf{PostBQP}$$$\mathsf{BQP}$ with postelection を導入し、それが $\mathsf{PP}$ に等しいことを示した。
本稿では,新しい複雑性クラスである$\mathsf{CorrBQP}$を定義する。
我々は、$\mathsf{CorrBQP}$がちょうど$\mathsf{BPP}^{\mathsf{PP}}$に等しいことを示す。
実際、$\mathsf{BQP}$(例えば、任意の量子状態のクローン化能力を持つ$\mathsf{CBQP}$)のような他のメタ物理学的な修正も$\mathsf{BPP}^{\mathsf{PP}}$と等しいことを示す。
さらに、$\mathsf{CorrBQP}$は古典的なクエリに関して自己低であることを示す。
対照的に、量子クェリで自己ローであれば、カウント階層(\mathsf{CH}$)は$\mathsf{BPP}^{\mathsf{PP}}$に崩壊する。
最後に、$\mathsf{BPP}^{\mathsf{PP}}$のクエリ複雑性を下げる有理次数の変種を導入する。
関連論文リスト
- Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
我々は、Aharanov と Regev [FOCS 2003] の複雑性クラス QMA+ の純粋状態類似体を定義し、PureSuperQMA と呼ぶ。
2-qubit還元密度行列の硬さを証明し、混合N-表現性はQMA完全であることを示す。
我々はこれを、PureCLDMがQMA(2)完全かどうかという長年の未解決問題に対する否定的な答えの証拠とみなす。
論文 参考訳（メタデータ） (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) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。