Measurement-based quantum computation and undecidable logic

DOI10.1007/S10701-008-9212-6zbMATH Open1140.81342arXivquant-ph/0610040OpenAlexW2005587022MaRDI QIDQ930147FDOQ930147

H. J. Briegel, Maarten Van den Nest

Publication date: 23 June 2008

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

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.

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)

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 (12)

• Title not available (Why is that?)
• Boolean powers and quantum measurements
• Undecidability of the Spectral Gap
• Epistemic horizons and the foundations of quantum mechanics
• Interaction-free measurements and counterfactual computation in IBM quantum computers
• Measurement-based quantum computation cannot avoid byproducts
• Outcome determinism in measurement-based quantum computation with qudits
• Determinism and computational power of real measurement-based quantum computation
• Undecidability and the problem of outcomes in quantum measurements
• Title not available (Why is that?)
• (Un)decidable Problems about Reachability of Quantum Systems
• Measurement theory in Deutsch's algorithm based on the truth values

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)