Measure commuting terms together

What it fills

• Estimate an observable

  Given the ability to prepare $|ψ⟩$ and a description of an observable $O$, return a classical scalar within $\varepsilon$ of $⟨O⟩$ at confidence $1−δ$. The state is never returned; only the number is.

When it applies

Verteletskyi et al. state the constraint that creates the problem — "current hardware can perform only projective single-qubit measurements", while "the number of terms in the Hamiltonian grows as $O(N^4)$ with the size of the system" — and then name the problem exactly: "qubit-wise commutativity between the Hamiltonian terms can be expressed as a graph and the problem of the optimal grouping is equivalent of finding a minimum clique cover (MCC) for the Hamiltonian graph". Two honest limits come with it. The optimum is not available — "the MCC problem is NP-hard but there exist several polynomial heuristic algorithms to solve it approximately" — and the saving quoted is measured rather than proved: "on average, grouping qubit-wise commuting terms reduced the number of operators to measure three times compared to the total number of terms in the considered Hamiltonians", on a set of molecular electronic Hamiltonians.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• Prepare an input state

  Map $|0\ldots0⟩$ to a state whose amplitudes are proportional to a specified vector $b$, to within $\varepsilon$. The cost is set by which description of $b$ you hold, not by the algorithm that consumes it.

  What this method asks for is one object: "a quantum state of an artificial qubit system $|\Psi_q\rangle$ that emulates $|\Psi(R)\rangle$", on which it "performs projective measurements". Grouping fixes how often that state is spent — once per group $\hat A_n$ of $\hat H_q = \sum_{n}\hat A_n$, not once per Pauli word $\hat P_I$ — because "partitioning of the $\hat H_q$ in Eq.~(5) allows one to measure all Pauli words within each $\hat A_n$ group in a single set of $N$ one-qubit measurements", one per qubit, after a pre-measurement rotation aligns $|\Psi_q\rangle$ with that group's shared eigenbasis using "only one-qubit unitary rotations". The disadvantage the paper states for a partition whose group count has not been minimized falls on this interface: "the Hamiltonian may require to measure too many $\hat A_n$ terms separately". assumption: the paper counts groups, not copies of $|\Psi_q\rangle$; no per-group or per-shot resupply count is stated.

  assumption

Example

given  qubit Hamiltonian  Hq = sum_I  C_I * P_I
       each Pauli word  P_I = tensor_{i=1..N} sigma_i^(I),  sigma_i^(I) in {X, Y, Z, I}   (Eq. 2-3)
       hardware that can perform only single-qubit projective measurements                (Sec. I)
       a state-preparation routine that produces |Psi_q>, invoked before each group's
           measurement round below (not once per Pauli word)

requires  a grouping relation strong enough that ALL terms in a group share one
    single-qubit measurement basis -- ordinary commuting is not enough: z1z2 and
    x1x2 commute and share eigenstates, but "they cannot be measured at the same
    time using single-qubit projective measurements"                            (Sec. I)
    the relation used is qubit-wise commuting (QWC), strictly stronger than
    commuting: QWC implies commuting but not conversely -- e.g. [x1x2,y1y2] = 0
    while [x1x2,y1y2]_qw != 0                                                   (Sec. II A, Eq. 4)

# --- build the QWC graph ----------------------------------------------------
for every pair (P_I, P_J) of Pauli words in Hq:
    [P_I, P_J]_qw = 0   if  [sigma_i^(I), sigma_i^(J)] = 0  for every qubit i
                    1   otherwise                                               (Eq. 4)
    add an edge (P_I, P_J) to graph G  iff  [P_I, P_J]_qw = 0
        # "the two conditions that are satisfied for the QWC relation are
        #   enough to represent the QWC relation as graph edges between the
        #   Pauli words of the Hamiltonian"                                     (Sec. II A)

