A Quantum Approximate Optimization Algorithm
2014 · paper · Computer science
Introduces a quantum algorithm for approximate solutions to combinatorial optimization problems, whose quality improves with an integer parameter p. Applied to MaxCut, for p=1 on 3-regular graphs it always finds a cut at least 0.6924 times the optimal size.
Checked: PDF from arxiv.org, fetched 4 Oct 2026. Page numbers are those of that PDF.
2 findings
Reference or label Eq. (23) prints "U†(C_g(j,k), γp) ··· U†(B_g(j,k), β1) C⟨jk⟩ U(B_g(j,k), β1) ··· U(C_g(j,k), γp)", which reverses the angle order used in Eqs. (6), (13), (14) and (24) (γ1 outermost, βp next to C⟨jk⟩).
- p. 5 Eq. (23)
U† (Cg(j,k), γp) · · ·U†(Bg(j,k), β1)C⟨jk⟩U (Bg(j,k), β1) · · ·U (Cg(j,k), γp)
- p. 4 Eq. (13)
U†(C, γ1) · · · U†(B, βp) C⟨jk⟩U(B, βp) · · ·U(C, γ1)
Judge's note: Checked the page images. Eq. (6) on p.4 defines |γ,β⟩ = U(B,βp)U(C,γp)···U(B,β1)U(C,γ1)|s⟩, so U(C,γ1) acts first. Eqs. (13) and (14) (p.4, crop C001-b) and Eq. (24) (p.6) all print U†(C,γ1)···U†(B,βp) C⟨jk⟩ U(B,βp)···U(C,γ1). Eq. (23) (p.5, crop C001-a) instead has γp outermost and β1 next to C⟨jk⟩. The text introduces it as the contribution to Fp from the sum in (13), with no relabelling. The evident fix is to swap γp↔γ1 and β1↔βp in (23).
Second check: another model agreed
Report a problem with this finding
Wording "make Fp(γ, β) as close to Mp as desired. With (9), this proves the assertion of (10).": Mp is defined in (8) as the maximum of Fp, so the step needed for (10) is closeness to max_z C(z).
- p. 11 top paragraph
make Fp(γ, β) as close to Mp as desired. With (9), this proves the assertion of (10).
Judge's note: Page 11, read against Eq. (8) on page 3. As written, the sentence is trivially true and does not establish lim Mp = max C. The adiabatic argument supports closeness to max_z C(z).
Second check: another model agreed
Report a problem with this finding
9 minor (typos and the like; most checked by the judge only)
Wording Section IV says the ring maximum is "n or n−1 depending on whether n is even or odd" (p.7), but later says "Since the best cut is n" (p.8) without limiting this to even n.
- p. 8 Section IV
Since the best cut is n, we see that
- p. 7 Section IV
its maximum is n or n−1 depending on whether n is even or odd
- p. 8 Section IV
Since the best cut is n, we see
Judge's note: Both passages are visible in the page images (crops C006-a and C006-b). For odd n the best cut is n−1, so the p.8 sentence is not literally true in general. Because n is an upper bound on the best cut in either case, the approximation-ratio conclusion is unaffected, so this is only loose wording.
Second check: another model agreed
Report a problem with this finding
Wording "then we have a 4 vertex disconnected 3-regular graph": the graph described is K4, which is connected.
- p. 8 Section V, paragraph after (31)
then we have a 4 vertex disconnected 3-regular graph
Judge's note: Page 8. If the two edges leaving the crossed square are the same edge, the graph is K4, and Section V restricts to connected graphs. The authors probably meant that the component is cut off from the rest of the graph, but the sentence calls the graph itself disconnected.
Second check: another model agreed
Report a problem with this finding
Typo Eq. (24) prints "U(B_{g(j,x)}β_p)" where every other factor reads g(j,k) and has a comma before the angle, i.e. it should read U(B_{g(j,k)}, β_p).
- p. 6 Eq. (24)
U(Bg(j,x)βp)
- p. 5 Eq. (23)
U† (Cg(j,k), γp) · · ·U†(Bg(j,k), β1)ChjkiU (Bg(j,k), β1) · · ·U (Cg(j,k), γp)
- p. 6 Eq. (24)
U†(Cg(j,k), γ1) · · · U†(Bg(j,k), βp)ChjkiU(Bg(j,x)βp)
- p. 6
U(Bg(j,x)βp) · · ·
Judge's note: The page 6 image (crops C002-a and C002-c) clearly shows the subscript g(j,x) and no comma before β_p. Every other operator in Eqs. (23) and (24) uses g(j,k) and a comma, so this is a typesetting slip. Reviewer note 4 here, about the reversed ordering in Eq. (23), is the same defect as C001 and is judged there.
Second check: none (judge only)
Report a problem with this finding
Typo "the numbers of qubits in this tree is" should read "the number of qubits in this tree is".
- p. 6 before Eq. (26)
the numbers of qubits in this tree is
Judge's note: Seen on page 6 just before Eq. (26). Plural noun with a singular verb.
Second check: none (judge only)
Report a problem with this finding
Typo "Given any 3 regular graph" is unhyphenated, whereas the paper writes "3-regular" elsewhere.
- p. 9 Text after Eq. (33)
Given any 3 regular graph
Judge's note: Page 9. An inconsistency in hyphenation only.
Second check: none (judge only)
Report a problem with this finding
Typo "more complicated then the p = 1 case" should read "than".
- p. 10 Section V, p=2 paragraph
more complicated then the p = 1 case
- p. 10 Section V, paragraph on p = 2
it is more complicated then the p = 1 case
Judge's note: Seen on page 10.
Second check: none (judge only)
Report a problem with this finding
Typo "γ1, γ2, .γp−1" has a single stray period where an ellipsis is intended.
- p. 13 first paragraph
γ1, γ2, .γp−1 ≡γ
- p. 13 Section VII, first paragraph
γ1, γ2, .γp−1
Judge's note: The page 13 image shows a single dot, so this is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling on p.14: "the Hamlitonian B for a time b" should read "Hamiltonian".
- p. 14 Section VII, second paragraph
the Hamlitonian B for a time b
- p. 14 Section VII, p=1 paragraph
Hamlitonian B for a time b
- p. 14
evolving the initial state |z = 0⟩with the Hamlitonian B for a time b
Judge's note: The page 14 image (crop C011-a) shows "Hamlitonian". This is a plain misspelling.
Second check: none (judge only)
Report a problem with this finding
Typo Stray article on p.15: "requires a strategy for a picking a sequence of sets of angles" should read "a strategy for picking a sequence".
- p. 15 Conclusion
requires a strategy for a picking a sequence
- p. 15 Conclusion, second paragraph
a strategy for a picking a sequence of sets of angles
- p. 15 Conclusion
strategy for a picking a sequence
Judge's note: The page 15 image (crop C012-a) shows "for a picking", which has an extra "a".
Second check: none (judge only)