PaperlayerView exact revision on arXiv

Source-linked AI summary

Measurement reduction in variational quantum algorithms

Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, Peter Love

arXiv:1908.08067v3quant-ph

TL;DR

Variational quantum algorithms require many separate measurements of Hamiltonian terms, a burden that can become large at near-term hardware scales. This paper uses unitary partitioning, with additional post-ansatz operations, to reduce the number of terms requiring measurement. It reports constant-factor reduction for some Hamiltonians, linear reduction for electronic-structure Hamiltonians in generic molecular-orbital bases, and a commuting-term mapping for noncontextual Hamiltonians.

  • Problem

    Variational quantum algorithms estimate Hamiltonian terms through separate measurements, and the number of terms may become overwhelmingly large at problem sizes accessible to NISQ hardware.

    Source: §I · p. 1

  • Method

    The paper uses unitary partitioning to reduce measured terms by appending additional unitary operations after ansatz preparation.

    Source: §I · pp. 1–2

  • Results

    Unitary partitioning gives constant-factor improvement for transverse Ising and random Hamiltonians, while electronic-structure reductions scale linearly with qubit number for generic molecular-orbital bases.

    Source: §VI · p. 14

  • Takeaways & Limitations

    Any noncontextual Hamiltonian may be transformed into a Hamiltonian of fully commuting terms using the developed rotations.

    Source: §VI · p. 14

    For the plane-wave dual basis, unitary partitioning provides only constant-factor term reduction because the representation has O(N^2) nonzero electronic-Hamiltonian weights.

    Source: §VI · p. 14

Abstract

from arXiv · show

Variational quantum algorithms are promising applications of noisy intermediate-scale quantum (NISQ) computers. These algorithms consist of a number of separate prepare-and-measure experiments that estimate terms in a Hamiltonian. The number of terms can become overwhelmingly large for problems at the scale of NISQ hardware that may soon be available. We approach this problem from the perspective of contextuality, and use unitary partitioning (developed independently by Izmaylov et al. [J. Chem. Theory Comput. 16, 190 (2020)]) to define variational quantum eigensolver procedures in which additional unitary operations are appended to the ansatz preparation to reduce the number of terms. This approach may be scaled to use all coherent resources available after ansatz preparation. We also study the use of asymmetric qubitization to implement the additional coherent operations with lower circuit depth. We investigate this technique for lattice Hamiltonians, random Pauli Hamiltonians, and electronic structure Hamiltonians. Using this technique, we find a constant factor speedup for lattice and random Pauli Hamiltonians. For electronic structure Hamiltonians, we prove that linear term reduction with respect to the number of orbitals, which has been previously observed in numerical studies, is always achievable. For systems represented on 10--30 qubits, we find that there is a reduction in the number of terms by approximately an order of magnitude. Applied to the plane-wave dual basis representation of fermionic Hamiltonians, however, unitary partitioning offers only a constant factor reduction. Finally, we show that noncontextual Hamiltonians may be reduced to effective commuting Hamiltonians using unitary partitioning.

I. INTRODUCTION

In NISQ-era VQE, separately estimating Hamiltonian terms can require overwhelmingly many measurements, motivating term reduction with additional coherent operations. The paper develops contextuality-based unitary partitioning, including rotations that combine pairwise anticommuting terms into single Pauli terms.

I. INTRODUCTION

  • VQE estimates Hamiltonian terms in separate prepare-and-measure experiments, and the required number of measurements may become overwhelming for problems of about 50 qubits.The experiments are repeated until each term’s statistical error meets a desired precision threshold.Source: §I · p. 1
  • Prior Clifford-based measurement reduction uses O(n^2) gates for numerical evidence of an O(n) measurement-count reduction, but term reduction requires non-Clifford structure.Clifford operations map individual Pauli operators to individual Pauli operators and lack transformation contextuality.Source: §I · p. 2

II. TERM REDUCTION FOR PAULI HAMILTONIANS

  • The paper presents unitary partitioning and asymmetric qubitization, the latter implementing the needed transformations more efficiently at the cost of some ancilla-state preparation.Asymmetric qubitization extends the linear-combination-of-unitaries model.Source: §I · p. 2
  • Term reduction appends unitary operations after ansatz preparation, allowing their complexity to use the coherent resources available on the device.The authors state that these operations may be made as simple or complex as those resources allow.Source: §II · p. 2

