dorsal/arxiv
View SchemaMeasurement-based quantum computation and undecidable logic
| Authors | M. Van den Nest, H. J. Briegel |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610040 |
| URL | https://arxiv.org/abs/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.
{
"annotation_id": "f3bf3a7d-4328-4f22-afb3-4ac225ea8203",
"date_created": "2026-03-02T18:02:30.845000Z",
"date_modified": "2026-03-02T18:02:30.845000Z",
"file_hash": "0f43f22ef0ba77ea4e402e3de21387e7eae8179da8107f8341abdea7f9089ce4",
"private": false,
"record": {
"abstract": "We establish a connection between measurement-based quantum computation and\nthe field of mathematical logic. We show that the computational power of an\nimportant class of quantum states called graph states, representing resources\nfor measurement-based quantum computation, is reflected in the expressive power\nof (classical) formal logic languages defined on the underlying mathematical\ngraphs. In particular, we show that for all graph state resources which can\nyield a computational speed-up with respect to classical computation, the\nunderlying graphs--describing the quantum correlations of the states--are\nassociated with undecidable logic theories. Here undecidability is to be\ninterpreted in a sense similar to Goedel\u0027s incompleteness results, meaning that\nthere exist propositions, expressible in the above classical formal logic,\nwhich cannot be proven or disproven.",
"arxiv_id": "quant-ph/0610040",
"authors": [
"M. Van den Nest",
"H. J. Briegel"
],
"categories": [
"quant-ph"
],
"doi": "10.1007/s10701-008-9212-6",
"title": "Measurement-based quantum computation and undecidable logic",
"url": "https://arxiv.org/abs/quant-ph/0610040"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6fe03401-bddc-4b56-80ec-fc08d8543cad",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}