PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient quantum measurement of Pauli operators in the presence of finite sampling error

Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, Stephen Brierley

arXiv:1908.06942v3quant-ph

TL;DR

Quantum computers’ fixed-basis measurements make estimating observables indirect, and measuring Pauli terms separately can be costly. The paper evaluates groupings under optimal measurement allocation, introduces Sorted Insertion and two rotation-circuit constructions, and reports improved grouping metrics and bounded circuit costs in molecular VQE examples.

  • Problem

    Fixed computational-basis measurements make observable estimation indirect, while measuring each Pauli term separately can be costly and grouping performance depends on the arrangement.

    Source: §1 · p. 1

  • Method

    The paper defines state-dependent and state-agnostic grouping metrics under optimal measurement allocation, proposes coefficient-aware Sorted Insertion, and constructs CZ and CNOT rotation circuits.

    Source: §1 · p. 2, §5 · p. 9

  • Results

    On molecular Hamiltonians, Sorted Insertion nearly always gives the best ˆR despite usually not minimizing collections, and typical CZ gate counts are about 3.5 times below the worst-case bound.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The smallest number of collections is not generally the best criterion for measurement efficiency, and splitting one collection under optimal allocation does not reduce the measurements needed for a target accuracy.

    Source: §1 · p. 2, §5 · p. 9

    Sorted Insertion is a heuristic that may not maximize ˆR; maximizing ˆR is NP-hard in general.

    Source: §2 · p. 5

Abstract

from arXiv · show

Estimating the expectation value of an operator corresponding to an observable is a fundamental task in quantum computation. It is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the operator into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version collects mutually commuting Pauli operators together before measuring all operators within a collection simultaneously. The effectiveness of doing this depends on two factors. Firstly, we must understand the improvement offered by a given arrangement of Paulis in collections. In our work, we propose two natural metrics for quantifying this, operating under the assumption that measurements are distributed optimally among collections so as to minimise the overall finite sampling error. Motivated by the mathematical form of these metrics, we introduce SORTED INSERTION, a collecting strategy that exploits the weighting of each Pauli operator in the overall sum. Secondly, to measure all Pauli operators within a collection simultaneously, a circuit is required to rotate them to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any collection of $k$ independent commuting $n$-qubit Pauli operators using at most $kn-k(k+1)/2$ and $O(kn/\log k)$ two-qubit gates respectively. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the operators in question are molecular Hamiltonians. As measured by our metrics, SORTED INSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of collections.

1 Introduction

Because quantum computers measure in a fixed computational basis, estimating observables often requires decomposing them into Pauli operators and grouping commuting terms. The paper defines metrics for comparing such groupings, proposes Sorted Insertion, and develops rotation circuits for simultaneous measurement.

1 Introduction

  • For second-quantized chemical Hamiltonians, separate Pauli measurements can scale as n^4, motivating simultaneous measurement of commuting collections.Any commuting collection can be simultaneously diagonalized by a single unitary.Source: §1 · p. 1
  • Prior VQE work proposed grouping commuting terms but did not show how to construct the collections or their rotation unitary.The paper also notes that some recent methods collect noncommuting Paulis, but says direct comparison was difficult.Source: §1 · pp. 1–2
  • The paper frames its collecting and rotation-circuit methods as addressing two related measurement-reduction problems.Measurement-allocation strategies that vary the number of shots across VQE iterations can complement and combine with its approach.Source: §1 · pp. 2–3
  • R and ˆR compare uncollected with collected measurement requirements under optimal allocation; R depends on the state, while ˆR approximates its uniform-spherical average.R is suited to cases where the quantum state is known; ˆR is suited to cases where it is not.Source: §1 · p. 2
  • Splitting one commuting collection into two never reduces the measurements needed for a target accuracy under optimal allocation.This differs from earlier results based on uniform allocation across collections.Source: §1 · p. 2
  • Sorted Insertion uses Pauli coefficients to seek high ˆR, rather than minimizing the number of collections.The two objectives are not equivalent.Source: §1 · p. 2
  • The CZ- and CNOT-constructions rotate arbitrary commuting Pauli collections for simultaneous measurement, including collections with k < n independent operators.The CNOT gate count is a worst-case upper bound; numerical results find typical CZ counts about 3.5 times below the worst-case bound.Source: §1 · p. 2
  • For molecular Hamiltonians from two-qubit H2 to 38-qubit H2Se, Sorted Insertion yields a 10 to 60 fold improvement in measurements required, with each measurement comprising all qubits.The study evaluates performance using ˆR; arrangements with the fewest collections do not typically perform best by that metric.Source: §1 · pp. 2–3

