For the superposition state of a composite system, how to use the quantum amplitude amplification algorithm to simultaneously amplify several of them

Question

For the superposition state $|\Phi \rangle =\frac{1}{16}\sum\limits_{i=0}^{15}{(|i\rangle |{{a}_{i}}\rangle )}$ (The second quantum system ${a}_{i}$ is not necessarily all orthogonal) of a composite system, how to use the quantum amplitude amplification algorithm to simultaneously amplify several of them, such as $|3\rangle |{{a}_{3}}\rangle $, $|5\rangle |{{a}_{5}}\rangle $ and $|8\rangle |{{a}_{8}}\rangle $? If this is not feasible, is it possible to use other methods to filter out unwanted items?

Answer 1

I shall assume a unitary $U$ such that $U |0\rangle^{\otimes(n+4)} = |\Phi \rangle \equiv \frac{1}{4} \sum_{i = 0}^{15} (|i \rangle |a_i \rangle)$ is given, where $\{|a_i \rangle\}_{i=0}^{15}$ are all $n$-qubit states. For the sake of concreteness, let us consider the particular example you mentioned, i.e., that the states to amplify are $\{|3\rangle |a_3\rangle, |5\rangle |a_5\rangle, |8\rangle |a_8\rangle\}$. In such case we can split the input state $|\Phi \rangle$ as

$|\Phi\rangle = \frac{\sqrt{3}}{4} |\Phi_{target}\rangle + \frac{\sqrt{13}}{4} |\Phi_{discarded}\rangle,$

where $|\Phi_{target}\rangle \equiv \frac{1}{\sqrt{3}}(|3\rangle |a_3\rangle + |5\rangle |a_5\rangle + |8\rangle |a_8\rangle)$. The diffusion operator is implemented as

where the $Z$ gate acting on the ancilla prepared in state $|1\rangle$ is only triggered if all $n+4$ qubits in the main register are in state $|0\rangle$. The oracle must apply a phase shift of $e^{i \pi} = -1$ only to $|\Phi_{target}\rangle$ and not to $|\Phi_{discarded}\rangle$. Perhaps the simplest implementation of this oracle corresponds to applying the phase shift to each term separately. For the particular case considered here, the oracle is implemented as follows.

Putting the pieces together, the full quantum amplitude amplification circuit looks like this.

The subcircuit inside the curved brackets is repeated $M$ times. For $M = 0$, such subcircuit is not executed at all, in which case we merely prepare $|\Phi \rangle$ and the weight carried by the desired part $|\Phi_{target} \rangle$ is $p = \frac{3}{16} = 18.75 \%$. Every repetition of the subcircuit rotates the state in the relevant two-dimensional subspace $\{ |\Phi_{target}\rangle, |\Phi_{discarded}\rangle \}$ by $\theta = \arctan(\frac{2\sqrt{p(1-p)}}{1-2p}) \approx 51^{\circ}$. The initial state is at an angle $\theta_0 = \arcsin(\sqrt{p}) \approx 26^{\circ}$ from the x-axis defined by $|\Phi_{discarded}\rangle$, so for $M=1$ the angle relative to the x-axis becomes $26^{\circ} + 51^{\circ} = 77^{\circ}$ and the weight carried by the target state is amplified to $\sin^{2}(77^{\circ}) \approx 95\%$. A second execution of the subcircuit (i.e., $M = 2$) will no longer produce an improvement; the weight of the desired part will fall to $\approx 62\%$. This is a manifestation of the so-called soufflé problem: Iterating too few times "undercooks" the state, but iterating too many "overcooks" it.

If we wish to increase the weight of the desired part arbitrarily close to $100 \%$, we can make use of a so-called fixed-point amplitude amplification method, which addresses the soufflé problem, in that the more iterations we execute, the greater the weight of the desired part is. The original fixed-point method, the so-called phase-$\frac{\pi}{3} method$, was devised by Lov Grover and corresponds to a clever recursive adaptation of his original algorithm. The state-of-the-art fixed point method was proposed by Yoder, Low and Chuang and addresses the soufflé problem whilst also retaining the quadratic speed-up of the Grover algorithm.