A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, Sam Gutmann · arXiv · 2014 · quantum-computing · record farhi2014-qaoa
tag layer · index · concepts · authors · עברית

Where this record's text came from. faceted 2026-08 by reading the locally held text (pdftext); every evidence string verified as an exact substring of that text before merging. METADATA MISMATCH: the queue entry is titled 'A Quantum Approximate Optimization Algorithm' (Farhi, Goldstone, Gutmann 2014, arXiv 1411.4028), but the article text below the quote line is a different paper — 'Analog Quantum Approximate Optimization Algorithm' by Barraza, Alvarado Barrios, Peng, Lamata, Solano and Albarrán-Arriagada (arXiv 2112.07461v2), which cites Farhi et al. as reference [14]. All facets here describe the text that is actually in the file, per the rule to quote only from below the line; the id is kept as given. Only one claim_relation is recorded: the paper also explicitly distinguishes itself from shortcuts-to-adiabaticity techniques ("our AQAOA algorithm is not a shortcut to adiabaticity (STA) technique"), but 'distinguishes-f | 2026-08-09: the staged full text was a different paper (arXiv 2112.07461, Barraza et al., "Analog QAOA"). Re-staged from arXiv 1411.4028v1; 11 of 16 stored excerpts re-verified against it, 5 traced to the wrong paper and deleted. Update, 12 August 2026: claim type, phenomenon and method (with their evidence) were BLANKED. They had been read from arXiv 2112.07461 (Barraza et al.), whose text stood in this record's place until the 2026-08-09 restaging; that pass replaced the text and deleted five quotes but left these facets. The record is queued to be re-read from the correct text. Other layers were left alone - they are not shown to be wrong. Update, 18 September 2026: this record was later re-read from the correct text, Farhi, Goldstone and Gutmann (2014); its quotes all verify against that paper; one concept term, 'variational algorithm', dates from the earlier reading and does not occur in it. The sentences above about the analog paper record what happened before the re-staging.

Some words in these quotes contain the wrong character. The PDF this text was extracted from substituted 5 characters inside a word — a currency sign or a stray accent where a letter pair belongs, as in signi¢cantly for significantly, or a single ligature glyph, as in conﬁdence. They are valid characters in the wrong place, so they survive every encoding check. The quotes keep them for the same reason as above, and a search of this page will not find the affected words.

3 quotes on this page break a word across a line. The PDF this text was extracted from hyphenated those words at the end of a printed line — adversar- ial, repre- sentations — and the extractor kept the hyphen and the space. The quotes keep them because a quote is reproduced exactly or it proves nothing: the break is the typesetter’s, not the author’s. A search of this page will not find the affected words.

1 quotation on this page contains a reference number where the paper printed a superscript. This journal style prints citations as raised numerals — parameters^12,13 — and the extraction flattened them into the line, so the sentence reads parameters 12 , 13 . The digits are citation markers and not part of what the author wrote. The quotes keep them for the same reason they keep every other extraction fault: a quote is reproduced exactly or it proves nothing.

How to read this page. The article itself is not reproduced here — this paper is not cleared for redistribution, so what follows is the tag layer alone. The evidence sentences are withheld with the article. The table at the foot lists every tag the record carries; each row names the facet it belongs to, and the whose words column says whether the tag records the paper's own wording or the tagger's sentence about the paper. Every tag links to each other paper in the corpus carrying it. The machine-readable edition of the same thing is the TEI file beside this one, where the tags live in standOff, and the article is at its publisher via the link below. When we have changed our mind. Some entries in the table begin with a word in capitals and the reason for it. EVIDENCE CORRECTED — the finding still stands, but we had quoted the wrong sentence from the paper, and the quotation has been replaced with the right one. RETRACTED — the entry itself was wrong; it stays on the page, marked, with the reason, rather than being deleted. WITHDRAWN AND REPLACED — the entry was wrong, and a corrected version of it appears in the entries below. Each mark carries its own reason, in brackets, because the reasons differ from one entry to the next. An entry we have WITHDRAWN is removed from this page and kept in the record, with its reason. A line reading Audit and a date is a later re-reading of the entry against its whole sentence: DOUBTFUL means it was kept, and the reason says what is loose about it. Quotation marks inside the tagger's sentence. Where a tag is the tagger's own sentence, a phrase in quotation marks inside it is borrowed from the paper — the tagger's wording around it is not. The paper's own sentence is the evidence quote for that row; on this page it is withheld with the article, and the article is at its publisher. Nothing inside quotation marks anywhere on this page is ours: if it is quoted, it is the paper's. Whose words a concept carries. A concept entry records a term the paper itself uses, so the term, the sense given for it, and its evidence are the paper's own words, quoted where the paper fixes them. This is the opposite of a sense entry in the tag table, which is the tagger's sentence about how the paper uses a term. Where a concept entry could not be grounded in the paper's words, the entry says so on its own row.

