Alternate a cost unitary with a mixer, p times

What it fills

• Search a cost Hamiltonian for the assignment it minimises

  A cost function over discrete assignments, rewritten as an operator diagonal in the computational basis, is searched for the assignment at or near its minimum — by alternating short unitaries at a fixed, chosen depth, or by interpolating continuously toward the operator's own ground state. Both routes read the same operator; what they promise about the assignment they hand back is where they differ.

When it applies

The objective is specified by $n$ bits and $m$ clauses, $C(z) = \sum_{\alpha=1}^{m} C_\alpha(z)$, read "as an operator which is diagonal in the computational basis" (§I), with each $C_\alpha$ depending "on only a few of the $n$ bits" (§I). The one stated performance guarantee is scoped to a single instance family: "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" (Abstract). Efficient classical angle-finding for fixed $p$ needs a further promise the paper states as a hypothesis rather than a general property: "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 efficient classical calculation that determines the angles that maximize $F_p$" (§I). Outside that bounded-degree, fixed-$p$ regime the paper falls back to a grid search over $[0,2\pi]^p \times [0,\pi]^p$ (§I), and for $p$ growing with $n$ it states only that "a different strategy is proposed" (Abstract), without detailing one in the sections read for this record.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  C(z) = sum_{alpha=1}^{m} C_alpha(z), a sum of m clause terms over n bits   (Sec. I, Eq. 1)
       C read as an operator diagonal in the computational basis
       p >= 1, the number of rounds

U(C, gamma) = product over clauses of exp(-i * gamma * C_alpha)          (Eq. 2)
                                          # gamma restricted to [0, 2*pi) -- C has integer eigenvalues
B = sum_j sigma_j^x                                                      (Eq. 3)
U(B, beta)  = product over qubits of exp(-i * beta * sigma_j^x)          (Eq. 4)
                                          # beta restricted to [0, pi)

|s> = uniform superposition over all 2^n computational basis states      (Eq. 5)

# angle-finding is classical work, done before the quantum computer runs at all
if p is fixed (independent of n) and each bit sits in at most a fixed number of clauses:
    (gamma*, beta*) = angles from an efficient classical calculation         (Sec. II)
else if p is fixed, without that bounded-degree promise:
    (gamma*, beta*) = angles from a grid search over [0,2pi]^p x [0,pi]^p    (Sec. I)
else:                                            # p grows with n
    # "a different strategy is proposed" -- not detailed in the sections read here

|gamma*, beta*> = U(B, beta*_p) U(C, gamma*_p) ... U(B, beta*_1) U(C, gamma*_1) |s>   (Eq. 6)
# produced by a circuit of depth at most m*p + p, without using any structure of the instance

repeat on the order of m * log(m) times:
    measure |gamma*, beta*> in the computational basis -> z
    evaluate C(z)
return the best z seen

# with probability 1 - 1/m, at least one repetition sees C(z) >= Fp(gamma*, beta*) - 1
# for p = 1 on 3-regular graphs this construction is guaranteed a cut >= 0.6924 of optimal;
# no bound is stated at any other p or graph family, and no classical comparison is made

Cost, as the source states it

Circuit depth is "at most $mp + p$" (§I), independent of any classical optimisation cost, because the angles are found before the quantum computer runs at all. Measurement cost is stated with an explicit probability bound: "an outcome of at least $F_p(\gamma, \beta) - 1$ will be obtained with probability $1 - 1/m$ with order $m \log m$ repetitions" (§II). No running time is stated for the algorithm as a whole, and no comparison against any classical algorithm is made anywhere in the sections read here: the 0.6924 figure is an approximation ratio for one instance family at $p = 1$, not a speedup.

Implementations

