Amplitude Amplification for Optimization
via Subdivided Phase Oracle

Before applying our algorithm to various optimization problems, it is in order to gain visual intuition about how it leads to amplitude amplification. Unlike the Grover’s algorithm, where all vector amplitudes are real numbers, the subdivided phase oracle produces complex amplitudes. Therefore each amplitude corresponding to a computational basis state $|x\rangle$ can be represented as a vector in the complex plane.

Figure 1(a) represents the amplitudes of the equal superposition state $|\Psi_{0}\rangle$, where all vectors are real and have the same length given by $1/\sqrt{N}$, where $N=2^{n}$. The action of the phase oracle $O_{\phi}(k)$ is to rotate each vector corresponding to all the computational basis states around the origin as seen in Figure 1(b). This introduction of relative phases does not change the probabilities of measuring the individual computational basis state. The amplitude amplification occurs after the application of the diffusion operator $D$, which can be visualized in the following three steps:

1. 1.

   Find the mean amplitude vector and scale its length by two, represented by a yellow arrow in Figure 1(c).

2. 2.

   Compute the vector differences between the amplitude vectors and the scaled mean amplitude vector, depicted by purple arrows in Figures 1(d) and (e).

3. 3.

   Finally, replace the old amplitude vectors with the newly computed vectors from Step 2. This effectively shifts these updated amplitude vectors to the origin, as shown in Figure 1(f).

The vector corresponding to the probability amplitude of the optimal computational basis state representing the solution to the optimization problem is given by the most saturated red color in Fig. 1. We can see that application of the subdivided phase oracle followed by the diffusion operator increases its magnitude, amplifying the probability of measuring the optimal solution.

Grover oracle, when viewed in the same picture can be tracked easily, as the $\pi$ phase flip would make the group of marked state’s amplitude vectors point to the reverse direction. When the diffusion operator is applied, the mean would lie on the real number line and after the difference vectors are created, all amplitude vectors would still lie on the real number line. It is noteworthy that when everything stays on the real number line, the amplitude of the marked states only gets larger when the mean vector is pointing in the opposite direction. The mean vector would get smaller and smaller after each iteration until it stops pointing in the opposite direction and starts to point in the same direction as vectors of marked states.

Sequences of applying $O_{\phi}(k)$ followed by the diffusion operator lead to a more complex scenario than the Grover oracle, as both the directions and norm of the amplitude vectors and the mean vectors largely depend on the choice of $O_{\phi}(k)$. The visualization that we discussed in the previous subsection however offers an intuitive picture when and how the subdivided phase oracles leads to amplitude amplification. Since we are interested in using this algorithm to solve optimization problems, we are only interested in the optimal state vector. The optimal state solution will grow larger up to a certain point and then shrink back and repeat this process in cycles. The condition when the vector gets larger after diffusion is only when $\left|\left|2\overrightarrow{\alpha}_{mean}-\overrightarrow{\alpha}_{best}\right|\right|>\left|\left|\overrightarrow{\alpha}_{best}\right|\right|$ where $\overrightarrow{\alpha}$ denotes the amplitude vector. This means the angle between the mean vector and the amplitude vector of the optimal state $\theta(\overrightarrow{\alpha}_{best},\overrightarrow{\alpha}_{mean})$ should be between $\pi/2$ and $3\pi/2$ in order to observe significant amplitude amplification after every iteration of our algorithm. For angles outside this range, amplitude amplification occurs but its magnitude is only marginal. As we will see later, the choice of $k$ affects this angle and hence the level of amplitude amplification.

We begin by considering the objective values to be normally distributed according to the probability density function,

where $\mu$ denotes the mean and $\sigma$ the standard deviation of the distribution, as shown in Fig. 2(a). This is a natural assumption as many instances of NP-hard optimization problems can be transformed into the Ising problem [30]. Such problems can be described by using local interactions between a small number of bits of the entire bit string. This property in turn allows for the distribution of objective values of a randomly generated large instance of such NP-hard problems with local cost term sampled from a single distribution to be well approximated by a normal distribution. This approximation becomes more accurate with increasing size of the problem due to the central limit theorem and the law of large numbers.

Normal distribution is symmetric, which makes it possible for the phase difference between the mean amplitude vector and the optimal solution to be $\pi$, leading to excellent amplification results. In fact, using the visualization technique discussed in subsection IV-A, it is straightforward to observe that the mean amplitude vector and the vector corresponding to the optimal solution $|N-1\rangle$ can be made to always lie on the real axis for appropriately chosen $k$.

Choosing $k$ such that the mean amplitude vector and the solution vector to lie on the real axis is actually the optimal $k$ value. Since the normal distribution is symmetric, it is the case that applying the algorithm does not only amplify the best state $\ket{N-1}$ but it also amplify the worst state $\ket{0}$ to the same probability.

