Усиление амплитуды это техника в квантовые вычисления который обобщает идею, лежащую в основе Алгоритм поиска Гровера, и дает начало семьеквантовые алгоритмы Это было обнаружено Жиль Брассар иПитер Хойер в 1997 г.[1]и независимо заново открыты Лов Гровер в 1998 г.[2]
В квантовом компьютере усиление амплитуды можно использовать для получения аквадратичного ускорения по сравнению с несколькими классическими алгоритмами.
Алгоритм
Представленный здесь вывод примерно соответствует приведенному в.[3]Предположим, у нас есть N-мерная Гильбертово пространство
представляющий пространство состояний нашей квантовой системы, охватываемой ортонормальными вычислительными базисными состояниями
. Кроме того, предположим, что у нас есть Эрмитский оператор проекции
. В качестве альтернативы
может быть дан в терминах aBoolean оракул функция
и ортонормированная операционная основа
,в таком случае
.
можно использовать для разделения
в прямую сумму двух взаимно ортогональных подпространств, хороший подпространство
и Плохо подпространство
:
![{ displaystyle { begin {align} { mathcal {H}} _ {1} &: = { text {Image}} ; P & = operatorname {span} {| omega _ {k} rangle in B _ { text {op}} ; | ; chi (k) = 1 }, { mathcal {H}} _ {0} &: = { text {Ker}} ; P & = operatorname {span} {| omega _ {k} rangle in B _ { text {op}} ; | ; chi (k) = 0 }. End {align}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/516b5910d65919f83680c31e41197149e13e9a6f)
Другими словами, мы определяем "
хорошее подпространство"
![{ displaystyle { mathcal {H}} _ {1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b3de4facc7bd3250b910c4363111ae952f7446f)
через проектор
![п](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
. Тогда цель алгоритма - развить некоторое начальное состояние
![| psi rangle in { mathcal {H}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a61d149966e0bed4ad430ca28b20067cba02a1ab)
в состояние, принадлежащее
![{ displaystyle { mathcal {H}} _ {1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b3de4facc7bd3250b910c4363111ae952f7446f)
.
Учитывая нормализованный вектор состояния
с ненулевым перекрытием с обоими подпространствами, мы можем однозначно разложить его как
,
куда
,и
и
нормированные проекции
в подпространства
и
соответственно, которое определяет двумерное подпространство
, натянутая на векторы
и
.Вероятность нахождения системы в хороший состояние при измерении
.
Определите унитарный оператор
,куда
![{ begin {align} S _ { psi} & = I-2 | psi rangle langle psi | quad { text {and}} S_ {P} & = I-2P. end { выровнен}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5994018637b336cb2ceda299fada03718d47e0c)
переворачивает фазу состояний в хороший подпространство, тогда как
переворачивает фазу начального состояния
.
Действие этого оператора на
дан кем-то
и
.
Таким образом, в
подпространство
соответствует повороту на угол
:
.
Применение
раз по состоянию
дает
,
вращая состояние между хороший и Плохо подпространства.
итераций вероятность нахождения системы в хороший состояние
.
Вероятность максимальна, если мы выберем
.
До этого момента каждая итерация увеличивает амплитуду хороший состояний, отсюда и название техники.
Приложения
Предположим, у нас есть несортированная база данных с N элементами и функция оракула
который может распознать хороший записи, которые мы ищем, и
для простоты.
Если есть
хороший всего записей в базе данных, то мы можем найти их, инициализировав квантовый регистр
с
кубиты куда
в равномерная суперпозиция всех элементов базы данных
такой, что
![| psi rangle = { frac {1} {{ sqrt {N}}}} sum _ {{k = 0}} ^ {{N-1}} | k rangle](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cf1289aee44528722a6177b8b42ae60ebbc7e0b)
и запустив вышеуказанный алгоритм. В этом случае перекрытие начального состояния с хороший подпространство равно квадратному корню из частоты хороший записи в базе данных,
. Если
, мы можем аппроксимировать количество требуемых итераций как
![n = left lfloor { frac { pi} {4 theta}} right rfloor приблизительно left lfloor { frac { pi} {4 sin ( theta)}} right rfloor = left lfloor { frac { pi} {4}} { sqrt {{ frac {N} {G}}}} right rfloor = O ({ sqrt {N}}).](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a25139283c3006acace17059f1b4f83417b3419)
Теперь измерение состояния даст один из хороший записи с большой вероятностью. Поскольку каждое приложение
требуется один запрос оракула (при условии, что оракул реализован как квантовые ворота ), мы можем найти хороший вход только с
oracle запрашивает, таким образом, получая квадратичное ускорение по сравнению с наилучшим классическим алгоритмом. (Классическим методом поиска в базе данных было бы выполнение запроса для каждого
пока решение не будет найдено, таким образом
запросы.)
Если мы установим размер набора
к одному, приведенный выше сценарий по существу сводится к исходному Поиск Гровера.
Рекомендации