# QWC is reflexive and symmetric but NOT transitive -- [x1,y2]_qw = 0 and
#   [y2,z1]_qw = 0 do not imply [x1,z1]_qw = 0 -- so it is NOT an equivalence
#   relation and there is no unique, canonical partition into groups            (Sec. II A)

# --- grouping = minimum clique cover (MCC) of G ------------------------------
# a set of mutually QWC terms is exactly a clique of G; splitting Hq into
#   groups A_n, each a clique, lets every Pauli word inside A_n be read from a
#   single set of N one-qubit measurements -- one measurement setting covers
#   the whole group at once                                                     (Eq. 5-6, Sec. II A)
Hq = sum_n  A_n,   A_n = sum_I  C_I^(n) P_I^(n),   with every pair inside A_n QWC   (Eq. 5-6)

# fewest groups = minimum clique cover of G, and MCC "is NP-hard in general,
#   and its decision version is NP-complete" -- so the optimum is not computed;
#   a polynomial heuristic approximates it instead                              (Sec. II A, ref. 17)

# --- heuristic actually used: color the COMPLEMENT graph ---------------------
Gbar = complement(G)
    # "the chromatic number chi(Gbar) is equal to the minimum number of
    #   cliques in G" -- so coloring Gbar solves the same problem as MCC on G   (Sec. II B.1)
order the vertices v_1, ..., v_n by the Largest First (LF) rule:
    # "puts the vertices of Gbar in the non-increasing degree order"
    #   (Sec. II B.1, ref. 19)
    # LF is one of SEVEN orderings the paper tests (GC, LF, SL, DSATUR, RLF,
    #   DB, COSINE) -- it is reported best, not proved optimal: "LF performance
    #   was superior to the other techniques in both the number of produced
    #   cliques and execution time", and across all seven "the difference
    #   between various methods does not exceed approximately 10%"              (Sec. III)
k = 1
color(v_1) = 1
for v in v_2 .. v_n, in that order:
    S = colors already assigned to v's neighbors in Gbar
    if S contains every color in {1, ..., k}:
        k = k + 1
        color(v) = k
    else:
        color(v) = lowest color in {1, ..., k} not in S                         (Sec. II B.1)

# each color class is one group A_n -- a clique of G, hence a QWC set           (Eq. 5)

# --- alternative NOT used for the recommended results ------------------------
# repeatedly find and remove a maximum clique from G instead of coloring Gbar;
#   even an EXACT maximum-clique search "does not necessarily form the minimum
# clique cover" -- this route can be non-optimal even without heuristic error (Sec. II B.2, Fig. 3)
# two such heuristics were tested: BKT (exact Bron-Kerbosch-Tomita max-clique
#   search -- not polynomial) and Ramsey (a polynomial NetworkX routine, the
#   one used in Rigetti's pyQuil). "DB, COSINE, and Ramsey spent almost two
#   orders of magnitude longer times for 14-qubit H2O than other algorithms,
#   and therefore could not be recommended for use in larger Hamiltonians"      (Sec. III)

# --- measurement, one group at a time -----------------------------------------
for each group A_n:
    apply the one-qubit unitary rotation, one per qubit, that brings |Psi_q>
        into A_n's shared eigenbasis
        # "the current approach involves only one-qubit unitary rotations" --
        #   the paper does not name the specific rotation, only that it is
        #   single-qubit
        #   (Sec. IV, Conclusion)
    measure all N qubits projectively, once
        # a single set of N one-qubit outcomes fixes every Pauli word's
        #   eigenvalue in this group: "it is known from the form of An, what
        #   Pauli operator needs to be measured"                                (Sec. II A)
    combine the N outcomes (product per Pauli word, weighted sum by C_I) into
        an estimate of <A_n>
        # the paper never writes this combination formula; it is the mechanical
        #   consequence of the line above, not a quoted derivation

return  <Hq> = sum_n <A_n>,  accumulated over one measurement setting per
    group instead of one per Pauli word

