Can an RBM solve this Autoencoder example?

I'm currently trying to debug my own RBM implementation by applying it to an autoencoder exercise I've done before. In this exercise I feed 8-dimensional unit vectors to 3 hidden nodes and force the network to learn a compressed binary representation, i.e.:

####### visible ########    ## hidden ##
[1, 0, 0, 0, 0, 0, 0, 0] ->  [0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0] ->  [1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0] ->  [0, 1, 0]
[0, 0, 0, 1, 0, 0, 0, 0] ->  [1, 1, 0]
...                   ...


With the three hidden nodes the network should be able to memorize / distinguish 2^3 = 8 different input vectors. Of course this requires heavy overfitting and the autoencoder only succeeded when I disabled the regularization term in the weight update rule.

Now when I train the RBM on this example, it is only able to reconstruct 3 vectors. All other inputs get scrambled, i.e.:

####### visible ########    ## hidden ##  #### reconstruction ####
[1, 0, 0, 0, 0, 0, 0, 0] ->  [0, 0, 0] -> [1, 0, 0, 1, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0] ->  [1, 0, 0] -> [0, 1, 0, 0, 0, 0, 0, 0] *correct
[0, 0, 1, 0, 0, 0, 0, 0] ->  [0, 0, 1] -> [0, 0, 1, 0, 0, 0, 0, 0] *correct
[0, 0, 0, 1, 0, 0, 0, 0] ->  [0, 0, 0] -> [1, 0, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 0] ->  [0, 1, 0] -> [0, 0, 0, 0, 1, 0, 0, 0] *correct
...                   ...                 ...


At first I thought that I had a bug in my RBM implementation, so I've tried others (e.g. this implementation by edwin chen), but the results were similar.

I've heard that the binary units of an RBM also act as regularizers. Is this the reason why the example doesn't work well? Or should I continue searching for bugs in my code?

I'm not totally sure but yes, binary RBM models comes with a builtin regularizer. When you compare the activation value in one unit with a number sampled from a uniform distribution you're limiting the amount of information this unit can transmit from $[0, 1]$ to $\{0, 1\}$ and this acts as a regularizer.