# How to identify index $k$ when presented with a state $\vert \psi_k\rangle$ from orthonormal states $\{\vert \psi_i\rangle\}_{1\le i\le n}$?

A passage on page 86 of Quantum Computation and Quantum Information by Michael A. Nielsen & Isaac L. Chuang has been bugging me for a while,

Suppose the states $$\vert \psi_i\rangle$$ are orthonormal. Then Bob can do a quantum measurement to distinguish these states, using the following procedure. Define measurement operators $$M_i\equiv \vert \psi_i\rangle\langle\psi_i\vert$$, one for each possible index $$i$$, and an additional measurement operator $$M_0$$ defined as the positive square root of the positive operator $$I-\sum_{i\ne0}\vert \psi_i\rangle\langle\psi_i\vert$$. These operators satisfy the completeness relation, and if the state $$\vert \psi_i\rangle$$ is prepared then $$p(i)=\langle\psi_i\vert M_i\vert\psi_i\rangle=1$$, so the result $$i$$ occurs with certainty. Thus, it is possible to reliably distinguish the orthonormal states $$\vert \psi_i\rangle$$.

Here Bob is presented with a state $$\vert \psi_i\rangle$$ from orthonormal states $$\{\vert \psi_i\rangle\}_{1\le i\le n}$$ and his task is to identify the index correctly.

The setup seems very strange to me. When Bob "measures" the state $$\vert \psi_i\rangle$$, shouldn't the state collapse to a computational basis assuming the measurement was done in it with probabilities given by the coefficients? And what does "$$i$$ occurs with certainty" even mean? Does it mean that $$\vert \psi_i\rangle$$ will always be from the given set? But then that's obvious since that was stated in the setup. And also, I don't see how Bob has even correctly identified the index at all.

It seems to me that there's a gap in my understanding of Postulate 3 which states the mathematical definition of quantum measurement. Any guidance would be helpful. Also, I wanna add that I'm not from a physics background. Thank you.

Bob's task is just to say which state he received, not to actually produce a particular state. So it doesn't really matter what the post-measurement state is.

When Bob "measures" the state $$|\psi_i\rangle$$, shouldn't the state collapse to a computational basis assuming the measurement was done in it with probabilities given by the coefficients?

The measurement is not* being done in the computational basis, the measurement operators are explicitly defined as $$\{M_i\}_i$$ where $$M_i = |\psi_i\rangle \langle \psi_i |$$. These operators are all orthogonal projectors that sum to the identity and hence form a valid measurement. By the measurement postulate we have that if Bob was sent $$|\psi_i \rangle$$ and the measurement gave outcome $$i$$ then the post-measument state is $$\frac{M_i^{1/2} |\psi_i\rangle}{\| M_i^{1/2} |\psi_i \rangle \|} = \frac{|\psi_i \rangle \langle \psi_i |\psi_i\rangle}{\| |\psi_i \rangle \langle \psi_i |\psi_i \rangle \|} = |\psi_i \rangle.$$

And what does "𝑖 occurs with certainty" even mean?

This means suppose that Bob is given the state $$|\psi_i \rangle$$ and performs the measurement corresponding to the operators $$\{M_i \}_i$$. Then with probability $$1$$ he will get the outcome $$i$$. To see this we just use the Born rule: the probability getting outcome $$j$$ given he received the $$i$$-th state is \begin{aligned} p(j|i) &= \mathrm{Tr}[ M_j |\psi_i \rangle \langle \psi_i |]\\ &= \mathrm{Tr}[ |\psi_j \rangle \langle \psi_j |\psi_i \rangle \langle \psi_i |] \\ &= \delta_{ij} \end{aligned} where $$\delta_{ij}$$ equals $$1$$ if $$i=j$$ and zero otherwise.

*Really we can choose any basis to be the computational basis so this is up to however you define computational.

