We propose a physical realization of quantum cellular automata (QCA) using arrays of ultracold atoms excited to Rydberg states. The key ingredient is the use of programmable multifrequency couplings which generalize the Rydberg blockade and facilitation effects to a broader set of nonadditive, unitary and nonunitary (dissipative) conditional interactions. Focusing on a 1D array we define a set of elementary QCA rules that generate complex and varied quantum dynamical behavior. Finally, we demonstrate theoretically that Rydberg QCA is ideally suited for variational quantum optimization protocols and quantum state engineering by finding parameters that generate highly entangled states as the steady state of the quantum dynamics.