Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 3

ФИЗИКА ИНФОРМАЦИИческого элементаNA.'iD,17который сохраняет всю входящую информацию:например, элемент Тоффоли(а,Ь,с) ~(1.2)(a,b,cE!Jal\b)яв.;IЯется обратимым трехбитоным элементом. который «инвертирует)> тре­тий бит1 если первые дна приннмают значениев остальных случаях. Если с ---=1,1.и ничего не \tСняетто третий выходящий бит принимаетногическое значение НЕ а И Ь. Заменяя логические элементыNANDэле­ментами ТоффоJJи, ~ы -можем нревратить необратимые вычиСJIСНИЯ в обра­тимые. В приm~ипе эти вычисления могут быть выполнены с ничтожнойдиссипацией.Однако в этом процсссе мы производим много лишней информации.Возникает вопрос: может бытт~, мы всего .1ишь от.ножи;rn энергетическиезатраты и нам придется расплатиться. когда потребуется уничтожить весьэтот хлам.

Обращаясь к этой проблеме, Беннет указал, чw обратимый ком­пьютер может выполнить вычисления до конца, распечатан. ответ (.~огиче­ски обратимая операция). а затем совершить все шаги в обратном нанрав­лении, чтобы вернуться к начальному состояиию. Эта процедура удаляетизбыточную информацию без каких-дибо энергетических :щтрат.Тогда в щтнципс нам пе нужно 1ратить энергию дшt НЫIЮJmения кы­чис:~ений. Па практике, испот..:1уемыс в настоящее врс.\tя (пеобратимые)комnьютеры рассеивают энер1·ию, во всяком случае на порядки большую,чемkT ln 2на один элемент, поэтому с технической точки зрения предел.Iанд:ауэра не существенен. Но, поскольку вычислительное «же~Iсзо» про­должает сокращаться в размерах, преодоление преде.Jа Лащщуэра можетока.:шться важным д..'lя предотвращения плавления деталей, и тоrда обрати­мые вычисдения могут оказа·Lъся единственной альтернативой.в• Демон1982 гому кМаксвелла.

