Embodiments described herein are generally related to a method and a system for performing a computation using a hybrid quantum-classical computing system, and, more specifically, to providing an approximate solution to an optimization problem using a hybrid quantum-classical computing system that includes a group of trapped ions. A hybrid quantum-classical computing system that is able to provide a solution to a combinatorial optimization problem may include a classical computer, a system controller, and a quantum processor. The methods and systems described herein include an efficient and noise resilient method for constructing trial states in the quantum processor in solving a problem in a hybrid quantum-classical computing system, which provides improvement over the conventional method for computation in a hybrid quantum-classical computing system.