Label function for a QNN designed to classify bit strings

Question

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, $$<z, 1|U^\dagger ( θ )Y_{n+1}U( θ )|z, 1>$$ 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 2ⁿ , n-bit strings and accordingly there are 2²ⁿ 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 2²ⁿ possible functions for it.

Answer 1

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.