A Quantum Approximate Optimization Algorithm

关键要点

• ▸Alternates between a problem-encoding layer and a mixing layer, repeated p times.
• ▸Solution quality improves as depth p grows, recovering the exact optimum in the limit.
• ▸Applies to NP-hard problems such as Max-Cut, portfolio selection, and scheduling.

通俗解读

Many valuable problems — routing trucks, scheduling shifts, splitting a network — involve picking the best option from astronomically many. QAOA encodes the problem so that good solutions have low energy, then alternates two operations: one that rewards good configurations and one that shuffles possibilities around so the search does not get stuck. A classical optimizer tunes how strongly to apply each, and more rounds generally means better answers. It is deliberately shallow enough to run on today's noisy machines, and it is the most common reason people try quantum computing for business optimization.

为何重要

QAOA is the main proposed route to quantum advantage in optimization — the application area with the clearest commercial demand. Whether it can actually beat good classical heuristics remains one of the field's most-studied open questions.