Just to make sure I'm not completely confused here: "Information can't be lost" and "you can't arrive to the same state of the universe through two different paths" are two ways to state exactly the same thing, right? Regardless of the the details of the rest of your physics (though you do need various notions to build up that far - time, with at least a past and a present, the ability to call states the "same" or not, etc.)

For instance, in cellular automata, the way that you would state that same concept is "the update function is injective". In our universe's physics, AIUI injectivity is involved somewhere in the definition of unitarity.