††thanks: These two authors contributed equally ††thanks: These two authors
contributed equally

# Overlapped grouping measurement: A unified framework for measuring quantum
states

Bujiao Wu  Center on Frontiers of Computing Studies, Peking University,
Beijing 100871, China  School of Computer Science, Peking University, Beijing
100871, China  Jinzhao Sun  Clarendon Laboratory, University of Oxford, Parks
Road, Oxford OX1 3PU, United Kingdom  Center on Frontiers of Computing
Studies, Peking University, Beijing 100871, China  Qi Huang  School of
Physics, Peking University, Beijing 100871, China  Center on Frontiers of
Computing Studies, Peking University, Beijing 100871, China  Xiao Yuan
<EMAIL_ADDRESS>Center on Frontiers of Computing Studies, Peking
University, Beijing 100871, China  School of Computer Science, Peking
University, Beijing 100871, China

(January 11th 2023)

###### Abstract

Quantum algorithms designed for realistic quantum many-body systems, such as
chemistry and materials, usually require a large number of measurements of the
Hamiltonian. Exploiting different ideas, such as importance sampling,
observable compatibility, or classical shadows of quantum states, different
advanced measurement schemes have been proposed to greatly reduce the large
measurement cost. Yet, the underline cost reduction mechanisms seem distinct
from each other, and how to systematically find the optimal scheme remains a
critical challenge. Here, we address this challenge by proposing a unified
framework of quantum measurements, incorporating advanced measurement methods
as special cases. Our framework allows us to introduce a general scheme —
overlapped grouping measurement, which simultaneously exploits the advantages
of most existing methods. An intuitive understanding of the scheme is to
partition the measurements into overlapped groups with each one consisting of
compatible measurements. We provide explicit grouping strategies and
numerically verify its performance for different molecular Hamiltonians with
up to 16 qubits. Our numerical result shows significant improvements over
existing schemes. Our work paves the way for efficient quantum measurement and
fast quantum processing with current and near-term quantum devices.

##  1 Introduction

How to efficiently measure a quantum state is a fundamental problem with great
practical relevance. Algorithms tailored for noisy intermediate-scale quantum
(NISQ) devices [53, 4, 20, 9] usually require measuring complicated multi-
qubit observables, such as the Hamiltonian [52, 50, 45, 39, 47, 40, 66, 41,
42, 69, 19, 29, 78, 38, 25, 13, 28, 68, 73, 72, 21, 48, 12, 22, 14, 5, 32, 43,
7, 60]. When decomposing the Hamiltonian into local measurable observables, it
may contain a large number of terms. For example, an electronic Hamiltonian
with Coulomb interaction generally has $\mathcal{O}(M^{4})$ terms when
represented with $M$ fermionic modes [43, 7, 3, 54]. The number of terms could
already become quite large when we consider the classical limit with a large
$M$, where the naive strategy of equally measuring all the observables
requires a prohibitively long time. We also need error mitigation techniques
to suppress calculation errors, which again introduces a large sample overhead
with increasing problem size [39, 18, 61, 45, 57, 6, 59, 17, 51, 46, 23].
Therefore, an efficient quantum measurement scheme is crucial for
demonstrating a clear and robust quantum advantage with NISQ devices.

Without introducing additional entangling circuits, three types of advanced
measurement schemes have been proposed to reduce the measurement cost by
exploiting different features of the to-be-measured observables [38, 65, 31,
67, 27, 33, 62, 11, 63, 15, 16]. First, observables may have different weight
coefficients and we can exploit importance sampling to distribute more
measurements to observables with large weights [67, 44]. Next, observables may
be compatible with some other ones, in the sense that they could be
simultaneously measured with the same measurement basis. We can thus group
observables into sets of compatible observables using fewer measurements [38,
65, 64, 35, 76, 28, 50, 16]. Another notable but conceptually different scheme
considers classical shadows of quantum states using uniformly random local
measurements, which are extensively investigated in theoretical and
experimental works [31, 1, 58, 10, 77, 2, 74]. By properly post-processing the
classical measurement outcomes, one can simultaneously obtain the expectation
values of any observables. The cost of the original uniform classical shadow
scheme [31] scales exponentially to the number of qubits that the observable
non-trivially acts on, and later LBCS and derandomized CS methods were further
proposed to reduce the measurement cost [27, 33]. While the optimized
classical shadow method outperforms the other two types of methods in
numerical experiments, how they are related, and how to find an optimized
method that exploits the advantages of all these advanced measurement schemes
remain open.

Here, we address these problems in quantum state measurement. We first
introduce a unified framework that integrates the advantages of the typically
advanced measurement schemes in Sec. 2. In particular, we show how to
understand the classical shadow method as a generalized observable grouping
method. We next introduce the overlapped grouping measurement scheme that
simultaneously exploits the features of the importance sampling, observable
compatibility, and classical shadows in Sec. 3. While finding the optimal
overlapped groups could be computationally challenging, we provide explicit
algorithms that output an optimized measurement scheme in Sec. 4. We then
numerically benchmark our method in Sec. 5 by comparing it to existing
advanced works [65, 31, 27, 33, 38] in estimating expectations of molecular
Hamiltonians, as a subroutine in most quantum algorithms. Our numerical result
shows prominent improvements over all the others. The proposed method is
immediately applicable to currently available and near-future quantum
computing experiments. In Sec. 6, we conclude this work and suggest some
interesting future investigations.

##  2 A unified framework

Now we introduce a framework for measuring hermitian objective observables
$\bm{\mathrm{O}}:=\sum_{j}\alpha_{j}Q^{(j)}$ on a multi-qubit quantum state
$\rho$. Here $Q^{(j)}\in\left\\{I,X,Y,Z\right\\}^{n}$ are tensor products of
single-qubit Pauli operators, and we also call $Q^{(j)}$ local Pauli strings.
Naively, we could measure each term $Q^{(j)}$ to obtain the expectation value,
$\tr(\rho Q^{(j)})$, and hence the expectation value of the objective
observable, $\tr(\rho\bm{\mathrm{O}})$, whereas more efficient schemes may be
found by exploiting the properties of the objective observables.

We first consider observable compatibility. Let $Q$ and $R$ be tensor products
of single-qubit Pauli operators $Q=\bigotimes_{i=1}^{n}Q_{i}$ and
$R=\bigotimes_{i=1}^{n}R_{i}$ with $Q_{i},R_{i}\in\left\\{I,X,Y,Z\right\\}$.
We let $Q\triangleright R$ denote $Q_{i}=R_{i}$ or $Q_{i}=I$ for any $i$,
indicating that measuring observable $R$ equivalently measures $Q$. We say
that $Q$ is _compatible_ with $R$ when $Q_{i}\triangleright R_{i}$ or
$R_{i}\triangleright Q_{i}$ for any $i$, meaning that $Q$ and $R$ can be
simultaneously measured. In an extreme case, when each operator $Q^{(j)}$ is
compatible with the same Pauli basis $P$, we can simultaneously obtain all the
expectation value $\tr(\rho Q^{(j)})$ by measuring one basis $P$.
Nevertheless, a practical case generally consists of observables that are
compatible with only a subset of other observables. Then we need to find a set
of Pauli bases $\\{P\\}$ such that each observable $Q^{(j)}$ is compatible
with at least one Pauli basis. After choosing the Pauli bases $\\{P\\}$, the
next question is how to distribute the measurement samples to each basis $P$,
which corresponds to the idea of importance sampling. Without loss of
generality, we select each basis $P$ randomly with the probability
$\mathcal{K}(P)$.

Now, suppose that we have determined $\\{(P,\mathcal{K}(P))\\}$, and we can
define an estimator

$\displaystyle\hat{v}=\sum_{j}\alpha_{j}f(P,Q^{(j)},\mathcal{K})\mu\left(P,\mathrm{supp}(Q^{(j)})\right),$
(1)

where $\mathrm{supp}(Q):=\left\\{i|Q_{i}\neq I\right\\}$ is the support of
$Q$,
$\mu(P,\mathrm{supp}(Q^{(j)})):=\prod_{i\in\mathrm{supp}(Q^{(j)})}\mu(P_{i})$,
and $\mu(P_{i})$ is the single-shot outcome by measuring the $i$th qubit with
single-qubit Pauli operator $P_{i}$. Here,
$\mu\left(P,\mathrm{supp}\left(Q^{(j)}\right)\right)$ effectively gives
measurement results of $Q^{(j)}$ obtained from measuring with the basis $P$.
$f(P,Q^{(j)},\mathcal{K})$ is associated with the probability distribution
$\mathcal{K}$ of measurement $P$ and $Q^{(j)}$, which is designed to guarantee
that $\hat{v}$ is an unbiased estimation of
$\tr\left(\rho\bm{\mathrm{O}}\right)$. It depends on the measurement scheme,
and we will show its explicit form for different schemes later. Assuming that
$\mathbb{E}\left[f\left(P,Q^{(j)},\mathcal{K}\right)\right]=1$, we will show
that $\mathbb{E}\left[\hat{v}\right]=\tr\left(\rho\bm{\mathrm{O}}\right)$,
i.e., $\hat{v}$ is an unbiased estimator of the observable expectation
$\tr\left(\rho\bm{\mathrm{O}}\right)$ in the following proposition.

######  Proposition 1.

Let $\bm{\mathrm{O}}=\sum_{j}\alpha_{j}Q^{(j)}$ where $Q^{(j)}$ are local
Pauli strings, and $\hat{v}$ be defined as in Eq. (1) with
$\mathbb{E}\left[f\left(P,Q^{(j)},\mathcal{K}\right)\right]=1$, then $\hat{v}$
is an unbiased estimation of $\tr\left(\rho\bm{\mathrm{O}}\right)$.

###### Proof.

By the definition of $\hat{v}$, we have

$\displaystyle\begin{aligned}
\mathbb{E}\left[\hat{v}\right]&=\mathbb{E}\left[\sum_{j}\alpha_{j}f(P,Q^{(j)},\mathcal{K})\mu\left(P,\mathrm{supp}(Q^{(j)})\right)\right]\\\
&=\sum_{j}\alpha_{j}\mathbb{E}_{P}\left[f\left(P,Q^{(j)},\mathcal{K}\right)\right]\mathbb{E}_{\mu|P}\left[\mu\left(P,\mathrm{supp}\left(Q^{(j)}\right)\right)\right]\\\
&=\sum_{j}\alpha_{j}\tr\left(\rho
Q^{(j)}\right)=\tr\left(\rho\bm{\mathrm{O}}\right)\end{aligned}$ (2)

where the first equation holds because of the conditional expectation formula.
∎

Figure 1:  An illustrative example of the (a) $l_{1}$-sampling, (b) LDF-
grouping, (c) LBCS, and (d) OGM methods. A vertex represents an observable,
and an edge is connected between two vertices when they are compatible. The
light blue (yellow) set represents a Pauli measurement basis. Different
measurement schemes correspond to different light blue (yellow) sets with
different probabilities. Here we consider an example of measuring
$\bm{\mathrm{O}}=X_{1}X_{2}/4+X_{2}X_{3}/4+X_{2}Z_{3}/12+Z_{2}Z_{3}/4+Z_{1}Z_{2}/12+X_{1}Z_{3}/12$
with a 3-qubit state $\ket{\psi}=\ket{000}/\sqrt{2}+\ket{111}/\sqrt{2}$. The
variance for importance sampling, LDF-grouping, LBCS and OGM algorithms of
this instance are $0.90,0.56,0.74,0.50$, respectively. (e) Schematic diagram
of the unified framework. We first determine the set of Pauli basis $\\{P\\}$
and the probability distributions $\\{\mathcal{K}(P)\\}$ using Algorithm 1. We
next measure the quantum state $\rho$ with a different Pauli basis drawn from
the distribution $\mathcal{K}$ and post-process the measurement outcomes to
obtain the estimation of $\tr(\rho\bm{\mathrm{O}})$.

In the following, we give explicit expressions of $f(\cdot,\cdot,\cdot)$ for
different existing measurement schemes.

