論文の概要: Whether a quantum computation employs nonlocal resources is operationally undecidable

• arxiv url: http://arxiv.org/abs/2501.14298v1
• Date: Fri, 24 Jan 2025 07:43:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-27 14:56:01.525343
• Title: Whether a quantum computation employs nonlocal resources is operationally undecidable
• Title（参考訳）: 量子計算が非局所的な資源を利用するかどうかは、運用上は決定不可能である
• Authors: Chris Fields, James F. Glazebrook, Antonino Marciano, Emanuele Zappala,
• Abstract要約: 計算複雑性は、計算プロセスによる空間的資源と時間的資源の使用を特徴付ける。 一般相対性理論と量子論は非局所的な資源を利用する計算プロセスの可能性を導入する。
• 参考スコア（独自算出の注目度）: 0.48212500317840945
• License:
• Abstract: Computational complexity characterizes the usage of spatial and temporal resources by computational processes. In the classical theory of computation, e.g. in the Turing Machine model, computational processes employ only local space and time resources, and their resource usage can be accurately measured by us as users. General relativity and quantum theory, however, introduce the possibility of computational processes that employ nonlocal spatial or temporal resources. While the space and time complexity of classical computing can be given a clear operational meaning, this is no longer the case in any setting involving nonlocal resources. In such settings, theoretical analyses of resource usage cease to be reliable indicators of practical computational capability. We prove that the verifier (C) in a multiple interactive provers with shared entanglement (MIP*) protocol cannot operationally demonstrate that the "multiple" provers are independent, i.e. cannot operationally distinguish a MIP* machine from a monolithic quantum computer. Thus C cannot operationally distinguish a MIP* machine from a quantum TM, and hence cannot operationally demonstrate the solution to arbitrary problems in RE. Any claim that a MIP* machine has solved a TM-undecidable problem is, therefore, circular, as the problem of deciding whether a physical system is a MIP* machine is itself TM-undecidable. Consequently, despite the space and time complexity of classical computing having a clear operational meaning, this is no longer the case in any setting involving nonlocal resources. In such settings, theoretical analyses of resource usage cease to be reliable indicators of practical computational capability. This has practical consequences when assessing newly proposed computational frameworks based on quantum theories.
• Abstract（参考訳）: 計算複雑性は、計算プロセスによる空間的資源と時間的資源の使用を特徴付ける。 古典的な計算理論では、例えばチューリングマシンモデルでは、計算プロセスは局所的な空間と時間資源しか使用せず、そのリソース使用量をユーザとして正確に測定することができる。 しかし、一般相対性理論と量子論は非局所的な空間的資源や時間的資源を利用する計算プロセスの可能性を導入する。 古典コンピューティングの空間と時間の複雑さは明確な運用上の意味を与えることができるが、非ローカルなリソースを含むあらゆる環境ではもはやそうではない。 このような環境では、資源利用に関する理論的分析は、実用的な計算能力の信頼性のある指標とはなり得ない。 共用エンタングルメント(MIP*)プロトコルを持つ複数対話型プロバーの検証器(C)が「複数」プローバーが独立であること、すなわち、MIP*マシンとモノリシック量子コンピュータとを運用的に区別できないことを示す。 したがって、C は MIP* マシンと量子TM を操作的に区別することができず、RE の任意の問題に対する解を操作的に示すことはできない。 したがって、MIP*マシンがTM決定不能な問題を解いたという主張は、物理系がMIP*マシンであるかどうかを判断する問題はTM決定不能である。 したがって、古典コンピューティングの空間と時間の複雑さが明確な運用意味を持っているにもかかわらず、もはや非ローカルなリソースを含むあらゆる環境ではそうではない。 このような環境では、資源利用に関する理論的分析は、実用的な計算能力の信頼性のある指標とはなり得ない。 これは、量子理論に基づいて新たに提案された計算フレームワークを評価する際に、実用的な結果をもたらす。

関連論文リスト

• On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
  計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。 また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
  論文  参考訳（メタデータ） (2023-10-19T17:39:47Z)
• Learnability with Time-Sharing Computational Resource Concerns [65.268245109828]
  本稿では,学習理論における計算資源の影響を考慮した理論的枠組みを提案する。 このフレームワークは、入ってくるデータストリームが潜在的に無限であるようなストリーム学習に自然に適用できる。 これはまた、インテリジェントなスーパーコンピュータオペレーティングシステムの設計に対する理論的視点を提供するかもしれない。
  論文  参考訳（メタデータ） (2023-05-03T15:54:23Z)
• Resources for bosonic quantum computational advantage [0.0]
  各ボソニック量子計算は連続可変サンプリング計算に再キャスト可能であることを示す。 ボソニック計算の強いシミュレーションのための一般的な古典的アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-07-24T17:50:20Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Quantum reservoir computation utilising scale-free networks [0.0]
  我々は,スケールフリーネットワークを利用した量子優位性を示すパターン認識のための新しい貯水池計算モデルを提案する。 このアプローチの単純さは、量子複雑性の計算能力を示すとともに、そのようなプロセッサに新しいアプリケーションを提供する。
  論文  参考訳（メタデータ） (2021-08-27T06:28:08Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。 量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
  論文  参考訳（メタデータ） (2021-03-12T20:58:41Z)
• Thermodynamically-Efficient Local Computation and the Inefficiency of Quantum Memory Compression [0.0]
  モジュラリティの散逸は、局所的に実装された計算が、ランダウアーが熱力学計算に縛り付けられているものよりもコストがかかることを示す。 我々は、効率的な局所計算のための一般的な定理を確立し、局所演算に必要な十分条件をゼロコストで提供する。
  論文  参考訳（メタデータ） (2020-01-07T19:44:13Z)
• Simulation of Thermal Relaxation in Spin Chemistry Systems on a Quantum Computer Using Inherent Qubit Decoherence [53.20999552522241]
  我々は,実世界の量子システムの振舞いをシミュレーションする資源として,キュービットデコヒーレンスを活用することを目指している。 熱緩和を行うための3つの方法を提案する。 結果,実験データ,理論的予測との間には,良好な一致が得られた。
  論文  参考訳（メタデータ） (2020-01-03T11:48:11Z)

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

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