Существуют классические задачи, нерешаемые квантовыми компьютерами
Примером того, как проблема, легко решаемая в классическом контексте, способна представлять непреодолимую трудность в квантовом, является вопрос с тремя возможными ответами: «Cуществует ли сквозное отверстие, через которое частица никогда не пролетит?».
Физики Йенс Айзерт (Jens Eisert) и Кристиан Гоголин (Christian Gogolin) из Free University of Berlin (Германия), вместе с Маркусом Мюллером (Markus P. Müller) из Perimeter Institute for Theoretical Physics (Ватерлоо, Канада) представили результаты своего исследования в недавнем выпуске Physical Review Letters.
Используя классическое измерительное устройство они показали, что всегда можно найти алгоритм, определяющий наличие или отсутствие результатов с нулевой вероятностью появления. В случае же квантового измерительного устройства, согласно их выводам, алгоритма, всегда предоставляющего правильный ответ на данный вопрос не существует. Ученые объясняют этот феномен взаимодействиями в квантовом устройстве, отмечая, что, по крайней мере в данном случае, нерешаемость, по-видимому, является чисто квантовым свойством.
К таким выводам физики пришли обратившись к хорошо известной вычислительной проблеме остановки, сформулированной Аланом Тьюрингом в 1936 г. — будет ли программа работать бесконечно? Тьюринг показал, что алгоритма решения, общего для всех входных данных не существует — результат, перекликающийся с более формальной теоремой Курта Гёделя о неполноте.
«Мы создали новую связь между квантовой физикой и компьютерной наукой: некоторые проблемы не только вычислительно сложны (например, нахождение базовых состояний стеклянных квантовых моделей из многих тел), но и абсолютно, принципиально нерешаемы, вне зависимости от потраченного машинного времени, — утверждает Айзерт. — Компьютер просто ходит по кругу. Этот удивительный факт освещает новую, ранее неизвестную, грань квантовой механики. Кроме того, он показывает, что помимо академических вопросов машин Тьюринга, нерешаемы могут быть также естественные, физические и интуитивные проблемы».