I've been looking at basic quantum algorithms such as the Deutsch-Jozsa algorithm that are able to characterize functions very well and I was wondering if similar approaches exist to characterize quantum states.

Consider the following example: Given a normalized state $\sum_{i=1}^{N} a_i\vert x_i\rangle$, is there some way to check if all the $a_i = 1/\sqrt{N}$ or if there exists some $a_i$ that are different from the others?

My initial lines of thinking were to apply a Hadamard on the state but for large $N$, it's not clear if that approach helps. Do you have any ideas on how to proceed, or is it the case that such problems are not things that quantum computers can help with?

EDIT: I should have emphasized some features of my question better

1) $N$ is large, yet the "unbalancedness" i.e. the variance among the $a_i$ can be small. Hence POVM measurements will succeed in giving me the answer with very low probability.

2) Methods that distinguish between two known non-orthogonal states seem slightly hard to apply since my question is subtly different. I ask if my state is of a specific kind (balanced) or not. Intuitively, my question seems easier to answer.

3) I should have stated it earlier but one can assume that one is allowed $c\ll N$ copies of the state if this helps.


2 Answers 2


It is not possible at an information-theoretic level to do what you want to do.

Let us suppose we have two pure states: $|\phi\rangle$ and $|\psi\rangle$, where $$ |\phi\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N |x_i\rangle $$ and $|\psi\rangle$ is similar to $|\phi\rangle$ but with a few of the coefficients tweaked in some way. Notice that we're fixing just two states, and even if you're promised that you're given one of these two states it will not be possible to determine which one you're given with high probability, under the assumption that $|\phi\rangle$ and $|\psi\rangle$ are close together. (As DaftWullie has suggested, a variant of this problem where $|\phi\rangle$ is fixed and $|\psi\rangle$ is not known ahead of time is certainly no easier than the case in which $|\psi\rangle$ is known ahead of time.)

To keep things simple, let us suppose that we're given $|\phi\rangle$ with probability $1/2$ and $|\psi\rangle$ with probability $1/2$, and we're aiming to maximize the probability of correctly determining which of the two states we were given. A theorem sometimes called the Holevo-Helstrom theorem tells us exactly what the optimal probability of a correct guess is: $$ \frac{1}{2} + \frac{1}{4} \bigl\| |\phi\rangle\langle \phi| - |\psi\rangle\langle \psi| \bigr\|_1, $$ where the norm is the trace norm. Because we're working with pure states, this expression can be simplified to $$ \frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle \psi | \phi \rangle|^2}. $$ This is for the optimal measurement; you cannot do any better than this, no matter what you try to do, assuming you start with one of the two states selected at random and by honest means do your best to determine which state you were given.

Now, the question suggests that the "unbalancedness," or variance among the coefficients of the states, is small. With that in mind we could define $$ \varepsilon = 1 - |\langle \psi | \phi \rangle|^2 $$ and regard $\varepsilon$ as a small (but nonnegative) real number. This means that our probability of a correct guess is $$ \frac{1}{2} + \frac{\sqrt{\varepsilon}}{2}, $$ which is not much better than just randomly guessing (which yields a correct answer with probability 1/2).

If you assume that you are given $k$ copies of $|\phi\rangle$ or $k$ copies of $|\psi\rangle$, the calculation is exactly the same, except replacing the states with $|\phi\rangle^{\otimes k}$ and $|\psi\rangle^{\otimes k}$, also as DaftWullie has suggested. We can see how this will affect the optimal correctness probability: it now becomes $$ \frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle \psi | \phi \rangle|^{2k}}. $$ Notice that we're placing no constraints on the measurements for distinguishing the two cases -- they could be arbitrarily correlated across the $k$ copies of the states.

We can compare this optimal correctness probability with the one-shot case by using the inequality $$ 1 - |\langle \psi | \phi \rangle|^{2k} \leq k \bigl(1 - |\langle \psi | \phi \rangle|^2\bigr). $$ To prove this inequality, notice that it is trivial if $|\langle \psi | \phi \rangle| = 1$, and otherwise we can use the crude estimate $$ \frac{1 - |\langle \psi | \phi \rangle|^{2k}}{1 - |\langle \psi | \phi \rangle|^2} = 1 + |\langle \psi | \phi \rangle|^2 + \cdots + |\langle \psi | \phi \rangle|^{2(k-1)} < k $$ for the case $|\langle \psi | \phi \rangle| < 1$. We find that the optimal correctness probability is upper-bounded by $$ \frac{1}{2} + \frac{\sqrt{k\varepsilon}}{2}. $$ So, if $k$ is considered to be much smaller than $N$, and $\varepsilon$ is on the order of $1/N$, then we're still not doing much better than randomly guessing.


There are many different variants depending on what it is precisely that you want to achieve (note, this was written before recent edits, although I think there is still value/relevance in this more general answer).

The closest analogy to the Deutsch-Jozsa algorithm is probably to say that you're given one of two states, and you want to know which you've been given (with maximum probability). If those two states are orthogonal, you can perfectly distinguish them just by using projective measurements, two of which project onto those particular states. Beyond the orthogonality assumption, there are ways of selecting the measurement to maximise the probability of distinguishing them. For more details, see this answer and this one.

On the other hand, if I take your question literally (which one certainly should given the edits to the question), then probably the best strategy is to define the projectors $$ E_1=|\psi\rangle\langle\psi|^{\otimes c}\qquad E_2=\mathbb{I}-E_1, $$ where $|\psi\rangle$ is the uniform superposition state ($a_i=1/\sqrt{N}$), and $c$ copies are allowed. If you get the measurement result $E_1$, you learn essentially nothing. However, if you get the answer $E_2$ (which may well happen with low probability if the $a_i$s are close to uniform), you know that the state definitely was not $|\psi\rangle$, so some of the amplitudes were different.

  • $\begingroup$ Thank you very much for the answer. I apologize for not emphasizing the features of my question better but I have edited the question to make it clearer. POVMs would succeed with very low probability in my case and I'm not sure how non-orthogonal distinguishing measurements work (since in my case the unbalanced state can be unbalanced in many ways - it isn't one specific unbalanced state). Your answer is, of course, completely correct but I will leave it open for a bit to see if a more efficient solution is possible. Thank you $\endgroup$ Nov 6, 2018 at 10:26
  • 1
    $\begingroup$ @user1936752 I believe that, for a single copy, this is the best that you can do. For multiple copies, you just update $E_1=|\psi\rangle\langle\psi|^{\otimes c}$. This is quite effective at improving your success probability. $\endgroup$
    – DaftWullie
    Nov 6, 2018 at 10:33
  • 1
    $\begingroup$ @user1936752 I suppose one thing to take away from the first part of my answer is that, even if you fix just one state (which is certainly easier than your stated problem), the probability of success is very low. $\endgroup$
    – DaftWullie
    Nov 6, 2018 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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