# Label function for a QNN designed to classify bit strings

The paper can be found https://arxiv.org/pdf/1802.06002.pdf here. They say that for each binary label function $$l(z)$$ where $$l(z)=−1$$ or $$l(z)=1$$, there exists a unitary $$U$$ such that, for all input strings $$z=z_0z_1...z_{n−1}$$ (where each $$z\in \{−1,1\}$$), The predicted output is defined as, $$$$ where $$Y_{n+1}$$ is the Pauli y operator on the last qubit. loss is defined as $$loss(~θ, z) = 1 − l(z)\langle z, 1|U^\dagger ( θ )Y_{n+1}U( θ )|z, 1>$$

In Representation section it is said that, Before discussing learning we want to establish that our quantum neural network is capable of expressing any two valued label function. There are 2n , n-bit strings and accordingly there are 22n possible label functions l(z). Another operator is defined as following, $$U_l |z, z_{n+1}\rangle = e^{il(z) π X_{n+1}/4}|z, z_{n+1}\rangle$$ Further $$l(z)$$ is obtained as following, $$\langle z, 1|U^\dagger_l Y_{n+1}U_l|z, 1\rangle = l(z)$$ I do not understand what $$l(z)$$ exactly is(true label I believe) and how there are 22n possible functions for it.

Yes, $$l(z)$$ is the true label, and so $$l$$ is the target function that you want to learn in order for the machine learning model to be correct. The set of functions $$l$$ that the model is capable of learning describes the expressiveness of the classifier, and they use the construction of $$U_l$$ to argue that there is a quantum circuit composed of two-qubit gates that can learn to represent any possible binary function on finite strings $$l: \{0,1\}^n\rightarrow \{-1, 1\}$$ and is therefore highly expressive.
Note that the quantum circuit predicts a label of $$\hat{y} = \langle z, 1|U^\dagger (\theta)Y_{n+1}U(\theta)|z, 1\rangle$$, and the goal of training circuit to find a set of $$\theta$$ such that $$\hat{y} = l(z)$$ as often as possible. You can see that the loss function provided is minimum for $$\hat{y} = l(z)$$ and maximum for $$\hat{y} = -l(z)$$, and from learning theory we know that minimizing this loss on a sample of possible datapoints ("empirical risk minimization") will often result in a classifier that generalizes well to unseen datapoints.
The reason why there are $$2^{2^n}$$ possible functions for $$l$$ is because there are $$2^n$$ possible length-$$n$$ bitstrings, and you want to count all of the ways you can assign one of two labels to each one. Say you want to design an arbitrary $$l$$: There are $$2$$ ways to label the string $$0\dots 00$$, times $$2$$ possible ways to label the string $$0\dots 01$$, times $$2$$ possible ways to label $$0 \dots 10$$ and so on. Multiplying out the possibilities you get $$\underbrace{2 \times 2 \times \dots \times 2}_{2^n} = 2^{2^n}$$ possible labeling $$l$$ schemes to choose from.