(1) _Importance sampling._ The strategy of the importance sampling measures
each observable $Q^{(j)}$ independently with the basis $P^{(j)}=Q^{(j)}$, and
the associated probability distribution is determined by the weight of the
observable as
$\mathcal{K}(P^{(j)})=|\alpha_{j}|/\left\|\bm{\alpha}\right\|_{1}$ with
$\left\|\bm{\alpha}\right\|_{1}=\sum_{j=1}^{m}\absolutevalue{\alpha_{j}}$
being the $l_{1}$ norm of
$\bm{\alpha}=\left(\alpha_{1},\ldots,\alpha_{m}\right)$, and $f$ defined as

$\displaystyle
f_{l_{1}}({P,Q^{(j)},\mathcal{K}})=\mathcal{K}(P)^{-1}\delta_{P,Q^{(j)}}.$ (3)

It is easy to check that
$\mathbb{E}_{P}\left[f_{l_{1}}\left(P,Q^{(j)},\mathcal{K}\right)\right]=1$.
This method is also referred to as $l_{1}$-sampling, since the sampling
probability is associated with the $l_{1}$-norm of $Q^{(j)}$. The
$l_{1}$-sampling needs
$\mathcal{O}({{\left\|\bm{\alpha}\right\|_{1}^{2}}/{\varepsilon^{2}}})$ copies
of quantum states $\rho$ to approximate the expectation of $\bm{\mathrm{O}}$
with an additive error $\varepsilon$. The number of copies is obtained from
Chebyshev inequality, and we leave details of error analysis in Appendix A.

(2) _Grouping._ The grouping method exploits observable compatibility by
partitioning the observables $\mathcal{O}=\\{Q^{(j)}\\}$ into several non-
overlapped sets $\mathcal{S}=\left\\{\bm{e}_{1},\ldots,\bm{e}_{s}\right\\}$
such that $\bm{e}_{j}\cap\bm{e}_{j^{\prime}}=\varnothing\leavevmode\nobreak\
(\forall j\neq j^{\prime}$), $\cup_{j}\bm{e}_{j}=\mathcal{O}$. It also
requires that observables in the same set are compatible with each other, such
that there exists a measurement basis $P^{(j)}$ satisfying $Q\triangleright
P^{(j)},\forall Q\in\bm{e}_{j}$. Let $\mathcal{K}(P^{(j)})$ be the probability
that $P^{(j)}$ is selected. It could be optimized using the importance
sampling by setting $\mathcal{K}(P^{(j)})$ proportional to the total weight of
the observables in the set $P^{(j)}$ as
$\mathcal{K}(P^{(j)})=\left\|\bm{e}_{j}\right\|_{1}/\left\|\bm{\alpha}\right\|_{1}$.
Here the weight of a set $\bm{e}_{j}$ is defined as the $l_{1}$-norm of the
weights of the observables in this set as
$\left\|\bm{e}_{j}\right\|_{1}=\sum_{Q^{(k)}\in\bm{e}_{j}}\absolutevalue{\alpha_{k}}$.
The function $f$ for the optimized grouping method is

$f_{\rm
Group}\left(P^{(j)},Q^{(k)},\mathcal{K}\right)=\mathcal{K}(P^{(j)})^{-1}\delta_{Q^{(k)}\in\bm{e}_{j}}.$
(4)

where $\delta_{P,Q^{(j)}}$ equals one if $P=Q^{j}$ and equals zero otherwise.
Then we have

$\mathbb{E}_{P}\left[f_{\rm
Group}\left(P,Q^{(k)},\mathcal{K}\right)\right]=\sum_{j}\mathcal{K}\left(P^{(j)}\right)\mathcal{K}\left(P^{(j)}\right)^{-1}[Q^{(j)}\in\bm{e}_{j}]=1.$
(5)

The number of copies of quantum states $\rho$ needed here is associated with
the grouping strategy, and we give an explicit upper bound for the number of
copies requiring to approximate $\tr\left(\rho\bm{\mathrm{O}}\right)$ with an
additive error $\varepsilon$ for any given grouping strategy in Appendix A.

Finding the exact minimum number of groups has been proved to be NP-hard [37].
Several heuristic algorithms, such as the _largest degree first_ (LDF) method
[65] have been proposed to give approximate solutions. We refer to Appendix B
for a detailed implementation of the heuristic grouping method.

(3) _Classical shadows._ The conventional classical shadow (CS) method
measures the quantum state with a random Pauli basis, which corresponds to a
Pauli string $P\in\\{X,Y,Z\\}^{\otimes n}$ within our framework. The original
scheme in the seminal work [31] considers a uniform probability
$\mathcal{K}(P)=1/3^{n}$ whereas the locally biased classical shadow (LBCS)
method [27] assumes a general product distribution
$\mathcal{K}(P)=\prod_{i}\mathcal{K}_{i}(P_{i})$. The function $f_{\rm CS}$ is

$f_{\rm
CS}\left(P,Q^{(j)},\mathcal{K}\right)=\prod_{i}f_{i}\left(P_{i},Q^{(j)}_{i},\mathcal{K}_{i}\right),$
(6)

with
$f_{i}\left(P_{i},Q^{(j)}_{i},\mathcal{K}_{i}\right)=\delta_{Q_{i},{I}}+\mathcal{K}_{i}(P_{i})^{-1}\delta_{Q^{(j)}_{i},P_{i}}$.
One can check that

$\mathbb{E}_{P}\left[f_{\rm
CS}\left(P,Q^{(j)},\mathcal{K}\right)\right]=\prod_{i}\sum_{P_{i}}\mathcal{K}\left(P_{i}\right)f_{i}\left(P_{i},Q^{(j)}_{i},\mathcal{K}_{i}\right)=1.$
(7)

The number of copies $\rho$ to approximate the expectation of
$\bm{\mathrm{O}}$ with an additive error $\varepsilon$ and $1-\delta$ success
probability is bounded to
$O\left(3^{\text{local(\bm{\mathrm{O}})}}\left(\sum_{j=1}^{m}\alpha_{j}\right)^{2}/(\delta\varepsilon^{2})\right)$,
where
local$\left(Q^{(j)}\right):=\\#\left\\{k|Q^{(j)}_{k}\neq\mathbb{I}\right\\}$
is the maximum number of qubits $k$ such that $Q^{(j)}_{k}$ is not identity
for all of $j$. We refer to Appendix A for detailed proof.

(4) _Derandomized CS._ Recently, Huang, Kueng and Preskill [33] proposed a
derandomized classical shadow algorithm, which shows great practical
performance compared with conventional classical shadow methods. The
derandomization algorithm first assigns a collection of $T$ completely random
$n$-qubit Pauli measurements, and then derandomizes the process for sampling
measurement set $\mathcal{P}$ by greedily and adaptively choosing current
$P^{(j)}$ in the $j$-th step, provided derandomized measurements
$P^{(1)}\ldots P^{(j-1)}$, that minimizes the conditional expected value over
all remaining random measurement assignments. Given all the selected
measurements $\mathcal{P}$, the estimator of the derandomized CS algorithm can
be expressed as

$\hat{v}=\sum_{j}\alpha_{j}\frac{1}{\sum_{P\in\mathcal{P}}\delta_{Q^{(j)}\triangleright
P}}\sum_{P:Q^{(j)}\triangleright
P}\mu\left(P,\mathrm{supp}\left(Q^{(j)}\right)\right)$ (8)

within our framework. Now we give a sampling version for this method and prove
that it can also be unified to the unified framework, as shown in Eq. (1).

For the measurement sequence $P^{(1)},\ldots,P^{(T)}$, suppose the frequency
of $P^{(k)}$ be $t_{k}$, let $p_{k}=t_{k}/T$ be the probability to select
$P^{(k)}$, and denote this distribution as $\mathcal{K}$. Then proposition 1
still holds as long as for any observable $Q^{(j)}$ where $j\in[m]$, there
exists a measurement $P^{(k)}$ in the measurement sequence such that
$Q^{(j)}\triangleright P^{(k)}$. In this case, we can rewrite Eq. (8) as

$\hat{v}=\sum_{j}\alpha_{j}\frac{1}{p\left(Q^{(j)}\right)}\mu\left(P^{(k)},\mathrm{supp}\left(Q^{(j)}\right)\right)$
(9)

for a selected measurement $P^{(k)}$, where $p\left(Q^{(j)}\right)$ is the
probability to measure $Q^{(j)}$. It is easy to check that
$\mathbb{E}\left[f\left(P^{(k)},Q^{(j)},\mathcal{K}\right)\right]=\mathbb{E}\left[\frac{1}{p\left(Q^{(j)}\right)}\right]=1$,
and hence
$\mathbb{E}\left[\hat{v}\right]=\tr\left(\rho\bm{\mathrm{O}}\right)$.

In Fig. 1, we show explicit examples of the above three typical methods. While
Ref. [27] showed the superiority of the LBCS method, we can see that LBCS
essentially exploits an alternative view of observable compatibility, which is
captured by the unified framework. However, since the measurements are
selected locally in LBCS, we have to measure redundant observables, such as
$X_{1}Z_{2}X_{3}$ in our example of Fig. 1. This term has no contribution to
the objective observable, but is still assigned a certain number of
measurements. For a general observable, many measurements might be assigned to
these redundant terms, and thus makes LBCS non-optimal or even costly with
increasing system size.

##  3 Overlapped grouping measurement

Here, we propose a new scheme that exploits the advantages of the
aforementioned typical measurement methods. We first introduce the concept of
_overlapped grouping_ and then give a comparison of this strategy and other
existing strategies.

###  3.1 Overlapped grouping

######  Definition 1 (Overlapped grouping).

For a set of observables $\mathcal{O}=\\{Q^{(j)}\\}$, the collection
$\mathcal{S}=\\{\bm{e}_{1},\ldots,\bm{e}_{s}\\}$ is an overlapped grouping
when $\cup_{j}\bm{e}_{j}=\mathcal{O}$ with corresponding measurements
$\\{P^{(1)},\ldots,P^{(s)}\\}$ satisfying $Q\triangleright P^{(j)},\forall
Q\in\bm{e}_{j}$.

Suppose that we have determined the probabilities
$\\{\mathcal{K}(P^{(j)})\\}$, and we can define a new function $f$ for the
overlapped grouping as

$f_{G}(P,Q,{\mathcal{K}})=\chi(Q)^{-1}\delta_{Q\triangleright P},$ (10)

where $\chi(Q):=\sum_{P:Q\triangleright P}\mathcal{K}(P)$ represents the
probability that $Q$ is effectively measured with the basis $P$. Now we can
define

$\hat{v}_{G}=\sum_{j}\alpha_{j}f_{G}(P,Q^{(j)},\mathcal{K})\mu\left(P,\mathrm{supp}(Q^{(j)})\right)$
(11)

as an unbiased estimator of $\tr\left(\rho\bm{\mathrm{O}}\right)$.
Intuitively, an unbiased estimation of $\tr\left(\rho Q^{(j)}\right)$ can be
generated from the measured results of $Q^{(j)}$ divided by its measured
probability. From the definition of $f_{G}$, we have
$\mathbb{E}_{P}[f_{G}(P,Q,\mathcal{K})]=\sum_{P:Q\triangleright
P}\mathcal{K}(P)\frac{1}{\chi(Q)}=1$, and hence $\hat{v}_{G}$ is also an
unbiased estimation of $\tr\left(\rho\bm{\mathrm{O}}\right)$ by Proposition 1.
To summarise, an overlapped grouping measurement (OGM) scheme works as
follows.

  * S1.

Find the overlapped sets $\mathcal{S}$ with corresponding measurements
$\\{P^{(1)},\ldots,P^{(s)}\\}$.

  * S2.

Find the probability distribution $\\{\mathcal{K}(P^{(j)})\\}$.

  * S3.

Measure the quantum state with a randomly generated basis $P$ and process the
outcomes with Eq. (1) and (10).

A specific OGM scheme is determined by the choice of sets $\mathcal{S}$
(equivalently $\\{P^{(j)}\\}$) and the probability distribution
$\\{\mathcal{K}(P^{(j)})\\}$. To quantify the performance of the scheme, we
consider the variance of the estimator, as shown in the following proposition.

######  Proposition 2.

The variance of $\hat{v}_{G}$ defined in Eq. (11) is

