論文の概要: Feynman Meets Turing: The Curse of Quantum Universality

• arxiv url: http://arxiv.org/abs/2607.16436v1
• Date: Fri, 17 Jul 2026 18:33:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-21 18:48:37.150126
• Title: Feynman Meets Turing: The Curse of Quantum Universality
• Title（参考訳）: Feynman、量子普遍性の曲線「チューリング」を語る
• Authors: Yannik N. Böck, Holger Boche, Frank H. P. Fitzek,
• Abstract要約: 量子回路記述言語(QCDL)の形式モデルを考える。 意味的に普遍的なQCDLは、意味的に意味のある記述の半決定可能な集合を持つことは不可能である。
• 参考スコア（独自算出の注目度）: 40.3363283392136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a formal model of quantum circuit description languages (QCDLs) in which semantically meaningful programs correspond to computable unitary matrices. We show that any semantically universal QCDL -- that is, any QCDL able to describe all computable unitary matrices, which in turn form the set of matrices we can meaningfully represent on digital hardware -- cannot have a semi-decidable set of semantically meaningful descriptions. In particular, no such language admits a compiler that reliably recognizes all valid program descriptions. This result stands in contrast to classical programming languages. While compilation in languages such as C or C++ may itself involve non-terminating computations, the set of semantically meaningful programs remains recursively enumerable, since successful compilation provides a witness of validity. The essential difference lies in the nature of the semantic domains: classical languages describe partial recursive functions, whereas QCDLs describe total unitary operators. Our analysis establishes a fundamental limitation of quantum circuit description languages and highlights a structural distinction between classical and quantum models of computation at the level of formal language theory.
• Abstract（参考訳）: 意味的に意味のあるプログラムが計算可能なユニタリ行列に対応する量子回路記述言語(QCDL)の形式モデルを考える。 意味的に普遍的なQCDL – すなわち、計算可能なユニタリ行列を記述可能な任意のQCDL – が、デジタルハードウェア上で有意義に表現できる行列の集合を形成する – は、意味的に意味のある記述の半決定可能な集合を持たないことを示す。 特に、そのような言語は、すべての有効なプログラム記述を確実に認識するコンパイラを認めない。 この結果は古典的なプログラミング言語とは対照的である。 C言語やC++などの言語でのコンパイルは、それ自体が非終端計算を含むかもしれないが、セマンティックな意味のあるプログラムの集合は、コンパイルが成功したことが妥当性の証となるため、再帰的に計算可能である。 古典言語は部分再帰関数を記述し、QCDLは総ユニタリ作用素を記述している。 我々の分析は量子回路記述言語の基本的限界を確立し、形式言語理論のレベルでの計算の古典的モデルと量子的モデルの間の構造的区別を強調している。

関連論文リスト

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• Circuit Width Estimation via Effect Typing and Linear Dependency (Long Version) [1.3597551064547502]
  本稿では,線形依存型・実効性を持つ回路記述言語Proto-Quipper-Rを提案する。 提案手法は現実的な量子アルゴリズムを検証するのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-10-29T18:10:31Z)
• QParallel: Explicit Parallelism for Programming Quantum Computers [62.10004571940546]
  並列量子プログラミングのための言語拡張を提案する。 QParallelは、現在の量子プログラミング言語における並列性に関する曖昧さを取り除く。 並列化によって最も利益を上げるサブルーチンを識別し,並列領域の配置にプログラマを誘導するツールを提案する。
  論文  参考訳（メタデータ） (2022-10-07T16:35:16Z)
• Qunity: A Unified Language for Quantum and Classical Computing (Extended Version) [3.862247454265945]
  量子プログラミング言語Quinityを紹介します。 Qunityは量子コンピューティングを古典コンピューティングの自然な一般化として扱う。 我々はQunityがいくつかの量子アルゴリズムをきれいに表現する方法を示す。
  論文  参考訳（メタデータ） (2022-04-26T15:34:22Z)
• Extending C++ for Heterogeneous Quantum-Classical Computing [56.782064931823015]
  qcorはC++とコンパイラの実装の言語拡張で、異種量子古典プログラミング、コンパイル、単一ソースコンテキストでの実行を可能にする。 我々の研究は、量子言語で高レベルな量子カーネル(関数)を表現できる、第一種C++コンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-08T12:49:07Z)

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

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