Fully Homomorphic Encryption over the Integers - perform an operation on an encrypted data
It's actually straight-forward; we'll assume that all the inputs are either encrypted versions of 0, or encrypted version of 1; then:


We can replace an AND gate with just an FHE multiplication of the two inputs:

$$AND(x,y) = x*y$$

Where $*$ is our Homeomorpic multiplcation operation.  This obviously evaluates to an encrypted 1 if both of the inputs are encryped 1's; and an encrypted 0 if either of the inputs are encryped 0's
To replace an exclusive or gate, we encrypt the constants 1 and -1, and then compute:

$$XOR(x,y) = x*(1 + (-1 * y)) + y*(1 + (-1 * x))$$

Where + is our homeomorphic addition operation, and 1 and -1 stand for our encrypted constants.
To replace an or gate, we take our encrypted 1 and -1 constants, and compute:

$$OR(x,y) = 1 + -1 * (-1 + x) * (-1 + y)$$
To replace a NOT gate (that doesn't appear in your circuit, but does come up in others), we compute:

$$NOT(x) = 1 + -1 * x$$


It is easy to see that, in all cases, if the inputs are restricted to encrypted 0 and encrypted 1, the result is either an encrypted 0 or an encrypted 1 (and which will be the logical result of the operation).  Obviously, things can be simplified somewhat if our FHE operation includes a subtraction operation.

As for the number of operations used, we just translate each gate and count them up.  On the other hand, this construction is really a proof that just addition and multiplication suffice to be complete operations (that is, given just those two operations, we can compute anything); when you look at operation count, it turns out to be quite inefficient.