How can information be preserved if quantum phenomena are uncertain? Firstly, I am a layman with an interest in physics only so please forgive any ignorance I demonstrate here. This question puzzles me and I'm sure there's a good answer. I've heard it said repeatedly when referencing things like the black hole information paradox that information is preserved. This was the impetus for Hawking and his theory on radiating black holes (Edit here - I believe I'm wrong about this in particular, however the two are related regardless of if evaporating black holes are the source of or part of the solution to the information paradox). The general description one gets here is that information is seemingly destroyed when it falls into a black hole, which violates the conservation of information. It's stated in simple terms like the following:
If one were to be able to track the position direction and velocity of every particle in a building, which is blown up, one could effectively run the clock backwards and reconstruct the building.
This seems straightforward enough. Given an input and a deterministic system, you can simply undo what was done using the same rules, but it then clashes with the idea of the inherently uncertain probabilistic nature of the atomic scale. We know this uncertainly exists, and we can see the effects of quantum uncertainly manifest in real world randomness, consider radioactive decay or interference patterns and so on. How then are these two ideas reconcilable? If I can not be certain of the all of the descriptors of a given particle, or indeed get the same numbers twice in a row when measuring location or momentum as it is forbidden by nature itself, I could never perform an experiment which is the equivalent of the aforementioned exploding building. I understand that on the macro scale, things seem predictable and deterministic, presumably because the average of the uncertainty gives the appearance of a deterministic system on a macro scale, or the determinism is otherwise emergent... but if the reality of the situation is that a given particle only has a chance of being at any given location with a specific momentum, it logically follows that one could never reconstruct any object after a state change with absolute certainty. I can see getting very close, but that doesn't really seem to constitute a 'law', like the conservation of information is said to be. What am I missing here?
 A: In quantum mechanics, there are two ways that a the quantum state of a system can evolve: 1) undergoing a reversible unitary evolution, which is what happens when the system evolves on it's own, or 2) undergoing irreversible projection onto a definite outcome when a measurement occurs.
The fact that there are two different kinds of evolutions in the theory, but no principled way to distinguish which evolution counts as "measurement" and which counts as "free evolution" is at the root of the so-called measurement problem, which is a very controversial subject that I don't want to get into here.
In practice, it is usually clear which of the two types of evolution should be used. For example, when a photon goes through a semi-reflective mirror (a beamsplitter), it undergoes reversible unitary evolution, which puts it in a superposition of two different paths. It is also experimentally relatively straightforward to reverse the evolution. What is important is that the inverse evolution does not involve any measurements. If we tried to measure the photon's position as a first step in the reversal process, we would indeed fail for reasons that you seem to grasp. The key is that quantum mechanics allows to reversibly undo time evolution, without ever having to know the state of the system.
Now for the information paradox in black hole evaporation, this is also a case where we would expect the system to evolve unitarily, and not irreversibly as there are no measurements being performed. Hawking's calculation seems to suggest that the evolution in such a case is irreversible. The fact that large black-holes do indeed produce Hawking radiation is pretty well accepted by physicists. However, in the opinion of many people (myself included), the fact that the calculation treats gravity classically does not in itself allow to conclude that the full evaporation process is irreversible. Nevertheless, this is puzzling and points to our lack of understanding about how to treat gravity in the quantum regime.
A: The equations of quantum mechanics are just as deterministic as those of classical mechanics. (Information preservation is slightly stronger than "deterministic", actually. The equations of quantum mechanics are information-preserving in that they are unitary.)
The only thing that is random is quantum measurement. How this randomness arises from unitary equations is an open problem in the philosophy of physics.
Some theories of quantum mechanics postulate that there is something extra that the universe does, besides just obey the unitary equations. These "collapse" theories do not preserve information.
Other theories hold that quantum wave functions only follow the unitary rules and no other rules. These theories, such as "decoherence", try to explain the random results in experiments as apparent randomness, where the information that might seem lost is still there in a "many worlds" interpretation. It is not practically accessible to us, but in principle never destroyed.
So there is no single resolution to your question.
