Theoretically, QNNs don't need backpropagation exclusively to train. See https://pennylane.ai/qml/glossary/parameter_shift.html to understand parameter shift rule. If you are willing to do a deeper dive, check out this paper: https://arxiv.org/abs/2105.00080 on Quantum GANs to get another sense of how the classical and quantum worlds diverge.

You also have to understand that quantum data is not the same as classical data. So your O(1) and O(n) are not really sensible in this argument. For more context, read quantum state preparation papers, and data loading papers (just google). You could also

Will any of this ever be feasible? Probably. Billions of dollars are being sunk in QEC and Hardware RnD. Some of the sharpest minds are working on it. Even if nothing works out, we at least know a new way to do math :D