# Does post selection of a qubit introduce non-linearity?

Problem

I have a multi-qubit state $$\lvert \psi \rangle$$ and an ancilla qubit $$\lvert 0 \rangle$$ that I use to extend my state, getting the new state $$\lvert 0\rangle \otimes \lvert \psi \rangle$$.

Suppose now I apply a generic unitary operation on this state and get a new state

$$\lvert \phi \rangle = \hat{U}\big(\lvert 0\rangle \otimes \lvert \psi \rangle\big)$$

which can be rewritten as

$$\lvert \phi \rangle = \lvert 0 \rangle \otimes\lvert a\rangle + \lvert 1 \rangle \otimes\lvert b \rangle$$

say I measure the first qubit and accept the remainder of the state only if the measurement outcome is $$0$$. Then, overall, I am implementing the transformation

$$\lvert \psi \rangle \longrightarrow \lvert a\rangle$$

Question

Can this transformation be non-linear in general? In other words: is there a matrix $$\hat{B}$$ such that $$\lvert a \rangle = \hat{B}\lvert \psi\rangle$$?

## Linearity before normalization

Yes this map is linear (up to normalization) if we don't care if the output of the map is normalized (i.e., the output is a vector but not a valid quantum state). To see it note that you can view it as a composition of three linear maps:

1. Embedding $$|\psi\rangle \to |0\rangle \otimes |\psi\rangle$$ This can be viewed as an application of the linear map $$V = |0\rangle \otimes I.$$
2. Transformation $$|0\rangle \otimes |\psi\rangle \to |0\rangle \otimes |a\rangle + |1\rangle \otimes |b\rangle$$ This involves the application of the linear map $$U$$ specified in the question.
3. Projection and removal of ancilla $$|0\rangle \otimes |a\rangle + |1\rangle \otimes |b\rangle \to |a\rangle$$ This can be viewed as action of the linear map $$W = \langle 0| \otimes I.$$

Composing all three maps to get $$WUV$$ we find that $$WUV |\psi\rangle = |a\rangle,$$ but again I stress that $$|a\rangle$$ is not necessarily a normalized vector.

## But what if I want a normalized vector?

Well so now we want the stronger condition that the map $$|\psi\rangle \to \frac{|a\rangle}{\sqrt{\langle a | a \rangle}}$$ is linear. Unfortunately this is no longer the case as renormalization is an inherently nonlinear transformation.

This is relatively immediate from the definition of renormalization as the map $$|a \rangle \to \frac{|a\rangle}{\sqrt{\langle a | a \rangle}}.$$ If this were linear then we should have that $$2 |a\rangle = |a\rangle + |a \rangle \to \frac{|a\rangle}{\sqrt{\langle a | a \rangle}} + \frac{|a\rangle}{\sqrt{\langle a | a \rangle}} = 2\frac{|a\rangle}{\sqrt{\langle a | a \rangle}}$$ but this can never be the case because the output of the map is always normalized and hence cannot be twice a normalized vector (which would not be normalized).

Moreover, it is clear this normalization map is not defined at the origin as you end up dividing by the norm of the $$0$$ vector which is $$0$$. Recall all linear maps satisfy $$M 0 = 0$$. Note that this case is relevant to the question. Imagine the unitary $$U$$ in the question is of the form $$U = X \otimes I$$ where $$X$$ is the Pauli X matrix. The resulting state after the application of the unitary $$U$$ is then $$|1\rangle \otimes |\psi\rangle$$ which when we perform the projection in step $$3$$ we end up with the $$0$$ vector. At which point the normalization is no longer well-defined.

• The map you have specified is not unitary, though, as it increases the norm of the state. Ahh, unless you assume $|a\rangle$ and $|b\rangle$ are not normalized, yes that is fine, but I think one should be cautious about this answer in the context of quantum states May 5 at 19:09
• This answer provides a nice breakdown of the operation in question, but unfortunately feels incomplete. Please consider adding step 4: renormalization. Its absence affects the conclusion and frankly skips over the most interesting part :-) For example, steps 1-3 are of course all linear, but 4 not only fails to be linear but fails to be a continuous and in fact even a total function (here "total" means "defined everywhere in its domain"). These properties of post-selection have important implications, both in theory (e.g. in computational complexity) and in practice (e.g. in error mitigation). May 5 at 20:17
• @AdamZalcman I stressed several times in the answer that this linear map does not preserve the norm. Moreover the way that the unitary transformation is defined in the question above (which I copied) is also implicit that $|a \rangle$ is not normalized and hence I interpreted the question actually with this lack of normalisation (which I mention). May 5 at 21:45
• @QuantumMechanic It is written that the map does not preserve the norm. The original question also does not ask for a unitary transformation but just linear. May 5 at 21:48
• @AdamZalcman Added a short discussion on the nonlinearity of renormalization. May 5 at 22:36

This transformation is almost linear, but normalization makes it non-linear in general. The state update rule following a generalized measurement on some state $$\rho$$ is $$\rho\to \frac{A_i\rho A_i^\dagger}{\mathrm{Tr}(A_i\rho A_i^\dagger )}.$$ For a pure state, that looks like $$|\psi\rangle\langle\psi|\to \frac{A_i|\psi\rangle\langle\psi| A_i^\dagger}{\mathrm{Tr}(A_i |\psi\rangle\langle\psi| A_i^\dagger )},$$ which looks like the linear transformation $$|\psi\rangle\to A_i|\psi\rangle$$. However, normalization is not linear. The pure state in question transforms as $$|\psi\rangle\to A_i|\psi\rangle/\sqrt{P_i(\rho)}$$, where $$P_i(\rho)=\mathrm{Tr}(A_i |\psi\rangle\langle\psi| A_i^\dagger )=\langle \psi|A_i^\dagger A_i|\psi\rangle$$ is the probability of obtaining measurement result $$i$$.

What does it mean to not be linear? A state $$p\rho+(1-p)\sigma$$ does not transform into a combination of the transformations of $$\rho$$ and $$\sigma$$. To wit, $$p\rho+(1-p)\sigma\to\frac{A_i[p\rho+(1-p)\sigma]A_i^\dagger}{\mathrm{Tr}\{A_i[p\rho+(1-p)\sigma]A_i^\dagger\}}=\frac{pA_i\rho A_i^\dagger+(1-p)A_i\sigma A_i^\dagger}{p\mathrm{Tr}(A_i\rho A_i^\dagger)+(1-p)\mathrm{Tr}(A_i\sigma A_i^\dagger)},$$ which is emphatically different from $$p\frac{A_i\rho A_i^\dagger}{\mathrm{Tr}(A_i\rho A_i^\dagger)}+(1-p)\frac{A_i\sigma A_i^\dagger}{\mathrm{Tr}(A_i\sigma A_i^\dagger)}.$$

Overall, the main idea is that the updated state must be normalized, and the normalization factor is not a linear function of the state because it shows up in the denominator (i.e., even though $$P_i(\rho)$$ is a linear function of $$\rho$$, the factor $$1/P_i(\rho)$$ that appears is not a linear function of $$\rho$$). This is true for any $$A_i$$.