論文の概要: Resource dependent undecidability: computability landscape of distinct Turing theories

• arxiv url: http://arxiv.org/abs/2112.13345v1
• Date: Sun, 26 Dec 2021 09:59:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-03 05:43:23.955644
• Title: Resource dependent undecidability: computability landscape of distinct Turing theories
• Title（参考訳）: 資源依存不確定性:異なるチューリング理論の計算可能性展望
• Authors: Airin Antony
• Abstract要約: 我々は、異なるチューリング理論の任意の対に対して無限に多くの問題を定式化する新しい論理構造を思いついた。 重要なことに、ハルティング問題のような他の決定問題のクラスは、これらのすべての理論では解決不可能である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can a problem undecidable with classical resources be decidable with quantum ones? The answer expected is no; as both being Turing theories, they should not solve the Halting problem - a problem unsolvable by any Turing machine. Yet, we provide an affirmative answer to the aforesaid question. We come up with a novel logical structure to formulate infinitely many such problems for any pair of distinct Turing theories, including but not limited to the classical and quantum theories. Importantly, a class of other decision problems, such as the Halting one, remains unsolvable in all those theories. The apparent paradoxical situation gets resolved once it is perceived that the reducibility of Halting problem changes with varying resources available for computations in different theories. In the end, we propose a multi-agent game where winnability of the player having access to only classical resources is undecidable while quantum resources provide a perfect winning strategy.
• Abstract（参考訳）: 古典的資源の問題は量子的に決定できないのか? どちらもチューリング理論であるため、チューリングマシンでは解決できない問題である停止問題を解くべきではない。 しかし、上記の質問に対する肯定的な回答を提供する。 我々は、古典理論や量子理論に限らず、異なるチューリング理論の任意の対に対して無限に多くのそのような問題を定式化する新しい論理構造を思いついた。 重要なことに、他の決定問題(例えば停止問題)のクラスは、これらの全ての理論において解決不可能である。 明らかなパラドックス的状況は、ハルティング問題の再現性が異なる理論の計算に利用できる様々な資源で変化すると認識されると解決される。 最後に、量子資源が完全な勝利戦略を提供する一方で、プレイヤーが古典的資源のみにアクセスすることは決定不可能であるマルチエージェントゲームを提案する。

関連論文リスト

• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。 初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
  論文  参考訳（メタデータ） (2024-03-25T15:47:35Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。 量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
  論文  参考訳（メタデータ） (2023-09-28T13:30:20Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
  ほとんどの人造システム、特にコンピュータは決定論的に機能する。 本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
  論文  参考訳（メタデータ） (2022-09-08T17:55:30Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• On a gap in the proof of the generalised quantum Stein's lemma and its consequences for the reversibility of quantum resources [51.243733928201024]
  一般化された量子シュタインの補題の証明は、Lemma III.9 につながる議論のギャップのために正しくないことを示す。 このことは、文献、特に量子絡み合いの可逆性においていくつかの確立された結果に疑問を呈する。
  論文  参考訳（メタデータ） (2022-05-05T17:46:05Z)
• 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)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。 我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
  論文  参考訳（メタデータ） (2021-06-03T17:22:08Z)
• Undecidability in resource theory: can you tell theories apart? [0.0]
  量子資源理論の文脈では、この問題のクラスは一般に決定不可能である。 これは、CPTPマップのメンバシップ問題の不確定性を証明し、他のすべての結果を仮定することで実現される。
  論文  参考訳（メタデータ） (2021-05-19T18:03:03Z)
• Computability Theory of Closed Timelike Curves [4.826802034066811]
  本研究では,過去へのタイムトラベルを備えたチューリングマシンで計算可能な問題について検討する。 別の見方として、計算可能なマルコフ鎖と数え切れないほど無限次元の量子チャネルの近似的な固定点を見つける複雑さについて研究する。
  論文  参考訳（メタデータ） (2016-09-18T16:08:04Z)

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

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