До сегодняшнего дня существовал только 17-ти кубитный компьютер, разработанный IBM. Авторы новой работы улучшили результат в три раза, создав компьютер на холодных атомах, удерживаемых оптическими пинцетами (о различиях этих двух машин можно узнать из ответа NEKTO V-PALTO) .
Число кубитов в квантовом компьютере так же важно, как и число битов в обычном ЭВМ. Только вот при измерении бита мы всегда получим один и тот же результат — «ноль» или «единицу», а измерение одинаково приготовленных кубитов будет с некоторой вероятностью давать и «ноль», и «единицу» — до измерения кубит будет одновременно и «нулем» и «единицей». Как говорят физики — он будет в суперпозиции двух состояний.
Такая необычная единица данных позволяет упростить решение многих вычислительных задач, в особенности — связанных с перебором.
Один из самых простых примеров — алгоритм Дойча. Предположим, у вас есть функция, которая может иметь значение ноль или единица, в зависимости от аргумента. Аргумент тоже может быть нулем или единицей. Всего существует четыре таких простых функции. Чтобы узнать, всегда ли эта функция выдает строго ноль или строго единицу, классическому алгоритму потребуется дважды ее вычислить. Для квантового алгоритма хватит одного вычисления.
Другой пример — алгоритм Шора для разложения натурального числа на простые множители. Классические алгоритмы могут сделать это только полным перебором, причем с ростом количества знаков в раскладываемом натуральном числе количество операций растет экспоненциально (условно, каждый знак увеличивает время расчета в 10 раз). Квантовому алгоритму требуется лишь полиномиальное время (полином от числа знаков в числе).
Есть еще несколько примеров, связанных с перебором, которые быстро решаются с помощью квантовых алгоритмов. Основной прирост производительности в таких задачах связан именно с существованием кубитов в суперпозиции состояний. Интересно, что в ряде случаев в алгоритм можно вводить суперпозицию порядка вычислений. То есть, например, одновременно проводить над числом умножение, а потом возведение в степень, и возведение в степень, а потом умножение. Такие операции позволяют выяснить за одно действие, есть ли разница между порядком выполнения двух операций (A, затем B, и B, затем A).
Зато такие задачи, как сложение двух натуральных чисел (например, 2+2), для квантового компьютера оказываются совсем не тривиальными.
Подробнее научно-популярным языком о квантовых компьютерах здесь.
Для более глубокого освоения этой темы можно прочитать обзорную статью Э. Риффеля, В. Полака "Основы квантовых вычислений". Освоив эту работу, вы сможете читать научные статьи по квантовым вычислениям.
Следующая литература будет полезна не только в познавательном, но и в историческом плане:
1) Ю. И. Манин. Вычислимое и невычислимое
2) И. фон Нейман. Математические основы квантовой механики
3) Р. Фейнман. Моделирование физики на компьютерах
4) Р. Фейнман. Квантово-механические компьютеры