We have investigated methods to learn about a given mystery quantum oracle. The Deutsch-Jozsa algorithm determines whether or not the function \(f:\{0, 1\}^n \rightarrow \{0, 1\}\) is well balanced and the Bernstein-Vazirani algorithm yields the unique string that satisfies \(f(x) = 1\). The oracle presented in the Bernstein-Vazirani algorithm provides ample information about the function for arbitrary input. The output transmitted to the ancilla qubit encodes the information of the dot product between the unique string \(x\) and the input string. In this post, we learn how to find the unique string for a quantum oracle that yields less information.
Problem. Let \(f:\{0, 1\}^n \rightarrow \{0, 1\}\) be a discrete function that maps a binary string to zero or one such that \(f(x_0) = 0\) for some unique nonzero string \(x_0\). A quantum oracle \(U_f\) is defined over the function \(f(x)\) as follows.
\[U_f|x\rangle \ = \ (-1)^{f(x)}|x\rangle\]
Find the unique string \(x_0\) using multiple iterations.
A trivial solution is to classically search over all binary strings by brute force. After \(2^n – 1\) trials, we are guaranteed to recover the unique string \(x_0\).
Yet, we wish to use the quantum nature of the oracle. Is it possible to increase the amplitude of the state \(|x_0\rangle\)? If this is the case, we can apply the Hadamard gate to create a uniform superposition among all binary strings, and increase the amplitude step-by-step. As long as the growth of amplitude is greater than logarithmic, then we have obtained a better solution than a classical search.
To our benefit, there exists a Grover Iteration that amplifies the magnitude. The procedure is defined as follows.
- Apply the Quantum Oracle \(U_f\)
- Apply Hadamard gates to all channels
- Apply \(U_{0\bot}\), the n-qubit phase shift operator
- Apply a layer of Hadamard gates again.
In symbols, the representation of the Grover Iteration is
\[G \ = \ HU_{0\bot}HU_f. \]
The n-qubit phase shift operator incurs a phase change of \(\pi\) to all basis states other than the zero state, i.e.
\[U_{0\bot} \ = \ \begin{cases}|0\rangle & (\text{if } x = 0)\\ -|x\rangle & (\text{if } x \neq 0)\end{cases}. \]
A geometrical interpretation of \(HU_{0\bot}H\) is an inversion around the mean. Rewrite the last three steps of the Grover Iteration as follows.
\[HU_{0\bot}H \ = \ H(-\mathbb I + 2|0\rangle\langle 0|)H \ = \ -\mathbb I + 2|\psi\rangle\langle \psi |\]
Here, we have defined \(|\psi\rangle = H |0\rangle\) as the superposition of all strings. Write out an arbitrary state \(|\phi\rangle \ = \ \sum_x \alpha_x |x\rangle\) and apply the operator to the state.
\[HU_{0\bot}H |\phi\rangle \ = \ \sum_x (2\mu – \alpha_x) |x\rangle\] And here, \(\mu = \frac 1 N \sum_x \alpha_x\) is defined as the mean. Rewriting \(2\mu – \alpha_x = \mu + (\mu – x)\), the second term can be considered as the drift from the mean, and the changed amplitude is an inversion around the mean.
The diagram below qualitatively describes the magnification of amplitude for \(N = 4\).
Luckiliy, for \(N=4\), the amplitudes other than the unique string vanishes after the first Grover Iteration. In the next post, we quantify the amplification of amplitude using trigonometry.
Leave a Reply