Measurement-based quantum computation and undecidable logic

DOI10.1007/S10701-008-9212-6MaRDI QIDQ930147zbMATHOpenAlexFDO

Authors Maarten Van den Nest, H. J. Briegel

Publication date 23 June 2008

Published in Foundations of Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0610040

zbMATH Keywords

LogicQuantum computationQuantum information theory

Mathematics Subject Classification ID

Quantum computation (81P68) Classical propositional logic (03B05) Undecidability and degrees of sets of sentences (03D35)

Abstract: We establish a connection between measurement-based quantum computation and the field of mathematical logic. We show that the computational power of an important class of quantum states called graph states, representing resources for measurement-based quantum computation, is reflected in the expressive power of (classical) formal logic languages defined on the underlying mathematical graphs. In particular, we show that for all graph state resources which can yield a computational speed-up with respect to classical computation, the underlying graphs--describing the quantum correlations of the states--are associated with undecidable logic theories. Here undecidability is to be interpreted in a sense similar to Goedel's incompleteness results, meaning that there exist propositions, expressible in the above classical formal logic, which cannot be proven or disproven.

Recommendations

• Topos logic in measurement-based quantum computation
• State complexity and quantum computation
• Quantum logic is undecidable
• Extended measurement calculus
• Hierarchies of resources for measurement-based quantum computation

Cites work

• On the role of entanglement in quantum-computational speed-up
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Cited in

(14)

• Boolean powers and quantum measurements
• Quantum logic is undecidable
• Undecidability of the Spectral Gap
• scientific article; zbMATH DE number 6746918 (Why is no real title available?)
• Topos logic in measurement-based quantum computation
• Undecidability and the problem of outcomes in quantum measurements
• Outcome determinism in measurement-based quantum computation with qudits
• Determinism and computational power of real measurement-based quantum computation
• Measurement-based quantum computation cannot avoid byproducts
• Epistemic horizons and the foundations of quantum mechanics
• Measurement theory in Deutsch's algorithm based on the truth values
• scientific article; zbMATH DE number 7339588 (Why is no real title available?)
• Interaction-free measurements and counterfactual computation in IBM quantum computers
• (Un)decidable Problems about Reachability of Quantum Systems

This page was built for publication: Measurement-based quantum computation and undecidable logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930147)