I'm also not a physicist so I don't really know what goes on in the lab when an experimentalist measures a quantum state. But fortunately, one of the great things about quantum information in my opinion, is that the theory is abstracted enough such that we do not necessarily need to know such details in order to be able to do meaningful things. A measurement (for me) is just some abstract box which is labelled by a set of measurement operators $$\{M_i\}$$ where the $$M_i$$ satisfy $$0 \leq M_i \leq I$$ and $$\sum_i M_i = I$$. When I measure some state $$\rho$$ with the measurement $$\{M_i\}_i$$ I send it into this box. After sending it into the box, the box responds with a piece of classical information which is the measurement outcome. The list of possible outcomes that it can choose from are defined by the indexes of the measurement operators. It chooses the outcome randomly, it doesn't matter for this exposition exactly how it chooses but it does so and it will, with probability $$p(j)$$, tell me that it measured the outcome $$j$$. The probability with which it reports the outcome $$j$$ is given by the Born rule, $$p(j) = \mathrm{Tr}[M_j \rho].$$ Some measuring devices may also output a post-measurement state and one rule for which state comes out is that when the measuring device outputs the outcome $$j$$ the state after measurement is $$\frac{M_j^{1/2} \rho M_{j}^{1/2}}{\mathrm{Tr}[M_j \rho]}.$$

• can you clarify what you mean by "measurement gave outcome $i$"? And if Bob was given $\vert \psi_i\rangle$, why does the state remain the same even after measurement? – Jamāl Nov 9 '20 at 17:23
• I guess my real doubt is which operator from $\{M_j\}_j$ does Bob choose to perform the measurement to know the fixed index $i$? – Jamāl Nov 9 '20 at 17:44
• @Jamāl I've added to my answer to try and clarify the issues you raised in your comments. – Rammus Nov 9 '20 at 20:16
• I think your black box interpretation will enable me to proceed for now(hope it won't cause me any trouble down the text). I do have a few queries regarding the response. Firstly, what does $0 \leq M_i \leq I$ mean? And whats the difference between outcome and post-measurement state? My last doubt was about the black box itself(how $M_j$'s operate on $\vert \psi_i\rangle$) but I guess I shouldn't worry about it for now. – Jamāl Nov 10 '20 at 17:19
• I'll be asking the question "whats the difference between outcome and post-measurement state?" separately since it steers away from the main question and is another of my deep seated doubts. – Jamāl Nov 11 '20 at 7:03

Here note that $$i$$ is fixed. Now, a measurement need not be in the computational basis (perhaps this is the gap in your understanding, there are many different orthonormal bases for a Hilbert space, just note that each nontrivial unitary operator gives a change of orthonormal basis) and so when Bob measures $$|\psi_i\rangle$$ with the positive operator $$|\psi_i\rangle\langle \psi_i|$$ the resulting state is $$|\psi_i\rangle$$ with probability $$1$$ (this is exactly by postulate 3). Also you should think about a measurement as a function that ultimately gives some outcome, it is convenient to think about outcomes as labels on an orthonormal basis for the Hilbert space, so in this case we would get the outcome $$i$$.

• How does Bob know with which operator to measure $\vert \psi_i\rangle$ beforehand? Ultimately that's what Bob wants to figure out right? – Jamāl Nov 9 '20 at 16:20
• You don't choose which operator to apply. You have an Observable whose eigenstates, in this case, are associated with $|\psi_{i}\rangle$. The Observable doesn't determine the measurement results. The projectors associated with it's eigenvalues do. So if $|\psi_{i}\rangle$ is an eigenstate of an observable, it will be obtained with probability 1. – GaussStrife Nov 9 '20 at 16:24
• He doesn't, beforehand $i$ it completely unknown to Bob. In general discriminating between unknown quantum states is very difficult, this is called quantum state discrimination and you can read more about it. – Condo Nov 9 '20 at 16:25
• @GaussStrife i'll have to look at what Observable means and also the association with eigenstates. Thanks for the direction. – Jamāl Nov 9 '20 at 17:29
• @Condo I still don't get it entirely. "so when Bob measures $|\psi_i\rangle$ with the positive operator $|\psi_i\rangle\langle \psi_i|$ the resulting state is $|\psi_i\rangle$", i don't get how Bob has come to know the index with this process. There's a fixed $i$ that Bob needs to figure out. How does Bob know to measure using the operator $\vert \psi_i\rangle\langle\psi_i\vert$? – Jamāl Nov 9 '20 at 17:36

