論文の概要: A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
- arxiv url: http://arxiv.org/abs/2302.10332v1
- Date: Mon, 20 Feb 2023 21:55:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 17:00:59.463900
- Title: A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
- Title（参考訳）: Qubit, Coin, and an Advice String Walk into a Relational problem
- Authors: Scott Aaronson and Harry Buhrman and William Kretschmer
- Abstract要約: PSPACE が NP/poly に含まれない限り, FBPP は FP/poly に含まれない。
この分離が「情報優位性」を示す実験の可能性をいかに高めるかについて議論する。
我々の証明はIP=PSPACEと時間境界コルモゴロフ複雑性を用いる。
- 参考スコア（独自算出の注目度）: 3.9747898273716697
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Relational problems (those with many possible valid outputs) are different
from decision problems, but it is easy to forget just how different. This paper
initiates the study of FBQP/qpoly, the class of relational problems solvable in
quantum polynomial-time with the help of polynomial-sized quantum advice, along
with its analogues for deterministic and randomized computation (FP, FBPP) and
advice (/poly, /rpoly).
Our first result is that FBQP/qpoly != FBQP/poly, unconditionally, with no
oracle -- a striking contrast with what we know about the analogous decision
classes. The proof repurposes the separation between quantum and classical
one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We
discuss how this separation raises the prospect of near-term experiments to
demonstrate "quantum information supremacy," a form of quantum supremacy that
would not depend on unproved complexity assumptions.
Our second result is that FBPP is not contained in FP/poly -- that is,
Adleman's Theorem fails for relational problems -- unless PSPACE is contained
in NP/poly. Our proof uses IP=PSPACE and time-bounded Kolmogorov complexity. On
the other hand, we show that proving FBPP not in FP/poly will be hard, as it
implies a superpolynomial circuit lower bound for PromiseBPEXP.
We prove the following further results: * Unconditionally, FP != FBPP and
FP/poly != FBPP/poly (even when these classes are carefully defined). *
FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by
contrast, SampBPP/poly != SampBPP/rpoly (and likewise for SampBQP).
- Abstract（参考訳）: 関係問題(多くの有効なアウトプットがある)は決定問題とは異なるが、どの程度の違いがあるかを忘れるのは容易である。
本稿では、FBQP/qpoly、多項式サイズの量子アドバイスの助けを借りて量子多項式時間で解ける関係問題のクラス、決定論的およびランダム化された計算(FP, FBPP)とアドバイス(/poly, /rpoly)の研究を開始する。
最初の結果はfbqp/qpolyです!
FBQP/poly, unconditionally, with no oracle -- 類似の意思決定クラスについて知っていることとは対照的です。
この証明は、Bar-Yossef、Jayram、Kerenidisによる量子的および古典的な一方的な通信複雑性の分離を再利用する。
この分離が、未証明の複雑性の仮定に依存しない量子超越性(quantum information supremacy)の形式である「量子情報優位性(quantum information supremacy)」を示すための短期的な実験の見通しをいかに高めるかについて議論する。
2つ目の結果は、fbpp が fp/poly に含まれないこと、つまり、adleman の定理は関係問題に対して失敗する、つまり pspace が np/poly に含まれない限り。
我々の証明はIP=PSPACEと時間境界コルモゴロフ複雑性を用いる。
一方,FP/poly では FBPP の証明は困難であり,PromiseBPEXP ではスーパーポリノミカル回路が低いことを示す。
以下の結果が証明される: * 非条件、FP!
FBPP と FP/poly !
FBPP/poly (これらのクラスが慎重に定義された場合でも)。
※FBPP/poly=FBPP/rpoly(FBQPも同様)
サンプリング問題に対して、SampBPP/poly !
SampBPP/rpoly(SampBQPも同様)。
関連論文リスト
- Are uncloneable proof and advice states strictly necessary? [0.14565169431855263]
我々は、QMA、BQP/qpoly、FEQP/qpolyといった言語が、不可能な量子証明とアドバイスを必要とすることを示す。
われわれはQMAを、不可能な証明しか持たない言語と定義している。
また、Aaronson、Buhrman、Kretschmerによって使われている言語が、厳密に拘束不能なFEQP/qpolyであるようなオラクルを使わずに示す。
論文 参考訳（メタデータ） (2024-10-15T17:53:08Z) - The status of the quantum PCP conjecture (games version) [0.6144680854063939]
多重対数的に長いメッセージを持つ多目的対話型証明システムはREにおける任意の決定問題を解くことができることを示す。
本稿では,(1)標準AM完全問題に対する効率的なプロバーを用いた簡潔なMIP*プロトコルを新たに構築し,(2)ナタラジャンとヴィディックのエネルギー増幅手順における誤差を説明する。
論文 参考訳（メタデータ） (2024-03-19T18:30:32Z) - The Power of Lorentz Quantum Computer [6.9754404995027794]
本稿では,最近提案されたローレンツ量子コンピュータ(LQC)の,従来の量子コンピュータと比較して優れた性能を示す。
計算複雑性クラス$text Psharp textP$を導入し、複雑性クラス$text Psharp textP$と等価性を実証する。
Aaronsonが提案したポストセレクションによる量子コンピューティングはLQCで効率的にシミュレートできるが、その逆ではない。
論文 参考訳（メタデータ） (2024-03-07T03:00:09Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。
我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。
これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文 参考訳（メタデータ） (2023-10-09T19:40:54Z) - Quantum Eigenvector Continuation for Chemistry Applications [57.70351255180495]
我々は、既に計算済みの基底状態を利用することで、相当量の(量子)計算作業を省くことができることを示す。
いずれの場合も、比較的少数の基底状態を用いてPSSを捕捉できることが示される。
論文 参考訳（メタデータ） (2023-04-28T19:22:58Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - 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) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。