PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, Frederic T. Chong

arXiv:1907.13623v1quant-ph

TL;DR

VQE’s O(N^4) Pauli-string measurements make state preparation costly for near-term quantum chemistry. This paper partitions commuting strings, synthesizes simultaneous-measurement circuits, and analyzes covariance, achieving 8-30x reductions in state preparations while validating the approach experimentally.

  • Problem

    VQE requires separate state preparations for O(N^4) Pauli-string terms, creating a costly measurement bottleneck for near-term applications.

  • Method

    The paper approximates MIN-COMMUTING-PARTITION, synthesizes simultaneous-measurement circuits, and adaptively estimates covariance to guard against harmful covariance terms.

  • Results

    The techniques achieve up to 30x fewer state preparations, with an alternate molecular-Hamiltonian strategy achieving 8x reduction with almost no additional pre-computation.

  • Takeaways & Limitations

    Simultaneous measurement can substantially reduce VQE state-preparation cost while retaining explicit attention to classical compilation and quantum circuit overheads.

  • Takeaways & Limitations

    The exact cost of VQE remains uncertain because ansatz exploration depends on the classical optimizer, ansatz type, and variational landscape.

Abstract

from arXiv · show

Variational quantum eigensolver (VQE) is a promising algorithm suitable for near-term quantum machines. VQE aims to approximate the lowest eigenvalue of an exponentially sized matrix in polynomial time. It minimizes quantum resource requirements both by co-processing with a classical processor and by structuring computation into many subproblems. Each quantum subproblem involves a separate state preparation terminated by the measurement of one Pauli string. However, the number of such Pauli strings scales as $N^4$ for typical problems of interest--a daunting growth rate that poses a serious limitation for emerging applications such as quantum computational chemistry. We introduce a systematic technique for minimizing requisite state preparations by exploiting the simultaneous measurability of partitions of commuting Pauli strings. Our work encompasses algorithms for efficiently approximating a MIN-COMMUTING-PARTITION, as well as a synthesis tool for compiling simultaneous measurement circuits. For representative problems, we achieve 8-30x reductions in state preparations, with minimal overhead in measurement circuit cost. We demonstrate experimental validation of our techniques by estimating the ground state energy of deuteron on an IBM Q 20-qubit machine. We also investigate the underlying statistics of simultaneous measurement and devise an adaptive strategy for mitigating harmful covariance terms.

1. Introduction

VQE targets exponentially sized eigenvalue problems on near-term hardware by shifting work to classical processing, but separate measurements create O(N^4) state-preparation costs. This paper reduces that cost by partitioning commuting Pauli strings, synthesizing simultaneous-measurement circuits, and analyzing covariance effects.

  • VQE approximates the lowest eigenvalue of an exponentially sized matrix using classical co-processing and low-resource quantum circuits.The paper focuses on molecular ground-state estimation while noting broader applications.
  • O(N^4) measured terms make repeated state preparations a practical limitation for VQE.Each iteration measures one term in the standard formulation.
  • Commuting observables can be measured in one state preparation, motivating systematic minimization of commuting-family partitions.
  • The paper develops approximation algorithms for MIN-COMMUTING-PARTITION and a circuit-synthesis tool for simultaneous measurement.
  • The study analyzes simultaneous-measurement statistics and proposes guarding against harmful covariance terms, alongside benchmark and experimental validation.

2. Background

The background explains how Pauli observables are measured through rotations into the computational basis, then frames VQE’s molecular-energy estimation problem and its resource costs. It also introduces Hamiltonian structure, standard VQE operation, and the UCCSD ansatz.

  • 2.1. Quantum Measurement: Z-basis measurement projects a qubit onto |0⟩ or |1⟩, while X and Y measurements first rotate their axes onto Z.
  • 2.1. Quantum Measurement: For multiple-qubit Pauli strings, a unitary with the observable’s eigenvectors as columns rotates the target eigenbasis onto the computational basis.
  • 2.2. Simultaneous Measurement and Commutativity: Pairwise commuting Hermitian observables share a common eigenbasis, enabling multiple Pauli strings to be measured with one circuit and state preparation.
  • 2.4. Variational Quantum Eigensolver (VQE): The molecular Hamiltonian becomes O(N^4) Pauli-string terms after fermionic-to-qubit encoding, and VQE estimates its energy by summing their expectations.
  • 2.4. Variational Quantum Eigensolver (VQE): Naive VQE prepares the ansatz and measures each Pauli term separately inside optimizer iterations.
  • 2.5. Unitary Coupled Cluster Single Double Ansatz: UCCSD has O(N^4) total gate count, parallelizable to O(N^3) circuit depth, and its demonstrated circuits already exceed present-machine capabilities.

