The paper introduces a quantum algorithm, the Quantum Approximate Optimization Algorithm (QAOA), designed to find approximate solutions for combinatorial optimization problems. The algorithm relies on an integer parameter \( p \geq 1 \), and the quality of the approximation improves as \( p \) increases. The quantum circuit implementing the algorithm consists of unitary gates whose locality is at most the locality of the objective function. The depth of the circuit grows linearly with \( p \) times the number of constraints. For fixed \( p \), efficient classical preprocessing can be used to determine the optimal angles, while for \( p \) growing with the input size, a different strategy is proposed. The algorithm is applied to MaxCut on regular graphs, and its performance is analyzed for 2-regular and 3-regular graphs. For \( p = 1 \), on 3-regular graphs, the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut. The paper also discusses the concentration of the distribution of the objective function and the performance on 2-regular and 3-regular graphs. Additionally, a variant of the algorithm is presented for finding large independent sets in graphs. The authors compare the QAOA with the Quantum Adiabatic Algorithm (QAA), noting that while the QAA aims to find the exact optimal solution, the QAOA focuses on finding approximate solutions. The QAOA's performance improves as \( p \) increases, which may be advantageous in certain scenarios. The paper concludes by discussing the potential of the QAOA in solving combinatorial optimization problems beyond what classical algorithms can achieve.The paper introduces a quantum algorithm, the Quantum Approximate Optimization Algorithm (QAOA), designed to find approximate solutions for combinatorial optimization problems. The algorithm relies on an integer parameter \( p \geq 1 \), and the quality of the approximation improves as \( p \) increases. The quantum circuit implementing the algorithm consists of unitary gates whose locality is at most the locality of the objective function. The depth of the circuit grows linearly with \( p \) times the number of constraints. For fixed \( p \), efficient classical preprocessing can be used to determine the optimal angles, while for \( p \) growing with the input size, a different strategy is proposed. The algorithm is applied to MaxCut on regular graphs, and its performance is analyzed for 2-regular and 3-regular graphs. For \( p = 1 \), on 3-regular graphs, the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut. The paper also discusses the concentration of the distribution of the objective function and the performance on 2-regular and 3-regular graphs. Additionally, a variant of the algorithm is presented for finding large independent sets in graphs. The authors compare the QAOA with the Quantum Adiabatic Algorithm (QAA), noting that while the QAA aims to find the exact optimal solution, the QAOA focuses on finding approximate solutions. The QAOA's performance improves as \( p \) increases, which may be advantageous in certain scenarios. The paper concludes by discussing the potential of the QAOA in solving combinatorial optimization problems beyond what classical algorithms can achieve.