論文の概要: Complexity limitations on one-turn quantum refereed games
- arxiv url: http://arxiv.org/abs/2002.01509v1
- Date: Tue, 4 Feb 2020 19:28:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-04 18:37:50.122716
- Title: Complexity limitations on one-turn quantum refereed games
- Title（参考訳）: 一ターン量子参照ゲームにおける複素性制限
- Authors: Soumik Ghosh, John Watrous
- Abstract要約: 本論文は,量子参照ゲームの理論的側面を研究する。
抽象ゲームは、審判に量子状態を送信する2人のプレーヤーの間のものである。
審判は、2つの状態に対して効率よく実施可能な共同測定を行い、どのプレイヤーが勝つかを判定する。
- 参考スコア（独自算出の注目度）: 0.6091702876917281
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies complexity theoretic aspects of quantum refereed games,
which are abstract games between two competing players that send quantum states
to a referee, who performs an efficiently implementable joint measurement on
the two states to determine which of the player wins. The complexity class
$\mathrm{QRG}(1)$ contains those decision problems for which one of the players
can always win with high probability on yes-instances and the other player can
always win with high probability on no-instances, regardless of the opposing
player's strategy. This class trivially contains $\mathrm{QMA} \cup
\text{co-}\mathrm{QMA}$ and is known to be contained in $\mathrm{PSPACE}$. We
prove stronger containments on two restricted variants of this class.
Specifically, if one of the players is limited to sending a classical
(probabilistic) state rather than a quantum state, the resulting complexity
class $\mathrm{CQRG}(1)$ is contained in $\exists\cdot\mathrm{PP}$ (the
nondeterministic polynomial-time operator applied to $\mathrm{PP}$); while if
both players send quantum states but the referee is forced to measure one of
the states first, and incorporates the classical outcome of this measurement
into a measurement of the second state, the resulting class $\mathrm{MQRG}(1)$
is contained in $\mathrm{P}\cdot\mathrm{PP}$ (the unbounded-error probabilistic
polynomial-time operator applied to $\mathrm{PP}$).
- Abstract（参考訳）: 本稿では、量子状態を送信する2人のプレーヤー間の抽象ゲームである量子参照ゲームの複雑性理論的側面について検討し、そのプレイヤーがどのプレイヤーが勝つかを決定するために、2つの状態に対して効率的に実装可能なジョイント計測を行う。
複雑性クラス $\mathrm{qrg}(1)$ は、一方のプレイヤーがyesインスタンスで常に高い確率で勝つことができ、もう一方のプレイヤーは、他方のプレイヤーの戦略に関わらず、常に無インスタンスで高い確率で勝つことができる決定問題を含んでいる。
このクラスは自明に$\mathrm{QMA} \cup \text{co-}\mathrm{QMA}$を含み、$\mathrm{PSPACE}$に含まれることが知られている。
このクラスの2つの制限付き不変量に対してより強い包含を証明します。
Specifically, if one of the players is limited to sending a classical (probabilistic) state rather than a quantum state, the resulting complexity class $\mathrm{CQRG}(1)$ is contained in $\exists\cdot\mathrm{PP}$ (the nondeterministic polynomial-time operator applied to $\mathrm{PP}$); while if both players send quantum states but the referee is forced to measure one of the states first, and incorporates the classical outcome of this measurement into a measurement of the second state, the resulting class $\mathrm{MQRG}(1)$ is contained in $\mathrm{P}\cdot\mathrm{PP}$ (the unbounded-error probabilistic polynomial-time operator applied to $\mathrm{PP}$).
関連論文リスト
- 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) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳（メタデータ） (2023-03-03T16:53:30Z) - Quantum free games [2.298932494750101]
我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
論文 参考訳（メタデータ） (2023-02-08T20:32:24Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
論文 参考訳（メタデータ） (2021-12-09T21:06:52Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。