Variational techniques have long been at the heart of atomic, solid-state, and many-body physics. They have recently extended to quantum and classical machine learning, providing a basis for representing quantum states via neural networks. These methods generally aim to minimize the energy of a given ansatz, though open questions remain about the expressivity of quantum and classical variational ansätze. The connection between variational techniques and quantum computing, through variational quantum algorithms, offers opportunities to explore the quantum complexity of classical methods. We demonstrate how the concept of non-stabilizerness, or magic, can create a bridge between quantum information and variational techniques and we show that energy accuracy is a necessary but not always sufficient condition for accuracy in non-stabilizerness. Through systematic benchmarking of neural network quantum states, matrix product states, and variational quantum methods, we show that while classical techniques are more accurate in non-stabilizerness, not accounting for the symmetries of the system can have a severe impact on this accuracy. Our findings form a basis for a universal expressivity characterization of both quantum and classical variational methods.