`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Существуют классические задачи, нерешаемые квантовыми компьютерами

+77
голосов

Существуют классические задачи, нерешаемые квантовыми компьютерами

Примером того, как проблема, легко решаемая в классическом контексте, способна представлять непреодолимую трудность в квантовом, является вопрос с тремя возможными ответами: «Cуществует ли сквозное отверстие, через которое частица никогда не пролетит?».

Физики Йенс Айзерт (Jens Eisert) и Кристиан Гоголин (Christian Gogolin) из Free University of Berlin (Германия), вместе с Маркусом Мюллером (Markus P. Müller) из Perimeter Institute for Theoretical Physics (Ватерлоо, Канада) представили результаты своего исследования в недавнем выпуске Physical Review Letters.

Используя классическое измерительное устройство они показали, что всегда можно найти алгоритм, определяющий наличие или отсутствие результатов с нулевой вероятностью появления. В случае же квантового измерительного устройства, согласно их выводам, алгоритма, всегда предоставляющего правильный ответ на данный вопрос не существует. Ученые объясняют этот феномен взаимодействиями в квантовом устройстве, отмечая, что, по крайней мере в данном случае, нерешаемость, по-видимому, является чисто квантовым свойством.

К таким выводам физики пришли обратившись к хорошо известной вычислительной проблеме остановки, сформулированной Аланом Тьюрингом в 1936 г. — будет ли программа работать бесконечно? Тьюринг показал, что алгоритма решения, общего для всех входных данных не существует — результат, перекликающийся с более формальной теоремой Курта Гёделя о неполноте.

«Мы создали новую связь между квантовой физикой и компьютерной наукой: некоторые проблемы не только вычислительно сложны (например, нахождение базовых состояний стеклянных квантовых моделей из многих тел), но и абсолютно, принципиально нерешаемы, вне зависимости от потраченного машинного времени, — утверждает Айзерт. — Компьютер просто ходит по кругу. Этот удивительный факт освещает новую, ранее неизвестную, грань квантовой механики. Кроме того, он показывает, что помимо академических вопросов машин Тьюринга, нерешаемы могут быть также естественные, физические и интуитивные проблемы».

+77
голосов

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT