Тест свопа

Схема, реализующая тест переключения между двумя состояниями $|\phi \rangle$ и $|\psi \rangle$

Тест подкачки — это процедура квантовых вычислений , которая используется для проверки того, насколько различаются два квантовых состояния . Впервые она появилась в работе Баренко и др. и позже вновь открыт Гарри Бурманом , Ричардом Кливом , Джоном Уотрусом и Рональдом де Вольфом . Он обычно появляется в квантовом машинном обучении и представляет собой схему, используемую для проверки концепции в реализации квантовых компьютеров.

Формально тест подкачки принимает два входных состояния. $|\phi \rangle$ и $|\psi \rangle$ и выводит случайную величину Бернулли , равную 1 с вероятностью $\textstyle {\frac {1}{2}}-{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}$ (здесь в выражениях используется обозначение Бра-кет ). Это позволяет, например, оценить квадрат внутреннего продукта между двумя состояниями: ${|\langle \psi |\phi \rangle |}^{2}$, к $\varepsilon$ аддитивная ошибка, когда среднее значение принимается за $O(\textstyle {\frac {1}{\varepsilon ^{2}}})$ запускает тест подкачки. Это требует $O(\textstyle {\frac {1}{\varepsilon ^{2}}})$ копии входных состояний. Квадрат внутреннего продукта грубо измеряет «перекрытие» между двумя состояниями и может использоваться в линейно-алгебраических приложениях, включая кластеризацию квантовых состояний.

Объяснение схемы

Рассмотрим два состояния: $|\phi \rangle$ и $|\psi \rangle$. Состояние системы в начале протокола: $|0,\phi ,\psi \rangle$. После ворот Адамара состояние системы следующее: ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle )$. Управляемый вентиль SWAP преобразует состояние в ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\psi ,\phi \rangle )$. Вторые ворота Адамара приводят к $${\frac {1}{2}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle +|0,\psi ,\phi \rangle -|1,\psi ,\phi \rangle )={\frac {1}{2}}|0\rangle (|\phi ,\psi \rangle +|\psi ,\phi \rangle )+{\frac {1}{2}}|1\rangle (|\phi ,\psi \rangle -|\psi ,\phi \rangle )$$

Измерительный вентиль на первом кубите гарантирует, что он равен 0 с вероятностью

$$P({\text{First qubit}}=0)={\frac {1}{2}}{\Big (}\langle \phi |\langle \psi |+\langle \psi |\langle \phi |{\Big )}{\frac {1}{2}}{\Big (}|\phi \rangle |\psi \rangle +|\psi \rangle |\phi \rangle {\Big )}={\frac {1}{2}}+{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}$$

при измерении. Если $\psi$ и $\phi$ ортогональны ​ $({|\langle \psi |\phi \rangle |}^{2}=0)$, то вероятность того, что 0 измерен, равна ${\frac {1}{2}}$. Если государства равны $({|\langle \psi |\phi \rangle |}^{2}=1)$, то вероятность того, что 0 измерен, равна 1.

В общем, для $P$ испытания теста подкачки с использованием $P$ копии $|\phi \rangle$ и $P$ копии $|\psi \rangle$, доля нулевых измерений равна $1-\textstyle {\frac {1}{P}}\textstyle \sum _{i=1}^{P}M_{i}$, поэтому, взяв $P\rightarrow \infty$, можно получить произвольную точность этого значения.

Ниже приведен псевдокод для оценки значения $|\langle \psi |\phi \rangle |^{2}$ используя P копий $|\psi \rangle$ и $|\phi \rangle$:

Inputs P copies each of the n qubits quantum states $|\psi \rangle$ and $|\phi \rangle$Output An estimate of $|\langle \psi |\phi \rangle |^{2}$for j ranging from 1 to P:    initialize an ancilla qubit A in state $|0\rangle$    apply a Hadamard gate to the ancilla qubit A    for i ranging from 1 to n:         apply CSWAP to $\psi _{i}$ and $\phi _{i}$ (the ith qubit of the jth copy of $|\psi \rangle$ and $|\phi \rangle$), with A as the control qubit    apply a Hadamard gate to the ancilla qubit A    measure A in the $Z$ basis and record the measurement Mj as either a 0 or 1compute $s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}$.return $s$ as our estimate of $|\langle \psi |\phi \rangle |^{2}$