# --- what the reduction actually is ------------------------------------------
# reported as MEASURED on instances, never proved.
# Table I -- 7 systems, 4 to 14 qubits, at most 1086 terms (H2O BK and JW; the
#   caption itself says "systems with up to 1100 terms"): "the number of An
#   groups is 3 to 5 times fewer than the number of Pauli words"                (Sec. III, Table I)
# Table II -- 8 systems, LF only. The largest system is 36 qubits with 34639
#   terms (N2/6-31G) and the largest term count is 52758 at 30 qubits
#   (NH3/6-31G): NO single row carries both maxima                              (Table II)
# the paper's summary of Table II reads "higher than or equal to three-fold
#   reduction ... independent of the type of the fermion-qubit mapping", but
#   its OWN Table II contradicts that on 4 of its 16 entries -- N2/STO-3G
#   2951/1178 = 2.5 (BK) and 2951/1187 = 2.5 (JW), NH3/STO-3G 3609/1271 = 2.8
#   (BK), N2/6-31G 34583/12399 = 2.8 (JW). Use the tabulated range, about
#   2.5-fold to 3.9-fold, not the "higher than or equal to" sentence; the
#   abstract's weaker "on average ... three times" does hold                    (Sec. III, Table II)
# the group count still scales with the term count, O(N^4) in qubit number N,
#   so the saving is a constant factor, not a change of scaling;
#   LF itself costs O(N^8) classically to run, RLF costs O(N^12)                (Sec. IV)
# no shot count, no epsilon-target, and no total measurement budget is stated
#   anywhere in the paper -- this method fixes only which terms share a
#   measurement setting, not how many times each setting is repeated

Cost, as the source states it

Verteletskyi, Yen and Izmaylov give a group count measured on instances, not proved: grouping qubit-wise commuting terms leaves "3 to 5 times fewer" groups than Pauli words on the seven systems of Table I (up to $1100$ terms, $4$ to $14$ qubits), and a $2.5$-fold to $3.9$-fold reduction on the larger systems of Table II (up to $36$ qubits, $52806$ terms), which the abstract averages as three times. The saving is a constant factor only — the number of groups stays proportional to the term count, which grows as $O(N^4)$ in the qubit number $N$. Each group costs one set of $N$ one-qubit measurements per circuit repetition, and the basis change is one-qubit rotations only, no entangling gates; the paper states no repetition count and no $\varepsilon$-dependent bound, so no total measurement cost follows from it. The grouping is minimum clique cover, "NP-hard in general"; the recommended Largest First heuristic costs $O(N^8)$ classically, and the heuristics tested differ by about $10\%$ at most on these instances.

Implementations