A. Unitary partitioning

  • Unitary partitioning groups pairwise-anticommuting Pauli terms, rescales their coefficients, and seeks rotations that map each group to a single Pauli operator.The groups are called completely anticommuting sets.Source: A. Unitary partitioning · p. 3
  • For a set of s terms in an l-local Hamiltonian, the construction replaces s separate expectation estimates with one, using s−1 appended operators that require O(sl) additional coherent operations.Directly appending the transformations uses half the coherent resources required by the compared controlled-operation approach in.Source: A. Unitary partitioning · p. 4

B. Low-depth implementation of the rotations

A single rotation can reduce a completely anticommuting set to one Pauli term. Asymmetric qubitization implements that rotation with quadratically improved asymptotic scaling, at the cost of additional qubits and more complex gates.

B. Low-depth implementation of the rotations

  • A single rotation maps a completely anticommuting set of Pauli operators to one Pauli operator by conjugation.Choosing α = φ_n−1 gives R H_n R† = P_n.Source: B. Low-depth implementation of the… · p. 4
  • Asymmetric qubitization reduces the rotation cost's asymptotic scaling quadratically compared with the earlier methods.The rotation is equivalent to evolution under X, and its cost scales as the square root of the number of terms in X.Source: B. Low-depth implementation of the… · p. 4
  • The rotation is implemented using asymmetric LCU because its operator X has ℓ2-normalized coefficients, unlike the ℓ1-normalized coefficients treated naturally by standard LCU.Asymmetric LCU was introduced to address this normalization mismatch.Source: B. Low-depth implementation of the… · p. 4
  • Asymmetric LCU requires O(log s) additional qubits and more complex gates than the earlier rotation method.Here s is the maximum size of an anticommuting set.Source: B. Low-depth implementation of the… · p. 4

C. Commuting terms

Commuting terms can sometimes be combined when coefficient-dependent cancellations satisfy the second reduction constraint. This possibility is more sensitive to coefficient values than grouping terms that all anticommute, and the authors leave further investigation for future work.

C. Commuting terms

  • Coefficient-dependent cancellations can satisfy the reduction constraint even when commuting terms do not individually vanish.The required pairwise coefficient magnitudes must match.Source: C. Commuting terms · pp. 4–5
  • The cancellation condition is more sensitive to coefficient values than simply requiring every term in a subset to anticommute.The paired operator indices must be distinct; the text gives an example where two products cancel.Source: C. Commuting terms · p. 5
  • The authors leave further investigation of this coefficient-dependent reduction possibility to future work.The text demonstrates that the required pairings are possible with a specific Pauli-operator example.Source: C. Commuting terms · p. 5

D. Total measurement cost estimates

The measurement-cost estimates account for statistical repetitions as well as the number of unique terms. Partition size and coefficient uniformity affect the estimated reduction, while the partitioning analysis uses unique-term counts as a rough proxy.

D. Total measurement cost estimates

  • Approximately |α_j|²/ϵ² measurements are naively required for the jth term to estimate its expectation value to precision ϵ.The total measurement bound uses the fact that each self-inverse Pauli term has variance at most 1.Source: D. Total measurement cost estimates · p. 5
  • The bound Λ_c ≤ Λ is saturated only when no partitioning is performed.Additional coefficient constraints could permit more measurement reduction without extra coherent rotations, but would require a weighted graph-coloring algorithm with more classical computation.Source: D. Total measurement cost estimates · pp. 5–6
  • Roughly, the measurement count M_c after partitioning is lower bounded by M/s_max, but Λ and Λ_c are themselves upper-bound estimates.Equation (38) gives an approximate sense of the maximum reduction when statistical repetitions are included.Source: D. Total measurement cost estimates · p. 6
  • When coefficient magnitudes are uniform within each set and set sizes are roughly equal, Λ_c is approximately Λ/√s_max.The lower bound is saturated when all coefficient magnitudes are equal.Source: D. Total measurement cost estimates · p. 6

III. PRELIMINARY APPLICATIONS

For the one-dimensional transverse-field Ising model with periodic boundary conditions, pairing anticommuting terms reduces the Hamiltonian's term count by half.

A. Transverse-field Ising model in one dimension

B. TIM on arbitrary graphs

The term-reduction prospects vary across Hamiltonian classes: transverse Ising models yield a constant-factor reduction, while random Pauli Hamiltonians exhibit asymptotic coloring behavior that also limits reduction to a constant factor. For random 2-local and k-local models, the analysis relates term reduction to interaction-graph structure and operator commutation.