3. Prior Work

Prior work reduced VQE measurement costs through ad hoc or graph-based partitioning, but this paper emphasizes practical classical compilation and quantum-circuit overheads. It adds general-commutativity methods, efficient synthesis, and validation across benchmarks and experiments.

  • Earlier work and experiments pursued simultaneous Pauli-string measurement through graph coloring, QWC partitioning, or related Hamiltonian transformations.
  • The paper differentiates itself by addressing both classical compilation costs and quantum overheads from simultaneous measurement.
  • Problem-aware molecular-Hamiltonian techniques operate in linear time, while prior graph algorithms could impose impractical classical costs.
  • The paper’s benchmark and experimental sections evaluate whether simultaneous-measurement costs are worthwhile, while its techniques compose with other VQE improvements.
  • General Commutation achieves significant cost reductions over Naive and QWC partitions even for previously studied small molecules.
  • Existing software implementations support QWC but omit General Commutativity and can require at least N^8 runtime.

4. Analysis of Commutativity

The paper formalizes commutativity for Pauli strings and uses it to define the partitioning problem underlying simultaneous measurement. Qubit-wise commutativity is easy to measure but narrower than general commutativity, whose optimization problem is NP-Hard.

  • Pauli strings are tensor products of single-qubit Pauli matrices, whose commutation relations determine multi-qubit commutativity.
  • Qubit-Wise Commutativity: Qubit-Wise Commutativity requires corresponding Pauli matrices to commute at every qubit index.
  • Qubit-Wise Commutativity: QWC partitioning is NP-Hard, so larger Hamiltonians require efficient approximation algorithms rather than ad hoc inspection.
  • Qubit-Wise Commutativity: QWC families have tensor-product eigenbases, making simultaneous measurement especially straightforward.
  • General Commutativity: General Commutativity allows Pauli strings that fail to commute at an even number of indices, such as XX, YY, and ZZ.

5. MIN-CLIQUE-COVER on Hamiltonian

MIN-COMMUTING-PARTITION is NP-hard, so the paper approximates it through minimum clique covers of Hamiltonian commutation graphs. General commutation yields denser graphs and smaller covers than QWC, while a structure-aware approximation keeps classical preprocessing practical.

  • Problem formulation: MIN-COMMUTING-PARTITION seeks the minimum number of commuting families covering Hamiltonian Pauli strings and is NP-hard even under QWC.The problem is mapped to graph partitioning rather than solved exactly.
  • Graph formulation: Cliques represent simultaneously measurable Pauli-string families, so the target becomes a MIN-CLIQUE-COVER of the commutation graph.Every pair of strings in a clique commutes, allowing one measurement partition.
  • Graph formulation: 14 →5 →2 measurement partitions are obtained for LiH by moving from Naive separate measurements to QWC and then GC.The QWC and GC covers use progressively broader commutation relationships.
  • QWC versus GC: GC produces denser commutation graphs than QWC, creating more opportunities for larger cliques and smaller clique covers.The QWC graph is asymptotically sparse, whereas GC has asymptotic density 1/2.
  • QWC versus GC: QWC has cheaper simultaneous-measurement circuits, but GC remains favorable because VQE circuit cost is dominated by ansatz preparation.The paper therefore treats the additional measurement-circuit cost of GC as comparatively small.
  • Approximation algorithms: O(N^4) classical runtime is achieved by exploiting molecular-Hamiltonian structure, avoiding potentially impractical O(N^8) or O(N^12) preprocessing from generic graph heuristics.Bron–Kerbosch has worst-case exponential runtime, while the Boppana–Halldórsson approach is estimated to scale roughly quadratically in graph size.

6. Linear-Time Partitioning

