Fugu-MT 論文翻訳(概要): Even quantum advice is unlikely to solve PP

論文の概要: Even quantum advice is unlikely to solve PP

arxiv url: http://arxiv.org/abs/2403.09994v1
Date: Fri, 15 Mar 2024 03:33:27 GMT
ステータス: 処理完了
システム内更新日: 2024-03-18 18:48:40.184692
Title: Even quantum advice is unlikely to solve PP
Title（参考訳）: 量子アドバイスでさえPPを解くことは不可能である
Authors: Justin Yirka,
Abstract要約: PP $subseteq$ BQP/qpoly ならば、カウント・ヒエラルキーは崩壊する。これは、PP が量子アドバイスでさえ任意の固定サイズ$nk$の回路を持っていないという関連する無条件の主張を回復させる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give a corrected proof that if PP $\subseteq$ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by Aaronson CCC'06 arXiv:cs/0504048. This recovers the related unconditional claim that PP does not have circuits of any fixed size $n^k$ even with quantum advice. We do so by proving that YQP*, an oblivious version of (QMA $\cap$ coQMA), is contained in APP, and so is PP-low.
Abstract（参考訳）: PP $\subseteq$ BQP/qpoly ならば、Aaronson CCC'06 arXiv:cs/0504048 が主張したように、カウント階層は崩壊する。これは、PP が量子アドバイスでさえ任意の固定サイズ $n^k$ の回路を持っていないという関連する無条件の主張を回復させる。 YQP*(QMA $\cap$ coQMA)がAPPに含まれており、PP-lowも同様です。

関連論文リスト

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
論文参考訳（メタデータ） (2024-03-07T19:00:06Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文参考訳（メタデータ） (2024-02-29T01:35:46Z)
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文参考訳（メタデータ） (2024-01-03T09:12:25Z)
Grüneisen parameter as an entanglement compass and the breakdown of the Hellmann-Feynman theorem [0.0]
Gr"uneisen ratio $Gamma$, すなわち、熱膨張と比熱の比の特異部分は、有限のT$と量子臨界点(QCP)の両方を探索するために広く用いられている。チューニングパラメータ$lambda$の関数として絡み合いを計算する量子アナログを$Gamma$に提案する。
論文参考訳（メタデータ） (2023-06-01T11:28:40Z)
On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文参考訳（メタデータ） (2023-05-25T08:43:11Z)
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem [1.9260081982051918]
PSPACE が NP/poly に含まれない限り, FBPP は FP/poly に含まれない。この分離が「情報優位性」を示す実験の可能性をいかに高めるかについて議論する。我々の証明はIP=PSPACEと時間境界コルモゴロフ複雑性を用いる。
論文参考訳（メタデータ） (2023-02-20T21:55:47Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文参考訳（メタデータ） (2022-10-12T17:54:02Z)
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection [0.0]
sf PostBQP$の任意の問題は、確率が1に近いポストセレクションのみによって解決できることを示す。また,1つの逆風演算子が量子計算に難解なタスクを達成するのに十分であることを示す。
論文参考訳（メタデータ） (2022-06-11T06:19:24Z)
Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文参考訳（メタデータ） (2022-03-24T08:14:12Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文参考訳（メタデータ） (2021-05-06T17:59:38Z)
Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文参考訳（メタデータ） (2020-07-23T10:50:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。