• The `qaoa_ansatz` function and `QAOAAnsatz` class in Qiskit's circuit library

  Qiskit ships the alternation as a circuit-library object rather than as an algorithm: the caller hands it a cost operator and a repetition count and gets back a parameterised `QuantumCircuit`, with no optimiser, no angle search and no measurement attached. Both entry points are documented as "A generalized QAOA quantum circuit with a support of custom initial states and mixers" and both name this record's source in an identical `References` block — "[1] Farhi et al., A Quantum Approximate Optimization Algorithm. `arXiv:1411.4028`". The function writes its arguments in the paper's own notation: `cost_operator` is "The operator representing the cost of the optimization problem, denoted as $U(C, \gamma)$ in [1]", `mixer_operator` is "An optional custom mixer, which defaults to global Pauli-$X$ rotations. This is denoted as $U(B, \beta)$ in [1]", and `reps` is "The integer determining the depth of the circuit, called $p$ in [1]". The class docstring makes the same two operator identifications with "in the original paper" where the function writes "in [1]", but it is not the same text throughout — its `reps` reads "The integer parameter p, which determines the depth of the circuit, as specified in the original paper, default is 1", and its `initial_state` "If `None` is passed then a set of Hadamard gates is applied as an initial state to all qubits". The class came first and the function was added in Qiskit 1.3, whose release note names the classes as pre-existing equivalents in a sentence that pairs them off: "`evolved_operator_ansatz` and `qaoa_ansatz` are functionally equivalent to `EvolvedOperatorAnsatz` and `QAOAAnsatz`, but generally more performant". `qaoa_ansatz.py` itself carries no deprecation decorator, but every construction of the class in the repository's own test module is wrapped in `self.assertWarns(DeprecationWarning)`; the only deprecation decorator anywhere on the inheritance chain `QAOAAnsatz` → `EvolvedOperatorAnsatz` → `NLocal` sits on `NLocal.__init__`, decorated `@deprecate_func(since="2.1", additional_msg="This applies to NLocal subclasses too. Use the corresponding function from the module qiskit.circuit.library.n_local instead.", removal_timeline="in Qiskit 3.0")`. The functional entry point carries no such warning.

  The defaults reproduce the paper's construction term by term. With `initial_state is None` the function builds `initial_state.h(range(num_qubits))` — a Hadamard on every qubit, which is the paper's $|s\rangle$, "the uniform superposition over computational basis states" (§I, Eq. 5); the docstring states the same intent, "defaults to a layer of Hadamard gates preparing the $|+\rangle^{\otimes n}$ state". With `mixer_operator is None` it builds `SparsePauliOp.from_sparse_list([("X", [i], 1) for i in range(num_qubits)], num_qubits)`, coefficient $1$ on each term, which is the paper's $B = \sum_{j=1}^{n} \sigma_j^x$ (§I, Eq. 3) with the same sign. It then composes that initial state with `evolved_operator_ansatz([cost_operator, mixer_operator], reps=reps, insert_barriers=insert_barriers, parameter_prefix=parameter_prefix, name=name, flatten=flatten)` under `parameter_prefix = ["γ", "β"]`. The alternation is therefore delegated, and it is that callee's docstring that states the order: "For a set of operators $[O_1, ..., O_J]$ and $R$ repetitions (`reps`), this circuit is defined as $\prod_{r=1}^{R} \left( \prod_{j=J}^1 e^{-i\theta_{j, r} O_j} \right)$" — with $O_1$ the cost operator and $O_2$ the mixer, the inner product is $e^{-i\beta_r B} e^{-i\gamma_r C}$, the order of the paper's Eq. (6). The angle ranges are the one place the construction departs from the paper, and the two entry points depart differently. §I bounds both angles: the cost angle, "Because $C$ has integer eigenvalues we can restrict $\gamma$ to lie between 0 and $2\pi$", and the mixer angle, "where $\beta$ runs from 0 to $\pi$". `QAOAAnsatz.parameter_bounds` bounds only one of the two, and not to the paper's width: it sets `beta_bounds = (0, 2 * np.pi)` and `gamma_bounds = (None, None)`, appending `self.reps` copies of `beta_bounds` when the mixer is not a Pauli identity and `self.reps` copies of `gamma_bounds` when the cost operator is not. So the mixer angles are bounded to $[0, 2\pi]$ rather than $[0, \pi]$, and the cost angles are left unbounded — consistent with a `cost_operator` typed as an arbitrary `BaseOperator`, which the paper's integer-eigenvalue premise does not cover. The repository asserts exactly this in `test_parameter_bounds`: for `QAOAAnsatz(Pauli("Z"), reps=2)` the first two bounds are $(0, 2\pi)$ and the remaining two are `(None, None)`. That property belongs to the class alone; the function returns a plain `QuantumCircuit`, which carries no `parameter_bounds` at all, so the current entry point states no angle ranges rather than different ones.

  No dataset — the artefact is a circuit constructor, and nothing in it evaluates an objective. Its test module exercises it on hand-written operators rather than on problem instances. The cost operators are `Pauli("I")`, `Pauli("Z")`, `Pauli("IZ")`, `Pauli("ZZ")`, `Pauli("IIII")`, `Pauli("I" * num_qubits)` for `num_qubits` in `range(1, 5)`, `SparsePauliOp.from_list([("I" * num_qubits, 1)])` and `SparsePauliOp(["Z"], coeffs=[1 + 0j])`; the custom mixers are `Pauli("Y")`, `Pauli("Z")` and hand-built one- and two-qubit `QuantumCircuit`s; and `test_empty_op` constructs the class with no cost operator at all. `reps` is exercised at 0, 1, 2, 4 and 5, and at $-1$ in `test_invalid_reps`, which asserts a raise. No graph, no molecule, no simulator and no hardware backend is named anywhere in `test_qaoa_ansatz.py`.

  `qiskit/circuit/library/n_local/qaoa_ansatz.py` in https://github.com/Qiskit/qiskit — Python, Apache License 2.0 ("This code is licensed under the Apache License, Version 2.0", file header; GitHub reports the repository licence as `Apache-2.0`). Read at tag 2.5.2. The file holds two entry points, the module-level function `qaoa_ansatz` and the class `QAOAAnsatz(EvolvedOperatorAnsatz)`; the alternation itself is delegated to `evolved_operator_ansatz` in the sibling file `qiskit/circuit/library/n_local/evolved_operator_ansatz.py`, and the deprecation the class inherits is declared on `NLocal.__init__` in `qiskit/circuit/library/n_local/n_local.py`. The tests are `test/python/circuit/library/test_qaoa_ansatz.py`, 256 lines. The release note that introduced the function is `releasenotes/notes/1.3/clib-evolved-ops-e91c00964c0209ce.yaml`.

  The repository reports no cut, no energy and no approximation ratio for this circuit; its test module asserts structure only. `test_zero_reps` asserts that `qaoa_ansatz(Pauli("IIII"), reps=0)` equals a four-qubit circuit of Hadamards alone. `test_default_qaoa` asserts one free parameter and that the first two operations are an `HGate` then an `RXGate`. `test_rebuild` starts from `QAOAAnsatz(cost_operator=Pauli("IZ"))`, resets the cost operator to `Pauli("Z")` and `reps` to 5, and asserts `1` qubit and `10` parameters. `test_circuit_mixer` asserts `3 * reps` parameters at `reps = 4` for a two-parameter circuit mixer on `Pauli("ZZ")`. `test_identity` asserts that a cost operator of $I^{\otimes 3}$ with a default mixer leaves `reps` parameters and with an identity mixer leaves `0`. `test_sympify_is_real` asserts that for `SparsePauliOp(["Z"], coeffs=[1 + 0j])` the first rotation's angle equals `2.0 * param`. The 0.6924 ratio of §V of arXiv:1411.4028 appears nowhere in the file or its tests.