• Qiskit's `group_commuting(qubit_wise=True)` and the `abelian_grouping` estimator option

  Qiskit ships the grouping as an operator utility rather than as an algorithm: `PauliList` and `SparsePauliOp` each expose `group_commuting(qubit_wise=...)`, and `PauliList` adds the alias `group_qubit_wise_commuting`, whose whole body is `return self.group_commuting(qubit_wise=True)`. The docstring states the reduction in the same terms the method is recorded in — "This transforms the measurement operator grouping problem into graph coloring problem". Because it is a Pauli-algebra utility rather than a measurement routine, it has callers inside Qiskit that measure nothing: a transpiler pass uses it as a predicate, taking `commuting_subparts = operator.paulis.group_qubit_wise_commuting()` and returning `len(commuting_subparts) == 1`, and `hamiltonian_variational_ansatz` calls `hamiltonian.group_commuting()` to split a `SparsePauliOp` into circuit layers. The caller that turns the groups into measurement circuits is `BackendEstimatorV2`, whose `abelian_grouping` attribute is declared `abelian_grouping: bool = True` and documented "Whether the observables should be grouped into sets of qubit-wise commuting observables. Default: True."

  The graph Qiskit builds is the complement, not the compatibility graph: `_noncommutation_graph(qubit_wise)` returns an edge list where "An edge (i, j) is present if i and j are not commutable", so the vertices that must take different colours are exactly the pairs that cannot share a measurement setting. The per-qubit test is a small integer trick — each Pauli is mapped to `op.z + 2 * op.x`, and the pairwise product `(mat1 * mat2) * (mat1 - mat2)` is "0 (false-y) iff one of the operators is the identity and/or both operators are the same". With `qubit_wise=True` that tensor is reduced with `np.logical_or.reduce(qubit_anticommutation_mat, axis=2)` — one disagreeing qubit position is enough to place an edge, which is the negation of requiring every one-qubit factor to commute; the `qubit_wise=False` branch reduces with `logical_xor` instead, the parity rule for ordinary commuting. `_commuting_groups` then colours the complement in one call, `coloring_dict = rx.graph_greedy_color(graph)`, and buckets indices by colour. No strategy argument is passed, and rustworkx documents what that means: "When the strategy is not explicitly specified, the `Degree` strategy is used by default", and "The `Degree` (aka `largest-first`) strategy colors the nodes with higher degree first" — the Largest First ordering. Rustworkx also states the same caveat the method carries: "The coloring problem is NP-hard and this is a heuristic algorithm which may not return an optimal solution." Downstream, `BackendEstimatorV2._create_measurement_circuits` iterates `for obs in observable.group_commuting(qubit_wise=True)`, takes the group's shared basis as the elementwise OR of its symplectic masks, `Pauli((np.logical_or.reduce(obs.z), np.logical_or.reduce(obs.x)))`, and hands it to `_measurement_circuit`, which emits `sdg` then `h` on a qubit carrying $Y$ and `h` alone on a qubit carrying $X$ — one qubit at a time, with no entangling gate anywhere in the routine.

  No dataset — symbolic. None of the files named below runs on a molecule; the only worked instances are two-qubit doctests, `PauliList(["XX", "YY", "IZ", "ZZ"])` in `pauli_list.py` and `SparsePauliOp.from_list([("XX", 2), ("YY", 1), ("IZ",2j), ("ZZ",1j)])` in `sparse_pauli_op.py`.

  `qiskit/quantum_info/operators/symplectic/pauli_list.py` (lines 1137-1242: `_noncommutation_graph`, `noncommutation_graph`, `_commuting_groups`, `group_qubit_wise_commuting`, `group_commuting`) and `qiskit/quantum_info/operators/symplectic/sparse_pauli_op.py` (`group_commuting` at line 1098, which delegates at line 1123 to `self.paulis._commuting_groups(qubit_wise)`), in https://github.com/Qiskit/qiskit — Python, Apache License 2.0, with the header "(C) Copyright IBM 2017, 2022" on `pauli_list.py`. Read on branch `stable/2.1`; the whole grouping block is byte-identical on `main`. The colouring itself is not Qiskit's code: `rx.graph_greedy_color` is rustworkx, https://github.com/Qiskit/rustworkx, `src/coloring.rs`, read on `main` with no version pin, so the Largest First default is that file's documented behaviour today rather than a pinned one. The three callers named above are `qiskit/primitives/backend_estimator_v2.py` (`abelian_grouping` at line 145, the loop at line 459, `_measurement_circuit` at line 513), `qiskit/transpiler/passes/routing/commuting_2q_gate_routing/pauli_2q_evolution_commutation.py` (line 92, inside `summands_commute`) and `qiskit/circuit/library/n_local/evolved_operator_ansatz.py` (line 268).

  One worked case, in the docstrings, and nothing larger: on `["XX", "YY", "IZ", "ZZ"]`, `op.group_commuting(qubit_wise=True)` returns `[PauliList(['XX']), PauliList(['YY']), PauliList(['IZ', 'ZZ'])]` — three groups from four Pauli words — while `op.group_commuting()` on the same list returns two, `[PauliList(['XX', 'YY']), PauliList(['IZ', 'ZZ'])]`. No molecular benchmark, no group-count reduction factor, no timing and no shot count is reported in any of the files named above.

