М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 67
Текст из файла (страница 67)
На каждом шаге квантового алгоритма старое состояние полностью заменяется новым; без серьезных изменений в алгоритме невозможно научиться извлекать (нетривиальную) информацию из его промежуточных шагов, так как состояния являются квантовыми. Более того, для получения желаемого результата заключительное измерение должно быть тщательно выбрано, поскольку оно возмущает квантовое состояние. Конечно, алгоритм квантового моделирования можно повторять много раз, чтобы набрать статистику, но желательно, чтобы количество циклов было не более чем полиномиально, Может случиться так, что, несмотря на эффективность моделирующего алгоритма, не удаегся эффективно провести измерение.
Кроме того, существуют гамильтонианы, которые вообще невозможно эффективно смоделировать. Как следует из подразд. 4.5.4, имеются такие унитарные преобразования, что квантовые компьютеры не могут их эффективно аппроксимировать. Следовательно, не для всякого гамильтониана уравнение Шредингера можно эффективно решить на квантовом компьютере-иначе оказалось бы, что любое унитарное преобразование можно эффективно аппроксимировать! Другая трудная (и очень интересная) проблема — моделирование процессов установления равновесия. Система с гамильтонианом Н, находящаяся в контакте с окружающей средой при температуре Т, придет, вообще говоря, к тепловому равновесию в состоянии, известном под названием гиббсовского, р„„„= е и!"эт/Я, где Я = сге н~"эт — обычная нормализация, обеспечивающая равенство Сг(р) = 1.
Процесс установления этого равновесия до сих пор плохо понят, хотя известны некоторые необходимые условия: окружающая среда должна быть обширной, она должна иметь состояния с энергиями, соответствующими собственным состояниям оператора Н, и ее взаимодействие с системой должно быть слабым. Нахождение ры, для произвольных Н и Т является, как правило, экспоненциально трудной задачей, если делать это на классическом компьютере.
Можно ли эффективно решить данную задачу на квантовом компьютере? Пока это неизвестно. 4.7. Моделирование квантовых систем 269 В то же самое время из наших обсуждений следует, что многие интересные квантовые задачи могши эффективно моделироваться на квантовом компьютере, даже при наличии дополнительных условий, которые не охвачены представленными здесь простыми алгоритмами. В частности, к таким условиям относится глобальная симметрия, происходящая из статистики частиц.
В нашем повседневном мире мы привыкли к тому, что можно различать отдельные частицы: можно проследить траектории теннисных мячей на корте, не путая их друг с другом. Такая различимость является общей чертой классических объектов: поскольку положение классической частицы меняется непрерывно, можно узнать ее положение в любой момент и тем самым отличить ее от других частиц. В квантовой механике, однако, так не выходит: проследить точно за движением отдельной частицы невозможно.
Если две частицы различны по сути (например, протон и электрон), то мы можем отличить их, измеряя, скажем, знак нх заряда. Но в случае одинаковых частиц оказывается, что они принципиально неразличимы. Неразличимость частиц налагает ограничения на вектор состояния системы, и эти ограничения проявляются двояким образом.
Из экспериментов известно, что существующие в природе частицы бывают двух типов, известных под названиями «бозоны» и «фермионы». Вектор состояния системы, состоящей из бозонов, не меняется, если поменять местами две частицы, в чем и выражается их неразличимость. В фермионных системах, напротив, при перестановке двух частей вектор состояния меняется на противоположный.
И те и другие системы эффективно моделируются на квантовом компьютере. Подробное объяснение того, как работают эти модели, выходит за рамки книги; достаточно сказать, что делается это довольно бесхитростно. Если начальное состояние не обладает нужной симметрией, его можно симметризовать перед началом работы модели. Операторы, участвующие в модели, могут быть построены таким образом, чтобы сохранять эту симметрию, даже с учетом членов высшего порядка. Читатель, желающий узнать подробнее о таком моделировании, может найти ссылки в разделе «История и дополнительная литература» в конце главы.
Задача 4.1 (вычислимые сдвиги фазы). Пусть т и и — целые положительные числа и у: (О,..., 2™ — Ц -+ (О,..., 2" — 1) — классическая функция перехода из «л-битовых чисел в п-битовые, которую можно обратимо вычислить с помощью Т-элементов Тоффоли, как описано в подрэзд. 3.2.5. Это означает, что функция (х, у) -«(з, у ю Дх)) может быть реализована с использованием Т-элементов Тоффоли. Постройте квантовую схему, с помощью 2Т+ п (или меньше) одно-, двух- и трехкубитовых элементов, которая выполняла бы унитарную операцию, заданную формулой (4.116) )х) -+ ехр (х).
Задача 4 2. Постройте схему глубиной 0(1оя и), реэлизуюшую элемент С" (Х). (Глубиной схемы называют число тактов ее работы; смысл этой задачи в том, 270 Глава 4. Квантовые схемы что при реализации С" (Х) можно заставить много элементов работать парал- лельно.) 1. матрица Н эрматова и ее собственные значения лежат в интервале [О; 2я]; 2.
Н можно записать в виде Н= Ей,д, (4.117) где Ьэ — действительные числа и д пробегает все возможаые и кратные тензорные произведения матриц Паули (1, Х, У, Я); 3. можно реализовать унитарную операцию ехр( — 1йэдЬ) с использованием 0(п) одно- и двухкубитовых операций, если Ь = 1/й, где й — целое положительное число; 4. формула ехр( — 1НЬ) = П ехр( — гйядб) + 0(4" Ь~); (4.118) д справедлива(подразумевается, что матрицы д берутся в каком-то фикси- рованном порядке); 5. справедлива формула У = П схр( — юйэдЬ) + 0(4" Ь). (4.119) 6. можно аппроксимировать У с точностью с ) О, используя 0(п16"/с) одно- и двухкубитовьж унитарных операций.
Задача 4.4 (минимальная конструкция Тоффоли (задача для иссле- дования) . 1. Какое наименьшее количество двухкубитовых элементов требуется для реализации элемента Тоффоли? 2. Какое наименьшее количество однокубитовых элементов и скот необходимо для реализации элемента Тоффоли? 3. Какое должно быть наименьшее количество однокубитовых элементов и элементов «управляемое Я» для реализации элемента Тоффоли? Задача 4.3 (альтернативная конструкция универсальности).
Пусть У— унитарная матрица, действующая на п кубитах, Н = Пп(У). Покажите, что 4.7. Моделирование квантовых систем 271 Задача 4.5 (задача для исследования). Постройте такую последовательность и-кубитовых гамильтонианов (Н„), чтобы для моделирования Н„требовалось суперполиномиальное количество операций. Задача 4.6 (универсальность с предварительным запутыванием). скот и однокубитовые элементы образуют универсальный набор квантовых логических элементов. Покажите, что альтернативный универсальный набор можно составить из однокубитовых унитарных операторов, измерений пары кубитов в базисе Белла и возможности приготавливать произвольные (запутанные) четырехкубитовые состояния.
Краткое содержание главы ° Универсальность. Произвольная и-кубитовая унитарная операция может быть реализована (точно) с помощью однокубитовых элементов и скот. ° 'Универсальность конечного семейства. Элементы Адамара, сдвига фазы, скот и х/8 образуют универсальный для квантовых вычислений набор в том смысле, что произвольная и-кубитовая унитарная операция может быть аппроксимирована с произвольной точностью е ) 0 с помощью схемы, использующей только элементы из этого набора. Если заменить элемент я/8 элементом Тоффоли, то также получится универсальный набор. ° Не каждая унитарная операция может быть эффективно реализована.
Существуют и-кубитовые унитарные операции, для аппроксимации которых с точностью с требуется не менее Й(2" 1о8(1/с)/ 1ок(п)) элементов из любого данного конечного набора. ° Моделирование. Для гамильтониана Н = 2 ьНю являющегося суммой полиномиального количества слагаемых Ню каждое из которых может быть эффективно реализовано с помощью квантовой схемы, на квантовом компьютере можно эффективно моделировать эволюцию е 'и' и аппроксимировать 1ф) = е 'н'~ф(0)), при условии что дано ~ф(0)). История и дополнительная литература Конструкция элементов, о которых шла речь в этой главе, взята из многочисленных источников.
Из статьи Баренко, Беннета, Клива и др.(24] взяты многие конструкции элементов, а также доказательство универсальности набора, состоящего из однокубитовых и скот-элементов. Другой полезный источник идей — статья Бекмана, Чари, Девабхактуни и Прескилла (33). Доступное и по- 272 Глава 4. Квантовые схемы следовательное введение принадлежит ДиВинченцо [125]. То обстоятельство, что измерения можно перенести в конец схемы, было отмечено Гриффитсом и Ниу [163]. Доказательство универсальности двухуровневых элементов принадлежит Реку, Цайлингеру, Бернштейну и Вертани [345].
Универсальность набора из однокубитовых элементов и скот была доказана ДиВинченцо [124]. Универсальный элемент С (упр. 4.44) иногда называют элементом Дойча [118]. Дойч, Баренко и Экерт [115], а также Ллойд [253] независимо показали, что почти любой двухкубитовый элемент универсален. То, что ошибка, накапливающаяся при применении последовательности элементов, не превосходит суммы ошибок каждого из них, доказана в работе Бернштейна и Вазирани [75]. Универсальность набора элементов, на котором здесь было сосредоточено внимание, состоящего из элементов Адамара, сдвига фазы, скот и я/8 — была обнаружена Войкином, Мором, Пулвером и др.
[62]; в этой работе содержится также доказательство того, что число 9, определенное соотношением соз(д/2) ш созе(я/8), является иррациональным кратным 2х. Оценка, сделанная в подразд. 4.5.4, основана на работе Нилла [223]; в этой статье содержится гораздо более подробное исследование трудности аппроксимации произвольных унитарных операторов с помощью квантовых схем. В частности, Нилл получил более точные и общие оценки; кроме того, он рассматривает и случай, когда семейство элементов, используемых для аппроксимации, непрерывно.
Вычислительная модель, основанная на квантовых схемах, введена Дойчем [118]; ее дальнейшую разработку выполнил Яо [425], который показал, что модель квантовых схем эквивалентна модели, основанной на квантовых машинах Тьюринга. Последние были введены в 1980 г. Бениоффом [45]; далее их теорию развили Дойч [117] и Яо [425], а современное определение было дано Бернштейном и Вазирани [75]. В последних двух статьях сделаны первые шаги в направлении теории квантовой вычислительной сложности, аналогичной обычной теории сложности. В частности, включение ВЯР С РБРАСБ и даже некоторое его усиление получены Бернштейном и Вазирани. Нилл и Лзфламм [217] обнаружили интересные связи между квантовой и классической вычислительной сложностью.
В числе других работ по квантовой вычислительной сложности следует отметить статьи Адлемана, Демарре и Хуанга [4] и Ватроуза [411]. Последняя содержит интригующие свидетельства в пользу того, что квантовые компьютеры эффективнее классических в «системах интерактивных доказательствь (шСегасФЬ е ргоо1 еув«еше). То обстоятельство, что квантовые компьютеры могут моделировать квантовые системы более эффективно, чем это могли бы сделать классические компьютеры, было отмечено Маниным [274] в 1980 г.; независимо от него эту идею более детально развил Фейнман ]149]. Более подробные исследования были предприняты Абрамсом и Ллойдом [12], Богосяном и Тейлором [74], Сорнборгером и Стюартом [369], Виснером [417] и Залкой [430].
Формула Троттера [386] была также доказана Черновым [84], а ее более простая форма (с унитарными операторами) была известна гораздо раньше и восходит к временам Софуса Ли. Формула Бейкера-Кэмпбелла-Хаусдорффа с точностью до третьего по- 4.7. Моделирование квантовых систем 273 рядка (согласно нашей нумерации формула (4.104)) была приведена в работе Сорнборгера и Стюарта [369].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
