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 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.


1 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.


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.