Quantum Computation and Information Seminar 

13/04/2007, 14:00 — 15:00 — Room P4.35, Mathematics Building
Maarten Van den Nest, U Innsbruck

Measurement-based quantum computation and undecidable logic

The introduction of the one-way quantum computer established that, in order to realize universal quantum computation, it is sufficient to perform local 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 such 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 arbitrary graph state 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.