phenomenon · claim-type · cross-domain-transfer · mechanism · claim-relation · replication-status · limitation — grounded in the full text| phenomenon | approximate solutions to combinatorial optimization problems— “Approximate optimization asks for a string z for which C(z) is close to the maximum of C.” | |
| claim-type | method— “The QAOA can be run on a quantum computer with p growing with n as long as there is a strategy for choosing sets of angles.” | |
| method — evidence | — “It is possible to analyze the performance of the QAOA for p = 2 on 3-regular graphs.” | |
| mechanism | 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— “We introduce a quantum algorithm that produces approximate solutions for combinatorial op- timization problems. The algorithm depends on an integer p ≥ 1 and the quality of the approx- imation improves as p is increased.” | mechanisms[0] |
| mechanism | 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— “All of the terms in this product commute because they are diagonal in the computational basis and each term’s locality is the locality of the clause α .” | mechanisms[1] |
| mechanism | 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— “Because C has integer eigen- values we can restrict γ to lie between 0 and 2 π.” | mechanisms[2] |
| mechanism | 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— “Note that the maximization at p − 1 can be viewed as a constrained maximization at p so Mp ≥ Mp−1. (9)” | mechanisms[3] |
| mechanism | 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— “Use the quantum computer to get the state |γ , β ⟩. Measure in the computational basis to get a string z and evaluate C(z). Repeat with the same angles. Enough repetitions will produce a strin g z with C(z) very near or greater than Fp” | mechanisms[4] |
| mechanism | 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 rub is that it is not obvious in advance how to pick good angles. If p doesn’t grow with n, one possibility is to run the quantum computer with angles (γ , β ) chosen from a fine grid on the compact set [0 , 2π]p × [0, π ]p, moving through the grid to find the maximum of Fp.” | mechanisms[5] |
| mechanism | 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— “Since the partial derivatives of Fp(γ , β ) in (7) are bounded by O(m2 + mn) this search will efficiently produce a string z for which C(z) is close to Mp or larger.” | mechanisms[6] |
| mechanism | 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— “However we show in the next section that if p does not grow with n and each bit is involved in no more than a fixed number of clauses, then there is an e fficient classical calculation that determines the angles that maximize Fp. These angles are then used to run the quantum computer to produce the state |γ , β ⟩ which is measured in the… | mechanisms[7] |
| mechanism | 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 Hilbert space for our quantum algorithm has an orthonormal ba sis |z⟩ where z is any string corresponding to an independent set. In cases of interest , the Hilbert space dimension is exponentially large in n, though not as big as 2 n. The Hilbert space is not a simple tensor product of qubits.” | mechanisms[8] |
| mechanism | 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— “Note that B is the adjacency matrix of the hypercube restricted to the legal s trings, that is, those that correspond to independent sets in the given graph.” | mechanisms[9] |
| builds-on | the quantum adiabatic algorithm— “There is an adiabatic path (which stays at th e top of the spectrum throughout) with run time T that achieves this as T goes to infinity.” | claim_relations[0] |
| sense | 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— “ratio is C(z), where z is the output of the quantum algorithm, divided by the maximum of C” | senses[0] |
| sense | 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 | senses[1] |
| sense | 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 | senses[2] |
| audit | QAOA —contrasted-with→ classical algorithms — 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). | concept_edges[1] |
| evidence status note | limitation — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[0] |
| for which use | limitation — the p = 1 performance reported here for 3-regular graphs: the authors state it Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[1] |
| for which use | limitation — 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 Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[2] |
| for which use | limitation — 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 Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[3] |
| for which use | limitation — 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 Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[4] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[0] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[2] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[4] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[7] |
| evidence status note | mechanism — 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. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | mechanisms[8] |
| replication | untested | |
| limitation | the classical preprocessing to choose the angles can require space doubly exponential in p Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[0] |
| limitation | The authors state their headline result is beaten by classical methods already known. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[1] |
| limitation | The next case up is analysed only partially, and the paper says so. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[2] |
| limitation | The cost of the improvement is circuit depth, which grows with the same knob that buys the quality. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[3] |
| limitation | There is a property of the input the algorithm at p = 2 is stated to be unable to see at all. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | limitations[4] |
finding · quantity · variable · definition · key-term — grounded in the full text| finding | The approximation ratio can be made arbitrarily close to 1 by making p large enough, independent of n. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.findings[0] |
| evidence status note | finding — 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] |
| finding | For MaxCut on 3-regular graphs at p=1, QAOA guarantees a cut at least 0.6924x the optimum. Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.findings[1] |
| quantity | 0.6924 — guaranteed approximation ratio for MaxCut on 3-regular graphs at p=1 Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.quantities[0] |
| quantity | 2p angles — variational parameters (γ, β) defining the depth-p QAOA state Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.quantities[1] |
| variable | approximation ratio (dependent) Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.variables[1] |
| evidence status note | variable — 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.variables[1] |
| definition | combinatorial optimization problem Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.definitions[0] |
| definition | MaxCut Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.definitions[1] |
| evidence status note | definition — 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.definitions[1] |
| key-terms | quantum, algorithm, optimization, circuit, MaxCut, graphs, unitary, objective, combinatorial |
| concept | MaxCut Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | concepts[4] |
| concept | QAOA Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | concepts[5] |
| concept | approximation ratio Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | concepts[6] |
| concept | classical algorithms Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | concepts[7] |
| concept | circuit depth Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | concepts[8] |
| mean μ | as written: mean of Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.statistics[0] |
| standard-deviation SD/σ | Quotation withheld — this paper is not ours to reproduce, and the page has already quoted as much of it as the rights layer allows. The tag, its field and its confidence stand; the sentence is at the publisher. | content_tags.statistics[1] |
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.
Tag layer © the Meta-Tagging Project, CC BY 4.0. The paper text is © its authors/publisher
and is linked, not reproduced. Excerpts shown are short quotations for identification and verification.
· back to index
· concepts · authors
· עברית
© 2026 Shir Sivroni · ORCID 0009-0000-2597-2824