論文の概要: Winning Mastermind Overwhelmingly on Quantum Computers

• arxiv url: http://arxiv.org/abs/2207.09356v3
• Date: Tue, 27 Sep 2022 07:07:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-04 12:59:55.770836
• Title: Winning Mastermind Overwhelmingly on Quantum Computers
• Title（参考訳）: 量子コンピュータに圧倒的に勝てるマスターマインド
• Authors: Lvzhou Li, Jingquan Luo, Yongzhen Xu
• Abstract要約: 我々はMastermindをプレイするための量子戦略を体系的に研究している。 非適応性および適応性の両方の設定で最適量子アルゴリズムを構築する。 一般的な文字列学習問題に対して,量子アルゴリズムを設計するためのフレームワークを開発する。
• 参考スコア（独自算出の注目度）: 0.2320417845168326
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: From the 1970s up to now, Mastermind, a classic two-player game, has attracted plenty of attention, not only from the public as a popular game, but also from the academic community as a scientific issue. Mastermind with n positions and k colors is formally described as: the codemaker privately chooses a secret $s\in [k]^n$, and the coderbreaker want to determine $s$ in as few queries like $f_s(x)$ as possible to the codemaker, where $f_s(x)$ indicates how x is close to s. The complexity of a strategy is measured by the number of queries used. In this work we have a systematic study on quantum strategies for playing Mastermind, obtaining a complete characterization of the quantum complexity and constructing optimal quantum algorithms in both non-adaptive and adaptive settings. Technically, we develop a framework for designing quantum algorithms for the general string learning problem, by discovering a new structure that not only allows quantum speedup to be maximized on Mastermind in the non-adaptive setting, but also is very likely helpful for addressing other string learning problems with different kinds of query oracles.
• Abstract（参考訳）: 1970年代から現在まで、クラシックな2人プレイゲームであるmastermindは、大衆から人気ゲームとしてだけでなく、科学的な問題として学術界からも多くの注目を集めてきた。 n位とk色を持つmastermindは公式に次のように記述される: コードメーカーは秘密の$s\in [k]^n$をプライベートに選択し、coderbreakerはsに近いxを示す$f_s(x)$をコードメーカーに対して可能な限り$f_s(x)$のようなわずかなクエリで$s$を判定したいと考えている。 戦略の複雑さは、使用するクエリの数によって測定される。 本研究では,マスターマインドを弾くための量子戦略に関する体系的な研究を行い,量子複雑性の完全なキャラクタリゼーションを求め,非適応的および適応的設定において最適な量子アルゴリズムを構築する。 技術的には,非適応的な設定でMastermind上で量子スピードアップを最大化できるだけでなく,異なる種類のクエリオーラクルで他の文字列学習問題に対処する上でも有効な新しい構造を見出すことによって,一般的な文字列学習問題の量子アルゴリズムを設計するためのフレームワークを開発する。

関連論文リスト

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
  量子量$k$-juntasの検証と学習の問題を考察する。 a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。 我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
  論文  参考訳（メタデータ） (2022-07-13T00:11:14Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum Semi-Supervised Learning with Quantum Supremacy [0.0]
  量子機械学習は重要な問題を解決することを約束する。 古典的な機械学習には、ラベル付きデータの欠如と計算能力の限界という2つの永続的な課題がある。 本稿では,量子セミ教師付き学習という,両方の問題を解決する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:58Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
  サブトラクションゲームはワンヒープニムゲームと呼ばれることもある。 量子ゲーム理論において、サブトラクションゲームの部分集合は、ゼロサムゲームの最初の明示的に定義されたクラスとなった。 サブトラクションゲームのより狭い部分集合については、すべての決定論的アルゴリズムを超える正確な量子サブ線形アルゴリズムが知られている。
  論文  参考訳（メタデータ） (2020-06-12T06:36:07Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。