  Solving combinatorial optimization problems using variational quantum
algorithms (VQAs) represents one of the most promising applications in the NISQ
era. However, the limited trainability of VQAs could hinder their scalability
to large problem sizes. In this paper, we improve the trainability of
variational quantum eigensolver (VQE) by utilizing convex interpolation to
solve portfolio optimization. The idea is inspired by the observation that the
Dicke state possesses an inherent clustering property. Consequently, the energy
of a state with a larger Hamming distance from the ground state intuitively
results in a greater energy gap away from the ground state energy in the
overall distribution trend. Based on convex interpolation, the location of the
ground state can be evaluated by learning the property of a small subset of
basis states in the Hilbert space. This enlightens naturally the proposals of
the strategies of close-to-solution initialization, regular cost function
landscape, and recursive ansatz equilibrium partition. The successfully
implementation of a $40$-qubit experiment using only $10$ superconducting
qubits demonstrates the effectiveness of our proposals. Furthermore, the
quantum inspiration has also spurred the development of a prototype greedy
algorithm. Extensive numerical simulations indicate that the hybridization of
VQE and greedy algorithms achieves a mutual complementarity, combining the
advantages of both global and local optimization methods. Our proposals can be
extended to improve the trainability for solving other large-scale
combinatorial optimization problems that are widely used in real applications,
paving the way to unleash quantum advantages of NISQ computers in the near
future.