B. TIM on arbitrary graphs

  • For a transverse Ising model on a graph, unitary partitioning reduces |E| + |V| terms to |E|, a constant-factor improvement of q/(q + 2) on regular degree-q graphs.The limited improvement reflects little anticommutative structure in the model's operators.Source: B. TIM on arbitrary graphs · p. 6

C. Compatibility graphs of random Hamiltonians

  • As n grows, randomly sampled fixed-locality Pauli terms with polynomially many terms are increasingly likely to commute, so their compatibility graphs approach complete subgraphs.The chromatic number is expected to be proportional to n, implying at most a constant-factor term reduction.Source: C. Compatibility graphs of random… · p. 7

D. Random 2-local Pauli Hamiltonians

  • For random 2-local Hamiltonians with m = O(n^τ) terms, the expected reduction is about a factor of 2τ.The analysis characterizes improvement through the fractional change in term count.Source: D. Random 2-local Pauli Hamiltonians · p. 7

E. Random k-local Hamiltonians

  • For random k-local Hamiltonians, the derived commutation expression supports using Erdős–Rényi coloring bounds when its large-n limit matches the earlier expression.Source: E. Random k-local Hamiltonians · p. 8

IV. ELECTRONIC STRUCTURE HAMILTONIANS

Electronic-structure VQE faces a large measurement burden because many Hamiltonian terms must be estimated independently. The paper analyzes term partitioning through Majorana operators, whose support-overlap rule gives a way to identify anticommuting groups.

IV. ELECTRONIC STRUCTURE HAMILTONIANS

  • At chemical accuracy, each Hamiltonian term requires hundreds of thousands of independent measurements, repeated across optimization steps and O(N^4) molecular terms.Jordan–Wigner transformation can require up to 16 Pauli strings for each molecular term.Source: §IV · p. 8
  • The authors frame partitioning as reducing separate expectation-value estimates to the number of fully anticommuting sets, with an O(N^4)-to-O(N^3) reduction always achievable for electronic-structure Hamiltonians.They also report constant-factor reduction for plane-wave dual-basis Hamiltonians.Source: §IV · pp. 8–9

A. Majorana operators

  • Majorana operators provide an encoding-agnostic representation useful for partitioning because they are Hermitian, unitary, and obey a single anticommutation relation.Source: A. Majorana operators · p. 9
  • For the even-parity products relevant to the electronic Hamiltonian, two Majorana operators anticommute exactly when their supports overlap on an odd number of indices.Source: A. Majorana operators · p. 9

B. Linear reduction in terms

The section constructs a partition of electronic-structure terms into completely anticommuting sets, establishing an O(N^3) upper bound and thus a guaranteed linear reduction relative to the O(N^4) term count. The construction is not claimed to be optimal.

B. Linear reduction in terms

C. Pauli-level colouring and numerics

Pauli-level colouring produces far fewer fully anticommuting sets than the full Pauli-term count, with Jordan–Wigner and Bravyi–Kitaev mappings performing similarly. Numerical results show roughly linear scaling, while greedy colouring improves on the numerical Majorana scheme at greater classical cost.

C. Pauli-level colouring and numerics

  • The colouring metric is the number of fully anticommuting sets; approximate colourings suffice because improving their quality has diminishing returns.The sets correspond to a colouring of the compatibility graph, whose nodes are terms and whose edges connect commuting terms.Source: C. Pauli-level colouring and numerics · p. 10
  • The greedy strategy finds at least an order of magnitude fewer fully anticommuting sets than Pauli terms, with Jordan–Wigner and Bravyi–Kitaev mappings performing almost equivalently.Figure 1 compares the number of sets with the number of terms in the full Pauli Hamiltonian.Source: Figure 1 · p. 11, C. Pauli-level colouring and numerics · p. 11
  • The number of sets grows roughly linearly with Hamiltonian terms, and the term-to-set ratio rises roughly linearly with spin orbitals, though with high variance.Numerical Majorana and greedy colouring results outperform the analytic upper bound, which is loose because molecular Hamiltonians are sparse.Source: C. Pauli-level colouring and numerics · p. 11, Figure 2 · p. 12
  • Greedy colouring yields roughly a factor of 10 improvement over numerical Majorana partitioning, while Majorana achieves the same term-reduction scaling with substantially lower classical overhead.The classical resources needed for greedy colouring may inhibit its use for systems with more spin orbitals.Source: C. Pauli-level colouring and numerics · p. 11
  • The maximum post-ansatz gate count is a hardware-dependent compile-time parameter, allowing term recombination to use available coherent resources.The reported circuit-length choices are illustrative; the limit should be set empirically for the hardware.Source: C. Pauli-level colouring and numerics · pp. 11–12

