Is there a quantum algorithm allowing to determine the state with the highest probability of occurring (i.e. highest square amplitude), more efficiently than repeatedly measuring and estimating a histogram?


Yes. It is, for instance, part of Grover's algorithm and to be precise it is the 'Amplitude Amplification' part. $2| \psi \rangle \langle \psi | - I$, which will increase the amplitudes by their difference from the average

  • $\begingroup$ I don't see how that answers the question. $\endgroup$ – splinter123 Sep 25 at 13:37

It looks like you want an algorithm that, given a state of the form $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$ with $|\alpha|\ge|\beta|$, gives back $|0\rangle$ with probability greater than $|\alpha|^2$.

I don't think this is possible. Indeed, say such a mapping $\mathcal E$ existed. This $\mathcal E$ must be such that the probability of finding $\mathcal E(\psi)$ in $|0\rangle$, that is, $\mathrm{Tr}[\mathbb P_0\mathcal E(\psi)]$, is greater than $|\alpha|^2$ if $|\alpha|\ge|\beta|$, while at the same time $\mathrm{Tr}[\mathbb P_1\mathcal E(\psi)]\ge |\beta|^2$ when $|\beta|\ge|\alpha|$. In other words, this map would have to satisfy \begin{aligned} \mathrm{Tr}[\mathbb P_0\mathcal E(\psi)]&\ge |\alpha|^2,\quad\text{if }|\alpha|\ge1/2\\ \mathrm{Tr}[\mathbb P_0\mathcal E(\psi)]&\le |\alpha|^2,\quad\text{if }|\alpha|\le1/2. \end{aligned} Note that I'm using the shorthand notation $\mathbb P_\psi\equiv|\psi\rangle\!\langle\psi|$ here.

Consider how such a $\mathcal E$ would have to act on the input $|\psi\rangle=|0\rangle$. The only way to satisfy the above relations is to have $\mathcal E(\psi)=\mathcal E(\mathbb P_0)=\mathbb P_0$, and similarly $\mathcal E(\mathbb P_1)=\mathbb P_1$. But this, by linearity, fully characterises $\mathcal E$, forcing it to equal the identity operation.

In other words, no, you cannot have an algorithm which magically amplifies the amplitude of the state with the largest probability.

Note that this argument relies on the fact that $\mathcal E$ cannot contain knowledge about the state to be amplified. If you instead ask for an algorithm which amplifies the amplitude of a target state, then this is possible, and it's called amplitude amplification, as has already been mentioned in the other answers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.