Квантовый компьютер — гипотетическое вычислительное устройство, использующее при работе квантовомеханические эффекты, такие как квантовая суперпозиция и квантовый параллелизм. Предполагается, что это позволит преодолеть ограничения классических компьютеров. Компьютерная технология развивается по пути миниатюризации деталей и удорожания их производства. Микропроцессоры содержат огромное число транзисторов, имеющих размеры в доли микрона. Предполагают, что в 2010-х годах миниатюризация достигнет атомных размеров, где начинают действовать законы квантовой механики. Другой серьезной проблемой является предел быстродействия классических компьютеров, алгоритмы поиска которых не справляются с миллионами записей.
Идею квантового компьютера высказал в 1982 году Ричард Фейнман. Основной единицей квантового компьютера является кубит (qubit, Quantum Bit) — квантовый бит (термин предложен американским физиком Беном Шумахером). Подобно классическому биту информации, кубит теоретически может быть реализован на любой двухуровневой системе, например атоме, который может находиться в двух энергетических состояниях — основном и возбужденном, которые будут соответствовать нулю и единице классического бита. Главное препятствие на пути построения квантового компьютера — вероятностная природа законов квантовой механики. Если классический бит имеет два состояния — 0 и 1, число состояний кубита значительно больше и описывается волновой функцией, которая в одну единицу может иметь большое число значений. Благодаря вероятностной природе волн объем информации, записанной такими q-битами, во много раз превышает тот, который несут обычные биты.
Согласно правилам, сформулированным в 1996 году Д. Дивиченцо, для построения квантовых вычислительных систем необходимо обеспечить высокую степень изоляции системы, точно знать число частиц системы, иметь возможность приводить систему в точно известное начальное состояние и уметь менять состояние системы.
Согласно правилам, сформулированным в 1996 году Д. Дивиченцо, для построения квантовых вычислительных систем необходимо обеспечить высокую степень изоляции системы, точно знать число частиц системы, иметь возможность приводить систему в точно известное начальное состояние и уметь менять состояние системы.
Выполнение этих требований вполне реально с помощью существующих квантовых технологий. Примерно с середины 1980-х годов было предложено несколько различных подходов к созданию квантовых устройств. Так, среди устройств, работающих в радиодиапазоне (длина волны > 1 мм), наибольший практический и научный интерес представляют так называемые атомные и молекулярные генераторы. Иногда их называют «мазеры» (от англ. microwave amplification by stimulated emission of radiation — усиление микроволн с помощью вынужденного излучения). Основное достоинство атомных и молекулярных генераторов — чрезвычайно высокая стабильность частоты излучаемых ими электромагнитных волн. Это свойство используется для точного измерения частоты и времени. Эталоны и стандарты частоты и времени на основе таких генераторов позволили создать атомные и молекулярные часы, стабильность которых в 100 раз выше, чем у обычных кварцевых часов. Другой пример — RISC-процессор на RSFQ-логике (Rapid Single Flux Quantum).
Модель квантового компьютера из двух кубитов на основе сверхпроводимости была построена в 1997 году на молекуле хлороформа группой исследователей из IBM, Массачусетского технологического института и Калифорнийского университета в Беркли.У этой технологии есть существенный недостаток: построение компьютера хотя бы из десятка кубитов потребует охлаждения молекул до температур, всего на тысячные доли градуса отличающихся от абсолютного нуля.
Достоинством квантовых компьютеров является естественный параллелизм квантовых вычислений. За счет параллельной работы с большим числом вариантов квантовому компьютеру необходимо гораздо меньше времени для решения задач. В 1994 году Питер Шор из Bell Laboratories предложил эффективный квантовый алгоритм для сложных вычислений, которые могут использоваться, к примеру, для взламывания систем шифрования информации. Алгоритм Шора позволяет за короткий промежуток времени решать на квантовом компьютере задачи, с которыми не могут справиться современные компьютеры. Коллега Шора по Bell Labs Лов Гровер показал, что квантовые вычисления эффективнее классических не только при взломе шифров, но и при поиске в неупорядоченных базах данных (такая проблема возникает, например, при поиске нужного номера в телефонной книге, где фамилии абонентов расположены произвольным образом). Обычному компьютеру, чтобы найти одну из тысячи несортированных записей в базе данных, придется перебрать все записи, в то время как квантовому компьютеру потребуется сделать примерно 5-6 запросов. Если будут созданы квантовые базы данных, то поиск в них будет производиться намного быстрее, нежели в обычных, а создание квантовых компьютеров с числом кубитов около 100 позволит решать любую задачу, которую раньше за приемлемое время решить было невозможно. К 2007 году наибольший квантовый компьютер был составлен из 7 кубитов. Этого достаточно, чтобы разложить 15 на простые множители 3 и 5.