Other fields define these differently the same word, defined another way in another discipline
algorithm 5 fields · standard-deviation 3 fields

Tags on this paper

Every tag the record carries, each linking to every other paper in the corpus that carries it. A tag appears here whether or not its words occur in the article — the spans below are only the ones a sentence in this paper licenses. Of the 8 concept tags on this paper, 5 are grounded in a quoted sentence.

quantum algorithm combinatorial optimization qubit MaxCut QAOA approximation ratio classical algorithms circuit depth THE WHOLE ALGORITHM IS ONE INTEGER KNOB: the state is built by alternating two operators p times over a uniform starting superposition, and the paper's claim is that the quality of the approximation improves as p is raised the first operator is made diagonal in the computational basis, which buys two things at once - every term in the product COMMUTES, and each term's locality is no worse than the locality of the clause it came from THE PARAMETER RANGE IS DERIVED FROM A PROPERTY OF THE OBJECTIVE, NOT CHOSEN: because the objective has integer eigenvalues, one angle can be restricted to lie between 0 and 2 pi MONOTONICITY IS STRUCTURAL RATHER THAN EMPIRICAL: the maximisation at p minus one IS a constrained maximisation at p, so the best value at each depth can never fall below the best value at the depth beneath it the algorithm is used by repetition rather than by a single shot: measure in the computational basis, evaluate the objective on the string obtained, and repeat with the SAME angles - enough repetitions produce a string whose value is very near or above the expectation the authors name the difficulty rather than presenting the method as complete - it is not obvious in advance how to pick good angles - and for p that does not grow with n they offer a search over a fine grid on the compact parameter set the grid search is made tractable by a BOUND ON THE PARTIAL DERIVATIVES of the objective's expectation, which is what turns a search over a continuous compact set into an efficient one for fixed p and bounded clause participation the angles are found by an EFFICIENT CLASSICAL CALCULATION rather than by quantum search, and those angles are then used to run the quantum computer and produce the measured string THE CONSTRAINT IS ENFORCED BY THE BASIS: for the independent-set variant the orthonormal basis consists only of strings that correspond to independent sets, so the space is exponentially large but smaller than the full 2^n, and is NOT a simple tensor product of qubits the mixing operator is likewise restricted rather than penalised: it is the adjacency matrix of the hypercube confined to the legal strings, so the walk it generates can only ever move between independent sets quantum algorithm optimization circuit graphs unitary objective combinatorial combinatorial optimization problem mean mean of standard-deviation standard deviation mathematical-proof

Method, as described: algorithm-design-and-proof

Legend

relation to other work	`claim_relations`	how this paper stands to another: agrees, contradicts, extends, qualifies
claim type	`claim_type`	the shape of the claim: existence, mechanism, method, critique, prediction, null
concept edge	`concept_edges`	an asserted relation between two concepts, with the sentence asserting it
concept	`concepts`	an idea the paper works with, quoted where the paper uses it
content tag	`content_tags`	a finding, definition, quantity, statistic or variable named in the paper
limitation	`limitations`	what the paper says its evidence cannot support
mechanism	`mechanisms`	how the reported effect is said to come about
method	`method`	how the paper produced its evidence
phenomenon	`phenomenon`	the effect or regularity under study
sense	`senses`	a distinct use of a term, quoted where the paper fixes it

The paper

The full text is not reproduced here. This article is not cleared for redistribution, so the page carries the tag layer only. Its evidence sentences are withheld; the grounding status remains with each tag, and the article itself is at https://arxiv.org/abs/1411.4028. The reading view exists for the papers whose licence permits it.

Every tag on this page

claim_relations 1 · claim_type 1 · concept_edges 1 · concepts 5 · content_tags 9 · limitations 5 · mechanisms 10 · method 1 · phenomenon 1 · senses 3

Relations on this page carry a quotation for the claim. Where a relation was separately evidenced — and so tested against the vocabulary for its type — the row says so; none of 1 relation here carry that mark. The rest are the tagger’s reading of the sentence quoted beside them.

This record holds no controls. A layer is empty when the tagger recorded nothing in it — which is not the same as the paper having nothing to record.