$\mathrm{Var}(\hat{v}_{G})=\sum_{j,k}\alpha_{j}\alpha_{k}g(Q^{(j)},Q^{(k)})\tr\left(\rho
Q^{(j)}Q^{(k)}\right){-\tr\left(\rho\bm{\mathrm{O}}\right)^{2}}$ (12)

where
$g(Q^{(j)},Q^{(k)}):=\chi^{-1}(Q^{(j)})\chi^{-1}(Q^{(k)}){\sum_{P:Q^{(j)}\triangleright
P\land Q^{(k)}\triangleright P}\mathcal{K}(P)}{}$.

###### Proof.

Since
Var$(\hat{v}_{G})=\mathbb{E}\left[\hat{v}_{G}^{2}\right]-\mathbb{E}\left[\hat{v}_{G}\right]^{2}$,
Proposition 2 follows from the following equations

$\displaystyle\mathbb{E}_{P}[f_{G}(P,Q,\mathcal{K})f_{G}(P,R,\mathcal{K})]=\frac{\sum_{P:Q\triangleright
P\land R\triangleright P}\mathcal{K}(P)}{\chi(Q)\chi(R)},$ (13)
$\displaystyle\mathbb{E}_{\mu(P|Q,R)}[\mu(P,\mathrm{supp}(Q))\mu(P,\mathrm{supp}(R))]=\tr(\rho
QR),$

where the first equation holds directly by its definition and the second
equation holds because we have
$\mu(P,\mathrm{supp}(Q))\mu(P,\mathrm{supp}(R))=\mu(P,\mathrm{supp}(Q\oplus
R))=\mu(P,\mathrm{supp}(QR))$ when $Q,R\in\\{I,X,Y,Z\\}^{n}$. ∎

The variance determines the sample complexity. In particular, we need the
total number of measurements
$T\geq\text{Var}\left(\hat{v}_{G}\right)/\left(\delta\varepsilon^{2}\right)$
samples to achieve
$\Pr\left[\absolutevalue{\hat{v}_{G}-\tr\left(\rho\bm{\mathrm{O}}\right)}\geq\varepsilon\right]\leq\delta$
with error $\varepsilon\geq 0$ and failure probability $\delta\in[0,1]$.

###  3.2 Illustration and comparison with other measurement schemes

We illustrate the differences between our OGM scheme and other measurement
schemes in Fig. 1. As illustrated in Fig. 1, importance sampling selects an
observable in each iteration, and measures the prepared state with the sampled
observables to obtain the estimations associated with this observable.
Grouping strategy leverages the compatible property of the observables, and
measures the observables that are compatible jointly. Nevertheless, it only
exploits a very limited space of the full probability space for $4^{n}$
possible measurements in $\left\\{I,X,Y,Z\right\\}^{n}$. Moreover, for the
sake of the grouping determination using the heuristic strategy, an observable
can not arise in two different sets. Therefore, it might be inefficient in
leveraging of the measurements. Classical shadow method finds the optimized
probabilities of each qubit of the measurement, and it also measures the
observables jointly. However, since the CS method independently generates
Pauli operators on each qubit, it will generate useless measurements, such as
$X_{1}Z_{2}X_{3}$ in Fig. 1(c). As a comparison, for any measurement $P$ in
set $\left\\{P^{(1)},\ldots,P^{(s)}\right\\}$ generated from the OGM scheme,
there exists at least an observable $Q^{(j)}$, such that
$Q^{(j)}\triangleright P$.

The overlapped grouping measurement framework defined as in Eq. (10) without
an explicit assignment of $\left\\{P^{(k)}\right\\}$ and $\mathcal{K}$ covers
importance sampling, LDF Grouping, CS and the “probabilistic version” of the
derandomized CS algorithm as in Eq. (9). The importance sampling, grouping and
CS algorithms can be regarded as a special OGM framework with some
restrictions for the distribution of measurements $\\{(P,\mathcal{K}(P))\\}$.
We note that in our method
$f_{G}(P,Q,{\mathcal{K}})=\chi(Q)^{-1}\delta_{Q\triangleright P}$ may lead to
more effective data post-processing since it exploits all the compatible
properties of observables in the overlapped sets, and the “probabilistic
version” estimation in Eq. (9) of the derandomized CS algorithm also belongs
to this scope, since it is equivalent to the estimation expression with the
OGM grouping strategy in Eq. (11).

We can also observe that OGM is strictly better than the classical shadow
method. The OGM scheme reduces to the CS method when we choose
$P^{(j)}\in\\{X,Y,Z\\}^{\otimes n}$ and restrict the probability distribution
$\mathcal{K}(P^{(j)})$ to have a local product structure on different qubits.
We remark that OGM will not measure redundant observables as that in the local
shadow methods.

The estimator in Eq. (8) indicates that derandomization utilizes the
compatible properties of observables when measuring on the predetermined
basis. Once the measurement bases are determined, it could be regarded as a
special overlapped grouping method.

In OGM, challenges remain to (1) determine the collection $\mathcal{S}$ and
(2) find the probability distributions $\mathcal{K}$. Similar to the case of
grouping method, finding the optimal overlapped groups given the objective
observables is also NP-hard. In Sec. 4, we develop an explicit strategy to
determine an approximate solution $\mathcal{S}$ by leveraging a greedy
algorithm based on the weights of the observables. To find the probability
distribution $\mathcal{K}$, we apply an optimization procedure to adaptively
search for the solution that minimizes the estimator variance.

##  4 Explicit grouping strategies

We show in Algorithm 1 our strategy to determine the overlapped sets
$\bm{e}_{1},\ldots,\bm{e}_{s}$ and the associated probability
$\mathcal{K}_{j}:=\mathcal{K}(P^{(j)})$. The main idea is that under the
premise of covering all the objective observables, we add an observable which
has not been accessed into a new set, and add all compatible observables into
this set. We give priority to observables with larger absolute weights since
it has more contributions to the estimation. We note that different sequences
to add a new observable into an existing set will influence the structure of
sets and the number of sets. Algorithm 1 provides a grouping strategy by
adding a new observable by its importance (weight) and trying to reduce the
number of sets as far as possible. Meanwhile, the procedure guarantees that
whenever an observable $Q^{(j)}$ is compatible with the measurement $P^{(i)}$,
it is in the set $\bm{e}_{i}$. See Appendix C for an alternative strategy,
which has slightly better performance however based on a more dedicated
optimization procedure.

Input : $n,m$ and $Q^{(1)},\ldots,Q^{(m)},\alpha_{1},\ldots,\alpha_{m}$.

Output : $\\{P^{(s)}\\}$ with initial probabilities $\\{\mathcal{K}_{s}\\}$.

1 _Sorting $\\{Q^{(j)}\\}$ to the descending order according to their weights
$\absolutevalue{\alpha_{j}}$_;

2 $j\leftarrow 1$ and $s\leftarrow 1$;

3 while  _$\exists Q^{(j)}$ that is not in any sets_ :

4  _Let $Q^{(j)}$ be the first observable in the sorted sequence which has
never appeared in any sets and add it into a new set $\bm{e}_{s}$_;

5  _$s\leftarrow s+1$_ ;

6  _Initialize the measurement of $\bm{e}_{s}$ as $P^{(s)}\leftarrow
Q^{(j)}$_;

7 for  _$k\leftarrow j+1$ to $m$ _ :

8

9 if  _observable $Q^{(k)}$ is compatible with $P^{(s)}$_ :

10  _Add $Q^{(k)}$ into set $\bm{e}_{s}$_;

 _Update $P^{(s)}$ to $P^{(s)}\bigvee Q^{(k)}$_ ;

/* $P=Q\bigvee R$ is defined as $P_{i}=Q_{i}$ if $Q_{i}=R_{i}$ and
$P_{i}=Q_{i}R_{i}$ otherwise. */

11

12

13  _Let the initial probability of $P^{(s)}$ be the summation of the weight
of all observables in this set_;

14 for  _$k\leftarrow 1$ to $j-1$_ :

15 if  _observable $Q^{(k)}$ is compatible with $P^{(s)}$_ :

16  _Add $Q^{(k)}$ into set $\bm{e}_{s}$, and update $P^{(s)}$ to
$P^{(s)}\bigvee Q^{(k)}$_;

17

18

19

Algorithm 1 Overlapped set generation.

The algorithm outputs the measurements $\\{P\\}$ with non-optimized
probabilities $\\{\mathcal{K}\\}$. Here the initial probability of $P^{(s)}$
is not chosen as the weight of $\bm{e}_{s}$ since we wish to distinguish the
importance of different sets and give more priority to the sets which are
generated in front of $\bm{e}_{s}$. We can then optimize $\\{\mathcal{K}\\}$
to further minimize the estimator variance. However, the variance
$\textrm{Var}(\hat{v}_{G})$ in Eq. (12) depends on the input state $\rho$,
which could be unknown in general. Alternatively, we consider the diagonal
approximation of Var$\left(\hat{v}_{G}\right)$ (see similar techniques in Ref.
[27]), which is explicitly expressed as

$l(\vec{\mathcal{K}})=\sum_{j}\frac{\alpha_{j}^{2}}{\chi({Q^{(j)},\vec{\mathcal{K}}})},$
(14)

where $\chi(Q,\vec{\mathcal{K}})=\sum_{P:Q\triangleright P}\mathcal{K}(P)$ and
$\vec{\mathcal{K}}:=\left(\mathcal{K}_{1},\cdots,\mathcal{K}_{s}\right)$
represents all the corresponding probabilities. We give the mathematical
supports that why we utilize $l(\vec{\mathcal{K}})$ as the cost function in
Appendix E. There are several advantages of using the diagonal approximation
$l(\vec{\mathcal{K}})$ instead of the actual variance — (1) independence of
the quantum state, (2) fast classical evaluation, (3) including dominant
contribution to the variance since $\tr\left(\rho
Q^{(j)}Q^{(k)}\right)<\tr\left(\rho Q^{(j)}Q^{(j)}\right)=1$ when $j\neq k$.
Therefore, we could instead regard $l(\vec{\mathcal{K}})$ as the cost function
and minimize it by optimizing over $\vec{\mathcal{K}}$. From the expression of
$l\left(\vec{\mathcal{K}}\right)$ in Eq. (14), we see the cost function is not
convex in $\vec{\mathcal{K}}$ and hence there is no closed minimum solution.
An estimation can be generated by searching for a local minimum solution of
the cost function in Eq. (14). To further give a better estimation and avoid
being trapped into bad local minima, we slightly revise the cost function, as
shown in the following subsection.

###  4.1 Optimization process

For the optimization process of the OGM method, we will further speed it up by
adaptively deleting the groups that have very small initial probabilities
until the cost function stops decreasing with the disturbance. Note that after
cutting down the groups with small weights, some observables with small
coefficients will disappear in the cost function. Therefore, we adjust the
final cost function as

$\displaystyle
l(\vec{\mathcal{K}})=\sum_{Q^{(j)}\in\mathcal{S}}\frac{\alpha_{j}^{2}}{\chi\left(Q^{(j)}\right)}+\sum_{Q^{(j)}\not\in\mathcal{S}}\alpha_{j}^{2}T,$
(15)

where $T$ is the total number of samples, $Q^{(j)}\in\mathcal{S}$ if there
exists a set $\bm{e}$ such that $Q^{(j)}\in\bm{e}$, and
$\sum_{Q^{(j)}\not\in\mathcal{S}}$ is the penalty caused by deleting some
sets. The selection of the final cost function in Eq. (15) is inspired by the
relationship between the variance and the number of samples. More
specifically, Chebyshev inequality
$T\geq\text{Var}(\hat{v})/\left(\delta\varepsilon^{2}\right)$ indicates that
Var$(\hat{v})$ is linear in $T$. Hence we introduce $\alpha_{j}^{2}T$ to
compensate the initial error $\varepsilon_{0}$ for excluding the observable
$Q^{(j)}$. The initial error
$\varepsilon_{0}=\absolutevalue{\sum_{j:Q^{(j)}\not\in\mathcal{S}}\alpha_{j}\tr\left(\rho
Q^{(j)}\right)}$ implies biases of our estimation. We could search for an
optimized $T$ in a real experiment with a small-scaled input size with an
initial $T_{0}$. Since the cost function in Eq. (15) is not convex, we could
find a local minimum solution using the nonconvex optimization methods.