Идеи Ландауэра и Беннета привели последнегопримирению демона Максвелла со вторым началом термоди­намики. МаксвеJL1 рассматривал газ в ящике, ра:щезенно~ персгоро;(кой надве части: А и В. В перегородке имеется заслонка, которой управдяст де­мон. Наблюдая за молеку71ами, приб.i1Ижаtощимися к заслонке, он пропуска­ет быстрые молеку;ш из А в В, а мед;rенныс ·-из В в А. Следовательно, Аохлаждается, а В нагревается с пренебрежимо малыми затратами работы.Тсило без затрат переходит из хоподной области в горячую, явно нарушаявrорое нача.,,о термодинамики.Решение Беннета состоит в том, что демон должен собирать и хра­нить иuформацию о мoJJcкynax. Ec~m обьем памяти демона ограничеп, тооп не может бесконечно продо:~жать охлаждение га.1а; и конце концов зтаГЛАВА 118информация должна быть удалена. В этот момент мы и рассчитываем­си энергией за достигнутое охлаждение. (Если же демон не уничтожаетсвою запись и.шt мы xornм сделать термодинамический расчет до ее уда­ления, то с записанной ииформацией следует связывать нсi«Jторую энтро­пию.)'Во многом этн идеи были предвосхищены еще в1929году Лео G'ци­лардом - настоящим лионером физики информации'.

В своем анализе де­мона Максвелла Сцилард преДдожил понятне бита информации (само сло­во «б!fш было введено позднее Тъюки) и связал энтропию 1'>.8 = k ln 2с приобретением одного бита (по-видимому, Сцилард не осознавал до концапринцип Лаидаузра, согласно которому неизбежных затрат требует именноуничтожение бита информации).Эти примеры показывают, что работа на стыке физики и информациипородила замечательные результаты, представляющие интерес как для фи­зиков, так и для исследователей в области вЬГiислений.1.2.Квантовая информацияИтак, мы выясни..rш, что «информация материальна» 3 , поэтому поучи­тельно посмотреть, что говорит физика об информации.

В своей основеВселенная является квантово-механической. Как квантовая теория освеща­ет природу информации?Уже на заре квантовой теории доткпо было стать ясно, что в све­те повой физики классические идеи об информации требуют пересмот­ра. Например, щелчки, регистрируемые детектором, который следит зарадиоактивнымисточником,описываютсяистиннаслучайнымпуассо­новским процессом. Напротив, в детерминистской классической динами­ке нет места истинной случайносrn [хотя, :конечно, наведение сложной1Попущрное изложение идей Беннета можно найти в статье Чарльз Г. Беннет, Демоны,днигаrели и иrорое начало термодинамики, В мире науки.NH, 52 (1988), перевод журналаScientific Amcrican.

Всестороннее обсуждение этих вопросов см. такж.е в книге Б. Б. Кадомцев,Дu~~Ш~tика и информация, редакция журнала УФН, М (1999).- Прим ред.2Классичес:ка.и работа Сци.аларда опубликована на немецком языке: L. Szi.lard, Ober dieEntropieverminderung in Einem Thermodynamischen System bei Eingriffen Intelligenter Wesen,Zeitschrift fiir Physik, 53, 84()..-856 (!929); на анrлийсюлwf жзыке стаn.я: L.

Szilard, Оп the Decreaseof Entropy in а Тhermodynamic System Ьу the lntervenlinn of intelligent Beings публиковаласьno меньшей мере трижды (1964, 1983, 2003rт.) см., наnример, Maxwe/IS Demon 2. Entropy,Classical and Quantum InformaJion, Computing, Ed.. Ьу H.S. Leff and A.F. Rex, IoP PuЬlishing,Bristo1, PЬi1ade1phia, (2003) рр. !10-119.- Прим. ред.3Эrот очень емкий 1:езис факmческн предстанляет собой назпание статьи Р.

Ландауэра:R Landaucr, Information is physicai, Phys. Today, Мау, 23·-29 (1991). -Прим ред.1.2. КВЛIIТОВЛЯ ИНФОРМАЦИЯ19(хаотической) системы может быть практически неотличимо от С~Jучай­нот].Более тою, п квантовой теории некоммутирующие наблюдаемые немогут одновременно иметь точно определенные значения (припцип неопре­деленности). Фактически измерение одной наблюдаемой А неизбежно в.::ш­яет на результат последующего измерения наблюдаемой В, есШ:I А и В некоммутируют. Следовательно, процесс получения информации о физиче­ской системе неизбежно возмущает ее состояние.

В классической фи:щксне существует надобного ограничения.Компромисс между получением информации и возмущением состоя­ния системы тесно связан с квантовой случайностью. llocкoJJькy рс·~ультатизмерения несет в себе элемент случайности, мы пе можем извлечь из HCI оинформапию о нача."Iьном состоянии системы.То, чrо получение информации является причиной возмущения, такжесвязано с другим существенным раmичием между квантовой и классиче­ской информацией: квантовую информацию нелыя воспрои:зtJСсти с абсо­лютной точностью (пршщип нсвозможности клонирования, аншlсирован­ный Вутерсом и Зуреком, а также Диксом в1982году). Если бы мы моглис;tелать rочную копию кнантового сос·rояния, то мы могли бы измеритьнаблюдаемую ;щнной копии, не нарушая состояние орю'Инала и отменяятем самым прющин возмущения.

С другой с·юроны, ничrо не мешает намточно копировап~ классическую информацию (приятное свойство, J:ающесвозможность засорять жесткие диски).Эти свойства квантовой информации существенны, по особенно се­рьезный аспект, от.;шчающий квантовую информацию от Юiассической, вы­яснен в работе Джана Белла в1964 году.Он показал, что никакая локальнаятеория скрытых параметров не может воспроизвести предскаэания кванто­вой механики. Согласно Бс;шу, квюi·ювая информация может бып. зако­дирована (и фактически закодирована) в пелскальных корреляциях меж­ду различными час"IЯм:и физической системы, в корреляциях, не имеющихклассического ана.:юга. Я еще вернусь к теореме Бешш в этой .-тсющи, нодетально мы обсудим ее позднее.Изучение квантовой информации как пос;:rедовательной дисциплиныначалось в 1980-х и достигло расцвета в 1990-х гг.

Многие из основныхрезультаrов теории классической информации имеют квантовые аналоги,которые бьыи обнаружены и разработаны н носледнее время. Некоторыеиз них мы обсудим в этом курсе, включая сжатие квантовой информации,пределы классической информации, закодированной в квантовых системах,rrpeдeJIЫ квантовой информации, надежно перссылаемой по квантовому ка­налу с помехами (шумом).ГЛАВА 1201.3.Эффективные кваитовые алгоритмыУчитывая то, что квантовая информация обладает множеством необыч­ных свойств, можно было ожидать, что квантовая теория окажет 1-:лубо:коевлияние на наше nонимание вычислений. Но то, чrо это действитеJТhно так,для многих из нас явилось как гром среди ясного неба, произведенный Пи­тером Шором в апреле1994года [специалист по вычислительной техникеАТ&Т (Америкав Телефон знл Телеграф) и выпускник КАЛТЕХа].

Шорноказал. что, по крайней мере в принципе, квантовый компьютер может1•эффективно факторизоваТЪ большое числоФакторизация (поиск простых множителей составного числа) являетсяпримерам трудно разрешимой задачи, обладающей следующими свойства­ми:Найденное решекие можно легко проверить.Но найти эrо решение сложно.То есть, есJШ р иq --большие простые числа, произведениеn = pqможет быть вычиснено быстро (необходимое число элементарных опера­ций примерно равноlog2 р log2 q). Но при заданном n найти р и q оченьсложм.

Время, необходимое для поиска множителей, твердо считается (хо­тя зто никогда не было доказано) суперполнномиальным поlog n.То ес1ъс ростом n необходимое время растет, как минимум, быстрее любой степе­ни log n. Наиболее известный алгоритм факторизации («решето числовогоПОЛЮ>) требуетtiшe се ехр [c(ln n) 1 1 3 (\п ln n )213 ],(1.3)где с= (64/9) 113 ~ 1,9. Текущее состояние дел таково, что 65-разрядныемножитс:ш 130-разрядноm числа могут быть най;\еRы в течение одноruмесяца сетью сотен процессоров. Используя зто для оценки ирефакторав уравнении(1.3), мы найдем, что факторизация 400-разрядного числа по­10 10 лет, что равно возрасту Вселенной. Итак, даже с учетом·гребовала бысущественного развития технологии, факторизация 400-разрядного числав ближайшее время останется недоступной.Проблема факгоризацни интересна с точки зрения теории сложности,как пример задачи, которая считается трудно разрешимой; то есть змачи,1Полная версия стат1.и: Р.

Shor, PoJinomial-Time Algorithms for Prime Factorizabon andDiscrete Logarithms onаQuantum Computer, SIAM J. on Compttting, 26, 1484 (1997);pycciGiйперевод в сборнике статей Кваитовый t<аМпЬютер и квантовые вычисления под ред. В.А.Садовничего, Ижевск, РХД(1999).-При.м. ред.1.4.21Квлнтовля сложностькоторая не может быть решена 3а время, полиномиально зависящее от д:tи­ны входящего сигнала, в .;:J.анном случае отlog n.Она также имеет и прак­тическое значение, носкольку сложное1ъ факгоризации лежит в основе си­стем шифрования с открытым ключом, например, ширОI\."0 используемойсхемы RSA 1•Новый воппующий результат, по.;rученный Шорам, состоит в rом, чтоквантовый компьютер мо~ет выполнять факторизацию за полиномиальноевремя, например, за щiемя O[(ln n) 1 j.