How to increase the probability of successful measurement to find out the largest amplitude?

Question

I have built a state $$A|0\rangle = |\Psi \rangle = \sum _n c_n |n\rangle$$ Where $A$ is a circuit. And I need to known, where is the largest $|c_n|$.

I find out that, I can simply do many measurements to find out which one is the largest. However, in my case $c_n$ are close to each other, so many measurements are needed, which means many times should $A$ been excuted.

So, my question is, given a state $\sum _n c_n |n\rangle$, is there an algorithm to amplify the ampltude for the largest $|c_n|$ without knowning $n$. I think this is not the case of amplitude amplification, is it?

Or, on the other hand, is there an algorithm to reduce the query of $A$ to find out the $n$ such that the corresponding $|c_n|$ is the largest?

I need your help, thank you very much!

Answer 1

There can be no efficient algorithm for doing this. Consider the complexity class PP: it contains the problems for which there is a polynomial time algorithm that succeeds with probability strictly higher than 1/2. It is an extremely powerful complexity class, containing not only BQP but also MA (and therefore NP), which is believed not to be contained in BQP.

If you could efficiently find the component with highest amplitude, you would be able to solve any problem in PP. You'd run the polynomial time algorithm coherently to get the decision variable with the correct amplitudes in a single qubit, and then then do the magical step of extracting the one with highest amplitude.

I don't think you can do any better than tomography. Even then the complexity will be unbounded, because as you have notice you'll need more measurements the closes the coefficients are.

Answer 2

The problem is ill-defined. What if the largest $|c_n|$ is not unique? What is the largest $|c_n|$ if you have a uniform superposition?

These issues aside, let's start with a simpler situation. First, assume that the dimension we are working with is $2^N$. Let's suppose for a second that we actually know the state $|n^*\rangle$ that corresponds to the largest amplitude $c_n^*$. Then we could use the Grover algorithm and perform $O\left( \sqrt{2^N}\right)$ iterations to boost the amplitude of $c_n^*$ even further. Note that even when we have information about $|n^*\rangle$, it still takes an exponential amount of Grover iterations. Not much better than performing exponentially many measurements to learn all $|c_n|^2$.

However, I think we could do a mix of amplitude amplification and measurement to get some speed up.

The simplest way I could think of is to boost the magnitudes of the states which occur with higher probability. In other words, states with larger $|c_n|^2$ will get their coefficients boosted even further through amplitude amplification. This is somewhat similar to the Markov Chain Monte Carlo methods.

The algorithm goes like this:

1. We know that the states with larger amplitudes have a higher probability of being measured. So we sample the state $|\Psi\rangle$ only once and obtain a state $|n_0\rangle$.
2. Next, we use $|n_0\rangle$ as a marked item in the Grover algorithm. Specifically, we perform a single Grover iteration on $|\Psi\rangle$. This will boost the amplitude of $|n_0\rangle$. Mathematically, we perform: $$ |\Psi_1\rangle = G_{|n_0\rangle}|\Psi\rangle, $$ where $G_{|n_0\rangle}$ is a single Grover iteration with marked item $|n_0\rangle$.
3. Measure $|\Psi_1\rangle$ once and obtain $|n_1\rangle$.
4. Using $|n_1\rangle$ and $|n_0\rangle$ compute $$ |\Psi_2\rangle = G_{|n_1\rangle}G_{|n_0\rangle}|\Psi\rangle.$$
5. Measure $|\Psi_2\rangle$ and obtain $|n_2\rangle$.
6. We keep repeating this process until the iteration budget is depleted or the same state is measured too many times in a row.

Essentially, the above algorithm boosts the amplitudes of the states that already have large $|c_n|^2$.