Квантовое сингулярное преобразование

Квантовое сингулярное преобразование является основой для разработки квантовых алгоритмов . Он включает в себя множество квантовых алгоритмов для задач, которые могут быть решены с помощью линейной алгебры , включая гамильтоновое моделирование , задачи поиска и решение линейных систем . ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} Он был представлен в 2018 году Андрашем Гильеном, Юань Су, Гуан Хао Лоу и Натаном Вибе, обобщая алгоритмы гамильтонового моделирования Гуан Хао Лоу и Исаака Чуана , вдохновленные обработкой сигналов. ^{[ 4 ]}

Описание высокого уровня

Базовым примитивом квантового преобразования сингулярных значений является блочное кодирование. Квантовая схема — это блочное кодирование матрицы A , если она реализует унитарную матрицу U такую, что U содержит A в указанной подматрице. Например, если $(\langle 0|\otimes I)U(|0\rangle |\phi \rangle )=A|\phi \rangle$ , то U является блочным кодированием A .

Фундаментальный алгоритм QSVT — это алгоритм, который преобразует блочное кодирование A в блочное кодирование A. $p(A,A^{\dagger })$ , где p — многочлен степени d и $A^{\dagger }$ обозначает сопряженное транспонирование только с d применениями схемы и одним вспомогательным кубитом. Это можно сделать для большого класса полиномов p , которые соответствуют применению полинома к сингулярным значениям A , что дает «преобразование сингулярного значения».

Вариант этого алгоритма также может быть выполнен, когда A является эрмитовым , что соответствует «преобразованию собственных значений». То есть, учитывая блочное кодирование A с собственным разложением матрицы $A=\sum \lambda _{i}u_{i}u_{i}^{\dagger }$ , можно получить блочную кодировку для $\sum p(\lambda _{i})u_{i}u_{i}^{\dagger }$ , при условии, что p ограничено. ^{[ 4 ]}

Алгоритм

Входные данные : матрица

A

которого по сингулярным значениям разложение

A=W\Sigma V^{\dagger }

где

\Sigma

являются сингулярными значениями A

Входные данные : полином.

P

Выход : унитарный, где

P

был применен к сингулярным значениям

A

:

{\begin{bmatrix}WP(\Sigma )V^{\dagger }&.\\.&.\end{bmatrix}}

Подготовьте унитарный $U$ который кодирует $A$ в верхней левой части $U$ , то есть $U={\begin{bmatrix}A&.\\.&.\end{bmatrix}}$
Инициализировать $n$ состояние кубита $|0\rangle ^{\otimes n}$
Если полином нечетный, сначала примените ${\tilde {\Pi }}_{\phi _{1}}U$ а потом $\prod _{k=1}^{\frac {d-1}{2}}\Pi _{\phi _{2k}}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k+1}}U$ к $|0\rangle ^{\otimes n}$
Если полином даже применим $\prod _{k=1}^{\frac {d}{2}}\Pi _{\phi _{2k}-1}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k}}U$ к $|0\rangle ^{\otimes n}$