• PennyLane's `qml.qaoa` module — `cost_layer`, `mixer_layer`, `x_mixer` and `maxcut`

  Xanadu's PennyLane ships the two halves of the alternation as separate callables and leaves the repetition to the caller. The module docstring describes it as "a collection of methods that help in the construction of QAOA workflows" and groups its contents under "Mixer Hamiltonians", "Cost Hamiltonians", "QAOA Layers" and "Cycle Optimization". It arrived in release v0.11.0, published 2020-08-18, whose changelog reads "Added built-in QAOA functionality via the new `qml.qaoa` module" and lists "Layers: `qml.qaoa.cost_layer` and `qml.qaoa.mixer_layer` take cost and mixer Hamiltonians, respectively, and apply the corresponding QAOA cost and mixer layers". `x_mixer`'s own docstring names this record's source: "This is mixer is used in *A Quantum Approximate Optimization Algorithm* by Edward Farhi, Jeffrey Goldstone, Sam Gutmann [`arXiv:1411.4028`]" — the wording is the docstring's own.

  `cost_layer(gamma, hamiltonian)` documents itself as "For the cost Hamiltonian $H_C$, this is defined as the following unitary: $U_C \ = \ e^{-i \gamma H_C}$" and `mixer_layer(alpha, hamiltonian)` as "For a mixer Hamiltonian $H_M$, this is defined as the following unitary: $U_M \ = \ e^{-i \alpha H_M}$" — note the mixer angle is named `alpha`, where §I of arXiv:1411.4028 writes $\beta$. Both return `ApproxTimeEvolution(hamiltonian, angle, 1)`, a single Trotter step, and `ApproxTimeEvolution`'s own docstring is explicit about when that is not the stated unitary: "this decomposition is exact for any value of $n$ when each term of the Hamiltonian commutes with every other term." For the paper's own two operators that condition holds on both sides, and the paper says so of each: of the mixer, §I introduces $U(B,\beta)$ as "the $\beta$ dependent product of commuting one bit operators" (preceding Eq. 4); of the cost unitary, §I says in the same breath as Eq. (2) that "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 $\alpha$". The module's other two mixers, `xy_mixer` and `bit_flip_mixer`, are covered by neither quote and this record does not check them. For the cost layer the diagonality that carries that argument is enforced, not assumed. `_diagonal_terms` walks `hamiltonian.terms()[1]` and returns `False` for any factor whose `name` is not `"PauliZ"` or `"Identity"`; `cost_layer` then raises `ValueError("hamiltonian must be written only in terms of PauliZ and Identity gates")`. Every Hamiltonian it accepts is therefore a sum of `PauliZ` and `Identity` products, whose terms commute. That check is the executable form of "view[ed]... as an operator which is diagonal in the computational basis" (§I). `x_mixer(wires)` builds $H_M \ = \ \displaystyle\sum_{i} X_{i}$ with `coeffs = [1 for w in wires]` — the paper's $B$, same sign. The alternation is assembled by the caller. The module's documentation page defines `def qaoa_layer(gamma, alpha): qaoa.cost_layer(gamma, cost_h); qaoa.mixer_layer(alpha, mixer_h)` and then a circuit that applies `qp.Hadamard(wires=w)` to every wire before `qp.layer(qaoa_layer, 2, params[0], params[1])`; `qp.layer` is not part of `pennylane/qaoa/`. On the objective the sign convention is inverted against the paper. `qaoa.maxcut(graph)` returns $H_C \ = \ \frac{1}{2} \displaystyle\sum_{(i, j) \in E(G)} \big( Z_i Z_j \ - \ \mathbb{I} \big)$, which is minus the paper's Eq. (12) clause $C_{\langle jk \rangle} = \frac{1}{2}\left(-\sigma_j^z \sigma_k^z + 1\right)$ (§II); correspondingly the documentation page optimises "until the expected value of the cost Hamiltonian is minimized", where Eq. (11) (§II) asks for a string that makes $C$ "as large as possible".

  MaxCut on small graphs, on a simulator. The documentation page and the integration test both run the triangle `Graph([(0, 1), (1, 2), (2, 0)])` on three wires, and `test_module_example_rx` repeats it as a `rustworkx` `PyGraph` with the same three edges; `maxcut`'s own docstring example uses the two-edge path `Graph([(0, 1), (1, 2)])`. The device named in both the page and the integration tests is `qp.device("default.qubit", wires=len(wires))`, PennyLane's state-vector simulator; no hardware backend is named. The layer tests in `TestLayers` name no device at all — they queue the operation in a `qp.queuing.AnnotatedQueue()` and compare `out.decomposition()` against an explicit gate list.

  `pennylane/qaoa/` in https://github.com/PennyLaneAI/pennylane — Python, Apache License 2.0 ("Licensed under the Apache License, Version 2.0" in each file header; GitHub reports the repository licence as `Apache-2.0`). The four files that carry this method are `layers.py` (`cost_layer`, `mixer_layer`, `_diagonal_terms`), `mixers.py` (`x_mixer`), `cost.py` (`maxcut`) and `__init__.py` (the module docstring and the re-exports listed in `__all__`). The tests are `tests/test_qaoa.py`, 2077 lines, of which the classes read here are `TestLayers` and `TestIntegration`; the prose walkthrough is `doc/code/qp_qaoa.rst`, whose examples import the package under the newer `qp` alias rather than the `qml` of the v0.11.0 changelog. Read from the `main` branch; this entry claims no release version beyond v0.11.0, where the module first shipped.

  One number, and it is asserted rather than only printed. `doc/code/qp_qaoa.rst` ends its MaxCut walkthrough with `>>> print(cost_function([[1, 1], [1, 1]]))` giving `-1.8260274380964299`, for the triangle at two layers with all four angles set to 1 on `default.qubit`; `TestIntegration.test_module_example` runs the same circuit and asserts `np.allclose(res, expected, atol=tol, rtol=0)` against `expected = -1.8260274380964299`. By the $H_C$ quoted above — $-1$ per cut edge, $0$ per uncut edge — that value is minus the expected number of cut edges. The layer tests report exact decompositions rather than energies: at `gamma = 1`, `cost_layer` on `qaoa.maxcut(Graph([(0, 1), (1, 2), (2, 0)]))[0]` decomposes to `PauliRot(1.0, "ZZ", wires=[0, 1])`, `PauliRot(1.0, "ZZ", wires=[0, 2])` and `PauliRot(1.0, "ZZ", wires=[1, 2])`, and at `alpha = 1`, `mixer_layer` on `qaoa.xy_mixer(Graph([(0, 1), (1, 2), (2, 0)]))` decomposes to six `PauliRot(1.0, ...)` gates. No approximation ratio is reported in the module, its tests or its documentation page.