Since our OGM method assumes measurements drawn from the probability
distribution, the measurement accuracy may fluctuate. We will derandomize the
scheme by fixing almost all of the choices of measurements $P$ in the next
subsection.

###  4.2 Sampling strategy

Suppose that we have determined the measurement basis sets
$\bm{e}_{1},\ldots,\bm{e}_{s}$ and the optimized probability distribution
$\\{(P,\mathcal{K}(P))\\}$ using the above strategy. In practical computation,
we usually have constraints on the maximum allowed number of measurements. In
what follows, we provide a partially derandomized strategy with the given
number of measurements $T$. For the $j$th measurement $P^{(j)}$ with sampling
probability $\mathcal{K}_{j}$, we choose $\left\lfloor
T\mathcal{K}_{j}\right\rfloor$ number of measurements for $P^{(j)}$, and
select an additional one $P^{(j)}$ with probability
$T\mathcal{K}_{j}-\left\lfloor T\mathcal{K}_{j}\right\rfloor$, as shown in the
Algorithm 2.

Input : Measurements $P^{(1)},\ldots,P^{(s)}$, which follows distribution
$\mathcal{K}=\left\\{\mathcal{K}_{1},\ldots,\mathcal{K}_{s}\right\\}$, the
number of selected measurements $T$.

Output : List $\mathcal{M}$ which contains selected measurements.

1 _Sorting measurements $P^{(1)},\ldots,P^{(s)}$ to descending order in terms
of its probabilities_;

2 for  _$j\leftarrow 1$ to $s$_

3  _Add $\left\lfloor\mathcal{K}_{j}T\right\rfloor$ number of $P^{(j)}$ into
list $\mathcal{M}$_;

4
_$\mathcal{K}_{j}\leftarrow\mathcal{K}_{j}T-\left\lfloor\mathcal{K}_{j}T\right\rfloor$_
;

5

6 for  _$j\leftarrow 1$ to $s$ and size$(\mathcal{M})<T$_

7  _Add one $P^{(j)}$ into list $\mathcal{M}$ with probability
$\mathcal{K}_{j}$_;

8

9 return _$\mathcal{M}$_ ;

Algorithm 2 Partially derandomized sampling process for OGM.

Observe that the estimation $\hat{v}_{G}$ does not rely on the arrangement of
measurements. Let $\mathcal{M}$ be the list for the selected measurements, and
note here we allow a measurement to appear more than once in the list
$\mathcal{M}$. It is easy to check the expectation number of samples for
$P^{(j)}$ is equal to $\mathcal{K}_{j}T$ with Algorithm 2. Note that in
Algorithm 2, the number of sampled measurements may not exactly equal $T$,
although it is close to $T$ if $s\ll T$. Hence in the numerical experiment we
additionally add $P^{(j)}$ to $\mathcal{M}$ for the measurement $P^{(j)}$
satisfies $\mathcal{K}_{j}T<1$ and size$(\mathcal{M})<T$ in the descending
sequence sorted in Step (1) of Algorithm 2 if the size of $\mathcal{M}$ is
less than $T$. We provide detailed discussions on the variance of the
partially derandomized strategy in Appendix D.

##  5 Numerical tests

In this section, we numerically demonstrate the overlapped grouping
measurement algorithms for the energy estimation of molecular systems, and
compare our methods with other advanced measurement strategies, including LDF-
grouping, locally biased classical shadows, and derandomized classical
shadows. We do not include importance sampling method in the comparison since
its performance is worse than others. Algorithm 3 gives the full estimation
process for the OGM algorithm.

Input : Hamiltonian $\bm{\mathrm{O}}=\sum_{i}\alpha_{i}Q^{(i)}$, the number of
samples $T$.

Output : Estimation $v$.

1 _Generate the initial measurement distribution
$\left\\{P^{(s)},\mathcal{K}_{s}\right\\}$ with Algorithm 1 or Algorithm 4_ ;

2 _Uniformly randomly pick $A=10$ groups of distributions
$\left\\{\mathcal{K}_{s}\right\\}$ proportional to
$[P^{(s)},P^{(s)}+\max_{s}P^{(s)}]$, and choose one with minimum cost function
Eq. (15) as the initial point_ ;

3 _Find the local optimal distribution
$\left\\{P^{(s)},\mathcal{K}_{s}\right\\}$ by optimizing the cost function Eq.
(15) with Matlab optimization package_;

4 _Sample $T$ measurements from the optimized distribution with Algorithm 2_;

5 _Calculate $v$ with Eq. (8)_;

Algorithm 3 Overlapped grouping measurement.

In Step 3 of Algorithm 3, we begin the optimization process from a better
initialized probabilities by picking the distribution with the minimum cost
function from uniformly randomly selected 10 distributions around the
initialized distribution $\mathcal{K}_{s}$ from Step 3. To show the robust
advantages of the OGM algorithm, we directly choose the probabilities
initialized in Algorithm 1 without performing Step 3 to give the optimized
measurement distributions, and outputs the errors for estimations with 1000
samples in Table 1.

We compare the measurement schemes for different molecular Hamiltonians,
ranging from $4$ to $16$ qubits. We first consider the molecular Hamiltonian
measurement on the ground state of molecular Hamiltonians, in which the
fermionic Hamiltonians are mapped to the qubit ones under the Jordan-Wigner
(JW) transformation and the number of terms in the molecular Hamiltonians
scales quartically to the system size. In practice, the cost function in Eq.
(14) might lead to the optimized result for the probability distributions
trapped in the local minimum. Here, we address this problem by adding an
additional disturbance term in the cost function to jump out of local minima.

We compare the estimation error (averaged over 100 independent tests) using
$1000$ measurement samples in Table 1. Here the error is estimated with the
formula
$\varepsilon_{v}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}\left(\hat{v}_{i}-\tr(\rho
O)\right)^{2}}.$ The definition of $\varepsilon_{v}$ is also consistent with
the standard deviation calculation of the estimation $v$. It is worth
mentioning that we numerically show that $N=1000$ independent experiments are
sufficient to output a convinced estimation error in Appendix G. We also
include the recently proposed derandomized classical shadow method, which is
the current state-of-the-art method and has been numerically tested to
outperform the others [33]. The numerical result again shows that our OGM
method achieves much higher accuracy than other methods when the number of
measurements is limited, including the derandomized classical shadow method,
verifying its significant performance in the practical computation. The OGM
algorithm has simultaneous advantages in the energy estimation under different
fermion-to-qubit encodings, including Bravyi-Kitaev (BK) and parity encodings,
and we refer to Appendix G for the numerical results and detailed comparison
under Bravyi-Kitaev and parity encodings.

Table 1: Estimation errors with 1000 samples for measuring molecular Hamiltonians (JW-encoding) on the corresponding ground states via LDF-grouping, LBCS, derandomized CS, and the OGM method, where the initialized probability for the OGM algorithm is chosen directly from Algorithm 1. Molecule | LDF | LBCS [27] | Derand [33] | OGM
---|---|---|---|---
H2($4$) | 0.019 | 0.043 | 0.018 | 0.011
H2 ($8$) | 0.149 | 0.128 | 0.067 | 0.051
LiH ($12$) | 0.231 | 0.122 | 0.063 | 0.036
BeH2 ($14$) | 0.426 | 0.275 | 0.103 | 0.072
H2O ($14$) | 1.090 | 0.549 | 0.257 | 0.129
NH3 ($16$) | 1.063 | 0.484 | 0.225 | 0.151

To verify that the OGM method also has advantages when we have a large number
of measurements, we show the comparison of the OGM algorithm and LDF Grouping,
LBCS, and derandomized CS algorithm for errors with different number of
measurements for molecules LiH, and BeH2 under the JW encoding, as shown in
Fig. 2.

Figure 2: The error of the estimations by the LBCS, LDF Grouping, derandomized
CS, and OGM algorithm with the number of measurements for the ground state
energy of molecules (a) LiH (12 qubits), and (b) BeH2 (14 qubits) with JW-
encoding.

The results show that the OGM algorithm scales linearly to $1/\sqrt{T}$ for a
large number of samples $T$. This numerical result is consistent with the
theoretical results. It can be shown that the OGM algorithm has clear
advantages for a large number of samples compared to other existing
algorithms. We also provide the comparison of the variances of existing
algorithms with OGM algorithm in Appendix F.

Figure 3: The error of the estimation by the LBCS, LDF Grouping, Derandomized
CS and OGM algorithm for the expectation of molecule $H_{2}$ (8 qubits) with
JW-encoding under 10 random generated 8-qubit state. (a) $T=1000$ number of
samples and (b) $T=10,000$ number of samples.

We also show Fig. 3 and 4 to illustrate that the advantage of OGM is
independent of the quantum input state, where we approximate the expectation
of molecule H2 (8 qubits) with JW-encoding. In Fig. 3, we compare the errors
of LBCS, LDF Grouping, Derandomized CS, and OGM algorithms under 10 random
generated 8-qubit states with (a) 1000 samples and (b) 10,000 samples. In Fig.
4 we further show the comparison of these algorithms on a randomly generated
8-qubit state with the increase of the number of samples, where the $x$-axis
and the $y$-axis are both in logarithmic scales. Here we choose the input
quantum state as an $8$-qubit state with uniformly randomly generated real
amplitudes.

We additionally provide the experimental results in Appendix I. The
experimental results clearly show a much faster convergence of our OGM method
using a few hundred of measurements, which aligns with our theoretical
prediction and numerical simulation. We can observe that our methods are
practically useful even for the current generation of quantum devices.

##  6 Discussion and outlook

We introduce a unified framework of quantum measurement that reveals the
underlying mechanism of the existing advanced measurement strategies, which
are seemingly distinct from each other. We further propose the overlapped
grouping measurement (OGM) scheme that integrates the advantages of these
typical measurement strategies. Our numerical results suggest a significant
improvement over existing advanced measurement methods. Our numerical result
shows that our method already demonstrates advantages in practical problems.
Since the efficient quantum measurement is crucial for many quantum algorithms
and quantum processing, our work has wide applications, such as in variational
quantum algorithms and quantum many-body tasks involving eigenenergy
estimation [43, 7, 3, 54], where we need to efficiently measure complicated
Hamiltonians $\innerproduct{H}{H}$ or their moments
$\innerproduct{H^{2}}{H^{2}}$ [64]. Our method could significantly reduce the
measurement cost and hence speed up the quantum computation, especially when
we aim to realize quantum advantage for realistic problems. Moreover, our
method applies to adaptive variational quantum simulation, which requires a
large number of measurements in each subroutine [75, 25]. It is expected that
our measurement scheme will show more advantages with an increasing system
size of great practical relevance to both theoretical and experimental tasks.

Figure 4: The error of estimation by OGM algorithm for the expectation of
molecule $H_{2}$ (8 qubits) with JW-encoding under a randomly generated
8-qubit state.

The optimization goal of the OGM algorithm is completely different from the
derandomized CS method, since here we utilize a partial variance as the cost
function, while the derandomized CS algorithm utilizes a confidence bound. The
numerical results also show that our algorithm has clear advantages for a
large number of measurements. Our work considers explicit strategies for
choosing the overlapped sets, which could be improved using more advanced
classical algorithms. Note that the dimension of the considered measurement
space is $4^{n}$, and both OGM and CS variant algorithms aim to find a good
distribution in this huge space. The expressivity of the CS algorithm is
limited since it only explores the $3n$ size of this space. One of the
approaches is to combine OGM algorithm with CS for the molecules where parts
of qubits have strong correspondence. Briefly speaking, we could utilize the
CS method to generate $n/s$ independent subspaces, each grouped with OGM with
dimension $4^{S}$. We leave this idea as an interesting future work. Another
possible extension is to utilize neural networks to generate samples within
the OGM framework [62, 8, 63]. In our work, we assume local Pauli
measurements, whereas more general measurements, such as arbitrary local
measurements or entangled measurements could be considered [44, 36, 55, 49,
70, 35, 76]. Several measurement schemes have been proposed by adding a
polynomial-depth circuit before the local measurement to implement entangled
measurements [34, 70, 24]. How to extend our OGM scheme to generalized
measurements is an interesting future direction.