• PennyLane's `PauliGroupingStrategy` and `optimize_measurements`

  PennyLane's `pennylane/pauli/grouping/` subpackage is described by its own `__init__` as defining "functions and classes for Pauli-word partitioning functionality used in measurement optimization", and its top-level entry point names this method's source paper for the qubit-wise arm. `optimize_measurements` says the observables "are partitioned into mutually qubit-wise commuting (QWC) or mutually commuting partitions by approximately solving minimum clique cover on a graph where each observable represents a vertex. The unitaries which diagonalize the partitions are then found. See `arXiv:1907.03358 <https://arxiv.org/abs/1907.03358>`_ and `arXiv:1907.09386 <https://arxiv.org/abs/1907.09386>`_ for technical details of the QWC and fully-commuting measurement-partitioning approaches respectively." Qubit-wise is the default at every entry point: `PauliGroupingStrategy`, `group_observables`, `compute_partition_indices` and `optimize_measurements` all default to `"qwc"`.

  `group_observables` states the two steps in the method's own order: "Partitions are found by 1) mapping the list of observables to a graph where vertices represent observables and edges encode the binary relation, then 2) solving minimum clique cover for the graph using graph-colouring heuristic algorithms." As in the paper's Sec. II B.1 route, the graph that is coloured is the complement: `PauliGroupingStrategy.adj_matrix` is documented as the "Adjacency matrix for the complement of the Pauli graph determined by the ``grouping_type``", where "matrix elements of 1 denote an edge (grouping strategy is **not** satisfied)", and `complement_graph` turns its upper triangle into an `rx.PyGraph`. `_idx_partitions_dict_from_graph` colours that with `rx.graph_greedy_color(self.complement_graph, strategy=RX_STRATEGIES[self.graph_colourer])`, where `RX_STRATEGIES = {"lf": rx.ColoringStrategy.Degree, "dsatur": rx.ColoringStrategy.Saturation, "gis": rx.ColoringStrategy.IndependentSet}`. `rlf` is the exception — it is not a rustworkx strategy, so `partition_observables` branches to a vendored `recursive_largest_first` instead. Of the four orderings offered, `lf` (the default), `rlf` and `dsatur` are three of the seven the paper tests; `gis` (Independent Set) is not among them. Only one of the two heuristics vendored into `graph_colouring.py` is reachable: `recursive_largest_first` is the one `group_observables.py` imports at line 37 and the one the `rlf` branch calls at line 206, while `largest_first` occurs nowhere else in the package than its own `def` line and its own doctest — a caller who accepts the default `lf` runs rustworkx's `Degree` strategy instead. The runtimes that file states are per vertex rather than per qubit, and the one on the live path is the cubic one: `recursive_largest_first` "Often yields a lower chromatic number than Largest Degree First, but takes longer (runtime is cubic in number of vertices)", against "Runtime is quadratic in number of vertices" for the unreachable `largest_first`. The diagonalisation half is qubit-wise only: `optimize_measurements` calls `diagonalize_qwc_groupings` when `grouping.lower() == "qwc"` and otherwise raises `NotImplementedError`, and its worked example returns post-rotations that are single-qubit rotations and nothing else, `RY(-1.5707963267948966)` on two wires for one partition and `RX(1.5707963267948966)` on one wire for the other. That colouring file is not PennyLane's own code either: inside an Apache-2.0 repository, `graph_colouring.py` carries a separate MIT header reading "Copyright (c) 2020 Jakob S. Kottmann, Sumner Alperin-Lea, Alán Aspuru-Guzik", which is the exact copyright line of Tequila's `LICENSE` file, and its `recursive_largest_first` is line-for-line Tequila's `src/tequila/grouping/binary_utils.py` function of the same name with the local names respelled.

  No dataset — symbolic. The worked instances are three observables on two wires each and no molecule anywhere. Two of them run this method's relation: `optimize_measurements(obs, coeffs, 'qwc', 'rlf')` on `[qp.Y(0), qp.X(0) @ qp.X(1), qp.Z(1)]` with coefficients `[1.43, 4.21, 0.97]`, and `compute_partition_indices(observables, grouping_type="qwc", method="lf")` on `[qp.X(0) @ qp.Z(1), qp.Z(0), qp.X(1)]`, which carries no coefficients. The `group_observables` example reuses the first three observables but runs them under `'anticommuting'`, not `'qwc'`, so it is not an instance of this relation; and the two doctests in `graph_colouring.py` take a symplectic matrix and an adjacency matrix directly rather than observables.

  `pennylane/pauli/grouping/group_observables.py` (`PauliGroupingStrategy` at line 56, `compute_partition_indices` at line 389, `group_observables` at line 464), `pennylane/pauli/grouping/optimize_measurements.py` (`optimize_measurements`, the `arXiv:1907.03358` citation at line 38, the `NotImplementedError` at line 91) and `pennylane/pauli/grouping/graph_colouring.py` (`largest_first` at line 35, `recursive_largest_first` at line 83), in https://github.com/PennyLaneAI/pennylane — Python, repository licence Apache-2.0, except `graph_colouring.py` which carries its own MIT header at lines 1-21. Read on the repository's default branch `main`. The colouring backend is rustworkx.

  Docstring examples only. `optimize_measurements(obs, coeffs, 'qwc', 'rlf')` on the first three observables above returns two partitions, `[[Z(0) @ Z(1)], [Z(0), Z(1)]]` after diagonalisation, with coefficients `[[4.21], [1.43, 0.97]]` and the two single-qubit rotation lists above; `compute_partition_indices` on the second three returns the index partition `((0,), (1, 2))`. No molecule, no Hamiltonian size sweep, no group-count reduction factor and no timing is reported in the subpackage.