2 Collecting strategies

The section develops performance metrics for Pauli collections under optimally distributed measurements, then uses those metrics to motivate a coefficient-aware collection strategy. It also shows that splitting a commuting collection cannot improve the metrics, while minimizing the number of collections need not maximize performance.

2 Collecting strategies

  • Optimally distributing measurements across collections makes R a metric of arrangement quality: larger R indicates greater measurement savings from grouping Paulis.R is evaluated for a given operator and quantum state.Source: §2 · p. 3
  • Splitting one commuting collection into two never reduces the required measurements under optimal allocation, for either R or ˆR.This contrasts with earlier results using sub-optimal allocation; the theorem does not establish that the fewest collections are best.Source: §2 · pp. 3–4
  • ˆR can favor more collections: the two-qubit example scores 1.47 with two collections and 1.71 with three.The example illustrates why minimizing collection count is not equivalent to maximizing ˆR.Source: §2 · p. 4
  • Sorted Insertion orders Paulis by decreasing absolute coefficient, then adds each to the first existing collection with which it commutes or starts a new collection.The strategy is designed to prioritize large coefficients when seeking to maximize ˆR.Source: §2 · pp. 4–5
  • Sorted Insertion has worst-case complexity O(nt2) and is at least as efficient as the compared greedy colouring algorithms.It is a heuristic that may not find collections maximizing ˆR; the section states that this maximization problem is NP-hard in general.Source: §2 · p. 5
  • The method does not split a Pauli coefficient across collections, a choice that may be sub-optimal; maximizing ˆR with coefficient splitting is left for future work.The section gives an example in which ˆR is maximized at α = 1.Source: §2 · pp. 3, 5

3 Rotation constructions

The rotation constructions transform independent generators of a commuting Pauli collection into a form that enables simultaneous computational-basis measurement. The CZ and CNOT constructions provide different worst-case two-qubit gate bounds, while prioritizing two-qubit gates because of their cost.

3 Rotation constructions

  • The circuit transforms a set of independent commuting Pauli generators, then computational-basis measurements and classical post-processing recover measurements of the full collection.The construction aims to reduce two-qubit gates because they are more costly than one-qubit gates and classical post-processing.Source: §3 · pp. 5–6

3.1 CZ-construction

  • The CZ-construction uses at most kn - k(k + 1)/2 two-qubit gates to rotate a collection of k independent Pauli operators on n qubits.Its reduction passes through a graph-state representation; local complementation can further reduce the CZ count.Source: §3.1 · pp. 6–7

3.2 CNOT-construction

  • The CNOT-construction starts from S4 of the CZ-construction and reduces to Send with three blocks of CNOT gates, using at most O(kn/log k) gates.The construction builds on the CZ method and prior CNOT synthesis work.Source: §3.2 · p. 7

4 Application to VQE

For molecular Hamiltonians, Sorted Insertion is compared with greedy coloring methods using R-hat, while the study also evaluates measurement reduction and rotation-circuit gate counts. Sorted Insertion performs best or jointly best on R-hat in all but two cases, and actual gate counts are typically below their worst-case bound.

