A method of solving a combinatorial optimization problem by finding a ground state of a Hamiltonian, H z wherein H z = Σ i,j J i,j Z i Z j, wherein i and j label different qubits, Z i is the Pauli Z matrix on the i th qubit, and J i,j is an integer weight, the method performed in a computing environment comprising: a quantum computing device comprising one or more read out devices and one or more quantum processing units comprising a set of one or more qubit, wherein the one or more quantum processing units execute quantum circuits; and a remote computer that comprises a classical computing environment; the method comprising: preparing the one or more qubits of the quantum computing device in an input state, ψ + = |+〉 ⊗ N of a Hamiltonian H s wherein H s = H z − sB X N K wherein X = Σ i X i and X i is the Pauli X matrix on an i th qubit, s=1, K is an odd integer, N is the number of qubits prepared in the input state, and B is a scalar wherein B > 0 is selected so that H s has all off-diagonal entries non-positive in the computational basis after preparing the input state, performing a phase estimation technique on the set of one or more qubits in the quantum computing device to determine an energy estimate of the input state; after performing phase estimation, evaluating, by the classical computing environment, results of the phase estimation technique to determine if the energy estimate is larger than E 0, s + Δ/2 wherein E 0,s is an energy of the input state ψ + of the Hamiltonian H s and if the energy estimate is larger than E 0, s + Δ/2 terminating the method; else if the results of the phase estimation technique are not greater than E 0, s + Δ/2, determining and outputting a computational basis state without evolving the set of one or more qubits. a quantum computing device comprising one or more read out devices and one or more quantum processing units comprising a set of one or more qubit, wherein the one or more quantum processing units execute quantum circuits; and a remote computer that comprises a classical computing environment; the method comprising: preparing the one or more qubits of the quantum computing device in an input state, ψ + = |+〉 ⊗ N of a Hamiltonian H s wherein H s = H z − sB X N K wherein X = Σ i X i and X i is the Pauli X matrix on an i th qubit, s=1, K is an odd integer, N is the number of qubits prepared in the input state, and B is a scalar wherein B > 0 is selected so that H s has all off-diagonal entries non-positive in the computational basis after preparing the input state, performing a phase estimation technique on the set of one or more qubits in the quantum computing device to determine an energy estimate of the input state; after performing phase estimation, evaluating, by the classical computing environment, results of the phase estimation technique to determine if the energy estimate is larger than E 0, s + Δ/2 wherein E 0,s is an energy of the input state ψ + of the Hamiltonian H s and if the energy estimate is larger than E 0, s + Δ/2 terminating the method; else if the results of the phase estimation technique are not greater than E 0, s + Δ/2, determining and outputting a computational basis state without evolving the set of one or more qubits. preparing the one or more qubits of the quantum computing device in an input state, ψ + = |+〉 ⊗ N of a Hamiltonian H s wherein H s = H z − sB X N K wherein X = Σ i X i and X i is the Pauli X matrix on an i th qubit, s=1, K is an odd integer, N is the number of qubits prepared in the input state, and B is a scalar wherein B > 0 is selected so that H s has all off-diagonal entries non-positive in the computational basis after preparing the input state, performing a phase estimation technique on the set of one or more qubits in the quantum computing device to determine an energy estimate of the input state; after performing phase estimation, evaluating, by the classical computing environment, results of the phase estimation technique to determine if the energy estimate is larger than E 0, s + Δ/2 wherein E 0,s is an energy of the input state ψ + of the Hamiltonian H s and if the energy estimate is larger than E 0, s + Δ/2 terminating the method; else if the results of the phase estimation technique are not greater than E 0, s + Δ/2, determining and outputting a computational basis state without evolving the set of one or more qubits. if the energy estimate is larger than E 0, s + Δ/2 terminating the method; else if the results of the phase estimation technique are not greater than E 0, s + Δ/2, determining and outputting a computational basis state without evolving the set of one or more qubits.