Measurement-based quantum computation and undecidable logic
Maarten van den Nest
IQOQI, Innsbruck, Austria
Abstract: A fundamental open problem in the field of quantum computation is to understand the essential features which give quantum computers their additional power over classical ones. The introduction of the one-way model for quantum computation established that, in order to realize universal quantum computation, it is sufficient to perform simple measurements on a system of qubits which have initially been prepared in a highly entangled cluster state. The computational power of such a measurement-based quantum computer originates in the strong quantum correlations which are initially present in the system. However, it is to date largely unknown which correlations allow a measurement-based computer to exhibit a computational speed-up with respect to classical devices. Here we provide a new perspective to this question by relating this issue to 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 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 proved or disproved.