• OpenQAOA's `QAOADescriptor` and its `abstract_circuit`

  • OpenQAOA -- An SDK for QAOA

  Entropica Labs' OpenQAOA is a "Multi-backend SDK for quantum optimisation" (the repository's own description) whose whole subject is this method and its descendants, rather than an application built on top of it. Its paper reviews the construction in §III and names this record's source as the baseline the SDK generalises from: "we refer to the original implementation of QAOA in Ref. [4] as standard QAOA", reference [4] being "E. Farhi, J. Goldstone, and S. Gutmann, 'A quantum approximate optimization algorithm,' arXiv preprint, 2014." §III A writes the standard ansatz as "$|\Psi(\gamma, \beta)\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_m} e^{-i\gamma_k H_c} |+\rangle^{\otimes n}$" (Eq. 1), states that "The circuit is initialised in the state $|+\rangle^{\otimes n}$, where $n$ is the number of qubits", and defines the repetition count: "the parameter $p$ corresponds to the number of layers in the circuit ansatz". The paper reports no benchmark: it carries three figures, all of them schematics of the software's own structure, and no table of measured values.

  `QAOADescriptor(cost_hamiltonian, mixer_block, p, mixer_coeffs=[], routing_function=None, device=None)` turns the two Hamiltonians into gate blocks — `self.cost_block = self.block_setter(cost_hamiltonian, GateMapType.COST)` — and its `abstract_circuit` property performs the alternation in an explicit loop: `for each_p in range(self.p):` it runs `_abstract_circuit.extend(self.cost_blocks[each_p][:: (even_layer_inversion) ** each_p])` and then `_abstract_circuit.extend(mixer_block)`. Cost block, then mixer block, `p` times. The gate order inside the cost block is reversed on alternate layers only when SWAP routing is in play — `even_layer_inversion = -1 if self.routed == True else 1`, commented "even layer inversion if the circuit contains SWAP gates" — and the mixer block is likewise reordered by `self.reorder_gates_block(self.mixer_blocks[each_p], each_p)` in that case only. The docstring names `p` as "Number of QAOA layers; defaults to 1 if not specified". Both Hamiltonians are the negation of those in arXiv:1411.4028. `X_mixer_hamiltonian(n_qubits)` sets `coeffs = [-1] * n_qubits if coeffs is None else coeffs` under the comment "If no coefficients provided, set all to -1", giving $H_m = -\sum_i X_i$ where §I of arXiv:1411.4028 defines $B = \sum_{j=1}^{n} \sigma_j^x$; the SDK paper writes the same minus sign, "the mixer operator is constructed from the Hamiltonian $H_m = -\sum_i X_i$". `ring_of_disagrees(reg)` builds the $n$ ring edges with `coeffs = [0.5] * len(terms)` and `constant = -len(terms) * 0.5`, i.e. $\frac{1}{2}\sum_i Z_i Z_{i+1} - n/2$, which is minus the $C$ of Eq. (11)–(12) (§II of arXiv:1411.4028); its docstring points back at the same paper — "This model is introduced in https://arxiv.org/abs/1411.4028".

  The ring of disagrees on 8 qubits — the 2-regular MaxCut instance of §IV of arXiv:1411.4028 — built as `ring_of_disagrees(range(8))` with `X_mixer_hamiltonian(8)`. The workflow tests add a weighted 3-regular graph, `random_k_regular_graph(degree=3, nodes=range(8), seed=2642, weighted=True, biases=False)`, cast to a QUBO by `MaximumCut(g).qubo`. Everything the two test modules read here run on is a simulator, and no QPU is named in either: `test_analytical_simulator.py` constructs `QAOABackendAnalyticalSimulator` and `create_device(location="local", name="analytical_simulator")`, and `test_sim_qiskit.py` imports and constructs three more — `QAOAQiskitBackendStatevecSimulator`, `QAOAQiskitBackendShotBasedSimulator` and `QAOAvectorizedBackendSimulator`. The paper states the SDK supports "Amazon Braket, IBMQ, and Rigetti Computing's Quantum Cloud Services".

  https://github.com/entropicalabs/openqaoa — Python, MIT licence (GitHub reports `license.spdx_id` as `MIT`). The construction is the class `QAOADescriptor(AnsatzDescriptor)` and its `abstract_circuit` property in `src/openqaoa-core/openqaoa/qaoa_components/ansatz_constructor/baseparams.py` (500 lines); the Hamiltonian helpers `X_mixer_hamiltonian` and `ring_of_disagrees` are in `src/openqaoa-core/openqaoa/utilities.py`; the angles are carried by `QAOAVariationalStandardParams`. The repository is split into five distributions — `openqaoa-core`, `openqaoa-qiskit`, `openqaoa-braket`, `openqaoa-pyquil` and `openqaoa-azure` — under `src/`. Read from the `main` branch. The newest release is v0.2.6, published 2024-07-10, which is also the date of the newest commit on `main` (`c6e7dd7`). `main` has had no commit since; the repository has — its `dev` branch carries a commit of 2024-08-29, which is the repository's `pushed_at`. It is not archived, and this entry claims nothing about whether it is maintained.

  The two test modules evaluate the ring of disagrees at one hard-coded angle pair rather than searching for one, and assert the same value twice by two different routes. In `src/openqaoa-core/tests/test_analytical_simulator.py`, `test_expectation` — "Testing if the analytical formula returns the energy expectation value for a given beta and gamma on an easy problem (Ring of disagree)" — builds `ring_of_disagrees(range(8))` with `X_mixer_hamiltonian(8)`, `p = 1`, `betas = [np.pi / 8]` and `gammas = [np.pi / 4]`, and asserts `np.isclose(exp_val, -6)`. In `src/openqaoa-qiskit/tests/test_sim_qiskit.py`, `test_cost_call` runs the same instance and the same angles through `QAOAQiskitBackendStatevecSimulator(qaoa_descriptor, prepend_state=None, append_state=None, init_hadamard=True)` and asserts `np.isclose(exp_qiskit_statevec, -6)`. On the same instance `test_exact_solution` reads `backend_analytical.exact_solution` and asserts `correct_energy = -8` with `correct_config = [0, 1, 0, 1, 0, 1, 0, 1]`; its angles sit under the comment "# The tests pass regardless of the value of betas and gammas is this correct?", so that one is an exact minimisation rather than a variational result. Neither module maximises over angles and neither names §IV of arXiv:1411.4028, so the correspondence with the paper is this record's arithmetic and not the repository's claim: under this repository's sign convention ($\frac{1}{2}\sum_i Z_i Z_{i+1} - n/2 = -C$) the two asserted values are minus 6 and minus 8, while §IV concludes $M_p = n(2p + 1)/(2p + 2)$, giving $M_1 = 6$ at $n = 8$, and states that "the best cut is $n$" $= 8$. Whether $\beta = \pi/8$, $\gamma = \pi/4$ are §IV's maximising angles is stated in neither document; what is checkable is that the asserted value and $M_1$ agree. The analytical backend is restricted to this case by construction: `test_p_not_1_fails` asserts it raises at `p = 2`, `test_different_mixer_fails` asserts it raises for an XY mixer, and `test_not_standard_params_fails` asserts it raises for `param_type="extended"` and `param_type="fourier"`. No approximation-ratio figure is reported by either test module.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Interpolate slowly to the problem Hamiltonian

  Build a time-dependent Hamiltonian H(t) that starts at an initial Hamiltonian whose ground state is trivial to prepare and ends at the final Hamiltonian encoding the problem, interpolate between them over a time T, and let the state track the instantaneous ground state along the whole path. The adiabatic theorem proves this works whenever the gap above the ground state never closes and T is long enough — and the same paper states, in the same breath, that outside a few symmetric special cases it cannot say how long that is.

In the Atlas

• The Quantum Approximate Optimization Algorithm

  A quantum algorithm that produces approximate solutions for combinatorial optimization problems, tunable by a positive integer p.

• QAOA MaxCut on a 5-node ring

  A p=1 QAOA circuit with a classical MaxCut comparison and reproducible simulation evidence.

• QAOA scaling on the low autocorrelation binary sequences (LABS) problem

  Given the low autocorrelation binary sequences (LABS) problem, an optimization problem that is classically intractable even for moderately sized instances, determine whether QAOA can act as an algorithmic component that provides an advantage over the best classical exact solvers.

Sources

• A Quantum Approximate Optimization Algorithm↗Edward Farhi, Jeffrey Goldstone, Sam Gutmann · 2014theory yes · simulation ? · hardware ?