Научно-исследовательская работа на кафедре сапр спбгэту «лэти»

Отступление. Выдающийся математик Д. Гильберт на Всемирном математическом конгрессе в Париже в августе 1900 г. сделал свой знаменитый доклад. В нём он сформулировал 23 фундаментальные математические проблемы. Одна из них – 23-ая в списке Гильберта – формулируется следующим образом: «Существует ли "механическая" процедура (механическая – в смысле алгоритмическая – прим.), которую можно выполнить по шагам любому человеку или прибору, дающая на любое математическое утверждение ответ: верно оно или ложно?». Проблему решили в 30-х гг. независимо друг от друга двое учёных и ответили на вопрос Гильберта отрицательно. Один из них – австрийский математик Курт Гензель, другой – известный английский математик Алан Тьюринг. Он разработал абстрактную (гипотетическую) машину именно для того, чтобы решить эту проблему. «Машина Тьюринга» чисто умозрительная механическая машина, которая считывает посимвольно информацию с некоей потенциально бесконечной ленты и обрабатывает её по определенной схеме в зависимости от считанного символа [13].
Именно эта машина и основанные на ней вычисления, исследованные Тьюрингом, положили начало математической теории вычислений. Существует тезис Чёрча-Тьюринга, согласно которому любая алгоритмическая процедура может быть выполнена на этой машине. В этом смысле машина Тьюринга эквивалентна любому современному компьютеру. Но в контексте нашего разговора важно, что это чисто «механическая» процедура. Это исключительно математический подход к компьютингу. С его помощью впервые было показано, что к теории вычислений можно подходить чисто математически, забывая, что любой компьютер – это физический прибор.
Быстродействие компьютеров в течение последних десятилетий растёт впечатляющими темпами. Однако этот рост имеет свои естественные пределы. Так, вряд ли можно ожидать, что размер транзистора может быть меньше размера атома водорода, а рабочая частота – больше 10¹⁵ Гц (частота атомных переходов). Фактически, проблемы начинаются гораздо раньше (в малых, но ещё не атомных масштабах¹). Некоторое время назад считалось, что квантовые эффекты ставят естественный барьер дальнейшему совершенствованию компьютерной элементной базы.
Квантовые компьютеры (КК) используют совершенно иную модель вычислений, основанную на особом наложении состояний элементарных ячеек информации – квантовых битов, или кубитов. Физики обратили внимание на важность квантовой механики для компьютинга и на преимущество КК над классическими компьютерами уже в начале 1980-х гг. – после работ нобелевского лауреата Р. Фейнмана. Он показал, что ни один классический компьютер не может нормально моделировать квантовую систему: требуется огромный временной ресурс. Основываясь на этом, Фейнман сделал вывод, что для успешного моделирования квантовой системы нужен принципиально новый компьютер, и предложил одну из теоретических моделей будущего КК.