Measurement-reduction metrics

  • Average collection size increases with qubit number, but collection size alone does not quantify measurement reduction; R measures that reduction for a given Hamiltonian and state.The molecular systems studied range from two to 38 qubits.Source: §4 · p. 8
  • For the nine smallest molecules, R-hat closely approximates mean R across 100 depth-1 hardware-efficient-ansatz parameter sets, though the relationship may differ for another ansatz.R-hat depends only on Hamiltonian coefficients and can be calculated analytically, unlike state-dependent R.Source: §4 · p. 8

Rotation-circuit gate counts

  • The largest actual two-qubit gate count is typically lower than the worst-case bound by a factor of about 3.5 for the molecules studied.Figure 3(c) plots the ratio of the worst-case maximum to the actual count against qubit number.Source: §4 · p. 8, Figure 3 · p. 8

Comparison of collecting methods

  • Sorted Insertion is best or joint best on R-hat in all but two cases, while Independent Set is best only once despite finding the fewest collections in all but one case.Table 3 compares four greedy coloring methods with Sorted Insertion by collection count and R-hat.Source: §4 · p. 9, Table 3 · p. 9

5 Conclusion

The paper addresses both grouping commuting Paulis for measurement and constructing circuits for simultaneous measurement. Its VQE molecular-energy evaluation found Sorted Insertion nearly always gives the best ˆR, while the CZ construction typically uses fewer gates than its worst-case bound.

5 Conclusion

  • The paper introduces R and ˆR, proposes Sorted Insertion, and presents CZ and CNOT rotation-circuit constructions for the two measurement problems.Source: §5 · p. 9
  • The CZ and CNOT constructions use at most kn−k(k+1)/2 and O(kn/log k) two-qubit gates, respectively.Source: §5 · p. 9
  • Sorted Insertion nearly always gives the best ˆR for molecular-energy estimation, although it does not normally produce the fewest collections.The comparison is with other collecting methods.Source: §5 · p. 9
  • The CZ construction's largest two-qubit-gate count is typically about 3.5 times below its theoretical worst-case bound.Source: §5 · p. 9

A Example to demonstrate that combining two collections into one never reduces R

In the example, splitting the {−XX, −Y Y, ZZ} collection into {−XX} and {−Y Y, ZZ} is not preferable under the optimal measurement strategy. The calculation sets certain covariances to zero for convenience.

A Example to demonstrate that combining two collections into one never reduces R

B Derivation of ˆR formula

The derivation defines ˆR by replacing variances and covariances in R with their expectations over a uniform spherical distribution. It uses the single-Pauli variance and covariance results to obtain the formula.

B Derivation of ˆR formula

C Binary representation

The appendix represents Paulis as binary vectors and uses a corresponding matrix to characterize commutation and independence. It also describes how common gates act on that matrix.

C Binary representation

  • The binary representation maps Paulis that differ only in phase to the same binary vector.The representation is attributed to Calderbank, Rains, Shor, and Sloane [53].Source: C Binary representation · p. 14
  • An n-qubit Pauli is represented by a 2n-dimensional binary vector, and a set of m Paulis by a 2n × m matrix whose columns represent them.Source: C Binary representation · p. 15
  • The matrix representation characterizes mutual commutation, and a set is independent when its matrix has rank m.Source: C Binary representation · p. 15
  • The matrix S is divided into upper S(Z) and lower S(X) halves; CZ, CNOT, Hadamard, and phase gates are represented by transformations on S.The transformation rules use addition modulo 2; one listed rule is S_ip ← S_ip + S_i+n,p.Source: C Binary representation · p. 15

D CZ-construction example

The CZ-construction walk-through extends and transforms a set of six commuting four-qubit Paulis, then uses the resulting rotation circuit to recover their measurements from computational-basis outcomes.

