Is this theory about Universe and information true? I recently saw this video about information and randomness.
At some point, it states that a completely predictable universe would infringe the second law of thermodynamics, because it would imply that the overall information of the Universe would be conserved throughout time, thus leading to a costant entropy Universe. Also, it states that the additional information that is increasing entropy is coming from QM randomness.
I recognize it's a really fascinating theory, but is it true? Is the equivalence between information and entropy sensible?
 A: The relation between entropy and information is well established; indeed, Shannon entropy is the seminal measure of the information in a system.
The other question, about determinacy and information, is more complex, and even more complex yet when extended to the entire universe.  Let us set aside, for now, the fact that quantum mechanics would seem to suggest -- under conventional interpretations -- an inherent indeterminacy.
We'll start from classical thermodynamic entropy: 'Maxwell's Demon' is a hypothetical entity with 'perfect knowledge' of a system, capable of sorting molecules according their energy, but Landauer showed that such a creature, in order to function, would itself have to increase the net entropy. Specifically, if there is a logically irreversible change in information, other degrees of freedom will experience an entropy increase. Naively, think of your computer's CPU getting hot. This means that at a minimum, by churning through our propositions in our 'theory of everything' for this determinist universe, we won't be decreasing the entropy, which is OK by the second law: consider an isolated system that has reached thermodynamic equilibrium, and then consider whether you are willing to accept that the universe may be a closed system.
Quantum mechanics complicates it.  Here, if conventional thought is followed, there is an inherent randomness.  Specifically, if we further accept unitarity (ie the sum of possible probabilities of measurement outcomes is 1, fairly uncontroversial), then we have, thanks to Everett, a proof that the second law is implied (the theorem is independent of his `many worlds' interpretation, which is rather an attempt to explain what the implications are) -- pg 122 here.  
What this tells us, in summary, is that classical thermodynamics is consistent with a determinate universe under some constraints, but the very reason that QM says the universe is not determinate is precisely an explanation of the second law.  Can we infer from this that QM is the sole cause of this?  Under the assumption that QM is a complete theory, then yes.  We know that it is isn't, in the sense that it doesn't tell us everything we would like to know about the world -- but most of the attempts to extend it to include general relativity, for example, and certainly the credible ones, accept the same assumption of unitarity, and the uncertainty principle, and so forth.  If these theories, such as string theory, don't end up introducing another mechanism by which entropy would increase, independent of QM randomness, then that is indeed the cause.
A: There are a lot of misconceptions here so let's take it one step at a time.
The entropy in classical mechanics is called the Gibbs entropy, 
$$S = - k_B \sum_i p_i \ln p_i,$$
where $p_i$ is the probability of some microstate $i$. 
This is essentially the same thing as Shannon entropy for physical systems. With this concept one can view knowing probabilities of something as "information". It is really just a different name for knowledge of probabilities so the more your knowledge of probabilities restricts the possible outcomes the more "information" you have. In this sense one may view entropy as the lack of information - the more entropy a system has the less you know about it.
Please don't be mystified by saying "information" is related to entropy. This is how we define information - via knowledge of probability distributions. 
As an example, say that you have $p_1=1$, $p_2=0$, $p_3=0$ etc. that means that you know that your system is in state $i=1$ with 100% certainty and your "information" about the system is maximal (because you know exactly in what state it is) and therefore the entropy is 0.  
With that out of the way, there are two possible sources of randomness in our Universe,


*

*Randomness of time evolution - meaning that the system evolves in random fashion. This is not the case for closed systems in neither classical nor quantum physics. Therefore simple evolution in time cannot increase entropy in either theory and information is always conserved. 

*Randomness of the initial conditions of the system - This is indeed a fundamental concept in quantum physics, one which you will always have in general.
Now, the above mentioned entropy does not hold in general in quantum physics. Rather one replaces it with its generalization, the von Neumann entropy,
$$ S = - \mathrm{tr}(\rho \ln \rho), $$
where $\rho$ is the density matrix (which encodes both classical and quantum uncertainties about the system). 
Now, if the system is in a so-called pure state, meaning that there is no classical uncertainty about it and is described by a wave function, then the entropy is 0. So you see, only the old idea of classical randomness influences the value of entropy. The new quantum randomness is fundamental. You can't avoid having it, but if you have only quantum randomness then the entropy is still 0. 
The second law of thermodynamics holds for both quantum and classical systems and quantum and classical entropy so the statement "that the additionally [sic] information that is increasing entropy is coming from QM randomness" is not true because it cannot explain why we still see entropy increase even when we count only classical randomness as entropy (von Neumann entropy). In fact, to derive the second law you need to go beyond closed, isolated, systems, but this is another issue. The point is that appealing to quantum physics will not help you to derive the second law.