Perhaps it's more illuminating to look at how the measurement is made.

Since the set of states $$\{|\psi_i\rangle\}_{1\le i\le n}$$ is not assumed to form a complete basis, we need to first complete them. Assume that the dimension of the Hilbert space is $$d \ge n+1$$, and define states $$|\psi_{n+1}\rangle,|\psi_{n+2}\rangle,\ldots,|\psi_{d}\rangle$$ so that the set $$\{|\psi_i\rangle\}_{1\le i\le d}$$ is a complete basis. This can always be done, for example with the Gram-Schmidt procedure.

We want to do a measurement in the basis $$\{|\psi_i\rangle\}_{1\le i\le d}$$, but we cannot do that, we can only make a measurement in the computational basis $$\{|i\rangle\}_{1\le i\le n}$$. This is always the case in quantum computing, and most experimental setups: there is one fixed basis in which the measurement is made, and it is difficult or impossible to measure in different basis.

What we do then is apply the unitary $$U = \sum_{i=1}^d |i\rangle\langle \psi_i|$$ to his initial state, and then make a measurement in the computational basis. It is easy to check that $$U$$ is in fact a unitary, as $$U^\dagger U = U U^\dagger = I$$, so it is always possible to implement it. How to implement it, and how difficult it is, depends of course on the specific set $$\{|\psi_i\rangle\}_{1\le i\le d}$$.

Now suppose the initial state is one of these states, say $$|\psi_3\rangle$$. What happens? Bob applies $$U$$ to it, and gets $$U|\psi_3\rangle = |3\rangle$$. Now he measures $$|3\rangle$$ in the computational basis, and the result will be 3 with certainty. In this way he can identify the index correctly, and it is easy to see that it holds for any possible index.

With this procedure the probability of outcome $$i$$ is given by the measurement operators defined in the question: $$M_i := |\psi_i\rangle\langle\psi_i|$$ for $$1\le i \le n$$, and $$M_0 := \sum_{k=n+1}^d |\psi_k\rangle\langle\psi_k| = I-\sum_{k=1}^n |\psi_k\rangle\langle\psi_k|.$$ The post-measurement state will not be given by them, though, as they give a post-measurement state in the set $$\{|\psi_i\rangle\}_{1\le i\le d}$$ , but the procedure here gives one in the computational basis.

• I don't see how the unitary transformation relates to measurement here(Do we absolutely need to use it to figure out the index?). I understand the math that you've described here. However i have a few queries. Firstly, why did you assume that $\{|\psi_i\rangle\}_{1\le i\le n}$ forms a basis for the system? Second, I have understood that measurement need not be made in the computational basis. So here, why are you performing measurement with respect to the computational basis? – Jamāl Nov 10 '20 at 16:44
• Lastly, can you guide me on how the measurement is performed with the measurement operators $\{M_j\}_{j}$ as given in the problem statement to figure out the correct index $i$? I know it's a lot to ask but I'm getting bogged down with these small chips in my understanding. Your help would be much appreciated. – Jamāl Nov 10 '20 at 16:45
• Oh, I missed that the states are not assumed to form a complete basis, I'll edit the answer accordingly. I assumed that the measurement is done in the computational basis because I thought it would be more clear and it is usually the case in real experiments. As you noticed, it doesn't need to be like this. – Mateus Araújo Nov 10 '20 at 19:59
• I shall be coming back to your answer as i continue with my textbook. It has definitely helped clear some doubts i had. Thank you. – Jamāl Nov 11 '20 at 9:22