Читать онлайн «Квантовый компьютер и квантовые вычисления»

Квантовый Компьютер & КВАНТОВЫЕ ВЫЧИСЛЕНИЯ Редакция журнала 'Регулярная и хаотическая динамика" Ижевск 1999 УДК 530. 15 Библиотека «Квантовый компьютер и квантовые вычисления», том II Главный редактор В. А. Садовничий Редколлегия: В. В. Белокуров А. П. Бельтюков А. В. Борисов И. С. Мамаев О. А. Хрусталев Издание осуществлено при финансовой поддержке Физико- технологического института «ФТИАН» и Московского государственного университета им. М. В. Ломоносова Квантовый компьютер и квантовые вычисления. — Ижевск: Ижевская республиканская типография, 1999. 288 стр. Второй выпуск библиотеки «Квантовый компьютер и кван- квантовые вычисления» представляет собой сборник классических работ (Фейнман, Шор и др. ) и новый обзор Ю. И. Манина. Для широкого круга читателей — физиков, математиков, инженеров, интересующихся возможностями создания кван- квантового компьютера и связанными с ним областями науки и техники. Ландауэр. Необратимость и выделение тепла в процессе вычислений 9 Ч. Беннетт. Логическая обратимость вычислений ... 33 П. Бенёв. Квантовомеханические гамильтоновы модели машин Тьюринга 53 Р. Фейнман. Моделирование физики на компьютерах . . 96 Р. Фейнман. Квантовомеханические компьютеры ... . 125 Д. Дойч. Квантовая теория, принцип Чёрча —Тьюринга и универсальный квантовый компьютер 157 Д. Дойч, Р. Джозса. Быстрое решение задач с помощью квантовых вычислений 190 П. Шор. Полиномиальные по времени алгоритмы разло- разложения числа на простые множители и нахождения дискрет- дискретного логарифма для квантового компьютера 200 Ю. И. Манин. Классическое вычисление, квантовое вы- вычисление и факторизация Шора 248 ФИЗИКИ УЧАТ КОМПЬЮТЕР СЧИТАТЬ ПО-НОВОМУ Вплоть до XIX века, несмотря на отдельные гениальные предви- предвидения вычисления было принято считать чисто мыслительным процес- процессом, и говорить, например, о рассеянии энергии при вычислениях на первый взгляд было столь же экстравагантно, как о термодинамике пя- пяти чувств. Однако, наш язык сохранил память о временах, когда вычисления были тесно связаны с физикой. Так, например, слово «пять» тесно свя- связано с понятиями, имеющими вполне определенный физический смысл, например, «пясть» — «пять косточек ... меж пальцев и запястья», или «пядь» — протяжение меж большого и указательного перстов, растяну- растянутых в плоскости» [1]. Можно сказать, что десятеричная система, которая совсем недав- недавно считалась «искони принятой», появилась в результате физических экспериментов. Связанная с десятеричной системой удобная формулировка про- процесса вычисления нашла, среди прочего, непосредственное физическое применение: уже в XVII веке Паскаль изобрел компьютер. Пока чело- человечество считало не слишком много, различного типа счетные машины рассматривались всего лишь как удобные в быту аппараты.