Ex7 3
$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.3}$
Let $f$ and $g$ be functions from the space of $n$-bit strings to the space of $m$-bit strings. Design a quantum subroutine that changes the sign of exactly the basis states $\ket{x}$ such that $f(x) = g(x)$, where $x$ and $y$ are both $n$-bit binary strings, and which is efficient if $f$ and $g$ have efficient implementations.
page revision: 1, last edited: 14 May 2022 18:11
Define $h\colon \mathbb{Z}_{2^n} \to \mathbb{Z}_{2}$ by
(1)The function $h$ can be computed efficiently since $f,g$ have efficient implementations.
(2)To change sign on the $n$-qubit states where $f$ and $g$ agree, we need a phase change of $e^{i\pi} = -1$.
This is achieved by using an ancilla qubit in state $\ket 0$, and the standard unitary transformation $U_h$ that efficiently computes $h$ in an ancilla qubit:
together with the unitary transformation that changes sign on the $\ket 1$ state: $Z = \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}$.
In total the subroutine looks like (with un-entanglement of the ancilla qubit):
If $\ket{x_i}$ is a basis state with $f(x_i)=g(x_i)$, then the subroutine works like this:
(3)Entanglement with the ancilla qubit in the process does not show here, the un-entanglement transformation just brings back the $\ket 0$ state in the ancilla qubit.
(4)Entanglement arises when the input state is a superposition of basis states $\ket{x}$, $0 \leq x < 2^n$: