††thanks: These authors contributed equally to this work.††thanks: These
authors contributed equally to this work.††thanks: These authors contributed
equally to this work.

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

Ophelia Crawford  Barnaby van Straaten  Riverlane, Cambridge, UK  Daochen Wang
Riverlane, Cambridge, UK  Joint Center for Quantum Information and Computer
Science, University of Maryland, College Park, USA  Thomas Parks  Riverlane,
Cambridge, UK  Earl Campbell  Riverlane, Cambridge, UK  Department of Physics
and Astronomy, University of Sheffield, Sheffield, UK  Stephen Brierley
Riverlane, Cambridge, UK

###### Abstract

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 with 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$ 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.

##  I Introduction

Estimating the expectation value of an operator corresponding to an observable
on a quantum state is a fundamental task in quantum mechanical experiments.
Expectation estimation of a Hamiltonian features prominently as the quantum
sub-routine of the Variational Quantum Eigensolver (VQE) algorithm Peruzzo
_et al._ (2014), which has emerged as a leading candidate for exhibiting
quantum advantage in the Noisy Intermediate Scale Quantum era Preskill (2018).
VQE is a hybrid quantum-classical algorithm designed to find the ground state
Peruzzo  _et al._ (2014); McClean  _et al._ (2016); O’Malley  _et al._ (2016);
Kandala  _et al._ (2017a); McArdle  _et al._ (2018); Ryabinkin  _et al._
(2019); Romero  _et al._ (2018); Wang  _et al._ (2019), or energy spectra
McClean  _et al._ (2017); Santagati  _et al._ (2018); Colless  _et al._
(2018); Heya  _et al._ (2019); Jones  _et al._ (2019); Higgott  _et al._
(2019), of a physical or chemical system. Often there is no natural way to
obtain the expectation of an operator directly and some indirect protocol is
required. In particular, this is true of current quantum computers, which can
only obtain measurements in the computational basis defined, by convention, as
eigenstates of the Pauli-$Z$ operator on each qubit.

One naive method of proceeding, therefore, is to decompose the operator into a
weighted sum of Pauli operators (or Paulis) and then measure each separately.
The paper that introduced VQE Peruzzo  _et al._ (2014) proposed measuring the
Hamiltonian in this way. However, this can be inefficient. For example, a
second-quantised chemical Hamiltonian on $n$ qubits decomposes into a very
large number of Paulis that scales as $n^{4}$. An improved method, therefore,
is to arrange the Paulis in commuting collections. All Paulis in a collection
can be measured at the same time, as any set of commuting Paulis can be
simultaneously diagonalised by a single unitary. There are typically many
arrangements of Paulis in mutually commuting collections, and the reduction in
the number of measurements required will depend on the structure of the
particular arrangement.

In the context of VQE, McClean  _et al._ McClean  _et al._ (2016) proposed
this improved protocol. The authors argued using a toy example that, due to
covariances between Paulis, the arrangement with the fewest collections may
not result in the greatest saving in number of measurements. However, Ref.
McClean  _et al._ (2016) neither proposed strategies to obtain the commuting
collections, nor presented a construction of the unitary rotation, $U$, that
enables simultaneous measurement.

Recently, a series of papers Verteletskyi  _et al._ (2019); Jena  _et al._
(2019); Yen  _et al._ (2019); Huggins  _et al._ (2019); Gokhale  _et al._
(2019); Zhao  _et al._ (2019); Gokhale and Chong (2019) 111We mention that
both the collecting and rotation circuit synthesis problems have been
addressed on an ad-hoc basis by experimentalists since Kandala  _et al._
Kandala  _et al._ (2017b). We refer readers to Table 2 of Ref. Gokhale  _et
al._ (2019) for a good summary. We also mention that recent Ref. Izmaylov  _et
al._ (2019) and the less recent Ref. Izmaylov  _et al._ (2019) allow for
collecting of non-commuting Paulis. We found it interesting that such
approaches are feasible, but found it hard to compare them to our work on a
like-for-like basis. have appeared that together make good progress on both
the collecting strategy and rotation circuit construction problems. Our paper
is in this same arena and addresses both problems.

First, we define two natural metrics, $R$ and $\hat{R}$, that quantify the
performance of any given arrangement. $R$ and $\hat{R}$ measure the ratio of
the number of measurements required in the uncollected case to the collected
case to attain a fixed level of accuracy. The key feature in these two metrics
is that they assume measurements are distributed optimally between the
collections to minimise the finite sampling error, following Refs. Wecker  _et
al._ (2015); Rubin  _et al._ (2018); Romero  _et al._ (2018). The difference
between them is that $R$ is state-dependent but $\hat{R}$ is designed to
approximate $\mathbb{E}[R]$ over the uniform spherical measure. Therefore, $R$
is more suitable for use given some knowledge of the underlying quantum state,
while $\hat{R}$ is more suitable otherwise.

With $R$ and $\hat{R}$ defined, we prove a first result that breaking a single
commuting collection into two is never advantageous, as the number of
measurements required to obtain an expectation estimate to a given level of
accuracy is never reduced. This first result already contradicts the
conclusion of the aforementioned toy example used by McClean  _et al._ McClean
_et al._ (2016), and analysed in full in Ref. (Gokhale  _et al._ , 2019, Sec.
10.1), that breaking a collection can be advantageous. The reason for the
discrepancy is that we distribute measurements optimally among the collections
so as to minimise the overall error due to finite sampling for a given number
of measurements. In contrast, in the previous works, measurements are
distributed uniformly between the collections.

We further propose an intrinsically new collecting strategy, which we call
SORTED INSERTION, that is designed to maximise $R$ and $\hat{R}$. Unlike all
strategies used previously that seek the minimum number of collections
Verteletskyi  _et al._ (2019); Jena  _et al._ (2019); Gokhale  _et al._
(2019); Zhao  _et al._ (2019), SORTED INSERTION seeks to maximise $\hat{R}$ by
explicitly exploiting the coefficients of Paulis in its assignment of
collections. It is important to stress that maximising $\hat{R}$ is not the
same as minimising the number of collections, as we show by a toy example.
Perhaps counter-intuitively, this does not contradict the above conclusion,
which showed only that it is never better to break a single collection into
two.

When considering the rotation circuit construction problem, we contribute two
new methods for constructing Clifford rotation circuits that enable
simultaneous measurement of a collection containing arbitrary commuting
Paulis. Like Ref. Gokhale  _et al._ (2019), we approach the problem via the
stabiliser formalism but further consider the case where the number of
independent operators, $k$, in a collection can be less than the number of
qubits, $n$. We show that the number of two-qubit gates in $U$ can be reduced
in a way that scales with $k$. This is important because it is atypical for
actual collections to have exactly $k=n$ independent Paulis and reducing the
number of two-qubit gates is important, especially in the near-term Blais  _et
al._ (2007); Laing  _et al._ (2010); Barends  _et al._ (2014); Ballance  _et
al._ (2016); Allen  _et al._ (2017); Linke  _et al._ (2017); Wendin (2017);
Reagor  _et al._ (2018); Schäfer  _et al._ (2018); Webb  _et al._ (2018);
Levine  _et al._ (2018); He  _et al._ (2019a); Huang  _et al._ (2019); Blumel
_et al._ (2019); He  _et al._ (2019b). As far as we are aware, ours is the
first paper to consider the $k<n$ case explicitly. Furthermore, we allow
classical post-processing, which can save quantum resources.

More specifically, we introduce constructions “CZ” and “CNOT”. The CZ-
construction builds on work by Van den Nest, Dehaene, and De Moor Van den Nest
_et al._ (2004) in the graph-state literature to yield $U$ with a number of
two-qubit gates at most

$u_{\text{cz}}(k,n)=kn-k(k+1)/2.$ (1)

The CNOT-construction builds on our CZ-construction, and work by Aaronson and
Gottesman Aaronson and Gottesman (2004) and Patel, Markov, and Hayes Patel
_et al._ (2008) to yield $U$ with a number of two-qubit gates at most

$u_{\text{cnot}}(k,n)=O(kn/\log k).$ (2)

We stress that $u_{\text{cnot}}$ and $u_{\text{cz}}$ are worst-case upper
bounds. In practice, numerical simulations are needed to determine whether the
CZ\- or CNOT-construction is actually more efficient. We note that, in the
case of $k=n$, our constructions have two-qubit gate-counts scaling no worse
than the previous best of $O(n^{2})$ Gokhale  _et al._ (2019). Other works,
such as Ref. (Jena  _et al._ , 2019, Appendix A), prove only that a Clifford
rotation exists, or demonstrate a scaling that is worse than $O(n^{2})$ (Yen
_et al._ , 2019, Appendix B), or present a method that only works for some
hand-picked arrangements of the second-quantised fermionic Hamiltonian Huggins
_et al._ (2019); Gokhale and Chong (2019).

We end our paper with a series of numerical results on molecular Hamiltonians
that serve to illustrate and validate our theoretical work. In doing so, we
first quantify the performance of SORTED INSERTION using the metric $\hat{R}$
for molecules ranging in size from hydrogen H2, which requires two qubits, to
hydrogen selenide H2Se, which requires 38, finding that it leads to a 10 to 60
fold improvement in the number of measurements required. Note that we are
defining a single measurement to consist of a measurement of all qubits, and
so the number of measurements equals the number of ansatz state preparations.

We further present results of using SORTED INSERTION alongside our CZ-
construction on molecules requiring up to 38 qubits to calculate the actual
number of two-qubit gates required for real molecular systems. Our numerical
results show that the typical number of two-qubit gates is fewer than the
worst-case $u_{\text{cz}}(k,n)$ by a factor of 3.5.

Lastly, we present data showing SORTED INSERTION outperforming the four
conventional greedy colouring algorithms we tested, as measured by the metric
$\hat{R}$. Our data strongly challenges the assumption that minimising the
number of collections is best, as arrangements with the smallest number of
collections do not typically perform the best with respect to $\hat{R}$.

##  II collecting strategies

In this section, we develop a method for collecting Pauli operators designed
to minimise the number of measurements required to obtain an estimate of the
expectation value of an operator to a given level of accuracy.

We have an operator, $O$, of the form

$O=\sum_{i=1}^{N}O_{i}=\sum_{i=1}^{N}\sum_{j=1}^{m_{i}}a_{ij}P_{ij}$ (3)

where $N$ is the number of collections of mutually commuting operators,
$m_{i}$ is the number of operators in collection $i$, $P_{ij}$ is the $j$th
Pauli operator in the $i$th collection and $a_{ij}\in\mathbb{R}$ is its
coefficient.

Given $\epsilon$, let $M_{u}$ and $M_{g}$ be the minimum number of
measurements required to attain an accuracy $\epsilon$ in the uncollected and
collected (as per Eq. 3) cases respectively. Finding $M_{u}$ is a special case
of finding $M_{g}$. To find $M_{g}$, we can solve the constrained optimisation
problem that asks how a given number of measurements should be distributed in
order to maximise accuracy. The solution to such a problem gives the optimal
measurement strategy for a given operator and state. Following Ref. Wecker
_et al._ (2015); Rubin  _et al._ (2018); Romero  _et al._ (2018), we can use
Lagrange multipliers to find

$M_{g}=\left(\frac{1}{\epsilon}\sum_{i=1}^{N}\sqrt{\mathrm{Var}[O_{i}]}\right)^{2},$
(4)

where

$\displaystyle\mathrm{Var}[O_{i}]$ $\displaystyle=\text{Cov}[O_{i},O_{i}]$ (5)
$\displaystyle=\expectationvalue{O_{i}^{2}}-\expectationvalue{O_{i}}^{2}.$ (6)

Since $M_{u}$ is just $M_{g}$ evaluated with every operator in its own
collection, we have

$M_{u}=\left(\frac{1}{\epsilon}\sum_{i=1}^{N}\sum_{j=1}^{m_{i}}|a_{ij}|\sqrt{\mathrm{Var}[P_{ij}]}\right)^{2},$
(7)

where

$\mathrm{Var}[P_{ij}]=1-\expectationvalue{P_{ij}}^{2}.$ (8)

The ratio $R$, defined as

$R\coloneqq\frac{M_{u}}{M_{g}}=\left(\frac{\sum_{i=1}^{N}\sum_{j=1}^{m_{i}}|a_{ij}|\sqrt{\mathrm{Var}[P_{ij}]}}{\sum_{i=1}^{N}\sqrt{\mathrm{Var}[O_{i}]}}\right)^{2},$
(9)

therefore acts as a natural metric for the performance of a particular
arrangement of Paulis under the assumption that measurements are distributed
optimally. The larger the value of $R$, the greater the saving that assembling
operators into collections provides. We now prove as Claim 1 that combining
two collections into one is never worse with respect to $R$.

######  Claim 1.

Consider two collections $\mathcal{A}$ and $\mathcal{B}$ of mutually commuting
Paulis, where each Pauli is in at most one collection. Suppose that it is
possible to combine $\mathcal{A}$ and $\mathcal{B}$ into a single commuting
collection $\mathcal{C}\coloneqq\mathcal{A}\cup\mathcal{B}$. Let
$R(\\{\mathcal{A},\mathcal{B}\\})$ and $R(\\{\mathcal{C}\\})$ denote the $R$
metric, as defined in Eq. (9), for the two collections separated and combined
respectively. Then

$R(\\{\mathcal{A},\mathcal{B}\\})\leq R(\\{\mathcal{C}\\})\ \ \text{ for all
}\ \ket{\psi}.$ (10)

###### Proof.

We write the operators associated with collections $\mathcal{A}$ and
$\mathcal{B}$ as

$\displaystyle O_{\mathcal{A}}$ $\displaystyle=\sum_{j=1}^{k}a_{j}P_{j},$ (11)
$\displaystyle O_{\mathcal{B}}$ $\displaystyle=\sum_{j=k+1}^{k+l}a_{j}P_{j},$
(12)

for some $k,l$ respectively, where the indexing of the sum in
$O_{\mathcal{B}}$ is for later convenience. The operator associated with
$\mathcal{C}$ can therefore be written as

$O_{\mathcal{C}}=\sum_{j=1}^{k+l}a_{j}P_{j}.$ (13)

We define the $(k+l)\times(k+l)$ covariance matrix $C$, which is symmetric and
positive semi-definite, associated with collection $\mathcal{C}$ by its
entries

$C_{ij}\coloneqq\text{Cov}[P_{i},P_{j}],$ (14)

with

$\text{Cov}[P_{i},P_{j}]\coloneqq\expectationvalue{P_{i}P_{j}}_{\psi}-\expectationvalue{P_{i}}_{\psi}\expectationvalue{P_{j}}_{\psi}.$
(15)

We write $\mathbf{a}$ for the vector of length $k+l$ whose first $k$ entries
are given by $\\{a_{j}\\}_{j=1}^{k}$ and the remaining $l$ entries are zero.
Similarly, we write $\mathbf{b}$ for the vector of length $k+l$ whose first
$k$ entries are zero and the remaining $l$ entries are given by
$\\{a_{j}\\}_{j=k+1}^{k+l}$.

Since the numerator of $R$ is constant for different arrangements, to prove
our claim it suffices for us to show that the denominator of $R$ is not
smaller in the case of $\\{\mathcal{A},\mathcal{B}\\}$ than in the case of
$\\{\mathcal{C}\\}$, i.e., that

$\sqrt{\mathrm{Var}[O_{\mathcal{A}}]}+\sqrt{\mathrm{Var}[O_{\mathcal{B}}]}\geq\sqrt{\mathrm{Var}[O_{\mathcal{C}}]}.$
(16)

With the above notation, this is equivalent to

$\sqrt{\mathbf{a}^{t}C\mathbf{a}}+\sqrt{\mathbf{b}^{t}C\mathbf{b}}\geq\sqrt{(\mathbf{a+b})^{t}C(\mathbf{a+b})}.$
(17)

We find

$\displaystyle\sqrt{\mathbf{a}^{t}C\mathbf{a}}+\sqrt{\mathbf{b}^{t}C\mathbf{b}}$
(18)
$\displaystyle=\sqrt{\left(\sqrt{\mathbf{a}^{t}C\mathbf{a}}+\sqrt{\mathbf{b}^{t}C\mathbf{b}}\right)^{2}}$
$\displaystyle=\sqrt{\mathbf{a}^{t}C\mathbf{a}+\mathbf{b}^{t}C\mathbf{b}+2\sqrt{(\mathbf{a}^{t}C\mathbf{a})(\mathbf{b}^{t}C\mathbf{b}})}$
$\displaystyle\geq\sqrt{\mathbf{a}^{t}C\mathbf{a}+\mathbf{b}^{t}C\mathbf{b}+2(\mathbf{a}^{t}C\mathbf{b}})$
$\displaystyle=\sqrt{(\mathbf{a+b})^{t}C(\mathbf{a+b})},$

where the third line follows due to the Cauchy-Schwarz inequality on a semi-
inner product defined by
$\langle{\mathbf{a}},{\mathbf{b}}\rangle\coloneqq\mathbf{a}^{\dagger}C\mathbf{b}$
(Conway, 1994, Example 1.1) and the fourth line follows as $C$ is symmetric.
This establishes our claim.

The inequality of Eq. 10 holds with equality if and only if there exist
$0\neq\alpha,\beta\in$ $\mathbb{C}$, such that
$\langle{\alpha\mathbf{a}+\beta\mathbf{b}},{\alpha\mathbf{a}+\beta\mathbf{b}}\rangle=0$
(Conway, 1994, Example 1.4). ∎

Claim 1 shows that it is impossible to mitigate covariances by splitting
collections under the optimal measurement strategy. This is in contrast to
Refs. McClean  _et al._ (2016); Gokhale  _et al._ (2019), which showed that it
is possible using a sub-optimal measurement strategy. In Appendix A, we re-do
precisely their example using the optimal measurement strategy. Note that
Claim 1 simply implies that it is never better to break a single collection
into two, and not that the minimum number of collections is necessarily the
best; indeed, we provide a counter-example below.

If all of the variances in $R$ are replaced by their expectation values over
the uniform spherical measure (see Ref. (Watrous, 2018, Ch. 7)), we obtain
another metric, $\hat{R}$, given by

$\hat{R}\coloneqq\left(\frac{\sum_{i=1}^{N}\sum_{j=1}^{m_{i}}|a_{ij}|}{\sum_{i=1}^{N}\sqrt{\sum_{j=1}^{m_{i}}|a_{ij}|^{2}}}\right)^{2}.$
(19)

The derivation of $\hat{R}$ is given in Appendix B. The same proof as in Claim
1 can be used to show that breaking a collection into two is never better when
measured by $\hat{R}$; the only difference is the covariance matrix must be
replaced by its expectation over the uniform spherical measure.

$\hat{R}$ is a particularly useful metric because it approximates $R$, but can
be calculated analytically. When ignorant of $\ket{\psi}$, a good collecting
strategy should aim to maximise $\hat{R}$. As mentioned above, this is
emphatically not the same as minimising the number of collections. For
example, let us consider the operator $O$, on two qubits, defined as

$O=4\,X_{1}+4\,X_{2}+Z_{2}+Z_{1}X_{2}.$ (20)

The operators cannot be assembled into a single commuting collection but there
is a unique arrangement, $\mathcal{G}_{1}$, consisting of two collections,
given by

$\mathcal{G}_{1}\coloneqq\Big{\\{}\\{4\,X_{1},\ Z_{2}\\},\\{4\,X_{2},\
Z_{1}X_{2}\\}\Big{\\}},$ (21)

which has $\hat{R}=1.47$ to two decimal places. $\mathcal{G}_{1}$ performs
worse than an arrangement $\mathcal{G}_{2}$, with three collections, given by

$\mathcal{G}_{2}\coloneqq\Big{\\{}\\{4\,X_{1},4\,X_{2}\\},\\{Z_{2}\\},\\{Z_{1}X_{2}\\}\Big{\\}},$
(22)

which has $\hat{R}=1.71$ to two decimal places.

Reflecting upon such examples and the nature of the square root function in
the denominator of $\hat{R}$ leads us to propose a collecting algorithm that
prioritises collecting Paulis with large coefficients.

This algorithm, which we name SORTED INSERTION, can be described as follows.
Given an operator

$O=\sum_{i=1}^{t}a_{j}P_{j},$ (23)

where $t$ is the total number of Pauli operators, the entire set
$\\{(a_{j},P_{j})\\}_{j=1}^{t}$ is sorted by the absolute value of
coefficients $a_{j}$, so that $|a_{1}|\geq\dots\geq|a_{t}|$. Then, in the
order $i=1,\dots t$, it is checked whether $P_{i}$ commutes with all elements
in an existing collection. If it does, it is added to that collection. If not,
a new collection is created and $P_{i}$ is inserted there. The collections are
checked in order of their creation. The collections formed are tracked and
outputted at the end once the final $P_{t}$ has been inserted.

SORTED INSERTION has worst-case complexity $O(nt^{2})$, where we recall that
$n$ is the number of qubits. In contrast, greedy colouring algorithms, as
implemented in Ref. Verteletskyi  _et al._ (2019), require pre-generating the
full commutation graph which has complexity $\Theta(nt^{2})$ even in the best
case. The colouring algorithms then run on this graph adding further
complexity – see Table 1. Therefore, SORTED INSERTION is always more efficient
than greedy colouring algorithms, such as those we will compare it to in Sec.
IV.

Colouring Algorithm | Time Complexity
---|---
Largest First | $O(t^{2})$
Connected Sequential d.f.s. | $O(t^{2})$
DSATUR | $O(t^{2}\log t)$
Independent Set | $O(t^{3})$
Table 1: Time complexities of the greedy colouring algorithms we compare with
SORTED INSERTION in Sec. IV after pre-generating the commutation graph
Kosowski and Manuszewski (2004).

##  III Rotation constructions

In this section, we present two methods of calculating a rotation circuit
which enables measurements of all operators in a mutually commuting collection
to be obtained simultaneously. We assume familiarity of the reader with the
stabiliser formalism, especially the $2n$-bit binary representation of
$n$-qubit Paulis Calderbank  _et al._ (1997); Gottesman (1997); Nielsen and
Chuang (2011); Aaronson and Gottesman (2004). We follow the convention that
the upper and lower halves of the binary matrix encode $Z$ and $X$ operators
respectively. This representation is reviewed in Appendix C. We also reserve
symbols $I_{m}$ and $0_{m}$ for the $m\times m$ identity and all-zero matrices
respectively.

Our starting point is a commuting collection,
$\mathcal{S}^{\prime}_{\text{start}}$, of $m$ Paulis which can be represented
as a binary $2n\times m$ matrix $S_{\text{start}}^{\prime}$. By Gaussian
elimination on $S_{\text{start}}^{\prime}$, we can form a $2n\times k$ matrix
$S_{\text{start}}$ representing a set $\mathcal{S}_{\text{start}}$ of $k$
independent Paulis drawn from $\mathcal{S}^{\prime}_{\text{start}}$ where
$k\leq\min(n,m)$. Our goal is to transform $S_{\text{start}}$, using certain
allowed transformations, into a $2n\times n$ matrix $S_{\text{end}}$ where

$S_{\text{end}}=\begin{pmatrix}I_{n}\\\ \hline\cr 0_{n}\end{pmatrix}.$ (24)

Let $U$ denote the circuit consisting of one-qubit and two-qubit
transformations in the order they were applied from
$S_{\text{start}}\rightarrow S_{\text{end}}$. Then applying $U$ to any state
$\ket{\psi}$, measuring in the computational basis, and classically post-
processing allows us to obtain measurements of all operators in
$\mathcal{S}^{\prime}_{\text{start}}$ on $\ket{\psi}$ simultaneously.

The allowed set, $\mathcal{T}$, of transformations on a binary $2n\times m$
matrix $S$ is, where $p$ ranges over all columns, $r$ ranges over all rows,
and addition is $\mathrm{mod}\ 2$:

  1. 1.

One-qubit and two-qubit quantum gates, corresponding to row operations,
specifically:

     * $\blacksquare$

CZ on qubits $i$ and $j$:
$S_{ip}\leftarrow S_{ip}+S_{j+n,p}$,
$S_{jp}\leftarrow S_{jp}+S_{i+n,p}$.

     * $\blacksquare$

CNOT on control-qubit $i$ and target-qubit $j$:
$S_{ip}\leftarrow S_{ip}+S_{jp}$,
$S_{j+n,p}\leftarrow S_{j+n,p}+S_{i+n,p}$.

     * $\blacksquare$

Hadamard (H) on qubit $i$:
$S_{ip}\leftrightarrow S_{i+n,p}$.

     * $\blacksquare$

Phase (P) on qubit $i$:
$S_{ip}\leftarrow S_{ip}+S_{i+n,p}$.

  2. 2.

Classical post-processing:

     * $\blacksquare$

Products of eventual single-qubit computational-basis measurements:
right-multiplication by invertible $m\times m$ matrix.

     * $\blacksquare$

Relabelling of qubits $i$ and $j$:
$S_{ip}\leftrightarrow S_{jp}$,
$S_{n+i,p}\leftrightarrow S_{n+j,p}$.

  3. 3.

Basis extension:

     * $\blacksquare$

Addition of further stabiliser:
appending of new column $S_{r,m+1}$.

In the near term, operations in $\mathcal{T}$ have justifiably different
costs. Two-qubit gates are much more costly than one-qubit gates, which are
more costly than classical post-processing. Basis extension has no cost. In
the context of one-qubit and two-qubit quantum gates, cost can refer to either
fidelity or gate-time Blais  _et al._ (2007); Laing  _et al._ (2010); Barends
_et al._ (2014); Ballance  _et al._ (2016); Allen  _et al._ (2017); Linke  _et
al._ (2017); Wendin (2017); Reagor  _et al._ (2018); Schäfer  _et al._ (2018);
Webb  _et al._ (2018); Levine  _et al._ (2018); He  _et al._ (2019a); Huang
_et al._ (2019); Blumel  _et al._ (2019); He  _et al._ (2019b). Therefore, we
have aimed to minimise the number of two-qubit gates in the $U$ resulting from
our constructions. This means, for example, we choose to perform a row swap
using classical post-processing rather than the two-qubit SWAP gate.

In presenting our constructions, we shall refer to the commutativity
condition, preserved under $\mathcal{T}$, given by

$S^{T}J_{2n}S=0_{m},$ (25)

where $S$ is the $2n\times m$ matrix encoding the Paulis and

$J_{2n}=\begin{pmatrix}0_{n}&I_{n}\\\ I_{n}&0_{n}\end{pmatrix}.$ (26)

We ignore any changes in sign of stabilisers under $\mathcal{T}$ as this can
be easily accounted for by classical post-processing. Readers interested in
this and other details are referred to Appendix D, where we work through our
CZ-construction with a specific example.

###  III.1 CZ-construction

Important to our first approach is the special class of stabiliser states
known as graph states. Consider any graph $G$ on $n$ vertices. The graph state
$\ket{\Phi_{G}}$ is then defined by $n$ independent stabiliser generators

$g_{i}=X_{i}\prod_{j\in\text{nbd}(i)}Z_{j},\ i=1,\dots,n,$ (27)

where $\text{nbd}(i)$ is the set of neighbours of vertex $i$ in $G$. The
binary representation of these stabilisers is

$S_{\text{graph}}=\begin{pmatrix}A\\\ \hline\cr I_{n}\end{pmatrix},$ (28)

where $A$, an $n\times n$ symmetric matrix with $0$s on its diagonal, is
exactly the adjacency matrix of $G$.

It is well-known that $\ket{\Phi_{G}}=V\textsc{H}^{\otimes n}\ket{0^{n}}$
where $V$ is a product of CZ gates and H is the Hadamard gate. More
specifically, $V$ applies CZ between qubits $i$ and $j$ if and only if vertex
$i$ neighbours $j$ in $G$. Van den Nest, Dehaene, and De Moor Van den Nest
_et al._ (2004) tell us that any stabiliser state can be transformed to a
graph state by a product of single-qubit Clifford gates. It is therefore clear
that we can transform any $S_{\text{start}}$ to $S_{\text{end}}$ via
$S_{\text{graph}}$ using at most $n(n-1)/2$ two-qubit (CZ) gates, as this is
the maximum number of edges on an $n$-vertex graph. The interesting question
is whether we can do better by exploiting the potential low rank $k\leq n$ of
$S_{\text{start}}$.

Our answer is in the affirmative and we now present an explicit and efficient
algorithm that constructs $U$ with at most $u_{\text{cz}}(k,n)=kn-k(k+1)/2$
two-qubit gates.

|  | $S_{1}$ |  | $S_{2}$ |  |
---|---|---|---|---|---|---
$S_{\text{start}}$ | $\xrightarrow{1}$ | $\begin{pmatrix}A\\\ \hline\cr B\end{pmatrix}$ | $\xrightarrow{2}$ | $\begin{pmatrix}C\\\ D\\\ \hline\cr I_{k}\\\ F\end{pmatrix}$ |  |
|  | $S_{3}$ |  | $S_{4}=S_{\text{graph}}$ |  |
| $\xrightarrow{3}$ | $\begin{pmatrix}C&D^{T}\\\ D&0_{n-k}\\\ \hline\cr I_{k}&0\\\ F&I_{n-k}\end{pmatrix}$ | $\xrightarrow{4}$ | $\begin{pmatrix}E&D^{T}\\\ D&0_{n-k}\\\ \hline\cr I_{k}&0\\\ 0&I_{n-k}\end{pmatrix}$ | $\xrightarrow{5}$ | $S_{\text{end}}$

Figure 1: Reductions used in our CZ-construction.

In Fig. 1, we illustrate the sequence of reductions that allow us to reach
$S_{\text{graph}}$, and so $S_{\text{end}}$, from $S_{\text{start}}$. We now
describe the salient aspects of each step.

  1. 1.

$S_{\text{start}}\rightarrow S_{1}.$ Following Ref. (Aaronson and Gottesman,
2004, Lemma 6), we can apply Hadamard gates so that $B$ has rank $k$. By
classical row-swaps (relabelling of qubits), we can ensure that the first $k$
rows of $B$ have full-rank.

  2. 2.

$S_{1}\rightarrow S_{2}.$ Since the upper $k\times k$ submatrix of $B$ has
full-rank, column operations corresponding to classical post-processing can
reduce it to $I_{k}$.

  3. 3.

$S_{2}\rightarrow S_{3}.$ Additional columns, corresponding to further
operators, are appended. We can directly verify that the extension to $S_{3}$
is valid by Eq. (25). Clearly $S_{3}$ has full column-rank $n$. The sparsity
of our chosen extension shall play a crucial role in the reduced two-qubit
gate size of $U$ when $k<n$ in both the CZ\- and CNOT-constructions.

  4. 4.

$S_{3}\rightarrow S_{4}=S_{\text{graph}}.$ Column operations can eliminate
$F$, then Phase gates can ensure $E$ has zeros on its diagonal. Importantly,
$S_{4}$ represents a graph state $S_{\text{graph}}$.

  5. 5.

$S_{4}\rightarrow S_{\text{end}}$. Phase and CZ gates can implement this final
reduction as discussed above. The maximum number of CZ gates required to map
$S_{4}$ to $S_{\text{end}}$ equals the maximum number of off-diagonal $1$s in
the upper half of $S_{4}$. When $n=k$, this is $n(n-1)/2=O(n^{2})$. When
$k\neq n$, this is $w_{cz}(k,n)=kn-k(k+1)/2$ due to sparsity of the upper half
of $S_{4}$ which traces back to the structure of the additional operators
appended in step $S_{3}\rightarrow S_{4}$.

Note that in step $S_{4}\rightarrow S_{\text{end}}$, we can first try to
reduce the upper half of $S_{4}$ by single-qubit gates before applying CZ. One
way to do this is to reduce the number of edges in the graph whose adjacency
matrix is specified by the upper half of $S_{4}$ by the so-called “local
complementation” operation Van den Nest  _et al._ (2004); Hein  _et al._
(2004); Bouchet (1993). This corresponds precisely to reducing the number of
CZ gates in our CZ-construction.

###  III.2 CNOT-construction

|  | $S_{5}$ |  | $S_{6}$ |  |
---|---|---|---|---|---|---
$S_{4}$ | $\xrightarrow{5}$ | $\begin{pmatrix}0_{k}&D^{T}\\\ D&0_{n-k}\\\ \hline\cr M&0\\\ 0&I_{n-k}\end{pmatrix}$ | $\xrightarrow{6}$ | $\begin{pmatrix}I_{k}&D^{T}\\\ D&I_{n-k}\\\ \hline\cr I_{k}&0\\\ 0&I_{n-k}\end{pmatrix}$ |  |
|  | $S_{7}$ |  | $S_{8}$ |  |
| $\xrightarrow{7}$ | $\begin{pmatrix}D_{1}M_{1}\\\ \hline\cr M_{1}\end{pmatrix}$ | $\xrightarrow{8}$ | $\begin{pmatrix}I_{k}-D^{T}D&0\\\ 0&I_{n-k}\\\ \hline\cr I_{k}&0\\\ 0&I_{n-k}\end{pmatrix}$ | $\xrightarrow{9}$ | $S_{\text{end}}$

Figure 2: Reductions used in our CNOT-construction starting at $S_{4}$ of our
CZ-construction.

We start from $S_{4}$ above which we reached without using two-qubit gates.
Now, instead of using one block of CZ gates, we reduce to $S_{\text{end}}$ as
shown in Fig. 2, using three blocks of CNOT gates.

  1. 5.

$S_{4}\rightarrow S_{5}$. Note that $E$ must be symmetric by the commutativity
condition given in Eq. (25). Then, following Ref. (Aaronson and Gottesman,
2004, Lemma 7), we can eliminate $E$ using single-qubit and $O(k^{2}/\log k)$
CNOT gates. This is accomplished by noting that any symmetric binary $E$ can
be Cholesky decomposed as $E=\Lambda+M^{T}M$, with $\Lambda$ diagonal and $M$
invertible.

  2. 6.

$S_{5}\rightarrow S_{6}$. Reduce $M$ to $I_{k}$ by column operations, then add
$1$s on the top diagonal by phase gates.

  3. 7.

$S_{6}\rightarrow S_{7}$. Now, the upper $n\times n$ matrix can be block-
Cholesky decomposed as

$\begin{pmatrix}I_{k}&D^{T}\\\ D&I_{n-k}\end{pmatrix}=M_{1}^{T}D_{1}M_{1},$
(29)

where

$\displaystyle M_{1}$ $\displaystyle\coloneqq\begin{pmatrix}I_{k}&0\\\
D&I_{n-k}\end{pmatrix},$ (30) $\displaystyle D_{1}$
$\displaystyle\coloneqq\begin{pmatrix}I_{k}-D^{T}D&0\\\
0&I_{n-k}\end{pmatrix}.$ (31)

Next, we apply CNOT gates corresponding to $M_{1}$. The number of CNOT gates
required here equals the number of row operations required to reduce $M_{1}$
to $I_{n}$. We find this is at most $u_{\text{cnot}}(k,n)=O(kn/\log k)$ via
arguments of Patel, Markov, and Hayes Patel  _et al._ (2008). The proof is
given in Appendix E.

  4. 8.

$S_{7}\rightarrow S_{8}$. Multiply by $M_{1}^{-1}$ on the right.

  5. 9.

$S_{8}\rightarrow S_{\text{end}}$. $I_{k}-D^{T}D$ is a $k\times k$ symmetric
matrix and so can be again eliminated via the Cholesky decomposition using
$O(k^{2}/\log k)$ CNOT gates.

Note that in the three steps $S_{4}\rightarrow S_{5}$, $S_{6}\rightarrow
S_{7}$, and $S_{8}\rightarrow S_{\text{end}}$, we have used blocks of CNOT
gates. The method we used to synthesise these blocks is size-optimal (Patel
_et al._ , 2008, Lemma 1), but we could have alternatively used methods in
Ref. Jiang  _et al._ (2019), that built on Ref. Moore and Nilsson (1998), to
achieve optimal space-depth tradeoff, where space refers to extra ancilla
qubits.

To end our discussion of constructing rotation circuits, we briefly mention a
third, ancilla-based construction with two-qubit gate size at most $kn$. This
construction is well-known in the context of syndrome measurement Nielsen and
Chuang (2011) in quantum error correction but does not seem to have been
mentioned in the context of measuring a Pauli decomposition of an operator, as
in VQE. To measure $k$ commuting Paulis $\\{P_{i}\\}_{i=1}^{k}$, this
“ancilla-construction” uses $k$ ancilla and involves $k$ consecutive blocks of
generalised-CNOT gates, each targeted at a different ancilla. The controls in
block $b\leq k$ are activated or deactivated by the $+1$ or $-1$ eigenstates
of the single-qubit Paulis forming $P_{b}$ 222So $Z$ corresponds to standard
control on $\\{\ket{0},\ket{1}\\}$, $X$ corresponds to control on
$\\{\ket{+},\ket{-}\\}$, $Y$ corresponds to control on
$\\{\ket{+i},\ket{-i}\\}$, and $I$ corresponds to not having a generalised-
CNOT. These generalised-CNOT gates can be implemented by the standard CNOT
conjugated by $H$ in case of $X$, or $SH$ in case of $Y$.. $k$ single-qubit
measurements are performed on the ancilla at the end of each block to exactly
give measurements of $P_{i}$. Unfortunately, this construction requires $k$
extra ancilla qubits and has worse worst-case two-qubit gate size than both of
our constructions. However, it does serve as a simple way to see, a priori,
that a two-qubit gate scaling of $O(kn)$ is possible.

##  IV Application to VQE

In this section, we present numerical results of the collecting method
discussed in Sec. II, alongside the CZ-construction of Sec. III.1 to construct
the rotation circuits for given commuting collections. In particular, we have
applied our methods to the Hamiltonians of simple molecules so as to
demonstrate their use in the context of VQE. The full results are given in
Table 4 of Appendix F, with a subset shown in Table 2. In all cases, we used
OpenFermion McClean  _et al._ (2017) to obtain Hamiltonians in the STO-3G
basis, at approximately the equilibrium geometry of the molecules, with the
symmetry conserving Bravyi-Kitaev transformation Bravyi and Kitaev (2002);
Bravyi  _et al._ (2017). In order to reduce the number of two-qubit gates
required, we considered qubits on which all operators in a collection locally
commute separately – a one-qubit rotation per locally commuting qubit is all
that is required to do so.

In Fig. 3(a), we plot the average collection size against the number of
qubits, $n$, for the molecular Hamiltonians. We can see that the average
collection size increases with increasing $n$, and the increase does not
appear to be slowing down. We therefore conclude that our sorting method works
well on systems up to at least size $n=38$, and looks likely to work for
larger systems. However, the key advantage of assembling a Hamiltonian into
collections of mutually commuting operators is a reduction in the number of
measurements required to obtain an energy expectation to a certain level of
accuracy, and collection size alone does not directly quantify this reduction.
For a given Hamiltonian and quantum state, the reduction is instead given by
$R$, as in Eq. (9).

Molecule |  $n$ qubits |  $t$ Paulis |  | Arrangement |  |  Ratios $R$, $\hat{R}$ |  |  Rotation Circuit $2q$-size
---|---|---|---|---|---|---|---|---
|  |  |  |  $N$ |  $\overline{m_{i}}$ |  $\overline{k_{i}}$ |  |  $R$ min |  $R$ mean |  $R$ max |  $\hat{R}$ |  |  theory max |  true max |  mean
H2 |  2 |  4 |  |  2 |  2.00 |  1.50 |  |  1.09 |  1.93 |  4.60 |  1.76 |  |  0 |  0 |  0
H${}_{3}^{+}$ |  4 |  59 |  |  10 |  5.90 |  3.50 |  |  3.76 |  11.92 |  33.04 |  10.25 |  |  6 |  3 |  0.80
LiH |  10 |  630 |  |  41 |  15.37 |  6.85 |  |  19.60 |  24.91 |  34.74 |  23.97 |  |  45 |  18 |  5.29
OH- |  10 |  630 |  |  38 |  16.58 |  7.29 |  |  6.32 |  8.90 |  12.86 |  8.51 |  |  45 |  17 |  5.63
HF |  10 |  630 |  |  39 |  16.15 |  6.97 |  |  6.07 |  8.57 |  12.27 |  8.21 |  |  45 |  16 |  5.74
H2O |  12 |  1085 |  |  51 |  21.27 |  9.04 |  |  7.68 |  11.27 |  16.96 |  10.67 |  |  66 |  26 |  7.37
BH3 |  14 |  1584 |  |  66 |  24.00 |  10.36 |  |  17.21 |  20.93 |  32.13 |  20.05 |  |  91 |  26 |  9.56
NH3 |  14 |  3608 |  |  118 |  30.58 |  11.34 |  |  12.65 |  15.96 |  26.93 |  15.31 |  |  91 |  28 |  10.26
CH4 |  16 |  3887 |  |  123 |  31.60 |  13.39 |  |  16.96 |  21.63 |  29.33 |  20.27 |  |  120 |  45 |  16.75
Table 2: A reduced set of results of the numerical simulations discussed in the main text, and shown in full in Table 4. For each molecule, we show a number of results related to the collecting of Hamiltonian terms, how the arrangement reduces the number of measurements required using the metrics $R$ and $\hat{R}$, and the number of two-qubit gates in the resulting rotation circuits. Note that the mean value of $R$ and $\hat{R}$ are very similar. Molecule |  | Largest First |  | Connected Sequential d.f.s. |  | Independent Set |  | DSATUR |  | SORTED INSERTION
---|---|---|---|---|---|---|---|---|---|---
|  |  $N$ |  $\hat{R}$ |  |  $N$ |  $\hat{R}$ |  |  $N$ |  $\hat{R}$ |  |  $N$ |  $\hat{R}$ |  |  $N$ |  $\hat{R}$
H2 |  |  2 |  1.76 |  |  2 |  1.76 |  |  2 |  1.76 |  |  2 |  1.76 |  |  2 |  1.76
H${}_{3}^{+}$ |  |  10 |  4.86 |  |  10 |  10.25 |  |  10 |  10.30 |  |  9 |  4.10 |  |  10 |  10.25
LiH |  |  39 |  23.87 |  |  45 |  23.33 |  |  30 |  5.72 |  |  29 |  10.47 |  |  41 |  23.97
OH- |  |  40 |  8.27 |  |  41 |  8.41 |  |  21 |  3.00 |  |  28 |  3.23 |  |  37 |  8.51
HF |  |  38 |  8.05 |  |  41 |  8.07 |  |  21 |  2.80 |  |  28 |  3.23 |  |  38 |  8.21
H2O |  |  57 |  2.98 |  |  55 |  10.66 |  |  42 |  3.87 |  |  51 |  3.18 |  |  51 |  10.66
BH3 |  |  66 |  4.80 |  |  85 |  18.70 |  |  60 |  7.85 |  |  72 |  4.11 |  |  68 |  20.05
NH3 |  |  124 |  6.50 |  |  174 |  13.97 |  |  126 |  4.03 |  |  137 |  2.92 |  |  117 |  15.31
CH4 |  |  122 |  5.84 |  |  176 |  18.93 |  |  114 |  9.88 |  |  110 |  4.90 |  |  125 |  20.27
O2 |  |  62 |  13.62 |  |  85 |  19.95 |  |  42 |  6.79 |  |  52 |  7.91 |  |  67 |  20.23
N2 |  |  62 |  15.00 |  |  86 |  21.15 |  |  39 |  8.37 |  |  49 |  5.80 |  |  78 |  22.10
CO |  |  124 |  20.70 |  |  155 |  20.67 |  |  89 |  6.03 |  |  106 |  4.55 |  |  128 |  21.31
HCl |  |  117 |  2.16 |  |  141 |  10.29 |  |  98 |  3.52 |  |  104 |  2.04 |  |  123 |  10.36
NaH |  |  121 |  8.78 |  |  181 |  12.40 |  |  149 |  3.44 |  |  145 |  3.65 |  |  135 |  12.90
H2S |  |  122 |  8.81 |  |  180 |  12.45 |  |  147 |  3.80 |  |  145 |  3.66 |  |  147 |  11.60
Table 3: Comparison of the arrangements produced by the greedy colouring
algorithms “Largest First”, “Connected Sequential d.f.s.” (depth first
search), “Independent Set” and “DSATUR” as implemented by the Python package
NetworkX Hagberg  _et al._ (2008) with our method SORTED INSERTION. For each
method, the number of collections produced, $N$, and the metric $\hat{R}$
given by equation (19), are presented. The best or joint best methods are
highlighted in bold for each molecule.

${0}$${20}$${40}$${60}$${80}$${100}$${120}$${140}$(a)$0$$10$$20$$30$$40$$50$$60$$70$(b)$0$$1$$2$$3$$4$$5$$0$$5$$10$$15$$20$$25$$30$$35$$40$(c)

Average collection size

Value of $\hat{R}$

Ratio of worst-case max number of

two-qubit gates to actual number

Number of qubits

Figure 3: The results of numerical simulations discussed in the text. We show
(a) the average collection size, (b) the value of $\hat{R}$, given by Eq.
(19), and (c) the ratio of the worst-case maximum number of two-qubit gates in
a single rotation circuit to the actual number as a function of the number of
qubits for a range of simple molecules. A collection of the data is shown in
Table 2, and the full data is shown in Table 4.

We therefore calculated the value of $R$ for 100 different quantum states,
generated using 100 random sets of ansatz parameters with a hardware efficient
ansatz of depth 1, for the nine smallest molecular systems. We show the mean,
minimum and maximum values for each molecule. In practice, the value of $R$
can at best be obtained approximately by making measurements on the quantum
computer and so cannot be used to determine the expected advantage of a
particular arrangement a priori. The metric $\hat{R}$, given by Eq. (19), on
the other hand, depends only on the coefficients of the terms in the
Hamiltonian. From Table 2, we can see that $\hat{R}$ closely approximates the
average of $R$ over many ansatz parameters, for the ansatz we have considered,
but can be calculated analytically without the need for simulations. Further
investigation of the relationship between $\hat{R}$ and $R$ will be useful if
considering a different ansatz. In Fig. 3(b), we show $\hat{R}$ as a function
of the number of qubits for our full selection of molecules. We can see that
it is highly molecule dependent, with systems of similar size having very
different values.

The reduction in the number of measurements required comes at the cost of
applying additional quantum gates before the qubits are measured, the most
costly of which are two-qubit gates. For the CZ-construction, we demonstrated
in Sec. III.1 that the maximum number of additional two-qubit gates required
for a collection with $k$ independent terms is $nk-k(k+1)/2$. We would like to
know, in practice, how many additional two-qubit gates are required at a
maximum, as this is the quantum resource that is most limiting. Assuming for a
given Hamiltonian that at least one collection has rank $n$, obtaining a
measurement of all terms in a Hamiltonian on $n$ qubits may therefore require
applying an additional $n(n-1)/2$ gates in a single circuit. However, for the
molecules we have considered, we find that the largest number of two-qubit
gates required is in fact far lower than this, typically by a factor of
approximately 3.5, as can be seen in Fig. 3(c).

Given the close relationship between the average value of $R$ and the value of
$\hat{R}$, we propose using $\hat{R}$ as a metric for the quality of a
collecting method and compare different methods of collecting the operators
with this metric in mind. The results are shown in Table 3, along with the
number of collections of operators, $N$, that each method produces. Out of the
methods, “Independent Set” was best at approximating the minimum clique cover
– it found the cover with the fewest cliques in all but one case. However, it
appears that the minimum clique cover does not necessarily result in the
fewest measurements, with “Independent Set” only performing best once with
respect to $\hat{R}$. Overall, our SORTED INSERTION was best at maximising
$\hat{R}$, performing best or joint best in all but two cases.

##  V Conclusion

We have addressed two problems related to the efficient measurement of Pauli
operators on a quantum computer in the presence of finite sampling error. The
first is how to assemble a set of Paulis into collections in which they
mutually commute, and the second is how to construct rotation circuits that
enable mutually commuting Paulis to be measured simultaneously.

For the first problem, we contribute two natural metrics, $R$ and $\hat{R}$,
that justifiably measure the effectiveness of an arrangement, followed by a
collecting strategy motivated by $\hat{R}$ that we call SORTED INSERTION. For
the second problem, we contribute two rotation circuit constructions CZ and
CNOT. The CZ-construction results in a maximum of
$u_{\text{cz}}(k,n)=kn-k(k+1)/2$ two-qubit gates while the CNOT-construction
results in a maximum of $u_{\text{cnot}}(k,n)=O(kn/\log k)$.

We have applied our theoretical work to the task of estimating energies of
molecules in the context of VQE. Comparison to other collecting methods shows
that while SORTED INSERTION does not normally result in the smallest number of
collections, it nearly always results in the best value of $\hat{R}$. We also
find that, for the CZ-construction, the largest number of two-qubit gates
required is typically less than the theoretical worst-case by a factor of
approximately 3.5.

##  VI Acknowledgement

We thank Oscar Higgott for informing us of the ancilla-based simultaneous
measurement method and Ref. (Dennis  _et al._ , 2002, Fig. 14).

## References

  * Peruzzo  _et al._ (2014) Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’Brien, “A variational eigenvalue solver on a photonic quantum processor,” Nature communications 5, 4213 (2014).
  * Preskill (2018) John Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018).
  * McClean  _et al._ (2016) Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms,” New Journal of Physics 18, 023023 (2016).
  * O’Malley  _et al._ (2016) P. J. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, P. J. Love, H. Neven, A. Aspuru-Guzik, J. M. Martinis, _et al._ , “Scalable quantum simulation of molecular energies,” Phys. Rev. X 6, 031007 (2016).
  * Kandala  _et al._ (2017a) Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta, “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” Nature 549, 242 EP – (2017a).
  * McArdle  _et al._ (2018) Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan, “Quantum computational chemistry,” arXiv e-prints (2018), arXiv:1808.10402 [quant-ph] .
  * Ryabinkin  _et al._ (2019) Ilya G. Ryabinkin, Scott N. Genin, and Artur F. Izmaylov, “Constrained variational quantum eigensolver: Quantum computer search engine in the fock space,”  _Journal of Chemical Theory and Computation_ , Journal of Chemical Theory and Computation 15, 249–255 (2019).
  * Romero  _et al._ (2018) Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter J Love, and Alán Aspuru-Guzik, “Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz,” Quantum Science and Technology 4, 014008 (2018).
  * Wang  _et al._ (2019) Daochen Wang, Oscar Higgott, and Stephen Brierley, “Accelerated variational quantum eigensolver,” Phys. Rev. Lett. 122, 140504 (2019).
  * McClean  _et al._ (2017) Jarrod R McClean, Mollie E Kimchi-Schwartz, Jonathan Carter, and Wibe A de Jong, “Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states,” Physical Review A 95, 042308 (2017).
  * Santagati  _et al._ (2018) Raffaele Santagati, Jianwei Wang, Antonio A. Gentile, Stefano Paesani, Nathan Wiebe, Jarrod R. McClean, Sam Morley-Short, Peter J. Shadbolt, Damien Bonneau, Joshua W. Silverstone, David P. Tew, Xiaoqi Zhou, Jeremy L. O’Brien, and Mark G. Thompson, “Witnessing eigenstates for quantum simulation of hamiltonian spectra,” Science Advances 4 (2018).
  * Colless  _et al._ (2018) J. I. Colless, V. V. Ramasesh, D. Dahlen, M. S. Blok, M. E. Kimchi-Schwartz, J. R. McClean, J. Carter, W. A. de Jong, and I. Siddiqi, “Computation of molecular spectra on a quantum processor with an error-resilient algorithm,” Phys. Rev. X 8, 011021 (2018).
  * Heya  _et al._ (2019) Kentaro Heya, Ken M Nakanishi, Kosuke Mitarai, and Keisuke Fujii, “Subspace Variational Quantum Simulator,” arXiv e-prints (2019), arXiv:1904.08566 [quant-ph] .
  * Jones  _et al._ (2019) Tyson Jones, Suguru Endo, Sam McArdle, Xiao Yuan, and Simon C. Benjamin, “Variational quantum algorithms for discovering Hamiltonian spectra,” Phys. Rev. A 99, 062304 (2019).
  * Higgott  _et al._ (2019) Oscar Higgott, Daochen Wang, and Stephen Brierley, “Variational Quantum Computation of Excited States,” Quantum 3, 156 (2019).
  * Verteletskyi  _et al._ (2019) Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F. Izmaylov, “Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover,” arXiv e-prints (2019), arXiv:1907.03358 [quant-ph] .
  * Jena  _et al._ (2019) Andrew Jena, Scott Genin, and Michele Mosca, “Pauli Partitioning with Respect to Gate Sets,” arXiv e-prints (2019), arXiv:1907.07859 [quant-ph] .
  * Yen  _et al._ (2019) Tzu-Ching Yen, Vladyslav Verteletskyi, and Artur F. Izmaylov, “Measuring all compatible operators in one series of a single-qubit measurements using unitary transformations,” arXiv e-prints (2019), arXiv:1907.09386 [quant-ph] .
  * Huggins  _et al._ (2019) William J. Huggins, Jarrod McClean, Nicholas Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, and Ryan Babbush, “Efficient and Noise Resilient Measurements for Quantum Chemistry on Near-Term Quantum Computers,” arXiv e-prints (2019), arXiv:1907.13117 [quant-ph] .
  * Gokhale  _et al._ (2019) Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T. Chong, “Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families,” arXiv e-prints (2019), arXiv:1907.13623 [quant-ph] .
  * Zhao  _et al._ (2019) Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter Love, “Measurement reduction in variational quantum algorithms,” arXiv e-prints , arXiv:1908.08067 (2019), arXiv:1908.08067 [quant-ph] .
  * Gokhale and Chong (2019) Pranav Gokhale and Frederic T. Chong, “$O(N^{3})$ Measurement Cost for Variational Quantum Eigensolver on Molecular Hamiltonians,” arXiv e-prints (2019), arXiv:1908.11857 [quant-ph] .
  * Note (1) We mention that both the collecting and rotation circuit synthesis problems have been addressed on an ad-hoc basis by experimentalists since Kandala  _et al._ Kandala  _et al._ (2017b). We refer readers to Table 2 of Ref. Gokhale  _et al._ (2019) for a good summary. We also mention that recent Ref. Izmaylov  _et al._ (2019) and the less recent Ref. Izmaylov  _et al._ (2019) allow for collecting of non-commuting Paulis. We found it interesting that such approaches are feasible, but found it hard to compare them to our work on a like-for-like basis.
  * Wecker  _et al._ (2015) Dave Wecker, Matthew B. Hastings, and Matthias Troyer, “Progress towards practical quantum variational algorithms,” Phys. Rev. A 92, 042303 (2015).
  * Rubin  _et al._ (2018) Nicholas C Rubin, Ryan Babbush, and Jarrod McClean, “Application of fermionic marginal constraints to hybrid quantum algorithms,” New Journal of Physics 20, 053020 (2018).
  * Blais  _et al._ (2007) Alexandre Blais, Jay Gambetta, A. Wallraff, D. I. Schuster, S. M. Girvin, M. H. Devoret, and R. J. Schoelkopf, “Quantum-information processing with circuit quantum electrodynamics,” Phys. Rev. A 75, 032329 (2007).
  * Laing  _et al._ (2010) Anthony Laing, Alberto Peruzzo, Alberto Politi, Maria Rodas Verde, Matthaeus Halder, Timothy C. Ralph, Mark G. Thompson, and Jeremy L. O’Brien, “High-fidelity operation of quantum photonic circuits,” Applied Physics Letters 97, 211109 (2010).
  * Barends  _et al._ (2014) R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O’Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and John M. Martinis, “Superconducting quantum circuits at the surface code threshold for fault tolerance,” Nature 508, 500 EP – (2014).
  * Ballance  _et al._ (2016) C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, “High-fidelity quantum logic gates using trapped-ion hyperfine qubits,” Phys. Rev. Lett. 117, 060504 (2016).
  * Allen  _et al._ (2017) Joseph L. Allen, Robert Kosut, Jaewoo Joo, Peter Leek, and Eran Ginossar, “Optimal control of two qubits via a single cavity drive in circuit quantum electrodynamics,” Phys. Rev. A 95, 042325 (2017).
  * Linke  _et al._ (2017) Norbert M. Linke, Dmitri Maslov, Martin Roetteler, Shantanu Debnath, Caroline Figgatt, Kevin A. Landsman, Kenneth Wright, and Christopher Monroe, “Experimental comparison of two quantum computing architectures,” Proceedings of the National Academy of Sciences 114, 3305–3310 (2017).
  * Wendin (2017) G Wendin, “Quantum information processing with superconducting circuits: a review,” Reports on Progress in Physics 80, 106001 (2017).
  * Reagor  _et al._ (2018) Matthew Reagor, Christopher B. Osborn, Nikolas Tezak, Alexa Staley, Guenevere Prawiroatmodjo, Michael Scheer, Nasser Alidoust, Eyob A. Sete, Nicolas Didier, Marcus P. da Silva, Ezer Acala, Joel Angeles, Andrew Bestwick, Maxwell Block, Chad T. Rigetti, _et al._ , “Demonstration of universal parametric entangling gates on a multi-qubit lattice,” Science Advances 4 (2018).
  * Schäfer  _et al._ (2018) V. M. Schäfer, C. J. Ballance, K. Thirumalai, L. J. Stephenson, T. G. Ballance, A. M. Steane, and D. M. Lucas, “Fast quantum logic gates with trapped-ion qubits,” Nature 555, 75 EP – (2018).
  * Webb  _et al._ (2018) A. E. Webb, S. C. Webster, S. Collingbourne, D. Bretaud, A. M. Lawrence, S. Weidt, F. Mintert, and W. K. Hensinger, “Resilient entangling gates for trapped ions,” Phys. Rev. Lett. 121, 180501 (2018).
  * Levine  _et al._ (2018) Harry Levine, Alexander Keesling, Ahmed Omran, Hannes Bernien, Sylvain Schwartz, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, “High-fidelity control and entanglement of Rydberg-atom qubits,” Phys. Rev. Lett. 121, 123603 (2018).
  * He  _et al._ (2019a) Y. He, S. K. Gorman, D. Keith, L. Kranz, J. G. Keizer, and M. Y. Simmons, “A two-qubit gate between phosphorus donor electrons in silicon,” Nature 571, 371–375 (2019a).
  * Huang  _et al._ (2019) W. Huang, C. H. Yang, K. W. Chan, T. Tanttu, B. Hensen, R. C. C. Leon, M. A. Fogarty, J. C. C. Hwang, F. E. Hudson, K. M. Itoh, A. Morello, A. Laucht, and A. S. Dzurak, “Fidelity benchmarks for two-qubit gates in silicon,” Nature 569, 532–536 (2019).
  * Blumel  _et al._ (2019) Reinhold Blumel, Nikodem Grzesiak, and Yunseong Nam, “Power-optimal, stabilized entangling gate between trapped-ion qubits,” arXiv e-prints (2019), arXiv:1905.09292 [quant-ph] .
  * He  _et al._ (2019b) Y. He, S. K. Gorman, D. Keith, L. Kranz, J. G. Keizer, and M. Y. Simmons, “A two-qubit gate between phosphorus donor electrons in silicon,” Nature 571, 371–375 (2019b).
  * Van den Nest  _et al._ (2004) Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor, “Graphical description of the action of local Clifford transformations on graph states,” Phys. Rev. A 69, 022316 (2004).
  * Aaronson and Gottesman (2004) Scott Aaronson and Daniel Gottesman, “Improved simulation of stabilizer circuits,” Phys. Rev. A 70, 052328 (2004).
  * Patel  _et al._ (2008) Ketan N. Patel, Igor L. Markov, and John P. Hayes, “Optimal synthesis of linear reversible circuits,” Quantum Info. Comput. 8, 282–294 (2008).
  * Conway (1994) J.B. Conway,  _A Course in Functional Analysis_, Graduate Texts in Mathematics (Springer New York, 1994).
  * Watrous (2018) John Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, 2018).
  * Kosowski and Manuszewski (2004) Adrian Kosowski and Krzysztof Manuszewski, “Classical coloring of graphs,” (2004).
  * Calderbank  _et al._ (1997) A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, “Quantum error correction and orthogonal geometry,” Phys. Rev. Lett. 78, 405–408 (1997).
  * Gottesman (1997) Daniel Gottesman,  _Stabilizer codes and quantum error correction_ , Ph.D. thesis, California Institute of Technology (1997).
  * Nielsen and Chuang (2011) Michael A. Nielsen and Isaac L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ , 10th ed. (Cambridge University Press, New York, NY, USA, 2011).
  * Hein  _et al._ (2004) M. Hein, J. Eisert, and H. J. Briegel, “Multiparty entanglement in graph states,” Phys. Rev. A 69, 062311 (2004).
  * Bouchet (1993) André Bouchet, “Recognizing locally equivalent graphs,” Discrete Mathematics 114, 75 – 86 (1993).
  * Jiang  _et al._ (2019) Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang, “Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis,” arXiv e-prints (2019), arXiv:1907.05087 [quant-ph] .
  * Moore and Nilsson (1998) Cristopher Moore and Martin Nilsson, “Parallel Quantum Computation and Quantum Codes,” arXiv e-prints (1998), arXiv:quant-ph/9808027 [quant-ph] .
  * Note (2) So $Z$ corresponds to standard control on $\\{\ket{0},\ket{1}\\}$, $X$ corresponds to control on $\\{\ket{+},\ket{-}\\}$, $Y$ corresponds to control on $\\{\ket{+i},\ket{-i}\\}$, and $I$ corresponds to not having a generalised-CNOT. These generalised-CNOT gates can be implemented by the standard CNOT conjugated by $H$ in case of $X$, or $SH$ in case of $Y$.
  * McClean  _et al._ (2017) Jarrod R. McClean, Kevin J. Sung, Ian D. Kivlichan, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Ryan Babbush, _et al._ , “OpenFermion: The Electronic Structure Package for Quantum Computers,” arXiv e-prints (2017), arXiv:1710.07629 [quant-ph] .
  * Bravyi and Kitaev (2002) Sergey B. Bravyi and Alexei Yu. Kitaev, “Fermionic Quantum Computation,” Annals of Physics 298, 210–226 (2002), arXiv:quant-ph/0003137 [quant-ph] .
  * Bravyi  _et al._ (2017) Sergey Bravyi, Jay M. Gambetta, Antonio Mezzacapo, and Kristan Temme, “Tapering off qubits to simulate fermionic Hamiltonians,” arXiv e-prints (2017), arXiv:1701.08213 [quant-ph] .
  * Hagberg  _et al._ (2008) Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” in  _Proceedings of the 7th Python in Science Conference_ , edited by Gaël Varoquaux, Travis Vaught, and Jarrod Millman (2008) pp. 11 – 15.
  * Dennis  _et al._ (2002) Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, “Topological quantum memory,” Journal of Mathematical Physics 43, 4452–4505 (2002), arXiv:quant-ph/0110143 [quant-ph] .
  * Kandala  _et al._ (2017b) Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta, “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” Nature 549, 242 EP – (2017b).
  * Izmaylov  _et al._ (2019) Artur F. Izmaylov, Tzu-Ching Yen, Robert A. Lang, and Vladyslav Verteletskyi, “Unitary partitioning approach to the measurement problem in the Variational Quantum Eigensolver method,” arXiv e-prints (2019), arXiv:1907.09040 [quant-ph] .
  * Izmaylov  _et al._ (2019) Artur F. Izmaylov, Tzu-Ching Yen, and Ilya G. Ryabinkin, “Revising the measurement process in the variational quantum eigensolver: is it possible to reduce the number of separately measured operators?” Chem. Sci. 10, 3746–3755 (2019).
  * Arlazarov  _et al._ (1970) V.L. Arlazarov, E.A. Dinic, M.A. Kronod, and I.A. Faradez, “On economical construction of the transitive closure of an oriented graph,” Soviet Mathematics Doklady , 1209–10 (1970).
  * Parrish  _et al._ (2017) Robert M. Parrish, Lori A. Burns, Daniel G. A. Smith, Andrew C. Simmonett, A. Eugene DePrince, Edward G. Hohenstein, Uğur Bozkaya, Alexander Yu. Sokolov, Roberto Di Remigio, Ryan M. Richard, Jérôme F. Gonthier, Andrew M. James, Harley R. McAlexander, Ashutosh Kumar, C. David Sherrill, _et al._ , “Psi4 1.1: An open-source electronic structure program emphasizing automation, advanced libraries, and interoperability,”  _Journal of Chemical Theory and Computation_ , Journal of Chemical Theory and Computation 13, 3185–3197 (2017).

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

Consider the example in Ref. McClean  _et al._ (2016); Gokhale  _et al._
(2019) where we consider measuring the energy, given by Hamiltonian

$H=-XX-YY+ZZ+IZ+ZI$ (32)

on the state $\ket{\psi}=\ket{01}$. The covariance matrix is

$C=\begin{pmatrix}1&1&0&\textbf{0}&\textbf{0}\\\
1&1&0&\textbf{0}&\textbf{0}\\\ 0&0&0&0&0\\\ \textbf{0}&\textbf{0}&0&0&0\\\
\textbf{0}&\textbf{0}&0&0&0\\\ \end{pmatrix}.$ (33)

The covariance between the non-commuting operators in the upper right and
lower left blocks is not defined. We have set them to equal zero for
convenience (highlighted in bold).

First, we consider collecting the Paulis into

$\\{-XX,-YY,ZZ\\},\ \\{IZ,ZI\\}.$ (34)

For these collections of Paulis, the coefficient vectors are

$\mathbf{a}=\begin{pmatrix}-1\\\ -1\\\ 1\\\ 0\\\ 0\\\ \end{pmatrix},\
\mathbf{c}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 1\\\ 1\\\ \end{pmatrix}.$ (35)

The number of measurements to achieve an accuracy of $\epsilon$ is

$\displaystyle M_{g}$
$\displaystyle=\frac{1}{\epsilon^{2}}\left(\sqrt{\mathbf{a}^{\dagger}C\mathbf{a}}+\sqrt{\mathbf{c}^{\dagger}C\mathbf{c}}\right)^{2}$
(36) $\displaystyle=\frac{1}{\epsilon^{2}}\left(\sqrt{4}+\sqrt{0}\right)^{2}$
$\displaystyle=\frac{4}{\epsilon^{2}}.$

Now, let us consider breaking up the first collection into

$\\{-XX\\},\ \\{-YY,ZZ\\}.$ (37)

In this case, the coefficient vectors are

$\mathbf{a}=\begin{pmatrix}-1\\\ 0\\\ 0\\\ 0\\\ 0\\\ \end{pmatrix},\
\mathbf{b}=\begin{pmatrix}0\\\ -1\\\ 1\\\ 0\\\ 0\\\ \end{pmatrix},\
\mathbf{c}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 1\\\ 1\\\ \end{pmatrix}.$ (38)

The number of measurements required to attain an accuracy $\epsilon$ is
therefore

$\begin{split}M_{g}&=\frac{1}{\epsilon^{2}}\left(\sqrt{\mathbf{a}^{\dagger}C\mathbf{a}}+\sqrt{\mathbf{b}^{\dagger}C\mathbf{b}}+\sqrt{\mathbf{c}^{\dagger}C\mathbf{c}}\right)^{2}\\\
&=\frac{1}{\epsilon^{2}}\left(\sqrt{1}+\sqrt{1}+\sqrt{0}\right)^{2}\\\
&=\frac{4}{\epsilon^{2}}.\end{split}$ (39)

Therefore, under the optimal measurement strategy it is not preferable to
break the $\\{-XX,-YY,ZZ\\}$ collection into $\\{-XX\\}$ and $\\{-YY,ZZ\\}$.
In this specific example we have equality because for $\alpha=-\beta$ we have
$\langle{\alpha\mathbf{a}+\beta\mathbf{b}},{\alpha\mathbf{a}+\beta\mathbf{b}}\rangle=0$.

##  Appendix B Derivation of $\hat{R}$ formula

######  Claim 2.

For $R$ as defined in Eq. (9), if all variances and covariances are replaced
with their expectation value over uniform spherical distribution, we obtain a
new metric, $\hat{R}$, given by

$\hat{R}=\left(\frac{\sum_{i=1}^{N}\sum_{j=1}^{N_{i}}|a_{ij}|}{\sum_{i=1}^{N}\sqrt{\sum_{j=1}^{N_{i}}a_{ij}^{2}}}\right)^{2}.$
(40)

###### Proof.

The variance of a single Pauli operator is

$\mathrm{Var}[P_{i}]\coloneqq 1-\expectationvalue{P_{i}}^{2}.$ (41)

The expectation of this variance for all $P_{i}\neq I$ is

$\begin{split}\mathbb{E}[\mathrm{Var}P_{i}]&=1-\mathbb{E}[\expectationvalue{P_{i}}^{2}]\\\
&=1-\int[\bra{\psi}P_{i}\ket{\psi}]^{2}\mathop{}\\!\mathrm{d}\psi\\\
&=1-\alpha_{n},\end{split}$ (42)

where $\alpha_{n}\coloneqq 1/(2^{n}+1)$, with $n$ the number of qubits, is
independent of $P_{i}$ (Watrous, 2018, Exercise 7.3). Trivially,
$\mathrm{Var}[I]=0$. In addition, it was shown in Ref. Gokhale  _et al._
(2019) that

$\mathbb{E}[\text{Cov}[P_{i},P_{j}]]=0,$ (43)

for all $P_{i}\neq P_{j}$. Substitution of these results yields Eq. (40). ∎

##  Appendix C Binary representation

The Pauli subset $\mathcal{P}_{n}$ on $n$-qubits is a collection of $4^{n+1}$
elements defined by

$\displaystyle\mathcal{P}_{n}=\\{$ $\displaystyle i^{k}\
\sigma_{1}\otimes\dots\otimes\sigma_{n}\ |\ \sigma_{i}\in\\{I,X,Y,Z\\},$
$\displaystyle\ k\in\\{0,1,2,3\\}\\}.$ (44)

The binary representation, first introduced by Calderbank, Rains, Shor, and
Sloane Calderbank  _et al._ (1997), is a representation of $\mathcal{P}_{n}$
as binary vectors. In this representation, Paulis differing only in phase
$i^{k}$ are represented in the same way.

Single-qubit Paulis are represented by 2-dimensional binary vectors, so that

$\displaystyle\sigma_{00}\coloneqq\ $ $\displaystyle I$
$\displaystyle\mapsto(0,0),$ (45) $\displaystyle\sigma_{01}\coloneqq\ $
$\displaystyle X$ $\displaystyle\mapsto(0,1),$
$\displaystyle\sigma_{10}\coloneqq\ $ $\displaystyle Z$
$\displaystyle\mapsto(1,0),$ $\displaystyle\sigma_{11}\coloneqq\ $
$\displaystyle Y$ $\displaystyle\mapsto(1,1).$

An $n$-qubit Pauli

$\sigma_{u_{1}v_{1}}\otimes\dots\otimes\sigma_{u_{n}v_{n}}$ (46)

is then represented by the $2n$-dimensional binary vector

$(u_{1},\dots,u_{n},v_{1},\dots,v_{n}).$ (47)

In this representation, two $n$-qubit Paulis with binary vectors $a$ and $b$
commute if and only if

$a^{T}J_{2n}b=0,$ (48)

where $J_{2n}$ denotes the $2n\times 2n$ matrix

$J_{2n}\coloneqq\begin{pmatrix}0&I_{n}\\\ I_{n}&0\end{pmatrix}.$ (49)

Given a set $\mathcal{S}$ of $m$ $n$-qubit Paulis, we can write down a
corresponding $2n\times m$ binary matrix $S$ where each column represents a
Pauli. Then, from Eq. (48), we deduce that all Paulis in $\mathcal{S}$
mutually commute if and only if

$S^{T}J_{2n}S=0_{m},$ (50)

which recovers Eq. (25) in the main text. We say that the set $\mathcal{S}$ of
Paulis is independent if the matrix $S$ has rank $m$.

We shall often find it helpful to write $S$ in terms of its upper half
$S^{(Z)}$ and lower half $S^{(X)}$, separated by a horizontal line for visual-
aid, i.e.,

$S=\begin{pmatrix}S^{(Z)}\\\ \hline\cr S^{(X)}\end{pmatrix}.$ (51)

The conjugation action of quantum gates on $\mathcal{S}$ can be represented as
transformations to the matrix $S$. For example, we document the
transformations on $S$ that represent four common quantum gates. In the
following, addition is $\mathrm{mod}\ 2$ and $p$ ranges over all columns
$\\{1,\dots,m\\}$.

  * $\blacksquare$

CZ on qubits $i$ and $j$:
$S_{ip}\leftarrow S_{ip}+S_{j+n,p}$,
$S_{jp}\leftarrow S_{jp}+S_{i+n,p}$.

  * $\blacksquare$

CNOT on control-qubit $i$ and target-qubit $j$:
$S_{ip}\leftarrow S_{ip}+S_{jp}$,
$S_{j+n,p}\leftarrow S_{j+n,p}+S_{i+n,p}$.

  * $\blacksquare$

Hadamard (H) on qubit $i$:
$S_{ip}\leftrightarrow S_{i+n,p}$.

  * $\blacksquare$

Phase (P) on qubit $i$:
$S_{ip}\leftarrow S_{ip}+S_{i+n,p}$.

These rules can be directly verified by conjugating $X_{i},\ X_{j},\ Z_{i},\
Z_{j}$ by the listed gates. They are also reproduced in Sec. III of the main
text.

##  Appendix D CZ-construction example

We walk through our CZ-construction for a specific example. In this example,
we would like to obtain measurements simultaneously of a collection
$\mathcal{S}^{\prime}_{\text{start}}$ of six four-qubit Paulis given by

$\displaystyle P_{1}$ $\displaystyle=Z_{1}Z_{2}Z_{3}Z_{4},$ (52)
$\displaystyle P_{2}$ $\displaystyle=X_{1}X_{2}Y_{3}Y_{4},$ $\displaystyle
P_{3}$ $\displaystyle=Y_{1}Y_{2}X_{3}X_{4},$ $\displaystyle P_{4}$
$\displaystyle=Y_{2}X_{3},$ $\displaystyle P_{5}$ $\displaystyle=Y_{1}X_{4},$
$\displaystyle P_{6}$ $\displaystyle=X_{1}Z_{2}Z_{3}Y_{4}.$

We can represent these Paulis in a matrix $S_{\text{start}}^{\prime}$ with

$S_{\text{start}}^{\prime}=\begin{pmatrix}1&0&1&0&1&0\\\ 1&0&1&1&0&1\\\
1&1&0&0&0&1\\\ 1&1&0&0&0&1\\\ \hline\cr 0&1&1&0&1&1\\\ 0&1&1&1&0&0\\\
0&1&1&1&0&0\\\ 0&1&1&0&1&1\end{pmatrix}.$ (53)

By Gaussian elimination, we find the reduced row echelon form of
$S_{\text{start}}^{\prime}$ to be

$\begin{pmatrix}1&0&1&0&1&0\\\ 0&1&1&0&1&1\\\ 0&0&0&1&1&1\\\ 0&0&0&0&0&0\\\
\hline\cr 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\
\end{pmatrix}.$ (54)

The pivot columns are numbers 1, 2 and 4 which tells us that $P_{1}$, $P_{2}$
and $P_{4}$ are the three independent Paulis from which the remaining Paulis
in $\mathcal{S}^{\prime}_{\text{start}}$ can be constructed. Therefore, we can
write $S_{\text{start}}^{\prime}=S_{\text{start}}R_{0}^{-1}$, where

$S_{\text{start}}\coloneqq\begin{pmatrix}1&0&0\\\ 1&0&1\\\ 1&1&0\\\ 1&1&0\\\
\hline\cr 0&1&0\\\ 0&1&1\\\ 0&1&1\\\ 0&1&0\end{pmatrix},\
R_{0}^{-1}\coloneqq\begin{pmatrix}1&0&1&0&1&0\\\ 0&1&1&0&1&1\\\
0&0&0&1&1&1\end{pmatrix}.$ (55)

Note that the inverse on $R_{0}^{-1}$ is purely notational. Now, the lower
half $S_{\text{start}}^{(X)}$ of $S_{\text{start}}$ has column echelon form

$S_{\text{start}}^{(X)}=\begin{pmatrix}1&0&0\\\ 1&1&0\\\ 1&1&0\\\
1&0&0\end{pmatrix},$ (56)

and so the first two rows are pivot rows. In order to give the lower half of
$S_{\text{start}}$ a rank of $k=3$, we therefore apply a HADAMARD to the rows
corresponding to qubits 3 and 4 so that

$S_{1}\coloneqq Q_{1}S_{\text{start}}=\begin{pmatrix}1&0&0\\\ 1&0&1\\\
0&1&1\\\ 0&1&0\\\ \hline\cr 0&1&0\\\ 0&1&1\\\ 1&1&0\\\ 1&1&0\end{pmatrix},$
(57)

where

$Q_{1}\coloneqq\begin{pmatrix}[cccc|cccc]1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\\\ \hline\cr 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ \end{pmatrix}.$ (58)

The lower half of $S_{1}$ now has rank 3, and performing Gaussian elimination
on it, we find

$S_{2}\coloneqq Q_{1}S_{\text{start}}R_{1}=\begin{pmatrix}1&0&1\\\ 0&1&1\\\
0&1&0\\\ 1&0&0\\\ \hline\cr 1&0&0\\\ 0&1&0\\\ 0&0&1\\\ 0&0&1\end{pmatrix},$
(59)

where

$R_{1}=\begin{pmatrix}0&1&0\\\ 0&1&1\\\ 1&1&0\\\
\end{pmatrix}^{-1}=\begin{pmatrix}1&0&1\\\ 1&0&0\\\ 1&1&0\end{pmatrix}.$ (60)

We now extend $S_{2}$ to a rank $n=4$ matrix by adding a column that
corresponds to a fourth Pauli $P_{ext}$. In the main text, this is the crucial
basis extension step from $S_{2}\rightarrow S_{3}$ which might have seemed
fortuitous. In fact, the extension was systematically obtained as follows.

To make our reasoning clearer, let us represent $S_{2}$ alternatively by the
matrix

$P(S_{2})\coloneqq\begin{pmatrix}Y&I&I&Z\\\ I&Y&Z&I\\\ Z&Z&X&X\end{pmatrix},$
(61)

where each row corresponds to a Pauli operator given by a column of $S_{2}$.
Looking at the form of $P(S_{2})$, we see that we can place $X$ in the $4$th
qubit position of $P_{ext}$ (and nowhere else) to ensure $P_{ext}$ is
independent of the other Paulis. Then we observe that the left 3-by-3 sub-
matrix of $P(S_{2})$ has $X/Y$ on the diagonal and $I/Z$ everywhere else. This
means we can place $I/Z$ in the other qubit positions of $P_{ext}$ depending
on whether the $X$ in its $4$th qubit position commutes with the $4$th
position terms of the other Paulis.

By this prescription, we find $P_{ext}=Z_{1}I_{2}I_{3}X_{4}$. Therefore
$S_{2}$ is extended to

$S_{3}\coloneqq\begin{pmatrix}1&0&1&1\\\ 0&1&1&0\\\ 0&1&0&0\\\ 1&0&0&0\\\
\hline\cr 1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&1&1\end{pmatrix}.$ (62)

and

$Q_{1}S_{\text{start}}R_{1}=S_{3}R_{2}^{-1},$ (63)

where

$R_{2}^{-1}\coloneqq\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\\\
0&0&0\end{pmatrix}.$ (64)

Note that the inverse on $R_{2}^{-1}$ is also purely notational. The lower
half of $S_{3}$ is full-rank and so we can take its inverse to find

$R_{3}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&1&1\end{pmatrix}^{-1}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&1&1\end{pmatrix}$ (65)

and

$S_{3}R_{3}=\begin{pmatrix}1&0&0&1\\\ 0&1&1&0\\\ 0&1&0&0\\\ 1&0&0&0\\\
\hline\cr 1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{pmatrix}.$ (66)

Finally, we apply PHASE to qubits 1 and 2 so that

$S_{4}=Q_{2}S_{3}R_{3}=\begin{pmatrix}0&0&0&1\\\ 0&0&1&0\\\ 0&1&0&0\\\
1&0&0&0\\\ \hline\cr 1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{pmatrix},$
(67)

where

$Q_{2}=\begin{pmatrix}[cccc|cccc]1&0&0&0&1&0&0&0\\\ 0&1&0&0&0&1&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ \hline\cr 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\end{pmatrix}.$ (68)

$S_{4}$ is of the form of a graph state and represents the following Paulis:

$\displaystyle\tilde{P}_{1}$ $\displaystyle=X_{1}\,I_{2}\,I_{3}\,Z_{4},$ (69)
$\displaystyle\tilde{P}_{2}$ $\displaystyle=I_{1}\,X_{2}\,Z_{3}\,I_{4},$
$\displaystyle\tilde{P}_{3}$ $\displaystyle=I_{1}\,Z_{2}\,X_{3}\,I_{4},$
$\displaystyle\tilde{P}_{4}$ $\displaystyle=Z_{1}\,I_{2}\,I_{3}\,X_{4}.$

We now have

$S_{\text{start}}^{\prime}=Q^{-1}S_{4}R^{-1},$ (70)

where

$Q^{-1}\coloneqq
Q_{1}^{-1}Q_{2}^{-1}=\begin{pmatrix}[cccc|cccc]1&0&0&0&1&0&0&0\\\
0&1&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\\\ \hline\cr
0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&0\\\ 0&0&1&0&0&0&0&0\\\
0&0&0&1&0&0&0&0\end{pmatrix}$ (71)

and

$R^{-1}\coloneqq
R_{3}^{-1}R_{2}^{-1}R_{1}^{-1}R_{0}^{-1}=\begin{pmatrix}0&1&1&0&1&1\\\
0&1&1&1&0&0\\\ 1&1&0&0&0&1\\\ 1&1&0&0&0&1\end{pmatrix}.$ (72)

The rotation circuit is shown in Fig. 4. Using $Q^{-1}$, $S_{4}$ and $R^{-1}$,
we can work out that the phases for the six original operators are
$\left(\begin{smallmatrix}+1&+1&+1&-1&-1&-1\end{smallmatrix}\right)$.
Therefore, we can construct measurements of the original Pauli strings as
follows:

  * $\blacksquare$

$P_{1}$ from product of measurements of qubits 3 and 4,

  * $\blacksquare$

$P_{2}$ from product of measurements of qubits 1 to 4,

  * $\blacksquare$

$P_{3}$ from product of measurements of qubits 1 and 2,

  * $\blacksquare$

$P_{4}$ from the negative of measurement of qubit 2,

  * $\blacksquare$

$P_{5}$ from the negative of measurement of qubit 1,

  * $\blacksquare$

$P_{6}$ from the negative product of measurements of qubits 1, 3 and 4.

@C=1.5em @R=1.4em q1 & S 3 H
q2 S 1 H
q3 H H
q4 H H

Figure 4: The rotation circuit $U$ for the CZ-construction walk-through
example.

##  Appendix E Proof of $O(kn/\log k)$

We prove the following Claim 3 via arguments of Patel, Markov, and Hayes Patel
_et al._ (2008). As acknowledged in Ref. Patel  _et al._ (2008), these
arguments originate from the “Method of Four Russians” Arlazarov  _et al._
(1970). Note that row operations correspond to CNOT gates, as explained in
detail in Ref. Patel  _et al._ (2008).

######  Claim 3.

Let $M$ be a $n\times n$ matrix with block form

$\begin{pmatrix}I_{k}&A\\\ 0&I_{n-k}\end{pmatrix},$ (73)

where $A$ is any $k\times(n-k)$ matrix. Then $O(kn/\log k)$ row operations
suffice to reduce $M$ to identity $I_{n}$.

###### Proof.

Let $m$ be a constant we later choose. Partition $A$ into $l\coloneqq(n-k)/m$
consecutive column-blocks $A_{i}$, each containing $m$ columns.

Start at $A_{1}$ and eliminate any duplicate rows using at most $k$ row
operations. There then remain at most $2^{m}$ unique rows in $A_{1}$ which can
be eliminated by at most $m2^{m-1}$ row operations that add rows from
$I_{n-k}$. $A_{1}$ is now zero.

For each of $A_{2},\dots,A_{l}$ perform the same operation as was done to
$A_{1}$. $M$ then becomes

$\begin{pmatrix}B&0\\\ 0&I_{n-k}\end{pmatrix},$ (74)

where $B$ is some $k\times k$ matrix that must be invertible. $B$ can then be
row-reduced to $I_{k}$ using $O(k^{2}/\log k)$ by the result of Ref. Patel
_et al._ (2008).

The total number $N$ of row operations is therefore

$N=\left(k+m2^{m-1}\right)\ \frac{n-k}{m}+O\left(\frac{k^{2}}{\log k}\right).$
(75)

Choosing $m=\alpha\log k$, we find

$N=\frac{k(n-k)}{\alpha\log
k}+\frac{k^{\alpha}(n-k)}{2}+O\left(\frac{k^{2}}{\log k}\right),$ (76)

which is $O(kn/\log k)$ provided $\alpha<1$. ∎

##  Appendix F Full numerical results

In this Appendix, we present the results of the numerical simulations
discussed in the main text.

Molecule |  $n$ qubits |  $t$ Paulis |  | Arrangement |  |  Ratios $R$, $\hat{R}$ |  |  Rotation Circuit $2q$-size
---|---|---|---|---|---|---|---|---
|  |  |  |  $N$ |  $\overline{m_{i}}$ |  $\overline{k_{i}}$ |  |  $R$ min |  $R$ mean |  $R$ max |  $\hat{R}$ |  |  max theory |  max true |  mean
H2 |  2 |  4 |  |  2 |  2.00 |  1.50 |  |  1.09 |  1.93 |  4.60 |  1.76 |  |  0 |  0 |  0
H${}_{3}^{+}$ |  4 |  59 |  |  10 |  5.90 |  3.50 |  |  3.76 |  11.92 |  33.04 |  10.25 |  |  6 |  3 |  0.80
LiH |  10 |  630 |  |  41 |  15.37 |  6.85 |  |  19.60 |  24.91 |  34.74 |  23.97 |  |  45 |  18 |  5.29
OH- |  10 |  630 |  |  38 |  16.58 |  7.29 |  |  6.32 |  8.90 |  12.86 |  8.51 |  |  45 |  17 |  5.63
HF |  10 |  630 |  |  39 |  16.15 |  6.97 |  |  6.07 |  8.57 |  12.27 |  8.21 |  |  45 |  16 |  5.74
H2O |  12 |  1085 |  |  51 |  21.27 |  9.04 |  |  7.68 |  11.27 |  16.96 |  10.67 |  |  66 |  26 |  7.37
BH3 |  14 |  1584 |  |  66 |  24.00 |  10.36 |  |  17.21 |  20.93 |  32.13 |  20.05 |  |  91 |  26 |  9.56
NH3 |  14 |  3608 |  |  118 |  30.58 |  11.34 |  |  12.65 |  15.96 |  26.93 |  15.31 |  |  91 |  28 |  10.26
CH4 |  16 |  3887 |  |  123 |  31.60 |  13.39 |  |  16.96 |  21.63 |  29.33 |  20.27 |  |  120 |  45 |  16.75
O2 |  18 |  2238 |  |  67 |  33.40 |  13.48 |  |  - |  - |  - |  20.23 |  |  153 |  44 |  21.57
N2 |  18 |  2950 |  |  78 |  37.82 |  13.91 |  |  - |  - |  - |  22.10 |  |  153 |  53 |  20.42
CO |  18 |  4426 |  |  128 |  34.58 |  13.48 |  |  - |  - |  - |  21.31 |  |  153 |  50 |  20.23
HCl |  18 |  4538 |  |  123 |  36.89 |  13.87 |  |  - |  - |  - |  10.36 |  |  153 |  49 |  20.35
NaH |  18 |  5850 |  |  135 |  43.33 |  14.73 |  |  - |  - |  - |  12.90 |  |  153 |  45 |  21.44
H2S |  20 |  6277 |  |  147 |  42.70 |  16.06 |  |  - |  - |  - |  11.60 |  |  190 |  58 |  25.98
PH3 |  22 |  19746 |  |  304 |  64.95 |  18.77 |  |  - |  - |  - |  13.05 |  |  231 |  67 |  28.02
SiH4 |  24 |  18713 |  |  304 |  61.56 |  20.98 |  |  - |  - |  - |  13.94 |  |  276 |  77 |  36.03
NaF |  26 |  16538 |  |  287 |  57.62 |  20.44 |  |  - |  - |  - |  23.36 |  |  325 |  90 |  42.28
LiCl |  26 |  17044 |  |  292 |  58.37 |  20.46 |  |  - |  - |  - |  12.22 |  |  325 |  89 |  39.42
KH |  26 |  24290 |  |  325 |  74.74 |  22.30 |  |  - |  - |  - |  12.87 |  |  325 |  115 |  45.18
CO2 |  28 |  11429 |  |  216 |  52.91 |  21.02 |  |  - |  - |  - |  38.47 |  |  378 |  104 |  44.51
F2O |  28 |  20541 |  |  317 |  64.80 |  22.83 |  |  - |  - |  - |  36.82 |  |  378 |  105 |  46.12
NO2 |  28 |  20549 |  |  311 |  66.07 |  22.93 |  |  - |  - |  - |  40.69 |  |  378 |  109 |  46.25
Cl2 |  34 |  34334 |  |  378 |  90.83 |  28.09 |  |  - |  - |  - |  26.58 |  |  561 |  156 |  73.24
NaCl |  34 |  42826 |  |  498 |  86.00 |  28.54 |  |  - |  - |  - |  20.46 |  |  561 |  166 |  74.34
SF2 |  36 |  56025 |  |  567 |  98.81 |  31.96 |  |  - |  - |  - |  30.65 |  |  630 |  180 |  78.67
HBr |  36 |  62589 |  |  602 |  103.97 |  31.88 |  |  - |  - |  - |  16.03 |  |  630 |  154 |  78.98
SO2 |  36 |  75315 |  |  691 |  108.99 |  33.21 |  |  - |  - |  - |  29.75 |  |  630 |  187 |  66.90
NO${}_{3}^{-}$ |  38 |  61132 |  |  622 |  92.28 |  31.23 |  |  - |  - |  - |  65.01 |  |  703 |  182 |  86.40
H2Se |  38 |  69684 |  |  631 |  110.43 |  33.91 |  |  - |  - |  - |  16.49 |  |  703 |  196 |  86.88
Table 4: The full set of results of the numerical simulations discussed in the
main text. The molecular geometry is approximately that of the equilibrium
configuration. A number of results related to the collecting of Hamiltonian
terms, how the arrangement reduces the number of measurements required, and
the number of two-qubit gates in the resulting rotation circuits are shown. We
used OpenFermion McClean  _et al._ (2017) and Psi4 Parrish  _et al._ (2017) to
obtain Hamiltonians in the STO-3G basis and under the symmetry conserving
Bravyi-Kitaev transformation Bravyi and Kitaev (2002); Bravyi  _et al._
(2017). Using our collecting method, SORTED INSERTION, the number of
collections, $N$, the average number of terms per collection,
$\overline{m_{i}}$, and the average rank of the collections,
$\overline{k_{i}}$ are shown, for molecules with $n$ qubits and $t$ Pauli
operators, excluding the identity, in the Hamiltonian sum. For the smallest
nine molecules, we calculated the resulting ratio $R$, as given in Eq. (9),
for 100 randomly selected trial states, prepared by choosing random sets of
parameters for a hardware efficient ansatz preparation circuit of depth 1. For
each molecule, we show the mean, minimum and maximum values of $R$ obtained
from the 100 runs. We also show the value of $\hat{R}$, given by Eq. (19)
obtained, which is close to the mean value of $R$ where this has been
calculated. A key result of interest is the maximum number of two-qubit gates
required to obtain a measurement of all the operators in a given Hamiltonian.
We show the theoretical maximum, given by the largest value of
$kn-\frac{1}{2}k(k+1)$ for any collection, and the true largest value for any
collection. The ratio of these two numbers is shown in Fig. 3(c). We also show
the mean number of two-qubit gates required in a rotation circuit, averaged
across all collections for a given molecule.