Measurement-based quantum computation and undecidable logic
arXiv:quant-ph/0610040 · doi:10.1007/s10701-008-9212-6
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.
10 pages. Presentation improved. Paper to appear in Found. Phys.; currently published online
References in corpus (10)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Efficient classical simulation of slightly entangled quantum computations
- Persistent entanglement in arrays of interacting particles
- Measurement-based quantum computation with cluster states
- On the role of entanglement in quantum computational speed-up
- Classical simulation of quantum many-body systems with a tree tensor network
- Universal resources for measurement-based quantum computation
- Classical simulation versus universality in measurement based quantum computation
- On measurement-based quantum computation with the toric code states
- Classical simulation of limited-width cluster-state quantum computation
Cited by in corpus (12)
- Measurement-based quantum computation
- Undecidability of the Spectral Gap (short version)
- Operator theory of electrical resistance networks
- Undecidability of the Spectral Gap in One Dimension
- Measurement-Based Quantum Computation
- Cluster State Generation with Spin-Orbit Coupled Fermionic Atoms in Optical Lattices
- Epistemic Horizons and the Foundations of Quantum Mechanics
- Undecidability of the Spectral Gap (full version)
- A quantum information approach to statistical mechanics
- Undecidability in Physics: a Review
- Can quantum gravity be both consistent and complete?
- Undecidability of the spectral gap in rotationally symmetric Hamiltonians