Source-linked AI summary
$O(N^3)$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians
Pranav Gokhale, Frederic T. Chong
TL;DR
Molecular energy estimation in VQE naively requires measuring O(N^4) terms, while Jordan-Wigner-encoded molecular Hamiltonians allow simultaneous measurement to reduce the cost to O(N^3). The paper studies MIN-COMMUTING-PARTITION at the fermionic-Hamiltonian level, uses commutativity of encoded terms with disjoint indices, and constructs partitions through a round-robin scheduling approach. Jordan-Wigner-encoded molecular Hamiltonians can be partitioned into O(N^3) commuting families of O(N) Pauli strings, reducing VQE measurement cost from O(N^4) to O(N^3).
Problem
Molecular energy estimation in VQE naively requires measuring O(N^4) terms, while Jordan-Wigner-encoded molecular Hamiltonians allow simultaneous measurement to reduce the cost to O(N^3).
Source: §I · p. 1Method
The paper studies MIN-COMMUTING-PARTITION at the fermionic-Hamiltonian level, uses commutativity of encoded terms with disjoint indices, and constructs partitions through a round-robin scheduling approach.
Source: §III · p. 2, §IV · p. 3Results
Jordan-Wigner-encoded molecular Hamiltonians can be partitioned into O(N^3) commuting families of O(N) Pauli strings, reducing VQE measurement cost from O(N^4) to O(N^3).
Source: §I · p. 1, §VI · p. 4Takeaways & Limitations
The construction depends only on N and can be precomputed; the partitioning may also help reduce Trotterization cost by ordering commuting Pauli strings consecutively.
Source: §I · p. 1, §VI · p. 5
Abstract
from arXiv · showhide
Variational Quantum Eigensolver (VQE) is a promising algorithm for near-term quantum machines. It can be used to estimate the ground state energy of a molecule by performing separate measurements of $O(N^4)$ terms. Several recent papers observed that this scaling may be reducible to $O(N^3)$ by partitioning the terms into linear-sized commuting families that can be measured simultaneously. We confirm these empirical observations by studying the MIN-COMMUTING-PARTITION problem at the level of the fermionic Hamiltonian and its encoding into qubits. Moreover, we provide a fast, pre-computable procedure for creating linearly-sized commuting partitions by solving a round-robin scheduling problem via flow networks.
I. BACKGROUND
VQE estimates molecular ground-state energies using modest quantum resources, but measuring the Hamiltonian’s terms separately creates a practical scaling challenge. This work establishes O(N^3) measurement cost for Jordan-Wigner-encoded molecular Hamiltonians and gives an efficient, reusable construction for the commuting partitions.
I. BACKGROUND
- VQE is a near-term quantum algorithm for molecular ground-state estimation, a classically hard problem and canonical VQE application.Its modest per-subproblem quantum requirements come with a potentially large number of subproblems.Source: §I · p. 1
- O(N^4) terms must be measured separately in the basic approach, making molecular energy estimation costly for molecules requiring hundreds of qubits.Each term maps to a constant number of Pauli strings, and measuring each string is a separate subproblem.Source: §I · p. 1
- Earlier work conjectured that simultaneous measurement could reduce molecular-Hamiltonian measurement scaling from O(N^4) to O(N^3), based on extrapolations across molecules.Commuting Pauli strings can be measured simultaneously.Source: §I · p. 1
- Jordan-Wigner-encoded molecular Hamiltonians admit O(N^3) measurement cost by partitioning their terms into pairwise-commuting families of O(N) terms.Terms within each family can be measured simultaneously.Source: §I · p. 1
- The partition construction takes O(N^5 log N) time and depends only on N, so it can be precomputed for each N.The passage contrasts this with prior simultaneous-measurement proposals whose runtimes reached O(N^12).Source: §I · p. 1
II. PRIOR WORK
Prior studies reported empirical signs of reduced measurement scaling, while other Pauli-string sets show that simultaneous measurement does not always help. A separate recent proof established O(N^3) cost for molecular Hamiltonians without relying on a particular fermion-to-qubit encoding.
II. PRIOR WORK
- Prior studies reported or conjectured increasing benefits from simultaneous measurement, including linear scaling claims across molecular Hamiltonians and encodings.[4] extrapolates linear scaling; [5] conjectures it for “almost all” Pauli-string sets; [6] [7] fit scaling for molecular Hamiltonians under Jordan-Wigner and Bravyi-Kitaev.Source: §II · pp. 1–2
- For some contrived Pauli-string sets, simultaneous measurement yields exponential gain or a square-root reduction, but it offers no advantage for another set whose pairs all anticommute.The examples in [4] include 2^N strings sharing a measurement basis and 4^N strings measurable with a 2^N reduction using Mutually Unbiased Bases.Source: §II · p. 2
- Recent work [10] also proves O(N^3) measurement cost for molecular Hamiltonians, using Majorana operators to make the proof agnostic to the fermion-to-qubit encoding.Source: §II · p. 2
III. COMMUTATIVITY OF INDEX-DISJOINT TERMS
The section proves that Jordan–Wigner encodings of fermionic terms with disjoint indices commute. It uses the parity of anticommuting Pauli positions to establish the result for the asymptotically dominant terms.
III. COMMUTATIVITY OF INDEX-DISJOINT TERMS
- The argument focuses on the O(N^4) terms with four distinct indices, which dominate asymptotically; the other terms number O(N^3).Source: §III · p. 2
- Jordan–Wigner encodings of two a†a†aa terms commute whenever their index sets are disjoint.This is the section’s core observation for constructing commuting families.Source: §III · pp. 2–3
- Only the eight endpoint indices can anticommute: an X or Y aligned with a Z contributes one, and an even count means the strings commute.The encoding of a†a†aa yields 16 Pauli strings with X or Y at the four endpoints and intervening Z strings.Source: §III · p. 2
- The proof checks 70 interleaved orderings (35 accounting for symmetry); sliding one endpoint preserves the parity of anticommuting indices.The parity is always even for disjoint-index terms, so their encodings commute.Source: §III · pp. 2–3
IV. EXISTENCE OF LINEARLY-SIZED PARTITIONS
For N divisible by 4, the terms can be partitioned into O(N^3) families of disjoint-index terms, whose Jordan–Wigner encodings can be measured simultaneously. The construction is related to scheduling 4-player games in rounds, and the N = 8 example illustrates the partition.
IV. EXISTENCE OF LINEARLY-SIZED PARTITIONS
- For N divisible by 4, the 16 Pauli strings associated with each term can be partitioned into 16 measurement families, or into just 2 using the within-term partition described in [4, Section 6].The disjoint indices let strings from each of the N^4 subsets be measured simultaneously.Source: §IV · p. 3
- The partition problem corresponds to scheduling N players’ 4-player games into rounds, with games in a round sharing no players.Equivalently, it asks whether the 4-uniform complete hypergraph on N vertices admits a 1-factorization.Source: §IV · p. 3
- For N divisible by 4, the terms can be partitioned into O(N^3) families, with disjoint indices within each family.By Baranyai’s Theorem, this partitions the O(N^4) terms.Source: §IV · p. 3
- For N = 8, Table I gives 35 rows, each pairing two fermionic terms with disjoint indices for simultaneous measurement of their Jordan–Wigner encodings.The partition is guaranteed to exist for N divisible by 4.Source: §IV · p. 3
V. CONSTRUCTION OF LINEARLY-SIZED PARTITIONS
The paper turns Baranyai’s existence result into an efficient construction using maximum-flow networks and flow rounding. The resulting partition depends only on N, can be precomputed, and takes O(N^5 log N) time to construct.
V. CONSTRUCTION OF LINEARLY-SIZED PARTITIONS
- The construction uses maximum flows in network graphs, building on later work that made an efficient construction from Baranyai’s proof possible.Prior literature had described the original proof as non-constructive or exponential-time.Source: §V · p. 3
- The example has 35 subsets, with the two terms in each subset having disjoint indices; such a partition is guaranteed to exist for all N divisible by 4 [12].Source: §V · p. 4
- The construction takes O(N^5 log N) time, using flow rounding to reduce each maximum-flow computation to O(N^4 log N) rather than O(N^7) per iteration.The networks have O(N^3) vertices and O(N^4) directed edges, and the outer loop runs N times.Source: §V · p. 4
- The procedure constructs a schedule of disjoint subsets by updating subset nodes from an integral flow in a two-layer network.The described network has O(N^3) partition and subset nodes, with O(N^4) edges.Source: §V · p. 4
- The construction depends only on N, not on Hamiltonian coefficients, so its partition can be precomputed for all N-qubit molecular Hamiltonians.For example, the N = 8 partition applies to all 8-qubit Hamiltonians.Source: §V · p. 4
VI. DISCUSSION
The discussion concludes that Jordan–Wigner molecular Hamiltonians admit O(N^3) commuting families, reducing VQE measurement cost from O(N^4), with O(N)-gate measurement circuits. It also identifies coefficient-based optimizations and a possible application to Hamiltonian-dynamics simulation.
VI. DISCUSSION
- Jordan–Wigner molecular Hamiltonians can be partitioned into O(N^3) commuting families of O(N) Pauli strings, reducing VQE measurement cost from O(N^4) to O(N^3).The simultaneous-measurement circuits require O(N) gates because the shared eigenbasis factors over 4-qubit chunks.Source: §VI · p. 4
- The technique depends only on N and is pre-computable, while coefficient symmetries may further reduce the Pauli strings per fermionic term from 16 to 8.The expected symmetry is h_pqrs = h_srpq.Source: §VI · p. 4
- The authors suggest that grouping commuting Pauli strings consecutively could reduce Trotterization cost by diminishing the need for fine time slicing of noncommuting terms.This reordering would have essentially no quantum cost because simultaneous-measurement circuits are not needed.Source: §VI · p. 5