  The protein design problem involves finding polypeptide sequences folding
into a given threedimensional structure. Its rigorous algorithmic solution is
computationally demanding, involving a nested search in sequence and structure
spaces. Structure searches can now be bypassed thanks to recent machine
learning breakthroughs, which have enabled accurate and rapid structure
predictions. Similarly, sequence searches might be entirely transformed by the
advent of quantum annealing machines and by the required new encodings of the
search problem, which could be performative even on classical machines. In this
work, we introduce a general protein design scheme where algorithmic and
technological advancements in machine learning and quantum-inspired algorithms
can be integrated, and an optimal physics-based scoring function is iteratively
learned. In this first proof-of-concept application, we apply the iterative
method to a lattice protein model amenable to exhaustive benchmarks, finding
that it can rapidly learn a physics-based scoring function and achieve
promising design performances. Strikingly, our quantum-inspired reformulation
outperforms conventional sequence optimization even when adopted on classical
machines. The scheme is general and can be easily extended, e.g., to encompass
off-lattice models, and it can integrate progress on various computational
platforms, thus representing a new paradigm approach for protein design.
