По поводу недавнего обсуждения в подкасте Радио-T и комментариях квантового компьютера.
Интересный пост с объяснениями принципов работы квантового компьютера написал ЖЖ пользователь ygam (кстати очень интересный журнал сам по себе – рекомендую) –получилось, по крайней мере, значительно понятней чем в Википедии.
Вот этот пост:

По заявкам трудящихся, в двух словах попытаюсь объяснить, что такое квантовый компьютер. Постараюсь не требовать знания никакой математики кроме комплексных чисел и линейной алгебры.

Представьте себе стальную пластину с двумя прорезями метр друг от друга, и пистолет, который может выстрелить в направлении пластины так, чтобы пуля прошла через одну из прорезей.

Эта система описывается двумя неотрицательными вещественными числами, сумма которых равняется единице — вероятностью того, что пуля пройдет через левую прорезь и через правую прорезь. Запишем их в виде столбцового вектора. Вероятность того, что пуля попадет в мишень за экраном, равняется произведению некоего строкового вектора на столбцовый вектор вероятностей.

Теперь представьте себе экран с двумя прорезями микрон друг от друга, и монохромную вспышку, лучи от которой проходят через обе прорези. Так, как свет — это волна, за экраном мы будем наблюдать интерференцию. В некоторых местах интенсивность света будет больше, чем можно было бы предсказать из интенсивности света в прорезях; там происходит конструктивная интерференция; в некоторых — меньше; там происходит деструктивная интерференция. Простая формула векторного умножения интенсивностей со светом не работает, как с пулями и вероятностями. Это показывает, что для описания системы недостаточно дать интенсивность света в двух прорезях (т.е. долю световой энергии вспышки, прошедшей через экран, которая прошла через левую прорезь и через правую прорезь); нужны амплитуды — комплексные числа, квадраты модулeй которых являются интенсивностями в двух прорезях. Сумма квадратов их модулей должна равняться единице, как сумма вероятностей для пули.

Луи де Бройль, Вернер Гейзенберг и другие физики первой половины прошлого века открыли, что предметы материального мира имеют свойства, средние между свойствами частицы вроде пули и волны вроде света. Если экран с прорезями — это кристаллическая решетка никеля, вместо пистолета у нас катод, а вместо пуль электроны, то вместо столбцового вектора вещественных вероятностей, сумма элементов которого — единица, у нас есть столбцовый вектор комплексных амплитуд, сумма квадратов модулей элементов которого — единица. Вероятность того, что электрон попадет на датчик за экраном — это комплексно-сопряженный и транспонированный вектор амплитуд, умноженный на некую эрмитову матрицу, и еще раз умноженный на сам вектор амплитуд. Эта матрица может быть диагональной — но в этом случае теряется весь смысл использования амплитуд вместо вероятностей; электроны становятся похожими на пули. Интереснее ситуация, когда какие-то недиагональные элементы матрицы не равны нулю, и означают интерференцию между возможными состояниями (например, проходом электрона через левую и через правую щель). Квантовая механика говорит нам, что в общем случае, она недиагональна, но по мере перехода из микромира в макромир шум взаимодействия с множеством объектов стирает элементы вне диагонали, так что для пуль амплитуды не нужны, и можно обойтись вероятностями. Это называется декогеренция; именно это происходит при измерении микроскопических величин макроскопическими инструментами.

Вопрос, что это значит, как электрон может пройти через две прорези одновременно и интерферировать сам с собой, занимает физиков и философов с тех пор, как квантовую механику сформулировали в 1930е годы. Подсоединим к датчику усилитель, соленоид и пистолет, направленный на кошку. Что такое живая или мертвая кошка с определенной вероятностью — понятно; кошка либо жива, либо мертва, мы просто это знаем не наверняка, а с некоторой степенью уверенности. Но живая или мертвая кошка с определенной комплексной амплитудой выходит за рамки здавого смысла. У науки не только нет ответа на этот вопрос, но этот вопрос выходит за рамки компетенции науки. Наука только знает, что мы имеем дело действительно с амплитудами, а не с вероятностями.

Если пистолет выстреливает в прорези в пластине, он сообщает системе за пластиной один бит информации — через левую прорезь прошла пуля или через правую. Если катод пускает электрон в никель, он сообщает системе за кристаллом один квантовый бит или кубит (qubit) квантовой информации — через левую прорезь прошел электрон или через правую. Пусть у нас есть сто таких катодов; у 2100 ≈ 1030 начальных состояний есть столько же амплитуд. Подвергнем нашу систему внешнему воздействию — магнитным полям, микроволнам. Возможно, мы сделаем так, чтобы «интересные» состояния конструктивно интерферировали, а «неинтересные» деструктивно. Потом мы измерим состояние системы; с высокой вероятностью оно будет «интересным». Если мы можем распознать «интересное» состояние, но не знаем его, то мы его узнаем. Мы построили квантовый компьютер.

Зачем нужен квантовый компьютер? Он не может вычислить ничего такого, чего не может вычислить классический, т.е. не-квантовый компьютер. Боги квантовой механики умножают матрицы; классический компьютер прекрасно делает то же самое. А что он может? Он может использовать конструктивную и деструктивную интерференцию для того, чтобы вычислить параллельно то, что классический компьютер должен вычислять последовательно.

В 1992 году Дэвид Дойч и Ричард Йожа придумали алгоритм для задачи про Алису и Боба из предыдущей записи — Боб посылает Алисе все возможные позиции и еще один кубит, Алиса производит над ними некоторые манипуляции и отвечает, а Боб измеряет дополнительный кубит и получает правильный ответ. В 1994 году Питер Шор из Bell Labs открыл квантовый алгоритм разложения целого числа на множители, время работы которого пропорционально кубу количества цифр числа; сейчас неизвестны классические алгоритмы для этой задачи, время работы которых пропорционально любому многочлену от количества цифр числа. Алгоритм Шора можно обобщить для других задач, используя понятия теории групп. В 1996 году Лов Кумар Гровер оттуда же изобрел квантовый алгоритм перебора. Если среди 2n строк из n бит одна удовлетворяет какому-то критерию (например, кодирует маршрут путешествующего коммивояжера короче 1000 километров), то алгоритм перебора на классическом компьютере требует 2n шагов; если мы можем подвергнуть квантовый компьютер воздействию, меняющему знак у амплитуды состояния, соответствующего этой строке, и еще одному воздействию, то после 2n/2 шагов все состояния кроме нашего деструктивно проинтерферируют; измерение даст нам наше состояние. В 2000е годы придумали быстрый квантовый алгоритм для решения уравнения x2 — n*y2 = 1 и еще нескольких математических задач.

Построить не-игрушечный квантовый компьютер пока никто не смог, и в ближайшее время не сможет. Используя параллельные спины триллионов триллионов ядер для кубитов и ядерный магнитный резонанс для измерений, в 2001 году исследователи из IBM и Стэнфорда исполнили алгоритм Шора и разложили на множители число 15. Есть ряд экзотических предложений вроде использования двумерных квазичастиц, являющихся ни фермионами, ни бозонами, а чем-то третьим, со странными топологическими свойствами, но до их осуществления тоже очень далеко. Возможно, даже если не-игрушечный квантовый компьютер построить невозможно, изучение квантовых алгоритмов каким-то образом помогло в изучении классических алгоритмов, и тем самым не было бесполезно, но я недостаточно компетентен, чтобы решить, так это или не так.

Квантовый компьютер