We have demonstrated that optimization problems with normally distributed objective values can be tackled easily by our algorithm. The key property that made this possible was the symmetry of the normal distribution. Real-world optimization problems on the other hand are unlikely to possess such nice property. In this and the following subsections, we evaluate the performance of our algorithm for optimization problems with objective value distributions which are not symmetric. We show that not only do they not pose an obstacle to our algorithm, asymmetry in the distributions works in our favor.

To capture the deviation from normally distributed objective values we now turn to skew normal distributions,

where $\phi_{\text{norm}}(x)$ is the probability density function of the normal distribution given in Eq. (6), and

The parameter $\alpha$ controls the shape of the distribution, as seen in Fig. 2(b)-(c). For $\alpha=0$, $\phi_{\text{skew}}(x;\alpha)$ becomes the normal distribution of Eq. (6), while for $|\alpha|>0$, the distribution in Eq. (7) becomes asymmetric. In the limit of $\alpha\rightarrow\infty$, $\phi_{\text{skew}}(x;\alpha)$ becomes a half-normal distribution.

We observe that as for the case of a normal distribution, there is always an optimal parameter $k$ which amplifies the amplitude of the optimal solution to a significant degree as depicted in Fig 2(e).

We have seen that our algorithm can be applied to optimization problems involving normal and skew normal distributions of objective values. In order to assess the applicability of the algorithm further, we expand our discussion to exponential distribution,

where $\lambda$ is the rate parameter, as depicted in Fig. 2(d). Despite their rather different definitions, all three objective distribution functions described above share a number of important features when it comes to amplitude amplification, which we discuss in the following subsection.

We have seen how Algorithm 1 can be applied to optimization problems with normal, skew normal, and exponential distribution of objective values. In Fig. 2(e), we display how the probability of measuring the optimal value, $P_{\text{solution}}$, gets amplified with every successive application of the subdivided phase oracle $O_{\phi}(k)$ and the diffusion operator $D$. Initially, $P_{\text{solution}}=1/N\approx 0$, as the input size of the optimization problem is set to $N=2^{25}$. We observe that the type of distribution affects both how many iterations are needed to achieve the maximum amplitude amplification, given by $P_{\text{solution}}^{*}$, as well as the value of $P_{\text{solution}}^{*}$. Interestingly, when the objective values are distributed according to the normal distribution, Algorithm 1 yields $P_{\text{solution}}^{*}\approx 0.5$. For the case of the two asymmetric objective value distributions on the other hand, the probability of measuring the optimal value gets amplified more strongly. $P_{\text{solution}}^{*}=0.94$ for the skew normal distribution, and $P_{\text{solution}}^{*}=0.97$ for the exponential distribution.

Figure 2(e) displays the number of iterations needed to achieve maximum amplification of the optimal solution. Extending the number of iterations further reveals that $P_{\text{solution}}$ begins to oscillate as depicted in Fig. 3. This is reminiscent of the behavior observed in amplitude amplification using the conventional binary oracle. Unlike the binary oracle, the oscillations of $P_{\text{solution}}$ display amplitude modulation not observed previously, leading to a number of oscillations of $P_{\text{solution}}$ before the value of $P_{\text{solution}}^{*}$ is reached again. This beating behavior is a consequence of the fact that the subdivided phase oracle introduces complex probability amplitudes into the state vector $|\Psi_{j}\rangle$. This basic pattern is observed for all distributions and tested objective functions. Increasing $k$ in the subdivided phase oracle $O_{\phi}(k)$ leads to decreased frequency of these oscillations.

As discussed in Section IV, in order to obtain the maximum probability $P_{\text{solution}}^{*}$, we have to choose the optimal $k$ in the subdivided phase oracle $O_{\phi}(k)$. Algorithm 1 is sensitive to this choice and deviating from the optimal $k$ rapidly decreases the achievable amplitude amplification. In Fig. 4, we show how the maximum amplified probability $P_{\text{solution}}^{*}$ depends on the deviation of $k$ from its optimal value for normal and skew normal distributions.

In Grover’s algorithm or the usual amplitude amplification algorithm, if the diffusion operator is kept the same, being the inversion around the mean operator $2\ket{\Psi_{0}}\bra{\Psi_{0}}-I$, it is known that in large search space, only $\pi$ phase shift on the solution states are acceptable. And if one were to change the oracle to use phase angle other than $\pi$, one would need to change the diffusion operator to match the angle of the oracle under some constraints as explored in [10, 12]. The same effect can also be seen in our results in Fig 3.

