Photonic-crystal surface-emitting lasers (PCSELs), which utilize a two-dimensional (2D) optical resonance inside a photonic crystal for lasing, feature various outstanding functionalities such as single-mode high-power operation and arbitrary control of beam polarizations. Although most of the previous designs of PCSELs employ spatially uniform photonic crystals, it is expected that lasing performance can be further improved if it becomes possible to optimize the spatial distribution of photonic crystals. In this paper, we investigate the structural optimization of PCSELs via quantum annealing towards high-power, narrow-beam-divergence operation with linear polarization. The optimization of PCSELs is performed by the iteration of the following three steps: (1) time-dependent 3D coupled-wave analysis of lasing performance, (2) formulation of the lasing performance via a factorization machine, and (3) selection of optimal solution(s) via quantum annealing. By using this approach, we discover an advanced PCSEL with a non-uniform spatial distribution of the band-edge frequency and injection current, which simultaneously enables higher output power, a narrower divergence angle, and a higher linear polarization ratio than conventional uniform PCSELs. Our results potentially indicate the universal applicability of quantum annealing, which has been mainly applied to specific types of discrete optimization problems so far, for various physics and engineering problems in the field of smart manufacturing.