A quantum algorithm for approximate optimization is introduced, which produces approximate solutions for combinatorial optimization problems. The algorithm depends on an integer p ≥ 1, with the quality of the approximation improving as p increases. The quantum circuit consists of unitary gates with locality at most that of the objective function. The circuit depth grows linearly with p times the number of constraints. For fixed p, efficient classical preprocessing is used, while for p growing with input size, a different strategy is proposed. The algorithm is studied on MaxCut for regular graphs, showing that for p = 1, on 3-regular graphs, the quantum algorithm finds a cut at least 0.6924 times the optimal size. The algorithm works in a 2^n dimensional Hilbert space with computational basis vectors |z>. The objective function C(z) is defined as the number of satisfied clauses. A unitary operator U(C, γ) is defined, and another operator B is the sum of single-bit σ^x operators. The quantum state is constructed using these operators and a uniform superposition state |s>. For any p and angles γ, β, the quantum state |γ, β> is defined. The expectation of C in this state is F_p(γ, β), and M_p is the maximum of F_p over angles. As p increases, M_p approaches the maximum of C(z). For fixed p, classical preprocessing determines the angles that maximize F_p. The algorithm is applied to MaxCut on regular graphs, with subgraphs analyzed to evaluate F_p. For 2-regular graphs, the algorithm achieves approximation ratios approaching 1 as p increases. For 3-regular graphs, the algorithm achieves an approximation ratio of at least 0.6924 for p = 1. The algorithm is also applied to finding large independent sets in graphs. The quantum state is constructed using operators associated with B and C. The algorithm is shown to improve approximation as p increases. The algorithm is compared to the quantum adiabatic algorithm, with the QAOA showing better performance in some cases. The algorithm is suitable for combinatorial optimization problems, with p fixed or growing slowly with input size. The algorithm can be implemented on a quantum computer with efficient classical preprocessing for fixed p. The algorithm is shown to be effective for finding approximate solutions to optimization problems beyond classical algorithms. The work is supported by grants from the US Army Research Laboratory and the National Science Foundation.A quantum algorithm for approximate optimization is introduced, which produces approximate solutions for combinatorial optimization problems. The algorithm depends on an integer p ≥ 1, with the quality of the approximation improving as p increases. The quantum circuit consists of unitary gates with locality at most that of the objective function. The circuit depth grows linearly with p times the number of constraints. For fixed p, efficient classical preprocessing is used, while for p growing with input size, a different strategy is proposed. The algorithm is studied on MaxCut for regular graphs, showing that for p = 1, on 3-regular graphs, the quantum algorithm finds a cut at least 0.6924 times the optimal size. The algorithm works in a 2^n dimensional Hilbert space with computational basis vectors |z>. The objective function C(z) is defined as the number of satisfied clauses. A unitary operator U(C, γ) is defined, and another operator B is the sum of single-bit σ^x operators. The quantum state is constructed using these operators and a uniform superposition state |s>. For any p and angles γ, β, the quantum state |γ, β> is defined. The expectation of C in this state is F_p(γ, β), and M_p is the maximum of F_p over angles. As p increases, M_p approaches the maximum of C(z). For fixed p, classical preprocessing determines the angles that maximize F_p. The algorithm is applied to MaxCut on regular graphs, with subgraphs analyzed to evaluate F_p. For 2-regular graphs, the algorithm achieves approximation ratios approaching 1 as p increases. For 3-regular graphs, the algorithm achieves an approximation ratio of at least 0.6924 for p = 1. The algorithm is also applied to finding large independent sets in graphs. The quantum state is constructed using operators associated with B and C. The algorithm is shown to improve approximation as p increases. The algorithm is compared to the quantum adiabatic algorithm, with the QAOA showing better performance in some cases. The algorithm is suitable for combinatorial optimization problems, with p fixed or growing slowly with input size. The algorithm can be implemented on a quantum computer with efficient classical preprocessing for fixed p. The algorithm is shown to be effective for finding approximate solutions to optimization problems beyond classical algorithms. The work is supported by grants from the US Army Research Laboratory and the National Science Foundation.