Methods are needed to address microplastics (MP), a concerning pollutant. Given the ability of peptides to adsorb strongly to materials of micro- or nanometer size, plastic-binding peptides (PBPs) could be useful for detecting or filtering MP pollution. However, the lack of PBPs for many plastics prevents the development of peptide-based MP remediation tools. In this work, we discover and evaluate PBPs for several common plastics via a computational nexus comprised of biophysical modeling, molecular dynamics, quantum computing, and reinforcement learning. PBPs are discovered by first using biophysical modeling to express peptide affinity for a given plastic as a function of the amino acid sequence, then using quantum annealing to search for amino acid sequences with the greatest predicted affinity. Additionally, proximal policy optimization finds PBPs with distinct physicochemical properties, namely net charge, from PBPs found using quantum annealing; this will facilitate MP remediation in a variety of environmental conditions. The discovered PBPs are validated in molecular dynamics simulations, which offer a more rigorous evaluation of a peptide’s adsorption free energy to a given plastic. Using the nexus, we found PBPs with high affinity for polyethylene and polypropylene. In summary, the nexus offers a powerful approach to discover peptides that can help in the fight against MP pollution.