## Acknowledgement

We would like to thank Charles Hadfield and Antonio Mezzacapo for providing
the Hamiltonians with their work [27] and sharing relevant recent papers. We
thank Charles Hadfield, Antonio Mezzacapo, Xiaoming Sun, and Xiaoming Zhang
for their helpful discussions. This work is supported by the National Natural
Science Foundation of China (Grant No. 12175003, No. 12147133), and Zhejiang
Lab’s International Talent Fund for Young Professionals. The numerics is
supported by High-performance Computing Platform of Peking University. We
acknowledge the use of the IBMQ for this work. The views expressed are those
of the authors and do not reflect the official policy or position of IBM or
the IBM Q team111The source code for the OGM optimization process is available
at https://github.com/GillianOoO/Overlapped-grouping-measurement..

_Note added.—_ Recently, two relevant works [26, 30] were posted, which
introduce optimized quantum measurement schemes that generalize the classical
shadow methods. Hillmich et al. [30] proposed a decision diagrams method to
generate an estimation and Hadfield [26] proposed an adaptive Pauli Shadow
algorithm to generate an estimation. While similar problems are considered,
the techniques are different and could be compared. After our work, Shlosberg
et al. [56] and Yen et al. [71] apply the shadow and overlapped grouping ideas
to commute measurement respectively, and their results have better
performances with the cost of a polynomial-size quantum circuit.

## References

  * Aaronson [2019] Scott Aaronson.  Shadow tomography of quantum states.  _SIAM Journal on Computing_ , 49(5):STOC18–368, 2019.  doi: 10.1145/3188745.3188802.  URL https://doi.org/10.1145/3188745.3188802.
  * Acharya et al. [2021] Atithi Acharya, Siddhartha Saha, and Anirvan M Sengupta.  Informationally complete povm-based shadow tomography, 2021.  URL https://doi.org/10.48550/arXiv.2105.05992.
  * Babbush et al. [2018] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan.  Low-depth quantum simulation of materials.  _Phys. Rev. X_ , 8:011044, Mar 2018.  doi: 10.1103/PhysRevX.8.011044.  URL https://doi.org/10.1103/PhysRevX.8.011044.
  * Bharti et al. [2021] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik.  Noisy intermediate-scale quantum (nisq) algorithms, 2021.  URL https://doi.org/10.1103%2Frevmodphys.94.015004.
  * Bravo-Prieto et al. [2019] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles.  Variational quantum linear solver, 2019.  URL https://doi.org/10.48550/arXiv.1909.05820.
  * Bravyi et al. [2021] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay, and Jay M. Gambetta.  Mitigating measurement errors in multiqubit experiments.  _Phys. Rev. A_ , 103:042605, Apr 2021.  doi: 10.1103/PhysRevA.103.042605.  URL https://doi.org/10.1103/PhysRevA.103.042605.
  * Cao et al. [2019] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik.  Quantum chemistry in the age of quantum computing.  _Chemical Reviews_ , 119(19):10856–10915, 2019\.  doi: 10.1021/acs.chemrev.8b00803.  URL https://doi.org/10.1021/acs.chemrev.8b00803.  PMID: 31469277.
  * Carrasquilla et al. [2019] Juan Carrasquilla, Giacomo Torlai, Roger G Melko, and Leandro Aolita.  Reconstructing quantum states with generative models.  _Nature Machine Intelligence_ , 1(3):155–161, 2019.  doi: 10.1038/s42256-019-0028-1.  URL https://doi.org/10.1038/s42256-019-0028-1.
  * Cerezo et al. [2021] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  _Nature Reviews Physics_ , 3(9):625–644, 2021\.  doi: 10.1038/s42254-021-00348-9.  URL https://doi.org/10.1038/s42254-021-00348-9.
  * Chen et al. [2021] Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia.  Robust shadow estimation.  _PRX Quantum_ , 2:030348, Sep 2021.  doi: 10.1103/PRXQuantum.2.030348.  URL https://doi.org/10.1103/PRXQuantum.2.030348.
  * Choo et al. [2020] Kenny Choo, Antonio Mezzacapo, and Giuseppe Carleo.  Fermionic neural-network states for ab-initio electronic structure.  _Nature communications_ , 11(1):1–7, 2020.  doi: 10.1038/s41467-020-15724-9.  URL https://doi.org/10.1038/s41467-020-15724-9.
  * Cirstoiu et al. [2020] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger.  Variational fast forwarding for quantum simulation beyond the coherence time.  _npj Quantum Information_ , 6(1):1–10, 2020.  URL https://doi.org/10.1038/s41534-020-00302-0.
  * 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, Feb 2018.  doi: 10.1103/PhysRevX.8.011021.  URL https://doi.org/10.1103/PhysRevX.8.011021.
  * Commeau et al. [2020] Benjamin Commeau, M. Cerezo, Zoë Holmes, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger.  Variational hamiltonian diagonalization for dynamical quantum simulation, 2020.  URL https://doi.org/10.48550/arXiv.2009.02559.
  * Cotler and Wilczek [2020] Jordan Cotler and Frank Wilczek.  Quantum overlapping tomography.  _Phys. Rev. Lett._ , 124:100401, Mar 2020.  doi: 10.1103/PhysRevLett.124.100401.  URL https://doi.org/10.1103/PhysRevLett.124.100401.
  * Crawford et al. [2021] Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley.  Efficient quantum measurement of pauli operators in the presence of finite sampling error.  _Quantum_ , 5:385, 2021.  doi: 10.22331/q-2021-01-20-385.  URL https://doi.org/10.22331%2Fq-2021-01-20-385.
  * Dumitrescu et al. [2018] E. F. Dumitrescu, A. J. McCaskey, G. Hagen, G. R. Jansen, T. D. Morris, T. Papenbrock, R. C. Pooser, D. J. Dean, and P. Lougovski.  Cloud quantum computing of an atomic nucleus.  _Phys. Rev. Lett._ , 120:210501, May 2018.  doi: 10.1103/PhysRevLett.120.210501.  URL https://doi.org/10.1103/PhysRevLett.120.210501.
  * Endo et al. [2018] Suguru Endo, Simon C. Benjamin, and Ying Li.  Practical quantum error mitigation for near-future applications.  _Phys. Rev. X_ , 8:031027, Jul 2018.  doi: 10.1103/PhysRevX.8.031027.  URL https://doi.org/10.1103/PhysRevX.8.031027.
  * Endo et al. [2020] Suguru Endo, Jinzhao Sun, Ying Li, Simon C. Benjamin, and Xiao Yuan.  Variational quantum simulation of general processes.  _Phys. Rev. Lett._ , 125:010501, Jun 2020.  doi: 10.1103/PhysRevLett.125.010501.  URL https://doi.org/10.1103/PhysRevLett.125.010501.
  * Endo et al. [2021] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan.  Hybrid quantum-classical algorithms and quantum error mitigation.  _Journal of the Physical Society of Japan_ , 90(3):032001, 2021.  doi: 10.7566/JPSJ.90.032001.  URL https://doi.org/10.7566/JPSJ.90.032001.
  * Fujii et al. [2022] Keisuke Fujii, Kaoru Mizuta, Hiroshi Ueda, Kosuke Mitarai, Wataru Mizukami, and Yuya O. Nakagawa.  Deep variational quantum eigensolver: A divide-and-conquer method for solving a larger problem with smaller size quantum computers.  _PRX Quantum_ , 3:010346, Mar 2022.  doi: 10.1103/PRXQuantum.3.010346.  URL https://doi.org/10.1103/PRXQuantum.3.010346.
  * Gibbs et al. [2021] Joe Gibbs, Kaitlin Gili, Zoë Holmes, Benjamin Commeau, Andrew Arrasmith, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger.  Long-time simulations with high fidelity on quantum hardware, 2021.  URL https://arxiv.org/abs/2102.04313.
  * Giurgica-Tiron et al. [2020] Tudor Giurgica-Tiron, Yousef Hindy, Ryan LaRose, Andrea Mari, and William J. Zeng.  Digital zero noise extrapolation for quantum error mitigation.  In _2020 IEEE International Conference on Quantum Computing and Engineering (QCE)_ , pages 306–316, 2020.  doi: 10.1109/QCE49297.2020.00045.  URL https://doi.org/10.1109/QCE49297.2020.00045.
  * [24] 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.  URL https://doi.org/10.48550/arXiv.1907.13623.
  * Grimsley et al. [2019] Harper R Grimsley, Sophia E Economou, Edwin Barnes, and Nicholas J Mayhall.  An adaptive variational algorithm for exact molecular simulations on a quantum computer.  _Nature comm._ , 10(1):1–9, 2019.  doi: 10.1038/s41467-018-07090-4.  URL https://doi.org/10.1038/s41467-019-10988-2.
  * Hadfield [2021] Charles Hadfield.  Adaptive pauli shadows for energy estimation, 2021.  URL https://doi.org/10.48550/arXiv.2105.12207.
  * Hadfield et al. [2022] Charles Hadfield, Sergey Bravyi, Rudy Raymond, and Antonio Mezzacapo.  Measurements of quantum hamiltonians with locally-biased classical shadows.  _Communications in Mathematical Physics_ , 391(3):951–967, 2022.  doi: 10.1007/s00220-022-04343-8.  URL https://doi.org/10.1007/s00220-022-04343-8.
  * Hempel et al. [2018] Cornelius Hempel, Christine Maier, Jonathan Romero, Jarrod McClean, Thomas Monz, Heng Shen, Petar Jurcevic, Ben P. Lanyon, Peter Love, Ryan Babbush, Alán Aspuru-Guzik, Rainer Blatt, and Christian F. Roos.  Quantum chemistry calculations on a trapped-ion quantum simulator.  _Phys. Rev. X_ , 8:031022, Jul 2018.  doi: 10.1103/PhysRevX.8.031022.  URL https://doi.org/10.1103/PhysRevX.8.031022.
  * Higgott et al. [2019] Oscar Higgott, Daochen Wang, and Stephen Brierley.  Variational Quantum Computation of Excited States.  _Quantum_ , 3:156, July 2019.  ISSN 2521-327X.  doi: 10.22331/q-2019-07-01-156.  URL https://doi.org/10.22331/q-2019-07-01-156.
  * Hillmich et al. [2021] Stefan Hillmich, Charles Hadfield, Rudy Raymond, Antonio Mezzacapo, and Robert Wille.  Decision diagrams for quantum measurements with shallow circuits.  In _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_ , pages 24–34, 2021.  doi: 10.1109/QCE52317.2021.00018.  URL https://doi.org/10.1109/QCE52317.2021.00018.
  * Huang et al. [2020] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  _Nature Physics_ , 16(10):1050–1057, 2020.  doi: 10.1038/s41567-020-0932-7.  URL https://doi.org/10.1038/s41567-020-0932-7.
  * Huang et al. [2021a] Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost.  Near-term quantum algorithms for linear systems of equations with regression loss functions.  _New Journal of Physics_ , 23(11):113021, nov 2021a.  doi: 10.1088/1367-2630/ac325f.  URL https://doi.org/10.1088/1367-2630/ac325f.
  * Huang et al. [2021b] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Efficient estimation of pauli observables by derandomization.  _Phys. Rev. Lett._ , 127:030503, Jul 2021b.  doi: 10.1103/PhysRevLett.127.030503.  URL https://doi.org/10.1103/PhysRevLett.127.030503.
  * Huggins et al. [2021] William J Huggins, Jarrod R McClean, Nicholas C Rubin, Zhang Jiang, Nathan Wiebe, K Birgitta Whaley, and Ryan Babbush.  Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers.  _npj Quantum Information_ , 7(1):1–9, 2021.  doi: 10.1038/s41534-020-00341-7.  URL https://doi.org/10.1038/s41534-020-00341-7.
  * Izmaylov et al. [2019a] 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.  _Journal of chemical theory and computation_ , 16(1):190–195, 2019a.  doi: 10.1021/acs.jctc.9b00791.  URL https://doi.org/10.1021/acs.jctc.9b00791.
  * Izmaylov et al. [2019b] 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?  _Chemical science_ , 10(13):3746–3755, 2019b.  doi: 10.1039/C8SC05592K.  URL https://doi.org/10.1039/C8SC05592K.
  * Jena et al. [2019] Andrew Jena, Scott Genin, and Michele Mosca.  Pauli partitioning with respect to gate sets, 2019.  URL https://doi.org/10.48550/arXiv.1907.07859.
  * Kandala et al. [2017] 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(7671):242–246, 2017.  doi: 10.1038/nature23879.  URL https://doi.org/10.1038/nature23879.
  * Li and Benjamin [2017] Ying Li and Simon C. Benjamin.  Efficient variational quantum simulator incorporating active error minimization.  _Phys. Rev. X_ , 7:021050, Jun 2017.  doi: 10.1103/PhysRevX.7.021050.  URL https://doi.org/10.1103/PhysRevX.7.021050.
  * Liu et al. [2019] Jin-Guo Liu, Yi-Hong Zhang, Yuan Wan, and Lei Wang.  Variational quantum eigensolver with fewer qubits.  _Phys. Rev. Research_ , 1:023025, Sep 2019.  doi: 10.1103/PhysRevResearch.1.023025.  URL https://doi.org/10.1103/PhysRevResearch.1.023025.
  * Ma et al. [2020] He Ma, Marco Govoni, and Giulia Galli.  Quantum simulations of materials on near-term quantum computers.  _npj Computational Materials_ , 6(1):1–8, 2020\.  doi: 10.1038/s41524-020-00353-z.  URL https://doi.org/10.1038/s41524-020-00353-z.
  * McArdle et al. [2019] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan.  Variational ansatz-based quantum simulation of imaginary time evolution.  _npj Quantum Information_ , 5(1):1–6, 2019.  doi: 10.1038/s41534-019-0187-2.  URL https://doi.org/10.1038/s41534-019-0187-2.
  * McArdle et al. [2020] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan.  Quantum computational chemistry.  _Rev. Mod. Phys._ , 92:015003, Mar 2020.  doi: 10.1103/RevModPhys.92.015003.  URL https://doi.org/10.1103/RevModPhys.92.015003.
  * 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(2):023023, feb 2016\.  doi: 10.1088/1367-2630/18/2/023023.  URL https://doi.org/10.1088/1367-2630/18/2/023023.
  * 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(4):042308, 2017.  URL https://doi.org/10.1103/PhysRevA.95.042308.
  * McClean et al. [2020] Jarrod R McClean, Zhang Jiang, Nicholas C Rubin, Ryan Babbush, and Hartmut Neven.  Decoding quantum errors with subspace expansions.  _Nature Communications_ , 11(1):1–9, 2020.  doi: 10.1038/s41467-020-14341-w.  URL https://doi.org/10.1038/s41467-020-14341-w.
  * Moll et al. [2018] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al.  Quantum optimization using variational algorithms on near-term quantum devices.  _Quantum Science and Technology_ , 3(3):030503, 2018.  doi: 10.1088/2058-9565/aab822.  URL https://doi.org/10.1088/2058-9565/aab822.
  * Nakanishi et al. [2019] Ken M Nakanishi, Kosuke Mitarai, and Keisuke Fujii.  Subspace-search variational quantum eigensolver for excited states.  _Physical Review Research_ , 1(3):033062, 2019\.  doi: 10.1103/PhysRevResearch.1.033062.  URL https://doi.org/10.1103/PhysRevResearch.1.033062.
  * O’Gorman et al. [2019] Bryan O’Gorman, William J Huggins, Eleanor G Rieffel, and K Birgitta Whaley.  Generalized swap networks for near-term quantum computing, 2019.  URL https://doi.org/10.48550/arXiv.1905.05118.
  * 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, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, P. V. Coveney, P. J. Love, H. Neven, A. Aspuru-Guzik, and J. M. Martinis.  Scalable quantum simulation of molecular energies.  _Phys. Rev. X_ , 6:031007, Jul 2016.  doi: 10.1103/PhysRevX.6.031007.  URL https://doi.org/10.1103/PhysRevX.6.031007.
  * Otten and Gray [2019] Matthew Otten and Stephen K Gray.  Accounting for errors in quantum algorithms via individual error reduction.  _Npj Quantum Inf._ , 5(1):11, 2019.  doi: 10.1038/s41534-019-0125-3.  URL https://doi.org/10.1038/s41534-019-0125-3.
  * 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 comm._ , 5:4213, 2014.  doi: 10.1038/ncomms5213.  URL https://doi.org/10.1038/ncomms5213.
  * Preskill [2018] John Preskill.  Quantum computing in the nisq era and beyond.  _Quantum_ , 2:79, 2018.  doi: 10.22331/q-2018-08-06-79.  URL https://doi.org/10.22331/q-2018-08-06-79.
  * Quantum et al. [2020] Google AI Quantum, Collaborators*†, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, et al.  Hartree-fock on a superconducting qubit quantum computer.  _Science_ , 369(6507):1084–1089, 2020.  doi: 10.1126/science.abb9811.  URL https://doi.org/10.1126/science.abb9811.
  * 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(5):053020, may 2018\.  doi: 10.1088/1367-2630/aab919.  URL https://doi.org/10.1088/1367-2630/aab919.
  * Shlosberg et al. [2021] Ariel Shlosberg, Andrew J. Jena, Priyanka Mukhopadhyay, Jan F. Haase, Felix Leditzky, and Luca Dellantonio.  Adaptive estimation of quantum observables, 2021.  URL https://doi.org/10.48550/arXiv.2110.15339.
  * Strikis et al. [2021] Armands Strikis, Dayue Qin, Yanzhu Chen, Simon C. Benjamin, and Ying Li.  Learning-based quantum error mitigation.  _PRX Quantum_ , 2:040330, Nov 2021.  doi: 10.1103/PRXQuantum.2.040330.  URL https://doi.org/10.1103/PRXQuantum.2.040330.
  * Struchalin et al. [2021] G.I. Struchalin, Ya. A. Zagorovskii, E.V. Kovlakov, S.S. Straupe, and S.P. Kulik.  Experimental estimation of quantum state properties from classical shadows.  _PRX Quantum_ , 2:010307, Jan 2021.  doi: 10.1103/PRXQuantum.2.010307.  URL https://doi.org/10.1103/PRXQuantum.2.010307.
  * Sun et al. [2021] Jinzhao Sun, Xiao Yuan, Takahiro Tsunoda, Vlatko Vedral, Simon C. Benjamin, and Suguru Endo.  Mitigating realistic noise in practical noisy intermediate-scale quantum devices.  _Phys. Rev. Applied_ , 15:034026, Mar 2021.  doi: 10.1103/PhysRevApplied.15.034026.  URL https://doi.org/10.1103/PhysRevApplied.15.034026.
  * Sun et al. [2022] Jinzhao Sun, Suguru Endo, Huiping Lin, Patrick Hayden, Vlatko Vedral, and Xiao Yuan.  Perturbative quantum simulation, Sep 2022.  URL https://doi.org/10.1103/PhysRevLett.129.120505.
  * Temme et al. [2017] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta.  Error mitigation for short-depth quantum circuits.  _Phys. Rev. Lett._ , 119:180509, Nov 2017.  doi: 10.1103/PhysRevLett.119.180509.  URL https://doi.org/10.1103/PhysRevLett.119.180509.
  * Torlai et al. [2018] Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo.  Neural-network quantum state tomography.  _Nature Physics_ , 14(5):447–450, 2018.  doi: 10.1038/s41567-018-0048-5.  URL https://doi.org/10.1038/s41567-018-0048-5.
  * Torlai et al. [2020] Giacomo Torlai, Guglielmo Mazzola, Giuseppe Carleo, and Antonio Mezzacapo.  Precise measurement of quantum observables with neural-network estimators.  _Phys. Rev. Res._ , 2:022060, Jun 2020.  doi: 10.1103/PhysRevResearch.2.022060.  URL https://doi.org/10.1103/PhysRevResearch.2.022060.
  * Vallury et al. [2020] Harish J Vallury, Michael A Jones, Charles D Hill, and Lloyd CL Hollenberg.  Quantum computed moments correction to variational estimates.  _Quantum_ , 4:373, 2020.  doi: 10.22331/q-2020-12-15-373.  URL https://doi.org/10.22331/q-2020-12-15-373.
  * Verteletskyi et al. [2020] Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F Izmaylov.  Measurement optimization in the variational quantum eigensolver using a minimum clique cover.  _The Journal of chemical physics_ , 152(12):124114, 2020.  doi: 10.1063/1.5141458.  URL https://doi.org/10.1063/1.5141458.
  * Wang et al. [2021] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles.  Noise-induced barren plateaus in variational quantum algorithms.  _Nature communications_ , 12(1):1–11, 2021.  doi: 10.1038/s41467-021-27045-6.  URL https://doi.org/10.1038/s41467-021-27045-6.
  * Wecker et al. [2015] Dave Wecker, Matthew B. Hastings, and Matthias Troyer.  Progress towards practical quantum variational algorithms.  _Phys. Rev. A_ , 92:042303, Oct 2015.  doi: 10.1103/PhysRevA.92.042303.  URL https://doi.org/10.1103/PhysRevA.92.042303.
  * Xu et al. [2021] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan.  Variational algorithms for linear algebra.  _Science Bulletin_ , 2021.  ISSN 2095-9273.  doi: 10.1016/j.scib.2021.06.023.  URL https://doi.org/10.1016/j.scib.2021.06.023.
  * Yang et al. [2017] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon.  Optimizing variational quantum algorithms using pontryagin’s minimum principle.  _Phys. Rev. X_ , 7:021027, May 2017.  doi: 10.1103/PhysRevX.7.021027.  URL https://doi.org/10.1103/PhysRevX.7.021027.
  * Yen et al. [2020] Tzu-Ching Yen, Vladyslav Verteletskyi, and Artur F Izmaylov.  Measuring all compatible operators in one series of single-qubit measurements using unitary transformations.  _Journal of chemical theory and computation_ , 16(4):2400–2409, 2020.  doi: 10.1021/acs.jctc.0c00008.  URL https://doi.org/10.1021/acs.jctc.0c00008.
  * Yen et al. [2022] Tzu-Ching Yen, Aadithya Ganeshram, and Artur F Izmaylov.  Deterministic improvements of quantum measurements with grouping of compatible operators, non-local transformations, and covariance estimates, 2022\.  URL https://doi.org/10.48550/arXiv.2201.01471.
  * Yuan et al. [2019] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin.  Theory of variational quantum simulation.  _Quantum_ , 3:191, 2019.  doi: 10.22331/q-2019-10-07-191.  URL https://doi.org/10.22331/q-2019-10-07-191.
  * Yuan et al. [2021] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou.  Quantum simulation with hybrid tensor networks.  _Phys. Rev. Lett._ , 127:040501, Jul 2021.  doi: 10.1103/PhysRevLett.127.040501.  URL https://doi.org/10.1103/PhysRevLett.127.040501.
  * Zhang et al. [2021] Ting Zhang, Jinzhao Sun, Xiao-Xu Fang, Xiao-Ming Zhang, Xiao Yuan, and He Lu.  Experimental quantum state measurement with classical shadows.  _Phys. Rev. Lett._ , 127:200501, Nov 2021.  doi: 10.1103/PhysRevLett.127.200501.  URL https://doi.org/10.1103/PhysRevLett.127.200501.
  * Zhang et al. [2020] Zi-Jian Zhang, Jinzhao Sun, Xiao Yuan, and Man-Hong Yung.  Low-depth hamiltonian simulation by adaptive product formula, 2020.  URL https://doi.org/10.48550/arXiv.2011.05283.
  * Zhao et al. [2020] Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter J. Love.  Measurement reduction in variational quantum algorithms.  _Phys. Rev. A_ , 101:062322, Jun 2020.  doi: 10.1103/PhysRevA.101.062322.  URL https://doi.org/10.1103/PhysRevA.101.062322.
  * Zhao et al. [2021] Andrew Zhao, Nicholas C. Rubin, and Akimasa Miyake.  Fermionic partial tomography via classical shadows.  _Phys. Rev. Lett._ , 127:110504, Sep 2021.  doi: 10.1103/PhysRevLett.127.110504.  URL https://doi.org/10.1103/PhysRevLett.127.110504.
  * Zhou et al. [2020] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.  _Phys. Rev. X_ , 10:021067, Jun 2020.  doi: 10.1103/PhysRevX.10.021067.  URL https://doi.org/10.1103/PhysRevX.10.021067.

##  Appendix A Sample complexity

In this section, we theoretically analyze the upper bound of the number of
copies for the existing algorithms, $l_{1}$-sampling, grouping, and classical
shadow algorithm theoretically. We further provide the variance of the
derandomization algorithm and show the relation to our overlapped grouping
measurement method.

Let $\hat{v}_{1},\ldots,\hat{v}_{T}$ be the estimations after $T$ independent
samples. Let $\hat{v}=\left(\hat{v}_{1}+\cdots+\hat{v}_{T}\right)/T$ be the
expectation of these samples. Then by Chebyshev inequality, we have

$\displaystyle\Pr\left[\absolutevalue{\hat{v}-\tr(\rho
Q)}\geq\varepsilon\right]\leq\frac{\text{Var}(\hat{v})}{\varepsilon^{2}}=\frac{\text{Var}\left(\hat{v}_{1}\right)}{T\varepsilon^{2}}.$
(16)

Hence the error can be bounded to $\varepsilon$ with probability $\delta$ when
the number of samples is
Var$\left(\hat{v}_{1}\right)/\left(\delta\varepsilon^{2}\right)$. By the
definition of $\hat{v}$ in Eq. (1), the variance of $\hat{v}$ equals
$\mathbb{E}\left[\hat{v}^{2}\right]-\tr(\rho\bm{\mathrm{O}})^{2}\leq\mathbb{E}\left[\hat{v}^{2}\right]$.

_$l_{1}$ -sampling.—_ The variance of $\hat{v}_{1}$ generated by
$l_{1}$-sampling can be bounded to

$\displaystyle\text{Var}\left(\hat{v}_{1}\right)\leq\sum_{j=1}^{m}\alpha_{j}^{2}\frac{\left\|\alpha\right\|_{1}}{\absolutevalue{\alpha_{j}}}=\left\|\alpha\right\|_{1}^{2}.$
(17)

Hence $T\geq\frac{\left\|\alpha\right\|_{1}^{2}}{\delta\varepsilon^{2}}$
suffices to give an estimation with error less than $\varepsilon$ and success
probability $1-\delta$.

_Grouping.—_ The variance of $\hat{v}_{1}$ generated by grouping method
satisfies

$\displaystyle\begin{aligned}
\text{Var}\left(\hat{v}_{1}\right)&\leq\sum_{j,k}\alpha_{j}\alpha_{k}f_{\text{Group}}\left(Q^{(j)},Q^{(k)},\mathcal{K}\right)\tr\left(\rho
Q^{(j)}Q^{(k)}\right)\\\
&\leq\left(\sum_{j}\alpha_{j}f_{\text{Group}}(Q^{(j)},Q^{(j)},\mathcal{K})\right)^{2}\\\
&=\left(\sum_{k=1}^{s}\frac{1}{\mathcal{K}_{j}}\sum_{j:Q^{(j)}\in\bm{e}_{k}}\alpha_{j}\right)^{2}\\\
&=\left\|\alpha\right\|_{1}^{2}\left(\sum_{k=1}^{s}\frac{1}{\left\|\alpha_{\bm{e}_{k}}\right\|_{1}}\sum_{j:Q^{(j)}\in\bm{e}_{k}}\alpha_{j}\right)^{2},\end{aligned}$
(18)

where
$\left\|\alpha_{\bm{e}_{k}}\right\|_{1}=\sum_{j:Q^{(j)}\in\bm{e}_{k}}\absolutevalue{\alpha_{j}}.$

_Classical shadow.—_ For classical shadow algorithm, the variance of the
generated estimation $\hat{v}_{1}$ satisfies

$\displaystyle\begin{aligned}
\text{Var}\left(\hat{v}_{1}\right)&\leq\sum_{j,k}\alpha_{j}\alpha_{k}f_{\text{LBCS}}\left(Q^{(j)},Q^{(k)},\mathcal{K}\right)\tr\left(\rho
Q^{(j)}Q^{(k)}\right)\\\
&\leq\left(\sum_{j}\alpha_{j}\prod_{k=1}^{n}\frac{1}{\chi_{k}\left(Q_{k}^{(j)}\right)}\right)^{2}\\\
&\leq
3^{\text{local(\bm{\mathrm{O}})}}\left(\sum_{j=1}^{m}\alpha_{j}\right)^{2}\end{aligned}$
(19)

where local$(\bm{\mathrm{O}})=\max_{j=1}^{m}\text{ local}(Q^{(j)})$, and the
locality of $Q^{(j)}$:
local$\left(Q^{(j)}\right)=\\#\left\\{k|Q^{(j)}_{k}\neq\mathbb{I}\right\\}$ is
the number of qubits $k$ such that $Q^{(j)}_{k}$ is not identity. Therefore,
$T\geq\frac{3^{\text{local}(\bm{\mathrm{O}})}\left(\sum_{j}\alpha_{j}\right)^{2}}{\delta\varepsilon^{2}}$
suffices to give an estimation with error $\varepsilon$ and success
probability $1-\delta$.

##  Appendix B LDF Grouping method

In the LDF Grouping method, we mapped the observables and the “compatible
with” relationship to a graph. In specific, we denote an observable as a
vertex, and if two observables do not have any “compatible with” relationship,
we connect them with an edge. Then we can obtain a graph $G(V,E)$, where the
number of vertices is equal to $m$. Next, we can proceed the grouping method
as follows.

  * (1)

Sorting vertices $V_{1},V_{2},\ldots,V_{m}$ in the descending order of its
degree.

  * (2)

Repeat the following step until all of the vertices are in one of the sets.

  * (3)

For $j$ goes from $1$ to $m$, if $V_{j}$ is not in any set, then add $V(j)$ to
a set such that there is no edge between $V(j)$ and any other vertices in this
set. If such a set does not exist, then add $V(j)$ to a new set.

After the above process and changing $V_{i}$ into $Q^{(i)}$, we can generate
the grouping sets which satisfy any two observables are compatible with each
other.

##  Appendix C Greedy overlapped grouping strategy

Aside from the overlapped set generation strategy in Algorithm 1 of the main
text, we proposed an alternative strategy that is slightly different in
selecting the observables for a set, denoted as Grouping version 2. The main
difference is in “the sequence of observables” adding to a new set. The new
strategy has a potentially better performance but it needs more time since it
has a larger number of sets. We further add a token to each observable to
represent how many times we can visit this observable to avoid the explosion
of the number of sets. Note that if there is no restriction, the observables
in the tail of the sequence will be much more difficult to be added to
existing sets, hence the number of sets could be very large.

Let the token of an observable $Q^{(k)}$ be $U_{k}=2^{d-1}$, where $d$ is the
number of digits of
$\left\lfloor\absolutevalue{\alpha_{k}}/\text{Min}{\text{Weight}}\right\rfloor$,
and $\text{Min}{\text{Weight}}=\min_{j\leq m}\absolutevalue{\alpha_{j}}$ is
the minimum weight. This new version of grouping strategy is depicted in
Algorithm 4.

Input : $n,m$ and $Q^{(1)},\ldots,Q^{(m)},\alpha_{1},\ldots,\alpha_{m}$,
$U_{1},\ldots,U_{m}$.

Output : $\left\\{P^{(s)}\right\\}$ with initial probabilities
$\left\\{\mathcal{K}_{s}\right\\}$.

1 _Sorting all of the observables $\\{Q^{(j)}\\}$ to the descending order
according to their weights $\absolutevalue{\alpha_{j}}$_;

2 $j\leftarrow 1$ and $s\leftarrow 1$;

3 while  _$\exists Q^{(j)}$ which is not in any sets_ :

4  _Let $Q^{(j)}$ be the first observable in the sorted sequence which has
never appeared in any sets and add it into a new set $\bm{e}_{s}$_;

5  _$s\leftarrow s+1$_ ;

6  _Initialize the measurement of $\bm{e}_{s}$ as $P^{(s)}\leftarrow
Q^{(j)}$_;

7 for  _$k\leftarrow 1$ to $m$ _ :

8

9 if  _$Q^{(k)}$ is compatible with $P^{(s)}$ and $k\neq j$, the number of
sets $Q^{(k)}$ appeared is less than token $U_{k}$_ :

 _Add $Q^{(k)}$ into set $\bm{e}_{s}$, and update $P^{(s)}$ to $P^{(s)}\bigvee
Q^{(k)}$_ ;

/* $P=Q\bigvee R$ is defined as $P_{i}=Q_{i}$ if $Q_{i}=R_{i}$ and
$P_{i}=Q_{i}R_{i}$ otherwise. */

10

11

12  _Let the initial probability of $P^{(s)}$ be the summation of the weight
of all observables in this set_;

13 for  _$k\leftarrow 1$ to $j-1$_ :

14 if  _$Q^{(k)}$ is compatible with $P^{(s)}$ and not in $\bm{e}_{s}$_ :

15  _Add $Q^{(k)}$ into set $\bm{e}_{s}$, and update $P^{(s)}$ to
$P^{(s)}\bigvee Q^{(k)}$_;

16

17

18

Algorithm 4 Second version of overlapped set generation.

We compared the error of the estimation generated by grouping versions 1 and 2
in Table 2. The table shows that when we take more consideration for the
observables with larger weight, we have better optimized results, while this
would give us a longer optimization time because of the expansion of sets
(optimized parameters).

Table 2: Comparison for the errors of the OGM algorithms with grouping version 1 and 2. The error is estimated with 1000 samples for the ground state of the corresponding molecules under JW-encoding. molecule | H2 (4) | H2 (8) | LiH | BeH2 | H2O | NH3
---|---|---|---|---|---|---
error (V1) | 0.011 | 0.051 | 0.036 | 0.072 | 0.129 | 0.151
error (V2) | 0.013 | 0.047 | 0.021 | 0.051 | 0.121 | 0.115

##  Appendix D Variance for the partially derandomized strategy

Suppose that we have determined the measurement basis set $\mathcal{M}$, in
which the number of measurement basis $P^{(k)}$ is assigned as $M_{k}$, and
the total number of measurements is $T=\sum_{k}M_{k}$. We show the variance
for the partially derandomized strategy with given measurements $T$. We denote
$\bm{e}_{k}$ containing all $Q^{(k)}$ element-wise commute with basis
$P^{(k)}$, and denote $s_{k}$ as the total number of times that $Q^{(k)}$ is
effectively measured, which is given by
$s_{k}=\sum_{P\in\mathcal{M}}\delta_{Q^{(k)}\triangleright P}$. Let
${t}_{j,k}$ be the measurement outcome of the $j$th observable $Q^{(j)}$
measured with the basis $P^{(k)}$ is $+1$. The measurement outcome associated
with the measurement $P^{(k)}$ for observable $Q^{(j)}$ is thus
$\hat{v}_{j,k}=2{t}_{j,k}/M_{k}-1$. As such, the estimator can be expressed by

$\hat{v}=\sum_{k}\hat{v}_{k}=\sum_{k}\sum_{j:Q^{(j)}\in\bm{e}_{k}}\frac{\alpha_{j}M_{k}}{s_{j}}\hat{v}_{j,k}.$
(20)

One can check that if $M_{k}>0$ ($\forall k$) holds, i.e., every observable is
assigned at least one measurement basis (one sample), the estimation in Eq.
(20) is unbiased.

The variance of the estimator $\hat{v}$ is given by

$\textrm{Var}[\hat{v}]=\sum_{k}M_{k}\sum_{j,j^{\prime}:Q^{(j)},Q^{(j^{\prime})}\in\mathcal{S}_{k}}\frac{1}{s_{j}s_{j^{\prime}}}\alpha_{j}\alpha_{j^{\prime}}\operatorname{Cov}\left(\hat{v}_{j,k},\hat{v}_{j^{\prime},k}\right).$
(21)

Here, we use the fact that measurement outcomes obtained from different
$P^{(k)}$ are independent since the measurements $P^{(k)}$ are independent of
each other. We also note that the outcomes $\hat{v}_{j,k}$ are correlated, so
the variance in Eq. (21) depends on the covariance
$\operatorname{Cov}\left(\hat{v}_{j,k},\hat{v}_{j^{\prime},k}\right)$.

##  Appendix E Relationship between cost function and variance

Let $o_{j}:=f(P,Q^{(j)},\mathcal{K})\mu\left(P,Q^{(j)}\right)$ be the
estimation of $\tr\left(\rho Q^{(j)}\right)$. The cost function in the
manuscript is selected as
$\sum_{j}{\alpha_{j}}^{2}\mathbb{E}\left[o_{j}^{2}\right]=\sum_{j}{\alpha_{j}}^{2}/\chi(Q^{(j)})$,
to evaluate $\text{Var}\left(v\right)$. In the following, we prove that
$\text{Var}\left(v\right)\leq
m\sum_{j}{\alpha_{j}}^{2}\mathbb{E}\left[o_{j}^{2}\right]$.

By Eq. (12), we have

$\displaystyle\mathrm{Var}(\hat{v})$
$\displaystyle\leq\sum_{j,k}\alpha_{j}\alpha_{k}g(Q^{(j)},Q^{(k)})\tr\left(\rho
Q^{(j)}Q^{(k)}\right)$ (22)
$\displaystyle=\sum_{j}\alpha_{j}^{2}\mathbb{E}\left[o_{j}^{2}\right]+\sum_{j\neq
k}\alpha_{j}\alpha_{k}\frac{\sum_{P:Q^{(j)}\triangleright
P,Q^{(k)}\triangleright
P}\mathcal{K}(P)}{\chi(Q^{(j)})\chi(Q^{(k)})}\tr\left(\rho
Q^{(j)}Q^{(k)}\right)$ (23)

and

$\displaystyle\sum_{j\neq
k}\alpha_{j}\alpha_{k}\frac{\sum_{P:Q^{(j)}\triangleright
P,Q^{(k)}\triangleright
P}\mathcal{K}(P)}{\chi(Q^{(j)})\chi(Q^{(k)})}\tr\left(\rho
Q^{(j)}Q^{(k)}\right)$ (24) $\displaystyle\leq\sum_{j\neq
k}\alpha_{j}\alpha_{k}\frac{\sum_{P:Q^{(j)}\triangleright
P,Q^{(k)}\triangleright P}\mathcal{K}(P)}{\chi(Q^{(j)})\chi(Q^{(k)})}$ (25)
$\displaystyle\leq\sum_{j\neq
k}\alpha_{j}\alpha_{k}\frac{\min(\chi(Q^{(j)}),\chi(Q^{(k)}))}{\chi(Q^{(j)})\chi(Q^{(k)})}$
(26) $\displaystyle=\sum_{j\neq
k}\alpha_{j}\alpha_{k}\frac{1}{\max(\chi(Q^{(j)}),\chi(Q^{(k)}))}$ (27)
$\displaystyle\leq\sum_{j<k}(\alpha_{j}^{2}+\alpha_{k}^{2})\frac{1}{\max(\chi(Q^{(j)}),\chi(Q^{(k)}))}$
(28)
$\displaystyle\leq\left(m-1\right)\sum_{j}\alpha_{j}^{2}\frac{1}{\chi(Q^{(j)})}$
(29)

As shown in Eq. (22), $\mathbb{E}\left[o_{j}o_{k}\right]$ is associated with
the quantum state $\rho$, and it is unknown for us, while it can be bounded by
Eq. (LABEL:eq:var_bounded). Hence we utilize
$\sum_{j}\absolutevalue{\alpha_{j}}^{2}\mathbb{E}\left[o_{j}^{2}\right]$ as
our cost function.

##  Appendix F Variance comparison

We compare the variances of different measurement schemes in Table 3, where
the initial point is directly chosen from Algorithm 1. Here we generate the
measurement distribution by choosing $T=1000$ in Eq. (15). With a negligible
small error $\varepsilon_{0}$, we find that our method has a much smaller
variance than that of LDF-grouping, and LBCS. The improvement becomes more
prominent for larger molecules (approximately one order compared to the
classical shadow methods), which indicates its effectiveness for large
practical problems with a limited number of measurements.

Table 3: Estimation variances computed on the ground state of the molecular Hamiltonian (under the JW-encoding). The number of qubits is noted in the bracket in the first column, from 4 qubits to 14 qubits. The first 3 columns are the variance of LDF-grouping and OGM algorithms. The last column is the initial error of OGM. Molecule |  | variance | $\varepsilon_{0}$
---|---|---|---
LDF | LBCS [27] | OGM | OGM
H2 ($4$) | 0.402 | 1.86 | 0.424 | 0
H2 ($8$) | 22.3 | 17.7 | 5.51 | 0
LiH ($12$) | 54.2 | 14.8 | 3.09 | $9.6\cdot 10^{-5}$
BeH2 ($14$) | 135 | 67.6 | 15.44 | $6.6\cdot 10^{-4}$
H2O ($14$) | 1040 | 258 | 39.64 | 0.053

##  Appendix G Numerical results and discussions

In this section, we numerically show the advantages of our OGM algorithm
compared with $l_{1}$-sampling, LDF Grouping, LBCS, and the derandomized CS
algorithm by computing the corresponding variances and errors.

Table 4 shows the comparison of variance of OGM, $l_{1}$-sampling, LDF
Grouping, and LBCS algorithms under different fermionic-to-qubit encodings,
including JW, bk, and parity encodings. The last column is the deviation of
the OGM algorithm after a small perturbation of the cost function as
introduced in the main text.

Table 4: Variance of estimations computed on the ground state of the molecular Hamiltonian with different encoding methods. The first 4 columns are the variance of $l_{1}$-sampling, LDF-grouping, and OGM algorithms. The last column is the corresponding initial error of algorithm OGM. Molecule |  | variance | $\varepsilon_{0}$
---|---|---|---
$l_{1}$ | LDF | LBCS [27] | OGM | OGM
H2($4$jw) | 2.536 | 0.402 | 1.86 | 0.424 | 0
H2($4$bk) | 2.539 | 0.193 | 0.541 | 0.297 | 0
H2($4$parity) | 2.539 | 0.193 | 0.541 | 0.297 | 0
H2 ($8$jw) | 119.8 | 22.3 | 17.7 | 5.51 | 0
H2 ($8$bk) | 124.9 | 38.4 | 19.5 | 5.66 | $8\cdot 10^{-6}$
H2 ($8$parity) | 124.9 | 38.0 | 18.9 | 6.96 | 0
LiH ($12$jw) | 145.4 | 54.2 | 14.8 | 3.09 | $9.6\cdot 10^{-5}$
LiH ($12$bk) | 138.5 | 75.5 | 68.0 | 3.53 | $1.74\cdot 10^{-3}$
LiH ($12$parity) | 138.5 | 85.8 | 26.5 | 5.52 | $3.03\cdot 10^{-4}$
BeH2 ($14$jw) | 453.4 | 135 | 67.6 | 15.44 | $6.6\cdot 10^{-4}$
BeH2 ($14$bk) | 464.9 | 197 | 238 | 17.84 | $3.6\cdot 10^{-3}$
BeH2 ($14$parity) | 446 | 239 | 130 | 17.28 | $3.42\cdot 10^{-3}$
H2O ($14$jw) | 4367 | 1040 | 258 | 39.64 | 0.053
H2O ($14$bk) | 5141 | 2090 | 1360 | 81.59 | 0.065
H2O ($14$parity) | 5017 | 2670 | 429 | 42.91 | 0.065

We compare the estimation accuracy with $1000$ measurements for molecules H2,
LiH, BeH2 and H2O with JW, BK and parity encodings in Table 5, where the
initialized probability for the OGM algorithm is chosen directly from
Algorithm 1.

Table 5: Error of estimations with 1000 samples for the ground state of the corresponding molecules with LDF-grouping, LBCS, Derandmized, and OGM algorithms. Molecule | LDF | LBCS [27] | Derand [33] | OGM
---|---|---|---|---
H2($4$jw) | 0.019 | 0.043 | 0.018 | 0.011
H2($4$bk) | 0.014 | 0.025 | 0.029 | 0.016
H2($4$parity) | 0.016 | 0.016 | 0.027 | 0.017
H2 ($8$jw) | 0.149 | 0.128 | 0.067 | 0.051
H2 ($8$bk) | 0.203 | 0.143 | 0.049 | 0.041
H2 ($8$parity) | 0.214 | 0.138 | 0.058 | 0.053
LiH ($12$jw) | 0.231 | 0.122 | 0.063 | 0.036
LiH ($12$bk) | 0.293 | 0.283 | 0.067 | 0.033
LiH ($12$parity) | 0.294 | 0.145 | 0.061 | 0.039
BeH2 ($14$jw) | 0.426 | 0.275 | 0.103 | 0.072
BeH2 ($14$bk) | 0.462 | 0.527 | 0.104 | 0.082
BeH2 ($14$parity) | 0.547 | 0.355 | 0.104 | 0.068
H2O ($14$jw) | 1.090 | 0.549 | 0.257 | 0.129
H2O ($14$bk) | 1.619 | 1.073 | 0.274 | 0.174
H2O ($14$parity) | 1.476 | 0.708 | 0.336 | 0.132
NH3 ($16$jw) | 1.063 | 0.484 | 0.225 | 0.151
NH3 ($16$bk) | 0.820 | 0.571 | 0.282 | 0.103
NH3 ($16$parity) | 2.018 | 0.663 | 0.294 | 0.173

##  Appendix H Error of the estimation

We leverage root-mean squared error to quantify the error of the estimation.
In each iteration, we generate an estimation $\hat{v}_{i}$ by independently
performing $T$ measurements of initial state $\rho$. For $N$ independent
repetitions, we get the average error of $T$ samples as

$\displaystyle\varepsilon_{v}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}\left(\hat{v}_{i}-\tr(\rho
O)\right)^{2}}.$ (31)

We plot the figure to show that the average error will fluctuate in a small
range after more than 10 iterations.

Figure 5: The average errors of different repetitions $N$ for H2 molecule
(8-qubit).

In our simulation experiment of the main file (Table 1 and Fig. 2), we choose
$N=100$ for the molecules in which the number of qubits is less than 14. For
NH3 molecule, we let $N=20$. Nevertheless, the experimental result on the IBM
Q device is an average of 12 rounds due to the high cost of the pending time.

##  Appendix I Experimental results

The numerical study ignored device errors, and how the noise in realistic
hardware affects the measurement efficiency is critical for studying their
practical performance with realistic quantum devices. To further demonstrate
the advantage of our OGM method with current quantum devices, we implement and
compare the measurement schemes on the IBM quantum cloud hardware with device
imperfections. We aim to estimate
$\tr(\ket{\psi}\bra{\psi}\bm{\mathrm{O}}_{H_{2}})$ with the GHZ state
$\ket{\psi}=({\ket{0000}+\ket{1111}})/{\sqrt{2}}$ and the four-qubit
Hamiltonian $\bm{\mathrm{O}}_{H_{2}}$ of the $H_{2}$ molecule under the JW-
encoding. We note that the GHZ state has a much larger variance compared to
the ground state, and thus could be a suitable testbed to compare the
performance of different measurement schemes. In Fig. 6, we compare estimation
errors using the $l_{1}$-sampling, LDF-grouping, LBCS, derandomized CS, and
the OGM method with a different number of copies (samples) of the prepared
entangled state. We evaluate the error by comparing the reference results
obtained using the OGM method with 49140 samples.

Figure 6: Comparison of OGM with $l_{1}$-sampling, LDF-grouping, LBCS, and
derandomized CS using (a) the IBM classical simulator (Repeat 100 rounds) and
(b) the IBMQ cloud devices ibmq_athens (Repeat 12 rounds).