facet	tag	field	conf.	whose words
claim_type	method Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_type`		the paper's words
phenomenon	approximate solutions to combinatorial optimization problems Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`phenomenon`		the paper's words
method	mathematical-proof Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: mathematical-proof	`method`		the paper's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: A WORD IS SPLIT BY A SPURIOUS SPACE INSIDE THIS QUOTE - "approx- imation" for "approximation". The extraction inserts a space at what was a line break in the PDF, and it does this throughout this file. The quote is an exact substring of the staged text and the meaning is unaffected, but A READER SEARCHING FOR THE UNBROKEN WORD WILL NOT FIND IT, which is the whole reason this is recorded. No pattern in our tools detects it: both halves of a broken word are plausible tokens, so it is invisible to every guard and was found by eye. also in: THE WHOLE ALGORITHM IS ONE INTEGER KNOB: the state is built by alternating two operators p times over a uniform starting superposition, and the paper's claim is that the quality of the approximation improves as p is raised	`mechanisms[0]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: the first operator is made diagonal in the computational basis, which buys two things at once - every term in the product COMMUTES, and each term's locality is no worse than the locality of the clause it came from	`mechanisms[1]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: A WORD IS SPLIT BY A SPURIOUS SPACE INSIDE THIS QUOTE - "eigen- values" for "eigenvalues". The extraction inserts a space at what was a line break in the PDF, and it does this throughout this file. The quote is an exact substring of the staged text and the meaning is unaffected, but A READER SEARCHING FOR THE UNBROKEN WORD WILL NOT FIND IT, which is the whole reason this is recorded. No pattern in our tools detects it: both halves of a broken word are plausible tokens, so it is invisible to every guard and was found by eye. also in: THE PARAMETER RANGE IS DERIVED FROM A PROPERTY OF THE OBJECTIVE, NOT CHOSEN: because the objective has integer eigenvalues, one angle can be restricted to lie between 0 and 2 pi	`mechanisms[2]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: MONOTONICITY IS STRUCTURAL RATHER THAN EMPIRICAL: the maximisation at p minus one IS a constrained maximisation at p, so the best value at each depth can never fall below the best value at the depth beneath it	`mechanisms[3]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: A WORD IS SPLIT BY A SPURIOUS SPACE INSIDE THIS QUOTE - "a strin g z" for "a string z". The extraction inserts a space at what was a line break in the PDF, and it does this throughout this file. The quote is an exact substring of the staged text and the meaning is unaffected, but A READER SEARCHING FOR THE UNBROKEN WORD WILL NOT FIND IT, which is the whole reason this is recorded. No pattern in our tools detects it: both halves of a broken word are plausible tokens, so it is invisible to every guard and was found by eye. also in: the algorithm is used by repetition rather than by a single shot: measure in the computational basis, evaluate the objective on the string obtained, and repeat with the SAME angles - enough repetitions produce a string whose value is very near or above the expectation	`mechanisms[4]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: the authors name the difficulty rather than presenting the method as complete - it is not obvious in advance how to pick good angles - and for p that does not grow with n they offer a search over a fine grid on the compact parameter set	`mechanisms[5]`	0.85	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: the grid search is made tractable by a BOUND ON THE PARTIAL DERIVATIVES of the objective's expectation, which is what turns a search over a continuous compact set into an efficient one	`mechanisms[6]`	0.95	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: A WORD IS SPLIT BY A SPURIOUS SPACE INSIDE THIS QUOTE - "an e fficient" for "an efficient". The extraction inserts a space at what was a line break in the PDF, and it does this throughout this file. The quote is an exact substring of the staged text and the meaning is unaffected, but A READER SEARCHING FOR THE UNBROKEN WORD WILL NOT FIND IT, which is the whole reason this is recorded. No pattern in our tools detects it: both halves of a broken word are plausible tokens, so it is invisible to every guard and was found by eye. also in: for fixed p and bounded clause participation the angles are found by an EFFICIENT CLASSICAL CALCULATION rather than by quantum search, and those angles are then used to run the quantum computer and produce the measured string	`mechanisms[7]`	0.85	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: 2026-08-16: A WORD IS SPLIT BY A SPURIOUS SPACE INSIDE THIS QUOTE - "an orthonormal ba sis" for "an orthonormal basis". The extraction inserts a space at what was a line break, throughout this file. Separately, this span was NARROWED: it originally ran through equation (39), whose large brace is stored as Private Use Area codepoints U+F8F1-U+F8F3. An internal tool refused it; the merge gate's dry run had reported it clean. also in: THE CONSTRAINT IS ENFORCED BY THE BASIS: for the independent-set variant the orthonormal basis consists only of strings that correspond to independent sets, so the space is exponentially large but smaller than the full 2^n, and is NOT a simple tensor product of qubits	`mechanisms[8]`	0.85	the tagger's words
mechanisms	mechanisms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: the mixing operator is likewise restricted rather than penalised: it is the adjacency matrix of the hypercube confined to the legal strings, so the walk it generates can only ever move between independent sets	`mechanisms[9]`	0.95	the tagger's words
limitations	the classical preprocessing to choose the angles can require space doubly exponential in p Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted. Update, 15 September 2026: CLEARED evidence status='quote-not-in-current-staged-text' - the quote now locates in the current staged text, so the condition the marker recorded no longer holds.	`limitations[0]`		the tagger's words
limitations	The authors state their headline result is beaten by classical methods already known. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the p = 1 performance reported here for 3-regular graphs: the authors state it	`limitations[1]`	1.0	the tagger's words
limitations	The next case up is analysed only partially, and the paper says so. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: any extrapolation from p = 1 to larger p: the authors state the p = 2 case on 3-regular graphs is more complicated and that they show only partial results for it	`limitations[2]`	1.0	the tagger's words
limitations	The cost of the improvement is circuit depth, which grows with the same knob that buys the quality. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: the claim that approximation quality improves with p: the depth of the circuit grows linearly with p times, at worst, the number of constraints, so the two move together	`limitations[3]`	1.0	the tagger's words
limitations	There is a property of the input the algorithm at p = 2 is stated to be unable to see at all. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. what this limits: results reported at p = 2 on 3-regular graphs: the authors state the algorithm at that depth cannot detect whether the graph is bipartite, that is, completely satisfiable	`limitations[4]`	1.0	the tagger's words
concepts	MaxCut Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: MaxCut	`concepts[4]`		the paper's words
concepts	QAOA Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: QAOA	`concepts[5]`		the paper's words
concepts	approximation ratio Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: approximation ratio	`concepts[6]`		the paper's words
concepts	classical algorithms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: classical algorithms	`concepts[7]`		the paper's words
concepts	circuit depth Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: circuit depth	`concepts[8]`		the paper's words
senses	the approximation ratio - AS OUTPUT OVER OPTIMUM: the quantity reported is the objective value at the algorithm's own output divided by the true maximum, so it is a ratio against a quantity that must already be known to state it Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[0]`	1.0	the tagger's words
senses	the algorithm's names - ITS OWN ACRONYM SURVIVED AND A SECOND NAME WAS ADDED LATER: the paper calls it the QAOA throughout - its expanded name survives only inside a damaged sentence - while the word the field now uses for its class, variational, appears nowhere in it Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[1]`	1.0	the tagger's words
senses	p - THE ONE KNOB, AND IT SETS BOTH SIDES OF THE TRADE: the paper introduces the algorithm as depending on an integer p, with quality improving as p rises and circuit depth rising with it, so a result quoted without its p is not a result about this algorithm Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`senses[2]`	0.9	the tagger's words
claim_relations	builds-on → the quantum adiabatic algorithm Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`claim_relations[0]`		the tagger's words
concept_edges	QAOA —contrasted-with→ classical algorithms Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. strength of the relation: 1 Audit 2026-09-28: DOUBTFUL - read against its full span and kept, but endpoint by anaphora: 'This p = 1 result' = the QAOA's result (previous sentence). also in: QAOA · classical algorithms	`concept_edges[1]`		the tagger's words
content_tags	0.6924 — guaranteed approximation ratio for MaxCut on 3-regular graphs at p=1 Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.quantities[0]`		the tagger's words
content_tags	2p — variational parameters (γ, β) defining the depth-p QAOA state Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.quantities[1]`		the tagger's words
content_tags	The approximation ratio can be made arbitrarily close to 1 by making p large enough, independent of n. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted.	`content_tags.findings[0]`		the tagger's words
content_tags	For MaxCut on 3-regular graphs at p=1, QAOA guarantees a cut at least 0.6924x the optimum. Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above.	`content_tags.findings[1]`		the tagger's words
content_tags	approximation ratio Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted. also in: approximation ratio	`content_tags.variables[1]`		the tagger's words
content_tags	combinatorial optimization problem Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: combinatorial optimization problem	`content_tags.definitions[0]`		the tagger's words
content_tags	MaxCut Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. about this quote: QUOTE RECOVERED FROM THE PAPER'S OWN CHARACTERS. The recorded quote was LETTERS-ONLY IDENTICAL to this stretch of the staged text but not an exact substring of it - spaces, hyphens, ligature glyphs or mathematical operators differed, so it could never anchor. This is the file's own text between the same two letters: not produced by a rule about the damage, copied out of the file. Round-trip checked (the recovered span is letters-only equal to the original) and length-checked. The text as originally recorded is kept in evidence as extracted. also in: MaxCut	`content_tags.definitions[1]`		the tagger's words
content_tags	mean Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: mean	`content_tags.statistics[0]`		the tagger's words
content_tags	standard-deviation Quotation withheld — this record is not cleared for redistribution. The sentence is in the paper at the link above. also in: standard-deviation	`content_tags.statistics[1]`		the tagger's words

Interpretive choices

Tags that could not be placed in the text:

none — every tag was located in the text

What was deliberately not tagged, and why, is recorded per paper by the tagger. Where a paper has no such record, this page says so rather than implying that nothing was declined.