This paper introduces a variational quantum solver for combinatorial optimization problems with a polynomial number of binary variables, m = O(n^k), using only n qubits, where k > 1. The method encodes binary variables into Pauli correlations across k qubits, enabling efficient quantum-classical optimization. The quantum circuit is trained to minimize a non-linear loss function, and the solution is obtained via classical post-processing. The scheme exhibits a super-polynomial suppression of barren plateaus, leading to high-quality solutions. For m = 7000, the solver produces solutions competitive with state-of-the-art classical solvers. For m = 2000, experiments with 17 trapped-ion qubits achieve approximation ratios beyond the hardness threshold of 0.941. The method is efficient, with circuit depth and parameter count scaling sublinearly with m. It is compatible with experimental quantum hardware and demonstrates superior performance compared to previous quantum solvers. The approach is applicable to a wide range of combinatorial optimization problems and offers a promising path for solving large-scale problems on near-term quantum devices. The results highlight the potential of quantum-inspired classical solvers and demonstrate the feasibility of quantum optimization on small-scale quantum hardware.This paper introduces a variational quantum solver for combinatorial optimization problems with a polynomial number of binary variables, m = O(n^k), using only n qubits, where k > 1. The method encodes binary variables into Pauli correlations across k qubits, enabling efficient quantum-classical optimization. The quantum circuit is trained to minimize a non-linear loss function, and the solution is obtained via classical post-processing. The scheme exhibits a super-polynomial suppression of barren plateaus, leading to high-quality solutions. For m = 7000, the solver produces solutions competitive with state-of-the-art classical solvers. For m = 2000, experiments with 17 trapped-ion qubits achieve approximation ratios beyond the hardness threshold of 0.941. The method is efficient, with circuit depth and parameter count scaling sublinearly with m. It is compatible with experimental quantum hardware and demonstrates superior performance compared to previous quantum solvers. The approach is applicable to a wide range of combinatorial optimization problems and offers a promising path for solving large-scale problems on near-term quantum devices. The results highlight the potential of quantum-inspired classical solvers and demonstrate the feasibility of quantum optimization on small-scale quantum hardware.