The section develops encoding-aware approximations to MIN-COMMUTING-PARTITION, exploiting molecular Hamiltonian structure to reduce measurement partitions. Jordan-Wigner and Parity achieve 8x reductions for dominant double-excitation terms, while Bravyi-Kitaev remains an open case.

  • Context-aware partitioning: The strategy attacks MIN-COMMUTING-PARTITION during fermion-to-qubit encoding, unlike molecular-property-agnostic clique-cover approximations.It is designed to reduce classical partitioning overhead by using context from molecular Hamiltonians.
  • Jordan-Wigner: 8x fewer partitions result when Jordan-Wigner strings from double-excitation terms use 2 GC partitions instead of 16 Naive partitions.When Hamiltonian symmetries leave only eight terms, the same 8x reduction remains achievable.
  • Parity: Parity also yields a MIN-CLIQUE-COVER of size 2 for the 16 relevant strings, giving an 8x partition reduction with a more expensive circuit over 8 indices.The encoding produces Pauli strings involving neighboring indices such as p, p−1, q, q−1, r, r−1, s, and s−1.
  • Bravyi-Kitaev: Bravyi-Kitaev complicates the commutation structure of double-excitation operators, leaving an immediately obvious clique-cover strategy as an open question.Its partial-sum index structure differs from the simpler patterns found for Jordan-Wigner and Parity.

7. Circuits for Simultaneous Measurement

The section presents circuits for simultaneously measuring commuting Pauli strings, with stabilizer-based synthesis handling general-commuting partitions. Although worst-case GC circuits use O(N^2) gates, the studied partitions retain near-linear, constant-depth measurement overhead.

  • Measurement circuits: Naive and QWC measurements use single-qubit basis rotations, while GC measurements require a nontrivial circuit-synthesis procedure.The synthesis tool was implemented as a Python library and validated across molecular Hamiltonians.
  • General-commuting measurement: A GC partition is measured by transforming its shared eigenbasis into computational-basis measurements before standard Z-basis readout.The procedure avoids explicitly constructing exponentially sized eigenvector matrices by using stabilizer formalism.
  • Bell-basis example: Bell-basis measurement illustrates GC measurement: a CNOT followed by H transforms XX and ZZ into computational-basis measurements, while YY follows from −(XX)(ZZ).The Bell states are entangled, so interactions between qubits are required.
  • Synthesis procedure: Stabilizer synthesis operates on a 2N × N matrix, with Gaussian elimination costing O(N^3) classically.This tractable representation avoids the exponential cost of manipulating simultaneous eigenvectors.
  • Circuit complexity: The synthesized circuit requires O(N^2) gates in the worst case, compared with O(N) for Naive or QWC measurement.The UCCSD ansatz has O(N^4) gates and O(N^3) parallelized depth, making measurement overhead asymptotically insignificant in that setting.
  • Circuit complexity: For the paper’s 8x partition approximations, only 4 or 8 indices are GC-but-not-QWC, so measurement remains O(N) with O(1) parallelizable depth.The remaining N−4 or N−8 indices use QWC measurement.

8. Benchmark Results

Benchmarks compare partition counts and runtimes across molecules, encodings, active spaces, and approximation algorithms. GC partitioning consistently reduces partitions more than QWC, while algorithm choice trades approximation quality against runtime.

  • Molecular benchmarks: Bron-Kerbosch reduces partitions by about 4–5x with QWC and 7x–12x with GC across representative molecules relative to Naive measurement.The GC reduction increases from H2 to CH4, suggesting greater state-preparation savings for larger molecules.
  • Encoding and active-space studies: Across H2 encodings, QWC improves by roughly 3x and GC by roughly 10x, while Bravyi-Kitaev Super-Fast reaches a 20x GC reduction.These results compare partition counts against the Naive baseline.
  • Encoding and active-space studies: As active spaces increase, GC partitioning advantages range from 3x to 12x.The trend is relevant because prior work reported that relatively many active spaces may be needed for chemical accuracy.
  • Algorithm comparisons: Boppana-Halldórsson and OpenFermion QWC methods consistently reduce partitions by 3–4x over Naive, with Boppana-Halldórsson marginally outperforming the OpenFermion heuristic.The broader benchmark spans Hamiltonians containing up to 5237 Pauli strings.
  • Algorithm comparisons: OpenFermion has the fastest runtime but the worst approximation, whereas Bron-Kerbosch shows exponential worst-case scaling and Boppana-Halldórsson suggests quadratic runtime scaling.Some Bron-Kerbosch benchmarks could not run because runtimes reached days for Hamiltonians larger than 1519 Pauli strings.

9. Experimental Results

