Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Как работает этот протокол? Предположим, Алиса хочет передать Бобу |ψ〉 = α|0〉 + β|1〉. Тогда первое, что она делает, это применяет функцию «управляемой инверсии» от |ψ〉 к своей половине ЭПР-пары. В результате она получает:

Далее Алиса применяет вентиль Адамара к своему первому кубиту (тому, что первоначально был |ψ〉). Получается состояние

Наконец, Алиса измеряет оба своих кубита в базисе {|0〉, |1〉} и высылает результат Бобу. Обратите внимание: каким бы ни был |ψ〉, Алиса увидит каждый из четырех возможных исходов (00, 01, 10 и 11) с вероятностью 1/4. Более того, если она видит 00, то состояние Боба равно α|0〉 + β|1〉, если она видит 01, его состояние равно β|0〉 + α|1〉, если 10 — его состояние α|0〉 — β|1〉, и если она видит 11, то состояние Боба равно β|0〉 — α|1〉. Следовательно, после получения от Алисы двух классических битов Боб точно знает, какие «поправки» внести, чтобы восстановить первоначальное состояние α|0〉 + β|1〉.

Два принципиальных момента: во-первых, здесь нет никакой мгновенной связи. Чтобы телепортировать |ψ〉, необходимо передать Бобу два классических бита от Алисы, и эти биты могут перемещаться не быстрее скорости света. Во-вторых, что еще интереснее, здесь нет нарушения теоремы о запрете клонирования. Чтобы телепортировать |ψ〉 Бобу, Алисе пришлось измерить свой экземпляр |ψ〉 и таким образом узнать, какие классические биты ему передавать, — а измерение неизбежно разрушило экземпляр Алисы. Может ли существовать какой-то более хитроумный протокол телепортации, который воспроизвел бы |ψ〉 на стороне Боба, но оставил бы и экземпляр |ψ〉 на стороне Алисы нетронутым? Я утверждаю, что ответ: нет. Что внушает мне такую уверенность? Ну конечно, теорема о запрете клонирования!

Дополнительная литература

Прочтите ставшую уже классической статью[65] Люсьена Харди о «выводе» квантовой механики, достаточно близкую по логике изложения к тому, что я говорил, но гораздо, гораздо более серьезную и тщательно проработанную. Или, если хотите познакомиться с более новым и иным по логике выводом, прочтите статью Чирибеллы с соавторами[66], где квантовая механика «выводится» как уникальная теория, удовлетворяющая (1) различным разумным на первый взгляд аксиомам, которым удовлетворяет и классическая теория вероятностей, и (2) аксиоме о том, что каждое «смешанное состояние», описанное теорией, можно получить, если начать с более широкого «чистого состояния», а затем вычеркнуть его часть. (Еще в 1930-е гг. Шрёдингер привлек внимание к последней аксиоме как к принципиально важному и отличительному свойству квантовой механики. Признаюсь, правда, что мне интуитивно не понятно, чем мир, удовлетворяющий этой конкретной аксиоме «очищения», может быть лучше, чем мир, подчиняющийся обобщенной теории вероятностей для второй нормы!) Наконец, стоит прочесть практически все, что написал Крис Фукс[67], особенно его статью в соавторстве с Кейвзом и Шаком[68], где говорится о том, почему амплитуды должны быть комплексными числами, а не действительными и не кватернионами.

10. Квантовые вычисления

Ну хорошо, теперь у нас есть прекрасная теория квантовой механики и, возможно, еще более прекрасная теория вычислительной сложности. Ясно, что, имея две теории такой невероятной красоты, мы не можем оставить их обе в одиночестве — мы просто обязаны их познакомить и посмотреть, что из этого выйдет.

Это приводит нас к классу BQP — квантовому с ограниченной ошибкой за полиномиальное время. В главе 7 мы говорили о классе BPP, вероятностном с ограниченной ошибкой за полиномиальное время. Если говорить неформально, BPP — это класс вычислительных задач, эффективно решаемых в физическом мире в том случае, если классическая физика верна. Теперь мы задаемся вопросом о том, какие задачи эффективно решаемы в том же физическом мире, если (что представляется более вероятным) верна квантовая физика.

Меня поражает от факт, что сколько-нибудь серьезно этот вопрос додумались задать только в 1990-е годы, при том что все инструменты для его рассмотрения были в наличии уже в 1960-х, если не раньше. Поневоле начинаешь задумываться: какие очевидные на первый взгляд вопросы никто не додумывается задать сегодня?

Итак, как мы определяем BQP? Ну, существует четыре момента, о которых нам следует позаботиться.

1. Инициализация. Мы говорим, что у нас есть система, состоящая из n квантовых битов (или кубитов), и все они инициализированы в некоторое простое, легкое и удобное в подготовке состояние. Для удобства мы обычно считаем его «вычислительным базисным состоянием», хотя позже имеет смысл подумать о более мягком подходе. В частности, если входная строка равна x, то начальное состояние будет иметь вид |x〉|0…0〉, то есть |x〉 плюс столько дополнительных кубитов, сколько мы хотим инициализировать в нулевом состоянии.

2. Преобразования. В любой момент состояние нашего компьютера будет суперпозицией по всем 2p(n) p(n) — битным строкам, где p — некоторый полином от n переменных:

Но какие операции мы можем использовать для преобразования одного состояния-суперпозиции в другое? Поскольку речь идет о квантовой механике, это должны быть унитарные преобразования, но какие именно? Для любой булевой функции f:{0, 1}n → {0, 1} существует какое-то унитарное преобразование, которое мгновенно вычислит для нас эту функцию. К примеру, мы могли бы взять произвольное унитарное преобразование, которое отображает каждое базисное состояние вида |x〉|0〉 на |x〉|f(x) 〉.

Но, конечно, для большинства функций f мы не в состоянии применить это преобразование эффективно. В точности по аналогии с классическими вычислениями, где нас интересуют только те схемы, которые можно построить из небольшого числа логических элементов и, или и не, здесь нас интересуют только те унитарные преобразования, которые можно построить из небольшого числа квантовых вентилей. Под «квантовым вентилем» я буду просто иметь в виду унитарное преобразование, действующее на небольшое число кубитов, скажем один, два или три.

Ну хорошо, рассмотрим примеры квантовых вентилей. Один известный пример — вентиль Адамара, действующий на единичный кубит следующим образом:

Еще один пример — вентиль Тоффоли, который действует на три кубита так:

Или, если сказать словами, вентиль Тоффоли меняет третий кубит на противоположный в том и только том случае, если оба первых кубита равны 1. Обратите внимание: вентиль Тоффоли имеет смысл и в классических компьютерах.

Далее, Ши[69] показал, что Тоффоли и Адамар уже составляют универсальный