Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 4
Описание файла
PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Таким обра1ом, ес:ш бы у нас былквантовый компьютер, который мог бы факторнзовать 130-разрядное числоза один месяц (конечно, у насcro нет,пока по крайней мере!), то, слс,1уя алгоритму Шора, оп смог бы факторизоватЪ 400-разрядное число менее, чемза три года. Чем сложнее задача, тем большим преимушеством обиадаетквантовый компьютер.Результат Шора нробудил мой собственный интерес к квантовой информации (если бы не Шор, не ду\-ШЮ, чrо я преподавал бы зтот курс).Очень прия·nrо размыш.1Ять о проблемах, требующих знания теории сложности, квантовой теории и нрик.:шдных наук.1.4.Квантовая сложностьКонечно, работа Шора имела серьезную предысторию.
На то, чrо квантовая система может выполнять вычисления, бьшо впервые явно указаноПолем Бениоффом и независимо Ричардом Фейнманом в 1982 году 2 В известном смысле интерес к этой nроблемс был понятен, принимая по внимание неуклонную тенденцию миниатюризации в микросхемотехнике. Еслизта тендеющя бул;ет продо.:Iжаться, мы неизбежно приблизимся к режиму, в ко·юром квантоnая теория исключительно важна для функционирования вычисшпе~1ьных устройств. Возможно, это набтодение обеснечиnанекоторую мотивацию после работы Бениоффа. Однако r;швная мотивапияФейнмана бьша совершенно иной и весьма интересной. Чтобы понять точку зрения Фейнмана, необходимо более точное математическое описаниеквантовой информации и квантовых вычислений.НедеJшмой С)\ИI-IИцей ю1ассичсской информации яв:mется бит: объект,1. Соответству-который может принимать .JIIOбoe из двух значений: О или1R.
Rivest, А. Shamir, L. Adleman.- При.м. peiJ.Р. Benioff, Quantum-Mechanical Hamiltonian Mode]s of Turing Machines, J. Stal Phys., 29,515, (1982); R.P. Feynman, Simulation Physics \\'ith Computers Int J. Theor. Phys., 21, 467 (1982);2русские пе~uоды в сборнике статей Квантовый ко.мпьютер и квантовые вычисления под ред.В.А. Садовничеrо, Ижевск, РХ.Д (1999). Нпервые идея квантовых uычислеiiИЙ f:iыла выдвинутаЮ.И. Маяиным имtщно в связи с большей информационной кмкостью квантовых систем. См.Ю.И. Мании BычurJlUМne и 11е6uчислимое, Сов.
Радио, М.,1980.llpuм. ред.Г.1АВА 122ющая спишща кваитовой информат,иикиантовый fiит ишi 1\.убшп. Куби1нрсдставляет собой вектор в двумерном кшшлсксном векторном пространстве со скалярным (внутренним) нроизведением; и3 уважения к к:шссическому биту бу,т~ем на1ывать элементы ортонормированноrо базиса в этомпространстве !О) и[1). То та нор,щрованный вектор может бытr, прсжтав-лен в виде:iW)~ а.!О)+ Ь[l),fnl 2 + IЬI2~ 1,(1.4)г;J;е а, Ь Е С. Мы можем выполнить иэ.\.fсренис, которое проецируетна базис\0), \1).Ре3уОJыат такого И3мерения не е~с·гсрминирован)1/-·)- вероятность тонJ, что в итоге мы получим IO), равна ia.l 2, а вероятность ТОПJ, чтомы получим \1), равна [Ь\ 2 .Квантовое состояние i'v' кубитов можно изобр<L1ить вектором в 2N -мерном 11ространствс.
В качестве орrонормированного бюиса н '}ТОМ пространстве можно выбрать состояния, в которых каждый кубит имеет определеннос значениеjO)ИШIjl).Их можно обо.1начип. J(Jюичными последоватсльностя!\ш чисел, тюсими как:IOllJOOJa ...10о1).( 1. 5)Произво.JЫIЫЙ норМИJЮВанный вектор разлагается в данном базисе как2.v -1(1 .6):.t=')где кажл;ой двоичной nосJIСдовательности сопоставяется номер, равный соответствующему ей числу в двоичной системе счисления и измсняющийсяв преде.1ах от О до 2N ~ 1.
Здесь величины а.хкомплексные числа, удовлетворяющие условию L \ах \2 = 1. Если мы измеряем все lvr кубитов,хпроспируя каждый из них на базис{10), \1)},то вероятность получениярезультата [х) равна \а.х\ 2 ,Итак,квантовоевычис.1ение можно описать СJJСдующим обрюом ..Мы собираемN кубитов и готовим их в стющартном нача.iiьном состоянии, таком как \0)\0)fO) · · ·IO) или fx ~ 0) . .Затем применяем к ним унитарное нреобраюпание U.
(Преобра.1ование U сконструировано как произНСitСнис стаJТJtартных квантовых логических веNmилей, унитарных преобразований, которые действуют лишь на неско.1ько кубитов отювременно).После применениябазис{\0), fl)}.Uмы измеряс:\1 все :кубиты путем проецирования наИтогом измерения явСJястся результат вычисления.
Такимобразом, окончательным результатом является классическая информация,которая может быть распечатана на Шiсте бумаги и онубникована в журнале «Фи:шкл Ревью>>(Physical Revicw).1.4.КВАlЛОВАЯ СJIОЖНОС1Ъ23Обратите внимание па то, что реализованный квантовым компьютером алгорил.1 является вероятностныА-1. То есть мы можем выполнить однуи 1у же ОIJсрацию /J:rшжды и, вследспше случайности процесса квантовогоизмерения, по.~ить разные результаты. Фактически, квантовый алmритм1юрождает распределение вероятностей возможных результаrов. (В дейСТ!ШТС."lьности алгоритм фаiС10ризации Шара не гарантирует успеха в получении простых множите.Jей; он достигает цели лишь с определенной вероятностью.
Однако этого-достаточно, цоскольку легко проверить, верны JШнайденные множители).Из ;щнного описания должно быть ясно, что квантовый компьютер,в отличие от классического, п:олжен бу;(ет работать в соответствии с ЩJУгими физическими принципами. Тем не менее он не сможет сделать ничего сверх тот, что может де.'JаТЬ к.rшссический компьютер. Классическиекомпьютеры могут храню_·,, векторы, враща·п~ их и мо;~елироnап~ процессквантового и.·змерения, просцируя векторы на юаимно ортогона.11ьпые оси.То есп. rстассичсский компьютер, несомненно, может скопь угодно точнои-митировать (моделировать) квантовый компьютер. Паше представлениео том, что яшrяется вычислимым, не зависит от того, попьзуемся мы классическим или квантоным компьютером.Но мы должны считаться с тем, как много времени занимает это моде.тирование.
Предположим, у нас есп. компьютер, который оперирует с умеренным количеслюм кубитов, например,N = 100.Тогда, чтобы представить типичное квантшюе состояние компьютера, нам приnтось бы запи1030сать 2л· = 2 с'""' 10комплексных чисел! Ни один из суш,ествуiОщих ИJШбулущнх !tифровых компьютеров не сможет сделать этого. А выпшrnениенроизнолыюго поворота вектора в пространстве размерности 10 30 находится ;щлеко за прелелами вычислителъных способностей moбoro мыслимогоклассического компьютера.(Конечно, N классических битов тоже могут принимать2N возможных :шачсний.
Но полное описание конфигурации каждого из них оченьпросто-::.то ~1иоичная пос~Jедоватепьность дт~ной I\Г. Квантовая информация ОТJшчается тем, что полное описание даже одной типичной конфигурации/'./ кубиrов очень сдожно).Итак, классический компыотер действительно может имитироватьквантовый, но с ростом числа кубитов1Vимитация становится крайненезффективной. Квантовая механика сложна (с точки зрения вычиСJJений), нотому что мы цолжны работать с огромными матрицами - гильберrовu прос1ранство слишком велико.
Это наблю;Jение припело Фейнманак прсл:nоложению, что квантовый компьютер может оказаться способнымиыпо:щять определенные '~адания, недосяrаемые для шобого возможногоГЛАВА241к..:1ассического компьютера (кнанrовому компьютеру не нужно моделировать самого себя!). Похоже, что результат Шора по~держиnает зту точкузрения.Так ;rn неизбежен этот вывод? В конце концов, моделированис должнопредоставить способ определения вероятностей всех возможных результатов окончательного и..1мерения. При классическом моделировании совсемне обя:~<iтелыю елелопать полному описанию кванrовоrо состоянияJ'vrкубитов.
Нас впоШiе устроил бы классический верояттюстный алгоритм, результаты каюрого не определяются однозначно входом, а возникают в соответствии с тем распредедением верояпюстей, которое генерируется квантовым вычислением. Мы моr.1и бы рассчитывать на выпоJПIСН11С ликалыюгамщелирования, при котором каждый кубит в каждый момент времени имеет опредепенное зпачепис, а каждый квантовый вентиm. может действоватьна кубиты ра:~Шiчными возможны.ми снособами, которые определяются генератором (псевдо-) случайных чисел. Такое моделирование было бы гораздо проще, чем описание эвоmоции вектора в экспопенциалыю огромномпространстве.О;щако Rывод теоремы Джона Белла однозначно говорит о том, чтотакое моделирование осуществить невозможно: не существует лттлышговероятоостн.ого алгоритма, способного воспроизводить результаты квантовой механики.
Таким образом, хотя доказательство этого отсутствует, кажется весьма правдоподобным, что моделирование квантоRОJ""О компьютераявляется очень сложной 'Ш;щчей для любого классическо1 о компьютера.Чтобы :тучше понять, почему математическое описание квантовой информющи с необходимостью такое СJюжнос, представим квантовую систему ЗN кубито11 (N1), состоящую из трех ПОI(Систс" по N кубитов»каждая (называемых подсистемами( 1), (2)и(3)).Мы случайным образомвыбираем квантовое состояние 3N кубитов, а затем разделяем три подсистемы, отllравпяя (!)в Санта-Барбару, (3)- в Сан-ДИего, в то время как (2)остается в Пасадене.
ТеперЕ:. мы бы хотели щюизнссти некоторые измерения, чтобы как можно больше узнать о квантовом состоянии. Чтобы облеr~шть себе за.л;ачу, предста.вим, что мы имеем огромное количество коnийсостояния системы, поэтому мы можем измерить любую из них, а также какие УI"<щно наблюдаемые 1 . Но при одном услою-ш: нам разрешеновыпо.··:шять измерения лишь внутри одной из подсистем ~ коллективныеизмерения, снимающие границы между подсистемами, запрещены. Тоглдд.""IЯ типичного состояния системы13Nкубитов наши измерения почти ни-Мы не можем сделать kОПИИ неизвестноrо кванrовоrо С<lстояния сами, но можем попросить приятслк приготовить множество идентичных ю:JПИЙ состояния (он :но может, потому чтознает, что делап.) и не сообщать нам о том, что оп c.JeJJaл.] .5.25КВ."'-НТUВЫЙ 11АРАЛЛЕЛИ3Мчего о нем не скажу~: Почти вся информация, отmrчающая одно состояние от другого, сол;ержится в иелокальных КfJрреляциях между результатами измерений в подсистемах (1), (2) и (3).
Зто и есть те самые нелокальные корреляции, коrорые Белл считал важнейшей частью физическогоописания.Мы увидим, что объем информации можно определить количественнос помощью энтропии (большая энтропия подразумевает незначительнуюинформацию). Если мы. выбираем сос:тояние ЗN кубитов случайно, то почти всеrда нахолим, что энтропия каждой подсистемы очень близка кS SO' N- г(N 11 !,ре:<ультат, пюученный Доном Пей,lЖСМ.
Здесь(1.7)N· максимальновозможное значение энтропии. соответствующее случаю, в котором ПО!\ СИстема вообще не несет доступной информапии. Таким образом, рассматривая каж;(уiО подсистему независи:мо, при большомNмы можем иметь ;~оступ лишьк экспоненциалыю малому количеству информат,ии.Тосетьизмерениядаюточеньмалоинформации,еслимынеучитываем корреляции рс1улыатов, полученных в Сан-Диего, Пасаденеи Санта-Барбаре.llтерминологии, которой я пользуюсь, измерение коррелщии считается «комсктивным» измерением (даже если бы фактическионо бьшо выполнено ~кспсриментаmrами, которые наблюдали ра:-шые части одной и той же копии состояния, а ]атем созвонились, чтобы сравнитьсвои резул~таты).