Source-linked AI summary
Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
Vladyslav Verteletskyi, Tzu-Ching Yen, Artur F. Izmaylov
TL;DR
VQE measurement is inefficient because current hardware measures only single-qubit parts of a Hamiltonian whose term count grows as O(N^4). The paper represents qubit-wise commuting terms as a graph, reformulates optimal grouping as minimum clique cover, and evaluates polynomial heuristics, finding an average three-fold reduction in measurement groups.
Problem
Current projective single-qubit measurements require measuring Hamiltonian parts separately, while the number of qubit-Hamiltonian terms grows as O(N^4).
Method
The paper represents Pauli words as graph vertices connected by qubit-wise commutativity and approximates minimum clique cover using graph-coloring and maximum-clique heuristics.
Results
Grouping qubit-wise commuting terms reduced the number of measurement groups by three times on average across the considered molecular Hamiltonians.
Takeaways & Limitations
The fastest generally recommended heuristics were LF and RLF, but further measurement-preprocessing improvements are needed for large systems because groups remain proportional to O(N^4) Pauli words.
Abstract
from arXiv · showhide
Solving the electronic structure problem using the Variational Quantum Eigensolver (VQE) technique involves measurement of the Hamiltonian expectation value. Current hardware can perform only projective single-qubit measurements, and thus, the Hamiltonian expectation value is obtained by measuring parts of the Hamiltonian rather than the full Hamiltonian. This restriction makes the measurement process inefficient because the number of terms in the Hamiltonian grows as $O(N^4)$ with the size of the system, $N$. To optimize VQE measurement one can try to group as many Hamiltonian terms as possible for their simultaneous measurement. Single-qubit measurements allow one to group only the terms that commute within corresponding single-qubit subspaces or qubit-wise commuting. We found that 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. The MCC problem is NP-hard but there exist several polynomial heuristic algorithms to solve it approximately. Several of these heuristics were tested in this work for a set of molecular electronic Hamiltonians. 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.
I. INTRODUCTION
VQE combines quantum expectation-value measurements with classical energy minimization, but current single-qubit projective measurements cannot measure the full qubit Hamiltonian at once. Because most Hamiltonian terms lack a shared tensor-product basis and their number scales as O(N^4), the paper formulates measurement grouping as a graph-optimization problem.
- VQE uses a quantum computer to obtain Hamiltonian expectation values for trial wavefunctions while classical optimization minimizes the electronic energy.
- The qubit Hamiltonian is built from Pauli words whose coefficients are numerical and whose count scales as N^4 with the number of qubits.The N^4 scaling arises from the two-electron integral component of the electronic Hamiltonian.
- Current hardware cannot measure the whole qubit Hamiltonian simultaneously and instead supports projective measurements of single-qubit operators.Terms can be measured together when they share the same tensor-product eigenbasis.
- Most Hamiltonian terms do not share one tensor-product basis, and the grouping into simultaneously measurable sets is not unique.
- The paper addresses this grouping problem by representing qubit-wise commuting terms as a graph and assessing graph-based approaches on molecular Hamiltonians up to 36 qubits and 53 thousand terms.
A. Simultaneously measurable fragments
Terms sharing a tensor-product basis can be measured together when they are qubit-wise commuting. Representing these relations as graph edges turns simultaneous measurement grouping into finding a minimum clique cover, although the non-transitive relation permits multiple covers.
- Qubit-wise commutativity requires corresponding one-qubit operators to commute on every qubit, which is stricter than ordinary commutativity.For example, x1x2 and y1y2 commute normally but are not qubit-wise commuting.
- Each group of mutually qubit-wise commuting Pauli words can be measured in one set of N single-qubit measurements.The required Pauli operator for each qubit is determined by the group’s tensor-product basis.
- Because qubit-wise commutativity is not transitive, it does not define a unique partition into non-overlapping equivalence classes.
- In the graph representation, mutually qubit-wise commuting terms form fully connected subgraphs called cliques.
- The optimal grouping is the minimum clique cover, while alternative covers can contain more cliques and therefore be non-optimal.The paper illustrates minimum and non-minimum covers for a model Hamiltonian.
- The minimum clique cover problem is NP-hard, motivating approximate polynomial approaches.
B. Solving the minimum clique cover problem
The paper considers two routes to approximate minimum clique covers: graph coloring and repeated maximum-clique search with removal. Although both involve NP-hard problems, they motivate practical heuristics.
- Two approaches are evaluated: mapping minimum clique cover to graph coloring and repeatedly finding and removing maximum cliques.Both approaches generate intuitive heuristic algorithms despite their NP-hard components.
1. Graph coloring
Minimum clique cover can be solved through coloring the complementary graph, where colors correspond to cliques in the original graph. Sequential coloring is polynomial but order-dependent, motivating several vertex-ordering and merging heuristics.
- Graph coloring: The chromatic number of the complementary graph equals the minimum number of cliques covering the original graph.Vertices assigned the same color in the complement are disconnected there and therefore form a clique in the original graph.
- Graph coloring: Sequential vertex coloring assigns each vertex the lowest available color, creating a new color when all existing colors appear among its neighbors.
- Graph coloring: Because sequential coloring is polynomial but not necessarily minimal, its result depends on the ordering of vertices.
- Graph coloring: The tested coloring orderings include Greedy Coloring, Largest First, Smallest Last, DSATUR, and Recursive Largest First.
- Graph coloring: The Dutton and Brigham technique merges disconnected vertex pairs with many common neighbors until a clique is produced, assigning merged vertices that clique’s color.
- Graph coloring: COSINE extends pair-merging by selecting a subsequent disconnected vertex with the largest number of common neighbors with the current merged vertex.
- Graph coloring: Greedy Coloring and Largest First scale as O(e + n), while Recursive Largest First is generally cubic and becomes quadratic when k·e ∼ n^2.For the studied graphs, k·e ∼ n^3.
2. Maximum clique search and removal
Maximum-clique search followed by removal provides an approximate clique cover, but even exact maximum-clique selection can yield more cliques than the minimum cover. Two heuristic implementations are described for this approach.
- Maximum-clique search and repeated removal produces an approximate solution to the minimum clique cover problem.
- An exact maximum-clique search can still produce a larger, non-minimal clique cover.Figure 3 contrasts the resulting larger cover with the minimum clique cover.
- The approach includes an improved Bron–Kerbosch search, implemented as FindClique and called BKT.
- A polynomial Ramsey algorithm provides a second heuristic for maximum-clique search and removal.
III. NUMERICAL STUDIES AND DISCUSSION
The heuristics were evaluated on small molecular Hamiltonians and compared by clique counts, computational cost, and clique-size statistics. LF generally provided the best balance, while larger systems retained at least a three-fold reduction in groups.
- The study evaluates grouping heuristics on small-molecule Hamiltonians generated with STO-3G and 6-31G bases.The reported systems include Hamiltonians with up to 1100 terms.
- 3 to 5 times fewer QWC groups than Pauli words were obtained in Table I.Randomized ordering tests found no smaller clique-cover numbers than the reported minimal values.
- Approximately 10% was the largest average difference between methods in total clique counts.
- LF was superior overall in clique count and execution time, motivating its use for larger Hamiltonians.
- Almost two orders of magnitude longer runtimes for 14-qubit H2O made DB, COSINE, and Ramsey unsuitable for larger Hamiltonians.RLF was the other method identified as potentially competitive without excessive computational cost.
- At least a three-fold reduction in clique number persisted for larger Hamiltonians regardless of fermion–qubit mapping.JW produced maximum clique sizes almost three times those of BK, with standard-deviation ratios of approximately one and a half.
IV. CONCLUSIONS
The paper represents qubit-wise commuting Pauli words as graph edges and reduces simultaneous-measurement grouping to minimum clique cover. Heuristic benchmarks achieve substantial grouping reductions, but further preprocessing improvements are needed for large systems.
- Each Pauli word becomes a graph vertex, while edges connect qubit-wise commuting terms that can be measured simultaneously.
- Optimal grouping corresponds to finding the fewest fully connected subgraphs, the minimum clique cover problem.The problem is NP-hard, so the paper benchmarks polynomial heuristics for approximate solutions.
- Three times fewer qubit-wise commuting groups than Hamiltonian terms were achieved by the benchmarked heuristics.
- Differences in group counts stayed within 10%, making the faster LF and RLF heuristics generally recommended.
- LF and RLF scale as O(N^8) and O(N^12), respectively, while the number of Pauli words scales as O(N^4).The conclusion states that further measurement-preprocessing improvements are needed for large systems.
- The current approach uses only one-qubit unitary rotations, whereas later proposals use multi-qubit transformations that can reduce measurable-group scaling at the cost of additional multi-qubit gates.
SUPPLEMENTARY MATERIAL: HAMILTONIAN DETAILS
The supplementary material specifies molecular geometries, basis sets, fermion-to-qubit mappings, and qubit-reduction procedures used to construct the evaluated Hamiltonians.
- H2 was generated with the BK transformation from RHF molecular-orbital integrals at R(H-H)=1.5 Å.
- LiH used a parity transformation and produced a 6-qubit Hamiltonian containing 118 Pauli words at R(Li-H)=3.2 Å.
- LiH stationary qubits reduced the problem to a 4-qubit effective Hamiltonian with 100 Pauli terms in the ground-state sector.
- H2O included 6-, 14-, and 26-qubit Hamiltonians, with reduced and unreduced constructions across the 6-31G and STO-3G bases.The geometries were R(O-H)=0.75 Å and ∠HOH=107.6°.
- Complete-active-space H2O Hamiltonians contained 185 Pauli terms before stationary-qubit reduction and 165 terms afterward.
- N2 produced 36- and 20-qubit Hamiltonians using BK and JW transformations with 6-31G and STO-3G bases.
- BeH2 produced 26- and 14-qubit Hamiltonians using BK and JW transformations with 6-31G and STO-3G bases.
- NH3 produced 30- and 16-qubit Hamiltonians using BK and JW transformations with 6-31G and STO-3G bases.