Цифровой журнал «Компьютерра» 2013 № 16 (169) (Журнал «Компьютерра») - страница 63
Несмотря на скромные успехи, квантовые вычисления обсуждают уже третий десяток лет, и интерес к ним не падает. Наоборот, в последнее время о них говорят особенно много. Квантовые компьютеры всё чаще упоминают в новостях, не имеющих прямого отношения к науке.
Аналитическая компания Gartner включила их в список перспективных технологий, которые «выстрелят» в ближайшие десять лет. Основатели компании Parallels, видимо, разделяют это мнение, потому что несколько месяцев назад основали венчурный фонд, который будет инвестировать в развитие квантовых технологий. Тем временем Google и Lockheed Martin тратят миллионы на устройства, использующие для работы квантовые эффекты. Как говорил Винни Пух, это «ж-ж-ж» неспроста!
И квантовые, и классические компьютеры обрабатывают данные, которые закодированы единицами и нулями. Разница в том, что в классическом компьютере значение каждого бита всегда известно. Значение кубитов — элементов для хранения информации, из которых состоит квантовый компьютер, может быть неопределённым и соответствовать сразу и единице, и нулю, причём с различной вероятностью для того и другого.
Во время работы квантового компьютера отдельные кубиты связаны между собой эффектом квантовой запутанности (entanglement). Несколько связанных кубитов с неопределённым значением содержат не одно число, а все возможные числа, умещающиеся в ячейке такой разрядности. Иными словами, квантовый компьютер одновременно рассматривает все решения задачи, и правильные, и ошибочные.
Проблема заключается в том, что при считывании информации неопределённость исчезает. Вместо бесчисленного множества решений, которые только что содержал квантовый компьютер, остаётся только одно, причём не самое верное, а первое попавшееся. Чтобы от квантового компьютера была какая-то польза, ненужные варианты нужно заранее отсеять.
Это делают с помощью квантовых алгоритмов, которые состоят из специальных операций, влияющих на кубиты. Ассоциация с компьютерными программами, которую, возможно, вызовет слово «алгоритм», не особенно точна. Квантовые алгоритмы совсем не похожи на программы. У них куда больше общего с логическими схемами, состоящими из вентилей И, ИЛИ и НЕ, только вместо булевой алгебры они используют квантовую логику.
В 1994 году математик Питер Шор придумал первый квантовый алгоритм, у которого потенциально может быть практическое применение. Алгоритм Шора предназначен для факторизации чисел, то есть разложения их на простые множители. Именно его работоспособность проверял квантовый компьютер, раскладывавший на множители число 15.