If the laws and initial state of the universe can be expressed in few enough bits, then all you need to store is a title and a date. Run a simulation of the universe, fast forward to the date the movie was released, use an AI to find a theater playing it, and digitize the tape. It may take longer to run than the current age of the universe, but eventually you’ll get it.
I don't think it is totally inconceivable. It is definitely possible that there are hacks such as compression that would allow a simulator to run at above 100% speed. It also might not need to be 100% accurate -- we might find that running below that threshold still produces an output that is practically indistinguishable from the real events, yet allows it to run.