Feynman Meets Turing: The Curse of Quantum Universality

• URL: http://arxiv.org/abs/2607.16436v1
• Date: Fri, 17 Jul 2026 18:33:27 GMT
• Title: Feynman Meets Turing: The Curse of Quantum Universality
• Abstract summary: We consider a formal model of quantum circuit description languages (QCDLs)<n>We show that any semantically universal QCDL cannot have a semi-decidable set of semantically meaningful descriptions.
• Score: 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.

Related papers

• Higher-Order Programs with Indefinite Causal Orders: a Linear Approach to Coherent Control of Quantum Processes [0.0]
  We introduce a higher-order quantum functional language for quantum computation.<n>It supports general quantum computation, not merely the permutation of channels.<n>It can express every quantum channel at first order, and at second order a large subclass of quantum circuits with quantum control.
  arXiv  Detail & Related papers  (2026-07-10T15:38:33Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Circuit Width Estimation via Effect Typing and Linear Dependency (Long Version) [1.3597551064547502]
  We present Proto-Quipper-R, a circuit description language endowed with a linear dependent type-and-effect system. We show that our approach is expressive enough to verify realistic quantum algorithms.
  arXiv  Detail & Related papers  (2023-10-29T18:10:31Z)
• The Quantum Monadology [0.0]
  Modern theory of functional programming languages uses monads for encoding computational side-effects and side-contexts. We analyze the (co)monads on categories of parameterized module spectra induced by Grothendieck's "motivic yoga of operations" We indicate a domain-specific quantum programming language (QS) expressing these monadic quantum effects in transparent do-notation.
  arXiv  Detail & Related papers  (2023-10-24T11:19:24Z)
• QParallel: Explicit Parallelism for Programming Quantum Computers [62.10004571940546]
  We present a language extension for parallel quantum programming. QParallel removes ambiguities concerning parallelism in current quantum programming languages. We introduce a tool that guides programmers in the placement of parallel regions by identifying the subroutines that profit most from parallelization.
  arXiv  Detail & Related papers  (2022-10-07T16:35:16Z)
• Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$ [0.0]
  We introduce the notion of a qc-modulus, which encodes approximations to quantum commuting correlations. We show that the existence of a computable qc-modulus gives a negative answer to a natural variant of the aforementioned question.
  arXiv  Detail & Related papers  (2022-09-16T15:45:49Z)
• Qunity: A Unified Language for Quantum and Classical Computing (Extended Version) [3.862247454265945]
  We introduce Qunity, a new quantum programming language.<n>Qunity treats quantum computing as a natural generalization of classical computing.<n>We show how Qunity can cleanly express several quantum algorithms.
  arXiv  Detail & Related papers  (2022-04-26T15:34:22Z)
• Enabling Retargetable Optimizing Compilers for Quantum Accelerators via a Multi-Level Intermediate Representation [78.8942067357231]
  We present a multi-level quantum-classical intermediate representation (IR) that enables an optimizing, retargetable, ahead-of-time compiler. We support the entire gate-based OpenQASM 3 language and provide custom extensions for common quantum programming patterns and improved syntax. Our work results in compile times that are 1000x faster than standard Pythonic approaches, and 5-10x faster than comparative standalone quantum language compilers.
  arXiv  Detail & Related papers  (2021-09-01T17:29:47Z)
• A MLIR Dialect for Quantum Assembly Languages [78.8942067357231]
  We demonstrate the utility of the Multi-Level Intermediate Representation (MLIR) for quantum computing. We extend MLIR with a new quantum dialect that enables the expression and compilation of common quantum assembly languages. We leverage a qcor-enabled implementation of the QIR quantum runtime API to enable a retargetable (quantum hardware agnostic) compiler workflow.
  arXiv  Detail & Related papers  (2021-01-27T13:00:39Z)
• Extending C++ for Heterogeneous Quantum-Classical Computing [56.782064931823015]
  qcor is a language extension to C++ and compiler implementation that enables heterogeneous quantum-classical programming, compilation, and execution in a single-source context. Our work provides a first-of-its-kind C++ compiler enabling high-level quantum kernel (function) expression in a quantum-language manner.
  arXiv  Detail & Related papers  (2020-10-08T12:49:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.