Квантовый алгоритм оценки собственных значений
Алгоритм оценки фазы квантового (называемый также квант собственного значение оценки алгоритма ), является квантовым алгоритмом для оценки фазы (или собственного значение) из собственных унитарного оператора. Точнее, учитывая унитарную матрицу и квантовое состояние, такое , что алгоритм оценивает значение с высокой вероятностью в пределах аддитивной ошибки , используя кубиты (без подсчета кубитов, используемых для кодирования состояния собственного вектора) и операции с управляемым U. U {\ displaystyle U} | ψ ⟩ {\ displaystyle | \ psi \ rangle} U | ψ ⟩ знак равно е 2 π я θ | ψ ⟩ {\ Displaystyle U | \ psi \ rangle = e ^ {2 \ pi i \ theta} | \ psi \ rangle} θ {\ displaystyle \ theta} ε {\ Displaystyle \ varepsilon} О ( бревно ( 1 / ε ) ) {\ Displaystyle О (\ журнал (1 / \ varepsilon))} О ( 1 / ε ) {\ Displaystyle О (1 / \ varepsilon)}
Оценка фазы часто используется в качестве подпрограммы в других квантовых алгоритмах, таких как алгоритм Шора [1] : 131 и квантовый алгоритм для линейных систем уравнений .
Пусть U - унитарный оператор , работающий с m кубитами с таким собственным вектором , что . | ψ ⟩ , {\ displaystyle | \ psi \ rangle,} U | ψ ⟩ знак равно е 2 π я θ | ψ ⟩ , 0 ≤ θ < 1 {\ Displaystyle U | \ psi \ rangle = e ^ {2 \ pi i \ theta} \ left | \ psi \ right \ rangle, 0 \ leq \ theta <1}
Мы хотели бы найти собственное значение из , что в данном случае эквивалентна оценка фазы , до конечного уровня точности. Мы можем записать собственное значение в форме, потому что U - унитарный оператор над комплексным векторным пространством, поэтому его собственные значения должны быть комплексными числами с модулем 1. е 2 π я θ {\ Displaystyle е ^ {2 \ пи я \ тета}} | ψ ⟩ {\ displaystyle | \ psi \ rangle} θ {\ displaystyle \ theta} е 2 π я θ {\ Displaystyle е ^ {2 \ пи я \ тета}}
Схема квантовой оценки фазы
Вход состоит из двух регистров (а именно, двух частей): верхние кубиты составляют первый регистр , а нижние кубиты - второй регистр . п {\ displaystyle n} м {\ displaystyle m}
Создать суперпозицию [ править ] Исходное состояние системы:
| 0 ⟩ ⊗ п | ψ ⟩ . {\ displaystyle | 0 \ rangle ^ {\ otimes n} | \ psi \ rangle.} После применения n-битной операции логического элемента Адамара к первому регистру состояние становится следующим: ЧАС ⊗ п {\ displaystyle H ^ {\ otimes n}}
1 2 п 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ п | ψ ⟩ {\displaystyle {\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle } Применить управляемые унитарные операции [ править ] Позвольте быть унитарным оператором с собственным вектором таким, что таким образом U {\displaystyle U} | ψ ⟩ {\displaystyle |\psi \rangle } U | ψ ⟩ = e 2 π i θ | ψ ⟩ , {\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle ,}
U 2 j | ψ ⟩ = U 2 j − 1 U | ψ ⟩ = U 2 j − 1 e 2 π i θ | ψ ⟩ = ⋯ = e 2 π i 2 j θ | ψ ⟩ {\displaystyle U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle } C − U {\displaystyle C-U} управляемый U-образный U {\displaystyle U} | 1 ⟩ {\displaystyle |1\rangle }
Предположим для ясности, что управляемые вентили применяются последовательно, после применения к кубиту первого и второго регистров состояние становится C − U 2 0 {\displaystyle C-U^{2^{0}}} n t h {\displaystyle n^{th}}
1 2 1 2 ( | 0 ⟩ | ψ ⟩ + | 1 ⟩ e 2 π i 2 0 θ | ψ ⟩ ) ⏟ n t h q u b i t a n d s e c o n d r e g i s t e r ⊗ 1 2 n − 1 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ n − 1 ⏟ q u b i t s 1 s t t o n − 1 t h = 1 2 1 2 ( | 0 ⟩ | ψ ⟩ + e 2 π i 2 0 θ | 1 ⟩ | ψ ⟩ ) ⊗ 1 2 n − 1 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ n − 1 {\displaystyle {\frac {1}{2^{\frac {1}{2}}}}\underbrace {\left(|0\rangle |\psi \rangle +|1\rangle e^{2\pi i2^{0}\theta }|\psi \rangle \right)} _{n^{th}\ qubit\ and\ second\ register}\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\underbrace {\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}} _{qubits\ 1^{st}\ to\ n-1^{th}}={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle |\psi \rangle +e^{2\pi i2^{0}\theta }|1\rangle |\psi \rangle \right)\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}} = 1 2 1 2 ( | 0 ⟩ + e 2 π i 2 0 θ | 1 ⟩ ) | ψ ⟩ ⊗ 1 2 n − 1 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ n − 1 = 1 2 n 2 ( | 0 ⟩ + e 2 π i 2 0 θ | 1 ⟩ ) ⏟ n t h q u b i t ⊗ ( | 0 ⟩ + | 1 ⟩ ) ⊗ n − 1 | ψ ⟩ , {\displaystyle ={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)|\psi \rangle \otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}={\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}\otimes \left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}|\psi \rangle ,} где мы используем:
| 0 ⟩ | ψ ⟩ + | 1 ⟩ ⊗ e 2 π i 2 j θ | ψ ⟩ = ( | 0 ⟩ + e 2 π i 2 j θ | 1 ⟩ ) | ψ ⟩ , ∀ j . {\displaystyle |0\rangle |\psi \rangle +|1\rangle \otimes e^{2\pi i2^{j}\theta }|\psi \rangle =(|0\rangle +e^{2\pi i2^{j}\theta }|1\rangle )|\psi \rangle ,\ \forall j.} После применения всех оставшихся управляемых операций с, как показано на рисунке, состояние первого регистра можно описать как n − 1 {\displaystyle n-1} C − U 2 j {\displaystyle C-U^{2^{j}}} 1 ≤ j ≤ n − 1 , {\displaystyle 1\leq j\leq n-1,}
1 2 n 2 ( | 0 ⟩ + e 2 π i 2 n − 1 θ | 1 ⟩ ) ⏟ 1 s t q u b i t ⊗ ⋯ ⊗ ( | 0 ⟩ + e 2 π i 2 1 θ | 1 ⟩ ) ⏟ n − 1 t h q u b i t ⊗ ( | 0 ⟩ + e 2 π i 2 0 θ | 1 ⟩ ) ⏟ n t h q u b i t = 1 2 n 2 ∑ k = 0 2 n − 1 e 2 π i θ k | k ⟩ , {\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle \right)} _{1^{st}\ qubit}\otimes \cdots \otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle \right)} _{n-1^{th}\ qubit}\otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle ,} где обозначает двоичное представление , то есть это вычислительная основа, а состояние второго регистра остается физически неизменным . | k ⟩ {\displaystyle |k\rangle } k {\displaystyle k} k t h {\displaystyle k^{th}} | ψ ⟩ {\displaystyle |\psi \rangle }
Применить обратное квантовое преобразование Фурье [ править ] Применение обратного квантового преобразования Фурье к
1 2 n 2 ∑ k = 0 2 n − 1 e 2 π i θ k | k ⟩ {\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle } дает
1 2 n 2 ∑ k = 0 2 n − 1 e 2 π i θ k 1 2 n 2 ∑ x = 0 2 n − 1 e − 2 π i k x 2 n | x ⟩ = 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e 2 π i θ k e − 2 π i k x 2 n | x ⟩ = 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) | x ⟩ . {\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}{\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .} Состояние обоих регистров вместе
1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) | x ⟩ ⊗ | ψ ⟩ . {\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle \otimes |\psi \rangle .} Представление аппроксимации фазы [ править ] Мы можем приблизить значение , округлив до ближайшего целого числа. Это означает, что где - ближайшее целое число, и разница удовлетворяет . θ ∈ [ 0 , 1 ] {\displaystyle \theta \in [0,1]} 2 n θ {\displaystyle 2^{n}\theta } 2 n θ = a + 2 n δ , {\displaystyle 2^{n}\theta =a+2^{n}\delta ,} a {\displaystyle a} 2 n θ , {\displaystyle 2^{n}\theta ,} 2 n δ {\displaystyle 2^{n}\delta } 0 ⩽ | 2 n δ | ⩽ 1 2 {\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}
Теперь мы можем записать состояние первого и второго регистров следующим образом:
1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − a ) e 2 π i δ k | x ⟩ ⊗ | ψ ⟩ . {\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}|x\rangle \otimes |\psi \rangle .} Выполнение измерения на вычислительной основе в первом регистре дает результат с вероятностью | a ⟩ {\displaystyle |a\rangle }
Pr ( a ) = | ⟨ a | 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − a ) e 2 π i δ k | x ⏟ State of the first register ⟩ | 2 = 1 2 2 n | ∑ k = 0 2 n − 1 e 2 π i δ k | 2 = { 1 δ = 0 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 δ ≠ 0 {\displaystyle \Pr(a)=\left|\left\langle a\underbrace {\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(x-a)}e^{2\pi i\delta k}\right|x} _{\text{State of the first register}}\right\rangle \right|^{2}={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\begin{cases}1&\delta =0\\&\\{\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&\delta \neq 0\end{cases}}} Поскольку приближение является точным, поэтому и в этом случае мы всегда измеряем точное значение фазы. [2] : 157 [3] : 347 [1] : 223 δ = 0 {\displaystyle \delta =0} a = 2 n θ {\displaystyle a=2^{n}\theta } Pr ( a ) = 1. {\displaystyle \Pr(a)=1.} | 2 n θ ⟩ ⊗ | ψ ⟩ {\displaystyle |2^{n}\theta \rangle \otimes |\psi \rangle }
Для поскольку алгоритм дает правильный результат с вероятностью . Докажем это следующим образом: [2] : 157 [3] : 348 δ ≠ 0 {\displaystyle \delta \neq 0} | δ | ⩽ 1 2 n + 1 {\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}} Pr ( a ) ⩾ 4 π 2 ≈ 0.405 {\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}
Pr ( a ) = 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 for δ ≠ 0 = 1 2 2 n | 2 sin ( π 2 n δ ) 2 sin ( π δ ) | 2 | 1 − e 2 i x | 2 = 4 | sin ( x ) | 2 = 1 2 2 n | sin ( π 2 n δ ) | 2 | sin ( π δ ) | 2 ⩾ 1 2 2 n | sin ( π 2 n δ ) | 2 | π δ | 2 | sin ( π δ ) | ⩽ | π δ | for | δ | ⩽ 1 2 n + 1 ⩾ 1 2 2 n | 2 ⋅ 2 n δ | 2 | π δ | 2 | 2 ⋅ 2 n δ | ⩽ | sin ( π 2 n δ ) | for | δ | ⩽ 1 2 n + 1 ⩾ 4 π 2 {\displaystyle {\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\[6pt]&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}\end{aligned}}} Этот результат показывает, что мы с высокой вероятностью измерим наилучшую n-битную оценку . Увеличивая количество кубитов и игнорируя эти последние кубиты, мы можем увеличить вероятность до . [3] θ {\displaystyle \theta } O ( log ( 1 / ϵ ) ) {\displaystyle O(\log(1/\epsilon ))} 1 − ϵ {\displaystyle 1-\epsilon }
См. Также [ править ] Алгоритм Шора Алгоритм квантового счета Ссылки [ править ] ^ a b Нильсен, Майкл А. и Исаак Л. Чуанг (2001). Квантовые вычисления и квантовая информация (Ред. Ред.). Кембридж [ua]: Cambridge Univ. Нажмите. ISBN 978-0521635035. ^ а б Бененти, Гильяно; Касати, Джулио; Стрини, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано. Ред.). Нью-Джерси [ua]: World Scientific. ISBN ^ a b c Cleve, R .; Ekert, A .; Macchiavello, C .; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: математические, физические и инженерные науки . 454 (1969). arXiv : квант-ph / 9708016 . Bibcode : 1998RSPSA.454..339C . DOI : 10,1098 / rspa.1998.0164 . Китаев, А.Ю. (1995). «Квантовые измерения и проблема абелевых стабилизаторов». arXiv : квант-ph / 9511026 . Критерии Ди Винченцо Квантовые вычисления Квантовая информация Квантовое программирование Кубитфизический против логического Квантовые процессоры
Белла Глисона Готтесман – Книл Холево Марголус – Левитин Нет трансляции Без клонирования Нет связи Без удаления Не прячется Нет телепортации PBR Квантовый порог Соловай – Китаев Классическая емкостьзапутанный Квантовая емкость Дистилляция сцепления LOCC Квантовый канал Квантовая криптографияКвантовое распределение ключей BB84 SARG04 Протокол трехэтапной квантовой криптографии Квантовая телепортация Сверхплотное кодирование Бернштейн – Вазирани Deutsch – Jozsa Гровера Квантовый счет Квантовая оценка фазы Шора Саймона Усиление амплитуды Линейные системы уравнений Квантовый отжиг Квантовое преобразование Фурье Квантовая нейронная сеть Универсальный квантовый симулятор Адиабатические квантовые вычисления Дифференцируемые квантовые вычисления Односторонний квантовый компьютер Квантовая схемаКвантовый логический вентиль Квантовая машина Тьюринга Топологический квантовый компьютер КодыCSS Квантовый сверточный стабилизатор Шор Steane Торический GNU Квантовая коррекция ошибок с помощью запутывания
Отбор проб бозона Полость QED Схема QED Линейные оптические квантовые вычисления KLM протокол Оптическая решетка Квантовый компьютер с захваченными ионами Кейн КК Спиновый кубит QC Азотно-вакансионный центр Ядерный магнитный резонанс QC Зарядить кубит Поток кубита Фазовый кубит Трансмон
OpenQASM - Qiskit - IBM QX Quil - Forest / Rigetti QCS Cirq Q # libquantum многие другие...
![\ theta \ in [0,1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/fead1e7dceab4be5ab2e91f5108144722daa8c36)
![{\ Displaystyle {\ begin {align} \ Pr (a) & = {\ frac {1} {2 ^ {2n}}} \ left | {\ frac {1- {e ^ {2 \ pi i2 ^ {n } \ delta}}} {1- {e ^ {2 \ pi i \ delta}}}} \ right | ^ {2} && {\ text {for}} \ delta \ neq 0 \\ [6pt] & = {\ frac {1} {2 ^ {2n}}} \ left | {\ frac {2 \ sin \ left (\ pi 2 ^ {n} \ delta \ right)} {2 \ sin (\ pi \ delta) }} \ right | ^ {2} && \ left | 1-e ^ {2ix} \ right | ^ {2} = 4 \ left | \ sin (x) \ right | ^ {2} \\ [6pt] & = {\ frac {1} {2 ^ {2n}}} {\ frac {\ left | \ sin \ left (\ pi 2 ^ {n} \ delta \ right) \ right | ^ {2}} {| \ sin (\ pi \ delta) | ^ {2}}} \\ [6pt] & \ geqslant {\ frac {1} {2 ^ {2n}}} {\ frac {\ left | \ sin \ left (\ pi 2 ^ {n} \ delta \ right) \ right | ^ {2}} {| \ pi \ delta | ^ {2}}} && | \ sin (\ pi \ delta) | \ leqslant | \ pi \ delta | {\ text {for}} | \ delta | \ leqslant {\ frac {1} {2 ^ {n + 1}}} \\ [6pt] & \ geqslant {\ frac {1} {2 ^ {2n}} } {\ frac {| 2 \ cdot 2 ^ {n} \ delta | ^ {2}} {| \ pi \ delta | ^ {2}}} &&| 2 \ cdot 2 ^ {n} \ delta | \ leqslant | \ sin (\ pi 2 ^ {n} \ delta) | {\ text {for}} | \ delta | \ leqslant {\ frac {1} {2 ^ {n + 1}}} \\ [6pt] & \ geqslant {\ frac {4} {\ pi ^ {2}}} \ end {выровнено}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a180a9a246f4103ecb6645bc3aacf88e2c7fbee6)
Темы квантовой механики