• The `vqe-term-grouping` clique-cover benchmark suite

  • Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families

  This is the code behind a paper written against the same problem at the same time, and it treats the method recorded here as its baseline rather than its contribution. The paper's Sec. 3 lists the concurrent work and places this method exactly: reference 40 is "Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F Izmaylov. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. arXiv preprint arXiv:1907.03358, 2019", and the sentence covering it says references 40 and 41-42 "respectively consider Qubit-Wise Commutativity and General Commutativity (defined in Section 4), treat measurement cost reduction as a minimum clique cover problem". The repository therefore ships the qubit-wise partitioner as one of two arms and benchmarks it against the general-commuting one. The repository's own README carries no text beyond its title; its GitHub description reads "Reduce the measurement costs of the VQE algorithm by simultaneously measuring mutually commuting terms." The paper does not name the repository anywhere — the link is authorship: the commit log's author names include "Pranav Gokhale", "Teague Tomesh" and "Yongshan Ding", three of the paper's eight authors, and the contributing account `guikaiwen` matches a fourth, Kaiwen Gui.

  `term_grouping.py` states the construction in its module docstring: "we treat the terms of H as nodes in a graph, G, where there are edges between nodes indicate those two terms commute with one another. Finding the circuits now becomes a clique finding problem which can be solved by the BronKerbosch algorithm." Unlike the two libraries above, the graph built here is the compatibility graph, not its complement, and the cover is taken by repeatedly removing a clique — the route Verteletskyi, Yen and Izmaylov set aside because "even if the maximum clique search is done exactly, which is an NP-hard problem, the obtained solution does not necessarily form the minimum clique cover", so it can be non-optimal even without heuristic error. Two commutativity relations are supplied as classes with the same interface: `QWCCommutativity.gen_comm_graph` draws an edge unless some position has `(c1 != c2) and (c2 != '*')`, i.e. two differing non-identity factors, and `FullCommutativity.gen_comm_graph` counts those positions and draws an edge when `(non_comm_indices % 2) == 0`. Two clique-cover heuristics are supplied likewise: `BronKerbosch`, which repeatedly runs `BronKerbosch_pivot` from the highest-degree vertex under `degree_ordering` and prunes the largest clique found, and `NetworkX_approximate_clique_cover`, which returns `approximation.clique_removal(G)[1]` and is documented as "NetworkX poly-time heuristic ... based on Boppana, R., & Halldórsson, M. M. (1992)". That NetworkX routine is the polynomial Ramsey algorithm Verteletskyi, Yen and Izmaylov describe as "implemented in the Python NetworkX library": `clique_removal` is a loop over `ramsey.ramsey_R2(graph)` with the returned clique removed each pass. `genMeasureCircuit` is the driver, taking the commutativity class and the cover method as arguments and returning the cliques; it reads the Hamiltonian from `H[1:]`, so the identity term parsed from the first data line never enters the graph. The measurement-circuit half is split in two: the block at the foot of `genMeasureCircuit` that builds one circuit per clique with `circ.h` for $X$ and `circ.sdg` then `circ.h` for $Y$ is commented out with the note that "it can only handle QWC cliques since commuting groups like [XX,YY,ZZ] require a bit more handling", and the live synthesis tool `generate_measurement_circuit.py` is the general one, a stabilizer-matrix routine whose gate primitives include `_apply_CZ`, `_apply_CNOT` and `_apply_SWAP`.

  58 files in `hamiltonians/`: $\mathrm{H_2}$ (13), $\mathrm{LiH}$ (8), $\mathrm{H_2O}$ (20) and $\mathrm{CH_4}$ (9), plus three `sampleH` files and five tapered files that `scaling.py` filters out with `if not 'taper' in h`. Bases are sto-3g (27 files) and 6-31g (21); the fermion-to-qubit encodings appearing in the file names are BK (33), JW (6), BKSF (3), BKT (3) and PC (3), and active-space variants run AS1 to AS9. Each file is a header line followed by one coefficient and one Pauli word per line. The paper states the provenance and the range: the Hamiltonians were "obtained via OpenFermion", and "We tested each of these algorithms on problem sizes ranging from 4 to 5237 terms in the molecular Hamiltonian. These Hamiltonians correspond to the H2 , LiH, H2 O, and CH4 molecules with varying numbers of active spaces."

  https://github.com/teaguetomesh/vqe-term-grouping — Python and Jupyter notebooks, MIT License, added in the repository's most recent commit (2021-08-19, "Add MIT License / open source vqe-term-grouping"). The partitioner is `term_grouping.py` (`QWCCommutativity` at line 35, `FullCommutativity` at line 58, `degeneracy_ordering` at line 88, `degree_ordering` at line 119, `BronKerbosch_pivot` at line 124, `NetworkX_approximate_clique_cover` at line 144, `BronKerbosch` at line 158, `genMeasureCircuit` at line 226); `scaling.py` is the sweep driver, selecting `-a BK|BH` and `-c QWC|FULL` and writing `Data/{algorithm}_{type}_results.txt`; `multiple_trials.py` runs 100 trials for each pairing of five encodings of one Hamiltonian — `['hamiltonians/H2_6-31g_{}_0.7_AS4.txt'.format(e) for e in ['JW','BK','BKSF','BKT','PC']]` — with the two relations `QWCCommutativity` and `FullCommutativity`; `generate_measurement_circuit.py` is the circuit synthesiser. The five Python files import `numpy`, `networkx` and `qiskit`. Read on branch `master`.

  The qubit-wise numbers the paper reports are reductions in the number of state preparations, measured on instances and given as ranges rather than per-molecule values. Figure 9, four representative molecules under Bron-Kerbosch: "The improvement from Naive to QWC is consistently about 4-5x", against "7x to 12x from H2 to CH4 (methane)" for the general-commuting arm. Figure 10, $\mathrm{H_2}$ across encodings: "performance is roughly consistent with a 3x improvement from QWC partitions and a 10x improvement from GC partitions." Across the whole sweep: "Among the QWC methods, we consistently see 3-4x reductions in number of partitions over Naive separate measurements, and our Boppana-Halldórsson QWC algorithm marginally outperforms the OpenFermion heuristic." The cost of the cover is why the paper keeps Bron-Kerbosch as a reference rather than as a usable algorithm — it "has exponential worst case runtime and should thus be considered a soft bound on the optimality of partitions produced by other graph approximation algorithms", and "some of the benchmarks were unable to be run due to prohibitive runtime costs on the order of days (e.g. Bron-Kerbosch for |H| > 1519 Pauli strings)", while the plots "corroborate the exponential worst-case scaling of Bron-Kerbosch and suggest quadratic runtime scaling for the Boppana-Halldósson algorithm". Neither of the two arms benchmarked here is the paper's own recommendation: "OpenFermion's function is clearly the fastest of the algorithms explored, but is also consistently the worst approximation to the MIN-COMMUTING-PARTITION", and the paper faults the graph algorithms of its references 39 to 42 for "impractical classical costs that may undo potential speedups from simultaneous measurement", offering instead "problem-aware techniques that operate on molecular Hamiltonian graphs in linear time". Part of the sweep survives in the repository: `Data/BoppanaHalldorsson_QWC_results.txt` and `Data/BronKerbosch_QWC_results.txt` each hold 47 rows of `nterms ncliques runtime`, the format `scaling.py` writes, and their first columns agree at all 47 positions, so the two heuristics were run on the same instances — for example `630 207 47.317436` against `630 205 14.251421`. That first column is `num_terms = len(comm_graph)`, the vertex count of the graph, which excludes the identity term dropped by `H[1:]`. These two files are the batch run only: `scaling.py` skips any Hamiltonian whose `total_terms` exceeds `--limit` (default 1000) and prints "Recommend running this Hamiltonian individually", writing single instances to `Data/{cover}_{relation}_{N}term_results.txt` instead, so both files stop at 630 while the paper's own plots run to 5237 Pauli strings. The paper also records that the optimum is unavailable here for the qubit-wise relation specifically, not only for the general one: "Appendix A demonstrates that optimally partitioning Pauli strings into QWC families is NP-Hard".

