Much of recent progress in geophysics can be attributed to the adaptation of heterogeneous high-performance computing architectures. It is projected that the next major leap in many areas of science, and hence hopefully in geophysics too, will be due to the emergence of quantum computers. Finding a right combination of hardware, algorithms, and a use case, however, proves to be a very challenging task - especially when looking for a relevant application that scales efficiently on a quantum computer and is difficult to solve using classical means. We find that maximizing stack power for residual statics correction, an NP-hard combinatorial optimization problem, appears to naturally fit a particular type of quantum computing known as quantum annealing. We express the underlying objective function as a quadratic unconstrained binary optimization, which is a quantum-native formulation of the problem. We choose some solution space and define a proper encoding to translate the problem variables into qubit states. We find that these choices can have a significant impact on the maximum problem size that can fit on the quantum annealer and on the fidelity of the final result. To improve the latter, we embed the quantum optimization step in a hybrid classical-quantum workflow, which aims to increase the frequency of finding the global, rather than some local, optimum of the objective function. Finally, we find that a generic, black-box, hybrid classical-quantum solver also could be used to solve stack-power maximization problems proximal to industrial relevance and capable of surpassing deterministic solvers prone to cycle skipping. A custom-built workflow capable of solving larger problems with an even higher robustness and greater control of the user appears to be within reach in the very near future.