論文の概要: Quantum Combinatorial Games: Structures and Computational Complexity
- arxiv url: http://arxiv.org/abs/2011.03704v1
- Date: Sat, 7 Nov 2020 06:09:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 22:52:36.697597
- Title: Quantum Combinatorial Games: Structures and Computational Complexity
- Title（参考訳）: Quantum Combinatorial Games: 構造と計算複雑性
- Authors: Kyle Burke, Matthew Ferland, Shang-Hua Teng
- Abstract要約: 近年,完全情報を持つ数理ゲームに量子インスパイアされた動きを導入するための標準化されたフレームワークが提案されている。
量子移動はゲーム構造を豊かにするだけでなく、計算の複雑さにも影響を及ぼすことを示す。
- 参考スコア（独自算出の注目度）: 2.284455793077548
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, a standardized framework was proposed for introducing
quantum-inspired moves in mathematical games with perfect information and no
chance. The beauty of quantum games-succinct in representation, rich in
structures, explosive in complexity, dazzling for visualization, and
sophisticated for strategic reasoning-has drawn us to play concrete games full
of subtleties and to characterize abstract properties pertinent to complexity
consequence. Going beyond individual games, we explore the tractability of
quantum combinatorial games as whole, and address fundamental questions
including:
Quantum Leap in Complexity: Are there polynomial-time solvable games whose
quantum extensions are intractable?
Quantum Collapses in Complexity: Are there PSPACE-complete games whose
quantum extensions fall to the lower levels of the polynomial-time hierarchy?
Quantumness Matters: How do outcome classes and strategies change under
quantum moves? Under what conditions doesn't quantumness matter?
PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into
outer polynomial space
We show that quantum moves not only enrich the game structure, but also
impact their computational complexity. In settling some of these basic
questions, we characterize both the powers and limitations of quantum moves as
well as the superposition of game configurations that they create. Our
constructive proofs-both on the leap of complexity in concrete Quantum Nim and
Quantum Undirected Geography and on the continuous collapses, in the quantum
setting, of complexity in abstract PSPACE-complete games to each level of the
polynomial-time hierarchy-illustrate the striking computational landscape over
quantum games and highlight surprising turns with unexpected quantum impact.
Our studies also enable us to identify several elegant open questions
fundamental to quantum combinatorial game theory (QCGT).
- Abstract（参考訳）: 近年,完全情報と偶然をもたない数理ゲームに量子インスパイアされた動きを導入するための標準化フレームワークが提案されている。
量子ゲームの美しさは、表現の簡潔さ、構造に富み、爆発的な複雑さ、可視化のためのダズリング、そして戦略的推論のために洗練されたものであり、我々は、微妙さに満ちた具体的なゲームをし、複雑さの結果に関係のある抽象的性質を特徴づけるようにしました。
個々のゲームを超えて、量子組合せゲーム全体のトラクタビリティを探求し、以下の基本的な問題に対処する。 複雑性の量子飛躍: 量子拡張が難解な多項式時間可解ゲームは存在するか?
複雑性における量子崩壊: 多項式時間階層の下位レベルに量子拡張が落ちるPSPACE完全ゲームはあるか?
量子性の問題: 結果のクラスと戦略は量子移動の下でどのように変化するか?
量子性はどんな条件で重要か?
PSPACE Barrier for Quantum Leap: Can quantum move launch PSPACE games into outer polynomial space 我々は、量子移動がゲーム構造を豊かにするだけでなく、計算複雑性にも影響を及ぼすことを示した。
これらの基本的な問題のいくつかを定め、量子移動のパワーと制限と、それらが生成するゲーム構成の重ね合わせの両方を特徴づける。
我々の構成的証明は、具体的量子ニムと量子無向幾何学における複雑性の跳躍と、量子環境において、多項式時間階層の各レベルへの抽象PSPACE完全ゲームにおける複雑さの連続的な崩壊についてである。
我々はまた、量子組合せゲーム理論(QCGT)の基本となるいくつかのエレガントなオープンな質問を特定できる。
関連論文リスト
- A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。
我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
論文 参考訳（メタデータ） (2024-08-13T08:11:56Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - The History of Quantum Games [0.0]
商用ゲーム、応用ゲーム、真剣ゲーム、および量子テーマゲームジャムや教育コースで開発されたゲームから、260以上の量子ゲームを収集します。
本稿では,3次元の量子ゲームについて概観する。
論文 参考訳（メタデータ） (2023-09-04T11:10:58Z) - A vertical gate-defined double quantum dot in a strained germanium
double quantum well [48.7576911714538]
シリコン-ゲルマニウムヘテロ構造におけるゲート定義量子ドットは、量子計算とシミュレーションのための魅力的なプラットフォームとなっている。
ひずみゲルマニウム二重量子井戸におけるゲート定義垂直2重量子ドットの動作を実証する。
課題と機会を議論し、量子コンピューティングと量子シミュレーションの潜在的な応用について概説する。
論文 参考訳（メタデータ） (2023-05-23T13:42:36Z) - Quantum Extensive Form Games [0.0]
古典的広角ゲームの拡張である量子広角ゲーム(quantum extensive-form game)の概念を提案する。
量子広範形式ゲームは、量子生成適応ネットワークを含む量子学習の一般化でもある。
論文 参考訳（メタデータ） (2022-07-12T09:58:21Z) - No-signalling constrains quantum computation with indefinite causal
structure [45.279573215172285]
我々は、不定因果構造を持つ量子計算の定式化を開発する。
我々は高階量子マップの計算構造を特徴付ける。
計算的および情報理論的な性質を持つこれらの規則は、量子システム間のシグナル伝達関係のより物理的概念によって決定される。
論文 参考訳（メタデータ） (2022-02-21T13:43:50Z) - Endless Fun in high dimensions -- A Quantum Card Game [0.0]
本稿では,量子コンピュータのビルディングブロックを体験できる戦略カードゲームを提案する。
プレイ中、参加者は最低の量子状態から始まり、カードをプレイして量子コンピュータを「プログラム」し、可能な限り高い量子状態を達成することを目指す。
高次元の量子状態、すなわち2つ以上の可能な値を取ることができるシステムを含めることで、ゲームはプレイヤーが複雑な量子状態の操作を理解するのに役立つ。
論文 参考訳（メタデータ） (2021-07-26T07:52:13Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。
本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T12:48:00Z) - Quantum walk processes in quantum devices [55.41644538483948]
グラフ上の量子ウォークを量子回路として表現する方法を研究する。
提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
論文 参考訳（メタデータ） (2020-12-28T18:04:16Z) - Quantum Go Machine [15.33065067850941]
偏光度に絡み合った相関光子対を用いたGoの量子バージョンを実験的に実証した。
コヒーレンスや絡み合いのようないくつかの量子資源は、量子石の状態を表すために符号化することもできる。
この結果から,量子可能困難を伴う新たなゲーム開発パラダイムが確立された。
論文 参考訳（メタデータ） (2020-07-23T18:00:01Z) - Quantum supremacy in driven quantum many-body systems [0.0]
一般周期駆動型量子多体系において量子超越性が得られることを示す。
我々の提案は、大規模な量子プラットフォームが量子超越性を実証し、ベンチマークする方法を開く。
論文 参考訳（メタデータ） (2020-02-27T07:20:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。