論文の概要: 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(参考訳): 古典的資源の問題は量子的に決定できないのか?
どちらもチューリング理論であるため、チューリングマシンでは解決できない問題である停止問題を解くべきではない。
しかし、上記の質問に対する肯定的な回答を提供する。
我々は、古典理論や量子理論に限らず、異なるチューリング理論の任意の対に対して無限に多くのそのような問題を定式化する新しい論理構造を思いついた。
重要なことに、他の決定問題(例えば停止問題)のクラスは、これらの全ての理論において解決不可能である。
明らかなパラドックス的状況は、ハルティング問題の再現性が異なる理論の計算に利用できる様々な資源で変化すると認識されると解決される。
最後に、量子資源が完全な勝利戦略を提供する一方で、プレイヤーが古典的資源のみにアクセスすることは決定不可能であるマルチエージェントゲームを提案する。
関連論文リスト
- Quantum Algorithms in a Superposition of Spacetimes [5.475280561991127]
量子コンピュータは私たちの情報処理能力に革命をもたらすと期待されている。
量子重力(QG)に基づく自然計算モデルの最初の例を示す。
量子コンピュータは,計算機科学の基本的な2つの問題を時間内に解くことができることを示す。
論文 参考訳(メタデータ) (2024-03-05T13:05:07Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - 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) - Is there a finite complete set of monotones in any quantum resource
theory? [58.720142291102135]
すべての状態変換を完全に決定する資源単調の有限集合は存在しないことを示す。
完全順序理論はすべての純状態間の自由変換を可能にすることを示す。
論文 参考訳(メタデータ) (2022-12-05T18:28: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) - Stochastic approximate state conversion for entanglement and general
quantum resource theories [62.997667081978825]
量子資源理論における重要な問題は、量子状態が互いに変換される方法を決定することである。
我々は、状態遷移の忠実さと確率の両方に制限を与えます。
ポーパスク・ロールリッヒ・ボックスと等方性ボックスとの間の忠実度は局所性保存型スーパーチャネルにより増大しないことを示す。
論文 参考訳(メタデータ) (2021-11-24T17:29:43Z) - Resource theory of quantum uncomplexity [0.5872014229110214]
ブラウンとススキンドの予想を証明し、非複素性の資源理論を定義できると証明する。
この研究は、量子情報理論から資源理論ツールキットの多体複雑性を解き放つ。
論文 参考訳(メタデータ) (2021-10-21T18:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。