The sensitivity to the angle or the $k$ value is not just for the efficiency in terms of number of iterations but is crucial in order to make algorithm 1 work.

An important observation to make at this point is that the effectiveness of our algorithm is not affected by the size of the input space. This is a desired feature and signifies the applicability of our subdivided phase oracle approach to optimization even for extremely large data sets. Below, we discuss optimization problems which do not share this property and the degree of amplitude amplification diminishes with increasing input space. This will lead to a modified algorithm which overcomes this issue.

We have seen above that Algorithm 1 possesses a number of desired properties when applied to common distributions of objective values. One such property is that its effectivity does not diminish with increasing size of the input space of the optimization problem. In this subsection we demonstrate that this is not always the case and introduce a modification to Algorithm 1 that counteracts this issue.

We focus on the following group of objective functions,

They map each state to a unique object value, therefore we refer to them as injective objective functions. These injective objective functions are not likely to appear naturally in optimization problems in this simple form. However, they serve the purpose of demonstrating an important property of Algorithm 1 that may be encountered when using objective functions not explicitly covered in our manuscript.

The primary quantity that we are concerned about in this subsection is the relative amplified probability of the optimal solution, $P_{\text{solution}}$, with its initial value, $P_{\text{initial}}=1/N$, before the first iteration of Algorithm 1. In particular, we are interested in determining how the ratio $P_{\text{solution}}/P_{\text{initial}}$ behaves for increasing input size space $N$. Figure 5 displays the scaling of this probability ratio as a function of the number of iterations of Algorithm 1 for increasing $N$. Interestingly, we can observe that the ratio $P_{\text{solution}}/P_{\text{initial}}$ converges to a single curve for increasing $N$. This is in stark contrast to behavior observed for normal, skew normal, and exponential distributions where the optimal solution amplitude could be amplified easily independently of the input space size $N$.

One might suspect that we would see a different picture if we fix the objective value ranges but increase the possible data points in between while keeping the density fixed (sampling more from the same density). Instead of mapping $\ket{x}$ to $x$, we map $\ket{x}$ to $x/m$ where $m$ is some constant and our total states then become $mN$ instead of $N$. We would still see the same picture, the highest achievable probability relative to initial $1/N$ approach a certain limit.

Figure 5 shows the behavior of $f_{q}(x)=x^{2}$ but identical observations were made for the remaining injective objective functions as well. In the remainder of this section, we present a modification that overcomes this size-induced limit to amplification.

So far we have only considered applying $O_{\phi}(k)$ with constant $k$ for all iterations of the algorithm. There are no real restrictions that this must be the case, and in fact, we can show that by changing the parameter $k$ to the operator $O_{\phi}(k)$ for each iteration, we can achieve better results and overcome the above mentioned issue. Recall that in Fig 3, the general trend is that the smaller the phase angle we choose, the shorter the period of the oscillating probability. This gives us some intuition that a smaller angle can be used in early iterations to quickly boost the amplitude of the solution state then later use a larger angle which allows it to get past the amplification limit of the smaller angle. An interesting effect of varying the $k$ at each iteration is that it allows the injective objective functions case to get past the negligible boosted probability limit by a single fixed $k$. We show in Fig 6 for injective families the probability of measuring the solution state at each iteration when using a greedy approach. $O_{\phi}$ at each iteration is chosen such that the $P(\ket{N-1})$ is highest by scanning the range of $k$.

Although the greedy approach to dynamically choose $k$ is not the optimal strategy, it serves as one point in favor of evidence that in general even the injective families of objective functions which cannot be boosted via a fixed choice of $O_{\phi}(k)$ are boostable with this amplitude amplification technique.

One way to avoid dealing with the complexity when using the subdivided phase oracle $O_{\phi}$ is to alternate the direction of the rotation for each iteration which can be done by applying $O_{\phi}(k)$ on the even iteration and $O_{\phi}(-k)$ on the odd iteration. This way the mean vector can be tracked easily as it always stays on the same axis throughout all iterations. Although this approach solves the problem of choosing the optimal $k$ since the algorithm performs best when $k$ approaches $0$, the number of iterations requires to amplify the probability grows much quicker than the fixed $k$ method, and the magnitude of the solution state is smaller. One interesting side effect of this approach is that the states with objective value $f(x)$ higher than the mean get larger while those lower than the mean get smaller. This approach of alternating between $O_{\phi}(k)$ and $O_{\phi}(-k)$ was explored in detail in [21] with the help of an interference pattern created by adding one ancilla qubit to select the rotation direction in superposition which can be thought of as doubling the number of amplitude vectors and splitting them into two groups. Having them rotate in opposite directions forces the mean vector to always stay on the real number line.