D CZ-construction example

  • Gaussian elimination identifies P1, P2, and P4 as the three independent Paulis from which the remaining operators can be constructed.The pivot columns are 1, 2, and 4.Source: D CZ-construction example · p. 15
  • Hadamard gates on qubits 3 and 4 raise the lower half of Sstart to rank 3 before further elimination.The text describes the lower half of S1 as having rank 3 after this step.Source: D CZ-construction example · p. 16
  • The construction extends S2 with Pext = Z1I2I3X4 to obtain a rank-n = 4 matrix.The extension is chosen to make Pext independent of the other Paulis.Source: D CZ-construction example · p. 16
  • The transformed operators S4 have graph-state form, with each of the four listed Paulis containing one X and the stated Z terms.The listed operators are ˜P1 = X1 I2 I3 Z4, ˜P2 = I1 X2 Z3 I4, ˜P3 = I1 Z2 X3 I4, and ˜P4 = Z1 I2 I3 X4.Source: D CZ-construction example · p. 17
  • The six original operators have phases (+1, +1, +1, −1, −1, −1), and their measurements are recovered as products of specified qubit outcomes, with negative signs for P4–P6.The listed measurement rules include a negative outcome for P4 and P5, and a negative product for P6.Source: D CZ-construction example · p. 17

E Proof of O(kn/ log k)

The proof establishes an O(kn/ log k) bound on row operations for the stated block-matrix reduction, using blockwise elimination and a final reduction of an invertible matrix.

E Proof of O(kn/ log k)

  • O(kn/ log k) row operations suffice to reduce the stated block-form matrix M to identity In.The claim assumes A is a k × (n−k) matrix.Source: E Proof of O(kn/ log k) · p. 17
  • The proof partitions A into consecutive column blocks and eliminates duplicate and then remaining rows within each block.For the first block, the text bounds these operations by k and m2^m−1, respectively.Source: E Proof of O(kn/ log k) · pp. 17–18
  • After processing all blocks, the remaining k × k matrix B is invertible and can be row-reduced to Ik using O(k^2/ log k) operations.The proof attributes this reduction bound to Ref..Source: E Proof of O(kn/ log k) · p. 18

F NP-hardness of maximising ˆR

The appendix reduces the difficulty of maximizing ˆR to Min-Clique-Cover, establishing that even approximation of the maximum is NP-hard.

F NP-hardness of maximising ˆR

  • The reduction represents graph vertices as Pauli operators, with commuting collections corresponding exactly to cliques.The construction follows Ref. [20, Appendix A].Source: F NP-hardness of maximising ˆR · p. 18
  • For the constructed operator, maximizing ˆR entails computing a √n-approximation to Min-Clique-Cover.The argument uses the relationship between the number of collections and the denominator of ˆR.Source: F NP-hardness of maximising ˆR · p. 18
  • A 1/n^(1/2−ϵ) approximation to the maximum ˆR is NP-hard for any ϵ > 0.This follows from the stated hardness of n^(1−ϵ)-approximating Min-Clique-Cover.Source: F NP-hardness of maximising ˆR · p. 18

G Full numerical results

The appendix table reports numerical results for Sorted Insertion on molecular Hamiltonians, including collection statistics, measurement ratios, and rotation-circuit gate counts.

G Full numerical results

  • Table 4 reports results for molecular Hamiltonians at approximately equilibrium geometries using the STO-3G basis and symmetry-conserving Bravyi–Kitaev transformation.Hamiltonians were obtained using OpenFermion and Psi4.Source: Table 4 · p. 19
  • For Sorted Insertion, the table lists the number of collections N and average terms mi and ranks ki per collection, alongside molecule qubit and Pauli counts.The Pauli count excludes the identity term.Source: Table 4 · p. 19
  • For the nine smallest molecules, the table reports mean, minimum, and maximum R across 100 depth-1 hardware-efficient ansatz trial states, plus ˆR where calculated.The caption says ˆR is close to the mean R where both are available.Source: Table 4 · p. 19
  • The table includes theoretical and actual maximum two-qubit gate counts per molecule, their ratio, and mean gate counts across collections.The theoretical maximum is the largest kn − 1/2 k(k + 1) value among collections.Source: Table 4 · p. 19

Related papers

Loading 1908.06942v3…