D. The plane-wave dual basis

For the plane-wave dual basis, unitary partitioning reduces the number of terms only by a constant factor, while noncontextual Hamiltonians can be mapped to effective commuting Hamiltonians. The conclusions compare electronic-structure strategies and discuss the coherent resources required to implement the reduction.

D. The plane-wave dual basis

  • The plane-wave dual basis has O(N^2) Hamiltonian terms and an identified set of N^2 commuting operators, precluding asymptotic term reduction.Unitary partitioning instead reduces the term count by a factor approaching 2.Source: D. The plane-wave dual basis · p. 13

V. NONCONTEXTUAL HAMILTONIANS

  • The noncontextual-Hamiltonian construction partitions terms into disjoint sets drawn from the commutation cliques, then maps each fully anticommuting set to one operator.The procedure first identifies the cliques and universally commuting terms.Source: §V · pp. 13–14
  • Any noncontextual Hamiltonian can be mapped to commuting terms using appended Pauli rotations, but the resulting Hamiltonian is not unitarily equivalent to the original.The rotations vary across the constructed anticommuting sets.Source: §V · p. 14

VI. CONCLUSIONS

  • Linear term reduction is achievable for generic molecular orbital basis sets, whereas the plane-wave dual basis gives only constant-factor reduction.The paper proves the linear-scaling result and confirms its practicality numerically.Source: §VI · p. 14
  • Majorana-based partitioning offers favorable scaling, while greedy coloring gives an order-of-magnitude reduction even below 30 qubits at greater classical computational cost.The choice depends on available post-ansatz coherent resources and the difficulty of classical partitioning.Source: §VI · p. 14
  • Modest additional coherent resources can be tuned to hardware, and some required rotations match those used in popular ansätze.With appropriate compilation, their rotation angles may be incorporated into ansatz parameters.Source: §VI · p. 14

Appendix A: Calculational details

Appendix A derives algebraic results used in the main text, including a rotation that maps an operator in an anticommuting set to a single Pauli operator and a Majorana-operator form of the electronic-structure Hamiltonian.

Appendix A: Calculational details

  • The appendix derives algebraic results used in the main text, including calculations for the ALCU method and the Majorana representation of electronic-structure Hamiltonians.The Majorana derivation uses coefficient symmetries and Majorana anticommutation relations to simplify the terms.Source: Appendix A · p. 16, §2 · p. 17

1. Computation of X for the ALCU method

  • Choosing the rotation angle to match φ_n−1 maps H_n to P_n, demonstrating how a self-inverse operator supported on pairwise anticommuting terms can be mapped to one Pauli operator.The derivation computes the rotation's adjoint action and its generator's commutation relations.Source: §1 · p. 17

2. Electronic structure Hamiltonian using Majorana operators

  • In the Majorana expansion, certain quadratic terms vanish by anticommutation, and the derivation collects the surviving contributions into the full electronic-structure Hamiltonian.The resulting Hamiltonian is expressed in terms of Majorana operators.Source: §2 · pp. 18, 20

Appendix B: Proof details for Theorem 1

The appendix proves the anticommuting partition used for the electronic-structure term-reduction result by reducing the quartic-term problem to a partition of quadratic Majorana operators. Its construction yields the required O(N^3) result.

Appendix B: Proof details for Theorem 1

  • Figure 4 illustrates disjoint anticommuting sets of even-index quadratic operators, including a red bin that combines two sets.For common index 2q, each set has size q; the red bin is the exception.Source: Figure 4 · p. 20, Appendix B · p. 20
  • The quartic-term partition reduces to partitioning quadratic Majorana operators with only even indices, then taking products with odd-index quadratic operators.The proof uses the condition of three matching indices in each term's support.Source: Appendix B · p. 20
  • O(N^3) anticommuting sets suffice for the partition, yielding the stated scaling result.The construction partitions even-index quadratic operators and takes products with odd-index quadratic operators.Source: Appendix B · p. 20

Appendix C: Electronic structure systems

The appendix identifies the systems used in the electronic-structure numerical analysis and gives the stated sources for geometries and molecular-orbital integrals.

Appendix C: Electronic structure systems

  • The numerical analysis uses systems whose geometries came from NIST CCBDB and whose Hartree–Fock molecular-orbital integrals came from Psi4 and OpenFermion.Source: Table I · p. 21

Related papers

Loading 1908.08067v3…