М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 82
Текст из файла (страница 82)
Построенная нами картина прояснит, какие ресурсы требуются, чтобы дать возможность квантовому компьютеру проводить поиск в классической базе данны х. Предположим, что имеется база данньгх, содержащая?»' = 2" записей, каждая длиной 1 битов. Обозначим эти записи как 4,...,4ч. Мы хотим определить, где именно находится заданная строка из 1 битов (обозначим ее буквой э).
332 Глава 6. Квантовые алгоритмы поиска Классический компьютер, используемый для решения такой задачи, обычно включает две части (рис. 6.8). В одной, называемой центщильнвьы процессором, происходит обработка данных с использованием небольшого объема временной памяти. Вторая представляет собой большой объем памлгли, где хранится база данных в виде строки из 2" блоков по ) битовых ячеек.
Предполагается, что память пассивна — в том смысле, что она сама по себе не может обрабатывать данные. Возможно только ЗАГРУЖАТЬ данные из памяти в процессор и СОХРА- нять в памяти данные, полученные от ЦП, а также проводить манипуляции с данными, временно хранимыми в процессоре. Классические компьютеры могут быть устроены по-разному, но их разделение на процессор и память является очень распространенным и стандартным для компьютерной архитектуры. Память РИ бит Хранение Рис. 6.6.
Классический поиск по базе данных с помощью компьютера, состоящего из центрального процессора и памяти Можно выполнить только две операции с памятью загрузку в процессор или пересылку записи на хранение из процессора в память В классическом случае наиболее эффективный алгоритм определения, где именно в неструктурированной базе находится заданная строка а, выглядит следующим образом.
Сначала в процессор помещают и-битовый указатель записи базы данных. Предполагается, что процессор обладает достаточной емкостью для того, чтобы хранить указатель из и = [!об И) битов. Вначале этот указатель равен нулю, а потом увеличивается на единицу при каждой итерации алгоритма. На каждой итерации в процессор загружается запись из базы данных, соответствующая текущему значению указателя, после чего она сравнивается с шаблоном отыскиваемой строки. Если они совпадают, алгоритм выдает значение указателя, происходит остановка. Если они различаются, алгоритм продолжает увеличивать значение указателя. Очевидно, что при таком алгоритме записи будут загружаться из памяти в худшем случае 2" раз. Ясно, что это наиболее эффективный алгоритм, позволяющий решить эту задачу при такой организации вычислений. Насколько эффективно аналогичный алгоритм может быть реализован с помощью квантового компьютера? А если ускорение с помощью квантового подхода возможно, то насколько такой алгоритм окажется полезным? Сначала покажем, что ускорение возможно, а затем вернемся к вопросу о пользе такого алгоритма.
Предположим, наш квантовый компьютер, как и в классическом случае, состоит вз двух частей — ЦП и памяти. Будем считать, что процессор содержит четыре регистра: 1) и-кубитовый «указатель», установленный в начальный момент времени в состояние ~0); 2) 1-кубитовый регистр, приведенный при запуске алгоритма в состояние ~я) и остающийся в таком состоянии до конца вычислений; 3) 1-кубитовый регистр данных, находящийся в 6.5. Квантовый поиск в неструктурированной базе данных 333 начальный момент в состояние ~0); 4) 1-кубитовый регистр, установленный в состояние ()О) — )1))/~/2.
Память может быть организована двумя различными способами. В простейшем случае — это квантовая память, состоящая из Ф = 2" ячеек по 1 битов, каждая из которых содержит запись базы данных К1 ). Второй способ предполагает построение классической памяти, содержащей Х = 2" ячеек по 1 битов, каждая из которых содержит запись И .
Однако в отличие от классической памяти к ней можно обращаться через указатель х, который находится в состоянии ~х), являющемся, вообще говоря, суперпозицией нескольких значений. Этот квантовый указатель позволяет выполнять ЗАГРУЗКУ суперпозиции значений из разных ячеек памяти. Доступ к памяти работает следующим образом: если регистр указателя находится в состоянии ~х), а регистр данных — в состоянии ф, то к регистру данных добавляется содержимое Из из х-й ячейки памяти: ф — ~ ~И 9 Н,), сложение выполняется побитово по модулю 2. Сначала посмотрим, как эта возможность используется для выполнения квантового поиска, а затем обсудим пути реального построения такой памяти.
Ключевой момент в осуществлении квантового алгоритма поиска — реализация оракула, который должен осуществлять переворот фазы указателя, задающего место кубита з в памяти. Предположим, процессор находится в состоянии !х)/з)!О) $0) — !1) (6.35) Применение операции ЗАГРУЗКА переведет компьютер в состояние !х)/з)!Н,) !О) — /1) (6.36) Теперь сравниваются второй и третий регистры, и если их значения совпадают, то к четвертому регистру применяется операция обращения бита; в противном случае ничего не меняется. Результат действия этой операции следующий: !О) — !1) ( — !х)!з)~Ф,) ', если ~, = з, У'2 ~ )х)!з)/сЕз) ', если сЕ, ЗЗ з.
После этого в регистре данных восстанавливается значение ~0) (для этого опять выполняется операция 3АГРУзкА). Все действия оракула оставляют неизменными значения регистров 2, 3 и 4; кроме того, они не будут запутаны с состоянием регистра 1. Таким образом, этот шаг заключается в том, чтобы перевести состояние в регистре 1 из ~х) в — ~х), если Нз = з, и оставить состояние в этом регистре неизменным в противном случае. С использованием построенного таким образом оракула можно применить квантовый алгоритм поиска для определения положения з в базе данных, выполнив 0(1/й) операций 3АГРУзкА (в то время как в классическом случае требовалось Ж таких операций).
На первый взгляд кажется, что для правильной работы оракула с суперпозиционными состояниями необходимо, чтобы память подчинялась квантовомеханическим законам. На самом деле, как было отмечено выше, с некоторыми 334 Глава 6. Квантовые алгоритмы поиска предосторожностями память может быть организована классическим образом, что, по-видимому, делает ее более устойчивой по отношению к шумам. Однако по-прежнему требуется квантовомеханическая схема адресации; принципиальная схема, иллюстрирующая такую организацию памяти, показана на рис. 6.9.
Рис. 0.9. Принципиальная схема классической памяти с 32 ячейками и пятикубитовой схемой адресации Каждый кружок представляет собой переключатель, и обращение к нему отвечает изображенному внутри кубиту Например, когда )э«) = (0), соответствующий переключатель отправляет входной кубит налево, когда (эе) = )1) — направо Если (х«) = ((О)+(1))/т/2, то будет суперпозиция обоих путей с равными весами Кубиты, отображающие регистр данных, входят в схему на вершине дерева и спускаются вниз к базе данных, которая меняет их состояние по правилам, определяемым содержимым памяти.
Далее кубиты переводятся назад в определенную позицию, сохраняя полученную информацию. С физической точки зрения такая скема может быть реализована с использованием, например, одиночных фотонов для кубитов, содержащих значения регистров данных, которые управляются с помощью нелинейных интерферометров (см. гл. 7).
Классическая база данных может быть просто кусочком пластика, в котором «нули» (светлые прямоугольники на рисунке) пропускают свет без изменений, а «единицы» (темные прямоугольники) поворачивают поляризацию падающего света на 90». 6.6. Оптимальность алгоритма поиска 336 Основная идея заключается в переходе от бинарного кодирования квантового указателя (состояния от 0 до (2" — 1) отображаются п битами) к унарному (состояния от 0 до (2" — 1) представляются положением одного «зонда» в одной из 2" возможных позиций), с помощью которого задавался указатель записи в классической базе данных.
Ваза данных действует на «внутреннюю» степень свободы «зонда», не связанную с его положением. Далее переход от бинарного кодирования к унарному обращается, оставляя в регистре данных требуемое содержимое. Существуют ли практические применения, в которых квантовый алгоритм поиска может быть полезен при поиске по классическим базам данных? Следует сделать два замечания. Во-первых, базы данных не являются абсолютно неструктурированными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
