We introduce a quantum algorithm that produces approximate solutions for
combinatorial optimization problems. The algorithm depends on a positive
integer p and the quality of the approximation improves as p is increased. The
quantum circuit that implements the algorithm consists of unitary gates whose
locality is at most the locality of the objective function whose optimum is
sought. The depth of the circuit grows linearly with p times (at worst) the
number of constraints. If p is fixed, that is, independent of the input size,
the algorithm makes use of efficient classical preprocessing. If p grows with
the input size a different strategy is proposed. We study the algorithm as
applied to MaxCut on regular graphs and analyze its performance on 2-regular
and 3-regular graphs for fixed p. 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.

介绍了一种量子算法，通过使用正整数 p 来提高近似解的质量，将其应用于组合优化问题的求解上，并分析了在正则图上，固定的 p 值下算法的性能表现。

量子近似优化算法

A Quantum Approximate Optimization Algorithm

We present a quantum algorithm that additively approximates the value of a
tensor network to a certain scale. When combined with existing results, this
provides a complete problem for quantum computation. The result is a simple new
way of looking at quantum computation in which unitary gates are replaced by
tensors and time is replaced by the order in which the tensor-network is
"swallowed". We use this result to derive new quantum algorithms that
approximate the partition function of a variety of classical statistical
mechanics models, including the Potts model.

提出了一种量子算法，可以逼近张量网络的值，在结合现有结果时，提供了一个完整的量子计算问题。该结果替代了量子计算中的幺正门，使用张量并根据其符合的顺序计算。利用这种方法，导出了逼近各种经典统计力学模型的配分函数的新型量子算法，包括 Potts 模型。