Квантовая фазовая оценка и алгоритм HHL - требуется знание собственных значений?

10

Алгоритм оценки квантовой фазы (КОО) вычисляет приближение собственного значения , связанного с данным собственного вектора квантового ворот .U

Формально пусть собственный вектор U , QPE позволяет найти | ~ & Thetas ; ⟩ , лучший м бит приближение 2 м & thetas ; такое , что & thetas [ 0 , 1 ) и U | г | = е 2 π я & thetas ; | г | .|ψU|θ~m2mθθ[0,1)

U|ψ=e2πiθ|ψ.

Алгоритм HHL ( оригинальная бумага ) принимает в качестве входных данных матрицы , которые удовлетворяют условие электронной I т  унитарна  и квантовое состояние | б и вычисляет | х , который кодирует решение линейной системы А х = Ь .A

eiAt is unitary 
|b|xAx=b

Примечание : Каждая эрмитова матрица Утоли условие на .A

Для этого алгоритм HHL использует QPE на квантовых воротах, представленных . Благодаря линейной алгебры результатов, мы знаем , что если { λ J } J являются собственные значения А , то { е я λ J т } J собственные значения U . Этот результат также изложен в алгоритмах квантовых линейных систем: учебник для начинающих (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018) (стр. 29, между уравнениями 68 и 69).U=eiAt{λj}jA{eiλjt}jU

θ[0,1)ei2πθ=eiλjt

2πθ=λjt+2kπ,kZ, θ[0,1)
θ=λjt2π+k,kZ, θ[0,1)
kZθ[0,1)λjt2π[0,1)k0

AAλjt2π[0,1)

eiAt16A{1,2,4,8}λjt2π[0,1)

t

Aλjt2π[0,1)

Nelimee
источник
t=1k=2t=10<(λ/2π)+2<14π<λ<2πλ=3πλ/2π0
λθ[0,1)λ<0λλ2kπk=λ2πλ2π

Ответы:

6

Atλt2πANQ

maxiaii+ji|aij|NQ,
miniaiiji|aij|NQ.
aijA

В пределах значений , , если вы беспокоитесь, что для большой матрицы (скажем, кубитов), в то время как сумма строк может быть легко вычислена (потому что записей не много), максимальное значение для всех строк может занять много времени. время (потому что есть строк), будет множество способов получить хорошие приближения к нему (например, выборка или использование знаний о структуре задачи). В худшем случае, вы можете использовать поиск Гровера, чтобы немного ускорить его.NQn2n

DaftWullie
источник
1
Гровер не является улучшением: даже если мы сможем использовать алгоритм, нам все равно потребуются запросы , которые уничтожают экспоненциальное улучшение HHL по сравнению с классическими методами и заменяют его квадратичным ускорением. Поэтому остается только надеяться на выборку (ввести другой источник ошибок) или молиться и надеяться, что проблема позволяет нам оценить верхнюю / нижнюю границы. Похоже, главный недостаток алгоритма для меня. O(N)
Нелиме
2
Конечно, я имел в виду только то, что Гровер дает вам ускорение по квадратному корню по сравнению с наивным способом получения максимума. Конечно, это плохо влияет на общее время работы.
DaftWullie