The experiments benchmark commuting-family partitioning and validate it on deuteron energy estimation using IBM Q20. Partitioning reduces state preparations substantially, but accuracy depends on the shot budget and circuit-noise regime.

  • Partitioning benchmarks: 4-20x reductions in state preparations and measurements were achieved relative to Naive measurement across the benchmarked algorithm-benchmark pairs.Naive measurement uses one partition per Pauli string, so its partition count equals the Hamiltonian size.
  • Deuteron validation: The deuteron Hamiltonian has four measured Pauli strings and is partitioned into two commuting families under General Commutativity.The families are {ZI,IZ} and {XX,YY}; the first is Qubit-Wise Commutative, while the second uses a Bell-basis circuit.
  • Deuteron validation: 11% lower average error was obtained with GC simultaneous measurement than Naive measurement under a total shot budget of 100.GC averaged 835 KeV error versus 940 KeV for Naive measurement, with GC better for 13 of 24 parameter values.
  • Deuteron validation: 7% lower average error was obtained with Naive measurement than GC simultaneous measurement under a total shot budget of 4000.Naive outperformed GC for 17 of 24 parameter values; systematic noise was expected to dominate in this higher-shot regime.
  • Interpretation: The authors characterize the experiments as proof-of-concept and argue that simultaneous measurement can achieve equal accuracy with fewer shots when the shot budget is limited.They also note that the small Hamiltonian provides only a 2x partitioning gain, compared with up to 30x gains reported for larger benchmarks.

10. Statistics of Simultaneous Measurement: Guarding Against Covariances

Simultaneous measurement can be harmed by covariance terms even when commuting strings are grouped optimally by count. The paper therefore combines a Haar-average justification for minimizing partitions with an adaptive strategy that estimates covariance and splits harmful groups.

  • Covariance effects: For the |01⟩ state, all listed covariances are zero except Cov(−XX,−YY)=1.The corresponding variances are zero for IZ, ZI, and ZZ, and one for −XX and −YY.
  • Covariance effects: Positive covariance between −XX and −YY makes the three-partition arrangement better than the two-partition arrangement for the specified Hamiltonian and state.This example shows that minimizing the number of commuting families does not always minimize the required state preparations.
  • Haar-average analysis: Under a uniform Haar distribution over states, the expected covariance of two distinct commuting Pauli strings is zero.This supports minimizing the total number of partitions when there is no prior information about the ansatz state.
  • Adaptive mitigation: The proposed adaptive strategy builds sample covariance matrices from repeated measurements and splits partitions when covariance terms harm measurement statistics.The same measurements used to estimate expectation values provide samples for estimating covariance.
  • Adaptive mitigation: A partition split is favorable when its covariance-based variance comparison indicates fewer state preparations are needed to reach the target accuracy.The variance of each partition is represented by the sum of entries in its covariance matrix.
  • Scope and limitations: Formalizing a reliable sample-covariance decision rule remains open because the distribution of sample variance and covariance terms requires further work.Candidate criteria include burn-in observations and a hypothesis test comparing the full and split partitionings.

11. Conclusion

The paper presents simultaneous measurement as a way to reduce VQE state-preparation cost while addressing classical compilation, circuit synthesis, and covariance effects. It reports reductions up to 30x, an 8x low-overhead alternative, and proof-of-concept validation on IBM 20Q.

  • Contributions and results: Up to 30x reductions in requisite state preparations are reported from simultaneous measurement techniques.The reductions arise because one preparation can cover several Pauli strings.
  • Contributions and results: An alternate molecular-Hamiltonian-aware strategy achieves an 8x reduction with almost no additional pre-computation.The paper also develops circuit synthesis and studies the statistics of simultaneous measurement.
  • Validation and future work: Proof-of-concept experimental validation was performed on the IBM 20Q quantum computer.The paper identifies further benchmarking, theoretical investigation, software packaging, and molecular-Hamiltonian-aware partitioning as ongoing work.

A. MIN-COMMUTING-PARTITION is NP-Hard

The paper proves that MIN-COMMUTING-PARTITION is NP-hard, including under the restricted Qubit-Wise Commutativity condition.

  • Complexity result: MIN-COMMUTING-PARTITION is NP-hard by reduction from MIN-CLIQUE-COVER.The construction maps commuting operator subsets to graph cliques.
  • Complexity result: The NP-hardness reduction uses only Qubit-Wise Commutativity relationships.Thus, restricting the problem to QWC does not remove the computational hardness established by the reduction.
Loading 1907.13623v1…