http://www.fqxi.org/community/articles/display/198
EXCERPT: Physicist Jens Eisert likens himself to Sherlock Holmes. The fictional sleuth was famously preoccupied with eliminating the impossible in his hunt for the truth. Eisert is involved in a similar quest: eliminating "undecidable" problems that cannot, even in theory, ever be resolved by a computer.
Eisert, who is based at the Free University of Berlin, is interested in the quantum world, and how we understand and describe tasks in terms of their computational complexity. So far, he says he has found "the most crazy, the most extreme forms of difference," where a problem is perfectly decidable in the classical world, and not just hard, but undecidable in the quantum world. The approach could, for instance, help physicists exploiting quantum properties for securely encoding data....
EXCERPT: Physicist Jens Eisert likens himself to Sherlock Holmes. The fictional sleuth was famously preoccupied with eliminating the impossible in his hunt for the truth. Eisert is involved in a similar quest: eliminating "undecidable" problems that cannot, even in theory, ever be resolved by a computer.
Eisert, who is based at the Free University of Berlin, is interested in the quantum world, and how we understand and describe tasks in terms of their computational complexity. So far, he says he has found "the most crazy, the most extreme forms of difference," where a problem is perfectly decidable in the classical world, and not just hard, but undecidable in the quantum world. The approach could, for instance, help physicists exploiting quantum properties for securely encoding data....