The paper introduces a variational solver for combinatorial optimizations over \( m = \mathcal{O}(n^k) \) binary variables using only \( n \) qubits, with tunable \( k > 1 \). The number of parameters and circuit depth scale mildly linearly and sublinearly in \( m \), respectively. The specific qubit-efficient encoding significantly mitigates barren plateaus, leading to superior quantum-solver performance. For \( m = 7000 \), numerical simulations produce solutions competitive with state-of-the-art classical solvers. For \( m = 2000 \), experiments with \( n = 17 \) trapped-ion qubits achieve MaxCut approximation ratios beyond the hardness threshold 0.941, the highest quality reported experimentally for such sizes. The findings offer a novel heuristic for quantum-inspired solvers and a promising route for solving commercially relevant problems on near-term quantum devices. The solver encodes variables into Pauli correlations across \( k \) qubits, trains a parameterized quantum circuit to minimize a non-linear loss function, and uses classical post-processing to enhance solution quality. The method operates in a regime where the circuit is classically intractable but qubit-efficient, preserving classical intractability in \( m \). The qubit-number compression also suppresses the decay of gradients, mitigating barren plateaus. Experimental demonstrations on IonQ's Aria-1 and QuantumH H1-1 trapped-ion devices show high-quality solutions for large MaxCut instances, outperforming state-of-the-art solvers. The approach is well-suited for standard error mitigation techniques and can be extended to generic polynomial unconstrained binary optimizations.The paper introduces a variational solver for combinatorial optimizations over \( m = \mathcal{O}(n^k) \) binary variables using only \( n \) qubits, with tunable \( k > 1 \). The number of parameters and circuit depth scale mildly linearly and sublinearly in \( m \), respectively. The specific qubit-efficient encoding significantly mitigates barren plateaus, leading to superior quantum-solver performance. For \( m = 7000 \), numerical simulations produce solutions competitive with state-of-the-art classical solvers. For \( m = 2000 \), experiments with \( n = 17 \) trapped-ion qubits achieve MaxCut approximation ratios beyond the hardness threshold 0.941, the highest quality reported experimentally for such sizes. The findings offer a novel heuristic for quantum-inspired solvers and a promising route for solving commercially relevant problems on near-term quantum devices. The solver encodes variables into Pauli correlations across \( k \) qubits, trains a parameterized quantum circuit to minimize a non-linear loss function, and uses classical post-processing to enhance solution quality. The method operates in a regime where the circuit is classically intractable but qubit-efficient, preserving classical intractability in \( m \). The qubit-number compression also suppresses the decay of gradients, mitigating barren plateaus. Experimental demonstrations on IonQ's Aria-1 and QuantumH H1-1 trapped-ion devices show high-quality solutions for large MaxCut instances, outperforming state-of-the-art solvers. The approach is well-suited for standard error mitigation techniques and can be extended to generic polynomial unconstrained binary optimizations.