Measurement-based quantum computation and undecidable logic

DOI10.1007/S10701-008-9212-6MaRDI QIDQ930147zbMATH OpenOpenAlexFDO

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

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

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
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(15)

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

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)