The paper introduces a comprehensive quantum solver for binary combinatorial optimization problems on gate-model quantum computers, which outperforms existing alternatives and consistently delivers correct solutions for problems with up to 127 qubits. The solver includes a customized ansatz, efficient error suppression, and overhead-free post-processing to correct bit-flip errors. Benchmarking on IBM quantum computers, the solver successfully solves Max-Cut instances for random regular graphs with up to 120 qubits, demonstrating a 4× increase in problem size compared to previous trapped-ion quantum computer implementations and a 9× increase in the likelihood of finding the correct solution. For higher-order binary optimization, the solver successfully searches for the ground state energy of a 127-qubit spin-glass model, increasing the likelihood of finding the minimum energy by up to 1,500× compared to published results using a D-Wave annealer. The solver also outperforms a heuristic local solver for both problem types. These results represent the largest quantum optimizations successfully solved on hardware to date and demonstrate the first time a gate-model quantum computer has outperformed a quantum annealer for binary optimization problems.The paper introduces a comprehensive quantum solver for binary combinatorial optimization problems on gate-model quantum computers, which outperforms existing alternatives and consistently delivers correct solutions for problems with up to 127 qubits. The solver includes a customized ansatz, efficient error suppression, and overhead-free post-processing to correct bit-flip errors. Benchmarking on IBM quantum computers, the solver successfully solves Max-Cut instances for random regular graphs with up to 120 qubits, demonstrating a 4× increase in problem size compared to previous trapped-ion quantum computer implementations and a 9× increase in the likelihood of finding the correct solution. For higher-order binary optimization, the solver successfully searches for the ground state energy of a 127-qubit spin-glass model, increasing the likelihood of finding the minimum energy by up to 1,500× compared to published results using a D-Wave annealer. The solver also outperforms a heuristic local solver for both problem types. These results represent the largest quantum optimizations successfully solved on hardware to date and demonstrate the first time a gate-model quantum computer has outperformed a quantum annealer for binary optimization problems.