We introduce several probabilistic quantum algorithms that overcome the normal unitary restrictions in quantum machine learning by leveraging the linear combination of unitaries (LCU) method. We cover three distinct topics, beginning with quantum native implementations of residual networks (ResNets). We demonstrate that while residual connections between layers of a variational Ansatz can prevent barren plateaus in models, this approach is accompanied by a trade-off in success probability. Second, we implement a quantum analogue of average-pooling layers from convolutional networks using single-qubit-controlled basic arithmetic operators and show that the LCU success probability remains stable for the Modified National Institute of Standards and Technology (MNIST) database. This method can be further generalized to convolutional filters, while using exponentially fewer controlled unitaries than previous approaches. Finally, we propose a general framework for applying a linear combination of irreducible-subspace projections on quantum encoded data for any finite group. This enables a quantum state to remain within an exponentially large space, while selectively amplifying specific subspaces relative to others, alleviating simulability concerns that arise when fully projecting to a polynomially sized subspace. We demonstrate improved classification performance for partially amplified permutation-invariant encoded point-cloud data when compared to noninvariant or fully permutation-invariant encodings. We also demonstrate a novel rotationally invariant encoding for point-cloud data via Schur-Weyl duality. These quantum computing frameworks are all constructed using the LCU method, suggesting that further novel quantum machine-learning (QML) algorithms could be created by utilizing the LCU technique.