Quantum algorithms¶
- amplitude amplification
- period finding
Deutsch-Jozsa algorithm¶
The complete version of Deutch algorithm solves the following problem: given a binary function \(f\) defined on binary strings of \(n\) digits,
with the guarantee that \(f\) is either constant or balanced (meaning that half of the answer is 0), determine whether it is constant or balanced.
On a classical computer, we will have to evaluate \(2^{n-1}+1\) inputs to know the answer. In contrast, Deutch algorithm needs only one measurement on \(n\) qubits: an exponential speedup! For simplicity, I will only consider the \(n=1\) case. Generalizing to the \(n\)-qubit case is somewhat straightforward. Again, in this simplified situation, classically we need to evaluate two inputs. With a quantum computer, we only need one readout on one qubit.
The first thing we need to worry about is how to implement \(f\). Obviously it cannot be applied on quantum states directly since its domain is binary strings. Without much surprise, it is implemented as a controlled unitary gate, with the action
where \(\oplus\) is the XOR gate. This action is obviously reversible, thus there must be a way to implement it on a quantum computer as a unitary time evolution. Let’s call it \(U_f\). Note that its action on \(\left|y\right>\) is controlled by the value of \(f(x)\) instead of the ancilla qubit state directly. It is a CNOT gate gate controlled by the value of \(f(x)\). Let me also assure you that in the \(n\)-qubit case, such \(U_f\) can be implemented on a quantum computer without exponential trouble. Thus the exponential speed up is real.
With a hardware implementation of \(U_f\), we can apply it on a special initial state, i.e.,
where the first qubit is the ancilla qubit, and the controlled qubit is in the eigenstate of the NOT gate (or X-gate since it’s the Pauli x matrix) \(H\left|1\right>\) with eigenvalue \(-1\), or equivalently \(\phi=\pi\). After simplification, the ancillar qubit is given by
Recall that \(f\) is either constant or balanced. Thus the phase kickback is either \(0\) or \(\pi\), which is particularly easy to distinguish since they are eigenstates of \(\sigma_x\). One can measure \(\sigma_x\) just once to tell them apart, with only one copy of the input state. In the quantum computing framework, the equivalent procedure is to first apply [Hadamard gate][h] and then check whether the state is \(\left|0\right>\) or \(\left|1\right>\).
Admittedly, Deutch algorithm is quite artificial. But it opens up the possibility of exponential speedup on quantum computers.
phase estimation algorithm (PEA)¶
In special occasions, the exponential speedup materializes. It happens when the answer corresponds to one of the QFT basis states. Then the application of QFT followed by a measurement can tell us the answer. This is the main idea of the quantum phase estimation algorithm (PEA), a quantum algorithm for eigenvalues and eigenvectors.
A simplified version of it can be stated as follows. Suppose we are given an eigenstate of a unitary gate/operator satisfying
where \(\phi\) is guaranteed to be smaller than 2pi, estimate \(\phi\).
For now, let’s assume that \(\phi\) happens to be \(\omega_N^k\) with an unknown \(k\) (here we assume we somehow know \(N\) and again \(N=2^n\)). Then we can use controlled-\(U\) gates and \(N\) ancilla qubits to do the phase kickback trick with the output state
In other words, we can transform it to be one of the QFT basis states and the unknown value $$k$$ is exactly the row index. Then it only takes a QFT transformation and one measurement to reveal \(k\).
What if \(\phi\) is not \(\omega_N^k\)? A moment of reflection will show that the aforementioned protocol produces the best \(N\)-bit approximation of \(\phi\) (in this case one also needs to repeat this protocol several times to be sure).