What it needs

Every step this method names is listed under Requires above. It walks its own span in one hop and calls out to the rest — that is a fact about the recorded route, not a claim that the span is simple.

Other ways to fill the same slot

Different approaches

• Direct sampling in a measurement basis

  Decompose $O$ into Pauli strings, rotate each into the computational basis with a layer of single-qubit Cliffords, sample bitstrings, and recombine the per-term averages linearly. No ancilla, no controlled operations, minimum added depth.

• Coherent amplitude-estimation readout

  Encode the expectation value into an amplitude and estimate that amplitude coherently — phase estimation on the Grover operator $Q = −A S_0 A^{-1} S_χ$, or one of the QPE-free variants — instead of averaging independent shots.

• Classical shadow readout

  Apply a random unitary from a chosen ensemble, measure in the computational basis, and keep the (unitary, outcome) pair; inverting the measurement channel turns each pair into an unbiased single-shot snapshot of $ρ$, and median-of-means over snapshots predicts many observables at once. The observables may be chosen after the data has been taken.

In the Atlas

• Measurement-grouped VQE

  Commuting Pauli terms are partitioned into compatible bases to reduce distinct measurement circuits.

Sources

• Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover↗Vladyslav Verteletskyi, Tzu-Ching Yen, Artur F. Izmaylov · 2019theory yes · simulation yes · hardware no