Efficient evaluation of quantum observables using entangled measurements

ABSTRACT The advent of cloud quantum computing has led to the rapid development of quantum algorithms. In particular, it is necessary to study variational quantum-classical hybrid

algorithms, which are executable on noisy intermediate-scale quantum (NISQ) computers. Evaluations of observables appear frequently in the variational quantum-classical hybrid algorithms for

NISQ computers. By speeding up the evaluation of observables, it is possible to realize a faster algorithm and save resources of quantum computers. Grouping of observables with separable

measurements has been conventionally used, and the grouping with entangled measurements has also been proposed recently by several teams. In this paper, we show that entangled measurements

enhance the efficiency of evaluation of observables, both theoretically and experimentally, by taking into account the covariance effect, which may affect the quality of evaluation of

observables. We also propose using a part of entangled measurements for grouping to keep the depth of extra gates constant. Our proposed method is expected to be used in conjunction with

other related studies. We hope that entangled measurements would become crucial resources, not only for joint measurements but also for quantum information processing. SIMILAR CONTENT BEING

VIEWED BY OTHERS CORRELATIONS FOR COMPUTATION AND COMPUTATION FOR CORRELATIONS Article Open access 10 February 2021 QUANTUM ZENO MONTE CARLO FOR COMPUTING OBSERVABLES Article Open access 12

March 2025 QUANTUM ALGORITHMIC MEASUREMENT Article Open access 16 February 2022 INTRODUCTION It has been reported that many researchers have been working tirelessly to build a fault-tolerant

quantum computer and quantum algorithms for years. Recently, the development of quantum computing has been huge research attention. The main reason is the rise of the noisy

intermediate-scale quantum (NISQ) computers1, which have 50–100 qubits, and its quantum error corrections are not yet implemented. They are developed using superconducting2 and trapped

ion3,4 systems. Although the number of qubits is small and the fidelity of operations is not very high, programmable quantum computers have been made available, not only for researchers but

also for public users. For instance, IBM released IBM Q Experience in 2016, Rigetti released Quantum Cloud Services in 2018, and IonQ is going to start Quantum Cloud Service in 2019.

Software stacks for NISQ computers have also been extensively developed, for instance, Qiskit5 by IBM, Forest6 by Rigetti, and Cirq7 by Google. Researchers are looking for killer

applications for NISQ. Quantum chemistry is one of the biggest targets2,8,9,10. Optimization problem11,12,13 and machine learning14,15,16,17 are also attractive applications. For finance,

some algorithms have also been proposed18,19,20. In this paper, we focus on variational quantum eigensolver (VQE), which is a quantum-classical hybrid algorithm proposed by Peruzzo et al.8

to compute eigenvalues and eigenvectors of matrices such as Hamiltonians. VQE has been applied in various fields such as quantum chemistry21 and is extensively being studied because NISQ

computers can handle only short-depth circuits and it is necessary to combine them with classical computers. Such hybrid algorithms are relatively robust to noise compared with full-quantum

algorithms. Interested readers should refer to a review by McArdle et al.22 for details of VQE. VQE minimizes the expectation value of the input operator by varying the quantum state

\(\left|\psi (\theta )\right\rangle\) with parameters _θ_. The expectation value of an operator _A_ with parameters _θ_ can be expressed as 〈_A_〉_θ_ = 〈_ψ_(_θ_)∣_A__ψ_(_θ_)〉. In quantum

chemistry, an operator _A_ is usually a qubit Hamiltonian mapped from a fermionic Hamiltonian of molecules. A qubit Hamiltonian can be written as a linear combination of tensor products of

Pauli operators including the identity operator; i.e., \(A=\mathop{\sum }\nolimits_{i = 1}^{n}{a}_{i}{P}_{i}\), where the tensor product of Pauli operators \({P}_{i}\in {\{{\sigma

}^{x},{\sigma }^{y},{\sigma }^{z},I\}}^{\otimes N}\) is referred to as Pauli string. VQE minimizes the expectation value by applying optimization algorithms for classical computers as

follows: $$\mathop{\min }\limits_{\theta }{\langle A\rangle }_{\theta }=\mathop{\min }\limits_{\theta }\langle \psi (\theta )| A\psi (\theta )\rangle$$ (1) $$\quad =\mathop{\min

}\limits_{\theta }\mathop{\sum }\limits_{i = 1}^{n}{a}_{i}\langle \psi (\theta )| {P}_{i}\psi (\theta )\rangle .$$ (2) Quantum computers can be used to evaluate the expectation values of

Pauli strings 〈_ψ_(_θ_)∣_P__i__ψ_(_θ_)〉. Algorithms require a large number of executions of quantum circuits to evaluate the expectation values of observables. According to Wecker et al.23,

“the required number of measurements is astronomically large for quantum chemistry applications to molecules”. VQE consists of three nested iterations: * Outer iteration: to update the

parameters _θ_ of quantum state \(\left|\psi (\theta )\right\rangle\), * Middle iteration: to evaluate the expectation value by calculating the weighted sum of Pauli strings, and * Inner

iteration: to evaluate the expectation value of a Pauli string through sampling. The inner iteration evaluates Pauli strings as an expectation value with multiple samples. This requires

_O_(_ϵ_−2) samples for the statistical error _ϵ_. To reduce the inner iteration, Wang et al.24 proposed another theoretical approach. Herein, we focus on how to reduce the number of

measurements in the middle iteration. If Pauli strings are commutative, it implies that they are compatible; i.e., they are jointly measurable. McClean et al.25 suggested a grouping of

jointly measurable Pauli strings by using sequential measurements and pointed out the covariance effect. Bravyi et al.26 introduced the notion of grouping based on a tensor product basis

(TPB). Kandala et al.2 addressed the grouping of qubit Hamiltonians using TPB and analyzed the distribution of the standard error of its expectation value numerically. Incompatibility by TPB

can be represented by a graph called Pauli graph. It has been known that the grouping of Pauli strings can be reduced to the coloring problem of the Pauli graph. Although the graph coloring

problem is an NP-complete problem, we can apply heuristic algorithms to obtain groups of Pauli strings, e.g., the largest-degree-first coloring (LDFC) algorithm. In this paper, we propose

the use of entangled measurements in addition to TPB for the grouping of Pauli strings. Entangled measurements are measurements of entangled observables. Entangled observables are described

by positive operator-valued measures that are not separable positive operator-valued measures27. The advantage of using entangled measurements is that it makes it possible to achieve a

smaller number of groups; however, it is necessary to add extra CNOT gates to construct a measurement circuit corresponding to the group, which may affect the fidelity of the resulting

expectation value. Therefore, we evaluate the properties of our grouping from both theoretical and experimental viewpoints. Furthermore, we also propose a sampling strategy to mitigate the

covariance effect by a group of qubit Hamiltonians. The contributions of this paper are as follows: * 1. Grouping of Pauli strings with a part of entangled measurements. * 2. Measurement

strategy based on the sizes of groups to suppress the covariance effects. * 3. Evaluation of the effect of the errors caused by additional CNOT gates. * 4. Proof-of-concept demonstration of

a simple Hamiltonian on real quantum computers. RESULTS EVALUATION OF PAULI STRINGS Let us consider the evaluation of the expectation values of quantum observables. Target observables are

mainly Hamiltonians. Such observables of the multipartite qubit systems can be written as a linear combination of the Pauli strings \(A=\mathop{\sum }\nolimits_{i = 1}^{n}{a}_{i}{P}_{i},\)

where _a__i_ denotes a real number and _P__i_ denotes an _N_-qubit Pauli string. When the observables are not for the qubit systems, the Jordan–Wigner transformation for fermions or the

Jordan–Schwinger transformation for bosons can be used to map the qubit systems from other systems. Herein, we present the transformations for fermions in more detail. The second quantized

fermionic Hamiltonian can be expressed as $$H=\mathop{\sum }\limits_{ij}{h}_{ij}{c}_{i}^{\dagger }{c}_{j}+\frac{1}{2}\mathop{\sum }\limits_{ijkl}{h}_{ijkl}{c}_{i}^{\dagger }{c}_{j}^{\dagger

}{c}_{l}{c}_{k},$$ (3) where _h__i__j_ denotes kinetic and potential energy and _h__i__j__k__l_ denotes interaction. Herein, _c__i_ denotes an annihilation operator of the _i_-th fermion,

and \({c}_{j}^{\dagger }\) denotes a creation operator of the _j_-th fermion. There are three well-known transformations from fermionic systems to qubit systems: the Jordan–Wigner

transformation28, that was originally proposed for lattice systems, parity transformation, and Bravyi–Kitaev transformation29,30. Note that the difference between transformations can affect

the results of grouping. When one prepares a quantum state \(\left|\psi \right\rangle\) in a quantum computer, the expectation value of a quantum observable _A_ can be expressed as 〈_A_〉 = 

〈_ψ_∣_A__ψ_〉. The expectation values of Pauli operators can be evaluated as follows. First, a measurement in the computational basis is available in a quantum computer. Then, by employing a

single-qubit unitary rotation before the measurements, we can implement the measurements of other bases. Calculation \(\langle A\rangle =\mathop{\sum }\nolimits_{i = 1}^{n}{a}_{i}\langle

{P}_{i}\rangle\) gives the expectation value of _A_. GROUPING PAULI STRINGS WITH TPB Some Pauli strings are simultaneously diagonalizable by using the tensor product of bases

\(\{{\mathcal{X}},{\mathcal{Y}},{\mathcal{Z}}\}\) where \({\mathcal{X}}=\left\{\left|0\right\rangle \pm \left|1\right\rangle \right\}\), \({\mathcal{Y}}=\left\{\left|0\right\rangle \pm

i\left|1\right\rangle \right\}\), and \({\mathcal{Z}}=\left\{\left|0\right\rangle ,\left|1\right\rangle \right\}\). Herein, the sets of bases are referred to as TPB sets. This implies that

some Pauli strings that are simultaneously diagonalizable by using TPB are jointly measurable by TPB. This also implies that such Pauli strings can be grouped and we can obtain their

expectation values at the same time. We introduce the Pauli graph _G_ = (_V_, _E_) of an observable _A_ = ∑_i__a__i__P__i_ as follows: nodes _V_ correspond to Pauli strings _P__i_ and edge

(_u_, _v_) ∈ _E_ spans if Pauli strings _u_ and _v_ are not jointly measurable by TPB. Further, a coloring of the Pauli graph gives groups of the Pauli strings that are jointly measurable.

For instance, Qiskit5 adopts the LDFC algorithm, which first sorts the nodes in descending order of degree and then assigns the smallest color number not used by its colored neighbors. The

details of the Pauli graph and LDFC algorithm are presented in Appendix A of the Supplementary Information. It executes fast for practical graphs of interest, and the number of the resulting

groups is close to the lower bound by the max clique of the Pauli graph (see Table 1 for details). GROUPING WITH TPB AND ENTANGLED MEASUREMENTS Measurements by TPB are separable

measurements. We propose taking advantage of entangled measurements. We introduce a new grouping approach for Pauli strings that uses not only TPB but also entangled measurements such as

Bell measurements to reduce the number of measurements. For instance, the expectation values of _σ__x__σ__x_, _σ__y__σ__y_, and _σ__z__σ__z_ cannot be obtained simultaneously from TPB

measurements. It requires three types of measurements to compute the expectation values of _σ__x__σ__x_, _σ__y__σ__y_, and _σ__z__σ__z_; however, these Pauli strings can be measured jointly

using Bell measurement (see the Methods section for details). Simultaneous diagonalization provides a joint measurement using entangled observables. The incompatibility of Pauli strings can

be checked by parity of the number of different Pauli operators _σ__x_, _σ__y_, and _σ__z_. It is possible to construct an extended Pauli graph based on this incompatibility and calculate

the number of groups using the LDFC algorithm, which we refer to as “ALL” in the subsequent sections. We will calculate the number of groups using all measurements and LDFC later (Table 1).

However, the computational cost of the circuit construction and the circuit depth increase according to the size of entanglements. Therefore, it may not be practical for NISQ computers to

use all measurements due to the fidelity of operations of NISQ computers, especially multi-qubit operations. To mitigate the drawback, we propose another approach that involves the use of a

part of the entanglement of the observables. It consists of two phases: choosing a set of entangled observables and grouping of Pauli strings with TPB and the set of entangled observables.

The first phase is to choose entangled measurements (e.g., Bell measurements and omega measurements31). We would present details of the Bell measurements in the Method section and present

other two-qubit entangled measurements in Appendix B of the Supplementary Information. One constructs quantum circuits corresponding to the entangled measurements. This task can be done by

using simultaneous diagonalization as a preprocessing technique. We can alternatively use other methods based on Clifford gates, which was proposed recently32,33,34. Because quantum circuits

can be generated in advance in this phase, therefore, the cost of circuit construction in the next phase can be reduced. The second phase is to construct groups of Pauli strings using TPB

and the entangled measurements chosen in the first phase. It is possible to construct a Pauli graph in the same way as using TPB-based methods and sort the nodes in descending order of

degree. Then, the nodes can be merged if they are jointly measurable by using TPB and the entangled measurements. It is noteworthy that this joint measurability depends on merge history. If

one merges nodes, it is necessary to use the entangled measurement at particular positions of Pauli strings, and after that, it is not possible to change the measurement. The merged nodes

correspond to groups of measurements, and one can construct quantum circuits corresponding to the groups and perform the measurements. We refer to the grouping that involves the use of TPB

and Bell measurements as “TPB+Bell”, and the grouping with TPB and all two-qubit measurements as “TPB+2Q”. Refer to the Methods section for details of the grouping algorithm. Entanglement of

observables could be considered as a resource of a joint measurement. In experiments with NISQ computers, available entangled measurements are limited because of multi-qubit gate errors

that may occur. Therefore, we need to consider algorithms with available measurements. For instance, if one uses two-qubit entangled measurements, only one entangler (e.g., CNOT gate) is

required for each of the qubits. Our proposed method requires constant depth measurement circuits for fixed entangled measurements. The advantage of our approach is that we can adjust the

depth of the additional circuits for entangled measurements by considering errors due to multi-qubit gates. STANDARD ERROR CAUSED BY THE GROUPING OF PAULI STRINGS McClean et al.25 discussed

covariance effects and showed that the additional covariance caused as a result of grouping may require more measurements. However, Kandala et al.2 numerically verified that the grouping

with TPB has fewer errors than the no-grouping strategy for some molecules. It is noteworthy that the square of the error is in inverse proportion to the number of samples. We show

mathematically that if the number of samples in each group is in proportion to the size of the group, the standard error of a grouping is smaller than that of no-grouping in Appendix C of

the Supplementary Information, where the total numbers of samples for the grouping and no-grouping strategies are the same. NUMBER OF GROUPS We applied four types of grouping methods (one

with TPB; one with TPB and Bell measurements; one with TPB and all two-qubit entangled measurements; and one with all measurements) to the following molecules: LiH, BeH2, H2O, NH3, and HCl.

We also computed the maximal clique sizes of Pauli graphs for TPB by applying the MCQD algorithm35. We ran MCQD on Intel Xeon E5-2690 CPU with a 1-hour time limit and were able to observe

the maximum cliques for all Pauli graphs except NH3 Parity and Bravyi–Kitaev. Note that the Hamiltonians of the molecules are presented as ancillary files in a previous study26. We present a

comparison of the numbers of groups in Table 1. The clique sizes with ‘*’ are the maximum. JW and BK are Jordan–Wigner and Bravyi–Kitaev transformations, respectively. TPB, TPB+Bell,

TPB+2Q, and ALL denote the groupings using TPB, TPB and Bell measurements, TPB and all two-qubit entangled measurements, and all measurements, respectively. The grouping with TPB yielded

several groups that are slightly larger than the clique sizes of the Pauli graphs. It should be noted that the grouping with TPB cannot yield fewer numbers of groups than the clique size

because it is based on a coloring algorithm (see Eq. 64.136). On the other hand, the groupings using entangled measurements (TPB+Bell, TPB+2Q, and ALL) achieved fewer numbers than the clique

sizes. The grouping with TPB and two-qubit entangled measurements (TPB+2Q) does not always result in a fewer number of groups than those obtained by grouping with TPB and Bell measurements

(TPB+Bell). This implies that our heuristic algorithm cannot take full advantage of more choices of measurements. We also observed that the grouping with all measurements (ALL) does not

always result in the smallest number of groups among all methods. This implies that LDFC cannot be used to obtain good solutions for the extended Pauli graphs. The number of groups depends

on the type of transformations as well as the grouping methods used. For instance, for Jordan–Wigner transformation, TPB+Bell results in a smaller number of groups for most molecules than

groupings using TPB and TPB+2Q. We observed that the entangled measurements are effective in reducing the number of measurements of Pauli strings. However, there exist various errors in

using NISQ computers, especially the two-qubit gate error that is generally much larger than a one-qubit error. In the next section, we discuss the effects of additional CNOT gates

introduced in entangled measurements. EFFECT OF ADDITIONAL CNOT GATES Entangled measurements require additional two-qubit gates. We evaluate the effect of additional CNOT gates for a Bell

measurement in one of the simplest models, two-qubit antiferromagnetic Heisenberg model, whose Hamiltonian can be expressed as $$H={\sigma }^{x}{\sigma }^{x}+{\sigma }^{y}{\sigma

}^{y}+{\sigma }^{z}{\sigma }^{z}.$$ (4) Herein, we set the coupling constant to be 1 for simplicity. These Pauli strings cannot be grouped by using TPB but can be grouped by using a Bell

measurement. We compute the expectation value with the ground state using a noise model in Qiskit Aer and readout error mitigation37 in Qiskit Ignis. We assigned 2000 samples to each group

of no-grouping (three groups) and 6000 samples to a group of the grouping obtained by using a Bell measurement (one group). We assume that the one-qubit readout errors are _p_(1∣0) = 0.01

and _p_(0∣1) = 0.1, and the one-qubit depolarizing error is 0.001. We simulated the expectation value of the Hamiltonian by varying the two-qubit depolarizing error. See Table 2 for the

results. The row “No-grouping (raw)” denotes the expectation values with the standard error, where we did not apply the readout error mitigation. On the other hand, “No-grouping (mit)”

denotes the results obtained when the readout error mitigation was applied. The rows of “Bell (raw)” and “Bell (mit)” show the results of the grouping of a Bell measurement with and without

the readout error mitigation, respectively. We observed that the grouping with a Bell measurement achieved comparable expectation value with less standard error compared with no-grouping up

to two-qubit error 0.010. The grouping with a Bell measurement resulted in worse expectation values with two-qubit error more than 0.010 owing to the extra CNOT gate introduced by using the

Bell measurement. It should be noted that we implemented our program with Qiskit Terra 0.7.2, Qiskit Aer 0.1.1, Qiskit Ignis 0.1.0, and Qiskit Aqua 0.4.1. We also evaluated additional CNOT

gate effects using real quantum computers, IBM Q Tokyo and IBM Q Poughkeepsie (Table 3). Note that both have 20 qubits. We picked out the pair of qubits with the best fidelity based on the

property data of the devices when we executed the circuits. The properties of the devices, including connectivity and error distributions, can be found in the literature38. We observed that

the grouping obtained using the Bell measurement achieved comparable expectation value with less standard error compared with the no-grouping type. These experiments suggest that readout

error has a significant influence (more than the additional two-qubit error). VQE WITH ENTANGLED MEASUREMENTS We incorporate the grouping with Bell measurements into VQE to calculate the

ground state energy of the two-qubit antiferromagnetic Heisenberg model (4), and we use the no-grouping as the baseline. We compared the number of circuits to be converged. We used _R__y_

trial wave function with depth 1 as the variational form and the simultaneous perturbation stochastic approximation (SPSA)39 as the optimizer. We executed VQE algorithm with 40 iteration

steps. We applied the readout error mitigation and calibrated the mitigation data every 10 iteration steps of VQE. We fixed the number of executions of quantum circuits to 8192 samples,

i.e., the maximum number for a job of the IBM Q systems as of July 2019. See Fig. 1 for the results. The horizontal axis and the vertical axis represent the number of quantum circuits used

and expectation values of the Hamiltonian, respectively. VQE with a Bell measurement used one circuit for each iteration, whereas VQE without grouping used three circuits for each iteration.

We plotted the standard error as well as the expectation values, but the error bar is small enough to be overshadowed by point. We observed that VQE with a Bell measurement required fewer

circuits than VQE with no-grouping to converge. We will present more results and discuss them in Appendix D of the Supplementary Information. DISCUSSION In this paper, we presented the

efficient evaluation of Pauli strings with a part of entangled measurements. We propose reducing the number of groups of Pauli strings that are jointly measurable by using both TPB and a

part of entangled measurements. It is remarkable that grouping by using TPB and Bell measurements (TPB+Bell) produces as few number of groups as the grouping obtained by using all

measurements (ALL) for some molecules with the Jordan–Wigner transformation as shown in Table 1 as the depth of the additional CNOT gates required for TPB+Bell is constant, 1. Jordan–Wigner

transformation has an even number of Pauli _σ__x_ and _σ__y_ for the fermion Hamiltonian. This even structure does not appear in Bravyi–Kitaev and parity transformations. This property might

be fit for the Bell measurement, which is a joint measurement of _σ__x__σ__x_, _σ__y__σ__y_, and _σ__z__σ__z_. It should be noted that grouping using all measurements were obtained by

applying LDFC to the extended Pauli graph; thus, the solutions may be suboptimal, and they can be improved by using more sophisticated coloring algorithms. We also showed that if the number

of samples in each group is in proportion to the size of the group, the standard error obtained with grouping is always equal to or smaller than that with no-grouping. We discuss the

connectivity of qubits of NISQ computers. There are two types of NISQ computers: one has full connectivity (e.g., trapped ion systems) and the other has limited connectivity such as nearest

neighbor connectivity (e.g., superconducting systems). It might be difficult to realize a quantum circuit corresponding to entangled measurements for devices with limited connectivity of

qubits. There are two strategies to apply our proposed method for such a case: (1) one limits the grouping algorithm to adapt the connectivity or (2) one changes the initial layout of the

qubits. For the latter, our proposed method using two-qubit measurements needs one nonlocal gate per two qubits and then low connectivity. For example, a one-dimensional lattice is

sufficient to map the measurement circuits. Public quantum computers are available as cloud service today. The computation time is bounded by job time, and we refer to it as job bound. The

time needed for a job to be completed is equal to the sum of waiting and execution time. The execution time can be regarded as the execution time of the circuits included in the job. In

other words, execution time is roughly proportional to the total number of circuits to be executed. Therefore, reducing the number of circuits in grouping contributes to the improvement of

execution time. In the present study, we implement the entangled measurements using the Heisenberg picture in the software layer. There are other possible candidates for implementing joint

measurements. The entangled measurements can be implemented in the hardware layer40, called joint readout. The joint readout may make our proposal more accurate and precise. Direct or

indirect sequential measurements also provide joint measurements. To accelerate the iterations of VQE, several approaches have been discussed. An efficient partitioning using mean-field

approach was proposed by Izmaylov et al.41 It requires feedforward measurements, which are not implemented in the current devices. However, once the feedforward is implemented, we may

achieve better efficiency when it is used in combination with our proposed methods. A sequential minimal optimization method42 reduces the outer iteration. The proposed method converges

faster than previous optimizers and uses no hyperparameter. Fermionic representability conditions can be used to reduce the middle iterations43. Some efficiency improvements that do not

relate to iterations were studied44,45,46,47,48. Our proposed method can be used together with them. Let us briefly review the history of the grouping based on TPB. Kandala et al.2 used the

grouping by TPB in their experiments on some molecules. Qiskit5 presented the implementation of a coloring-based grouping algorithm of the Pauli graph in June 2018, which was released as

QISKit ACQUA 0.1.0. The grouping by TPB was also implemented in the OpenFermion49 v0.9.0 (December 2018) and PyQuil6 2.2 (January 2019). Verteletskyi et al.50 systematically studied the

heuristic algorithms for grouping using the TPB. Recently, many studies to enhance the evaluation of observables have been presented32,33,34,51,52,53,54,55. Entangled measurements have been

used either implicitly or explicitly in some studies32,33,34,53,54,55. In contrast to these studies that use all measurements, we employ TPB and a part of entangled measurements. Jena et

al.32 showed that grouping of Pauli strings is NP-hard in general qudit system. They discussed the case when the available gate set is limited to Clifford gates or single-qudit Clifford

gates, whereas we discuss the case where available measurements are limited. The diagonalization by Clifford operators corresponds to all measurements, and the diagonalization by using

single-qubit Clifford corresponds to TPB. Yen et al.33 proposed a conversion method from groups of commuting Pauli strings into TPB using unitary transformations. Their unitary

transformations were discussed in the Schrödinger picture, but they used all measurements in the Heisenberg picture and proposed efficient circuit construction using Clifford gates. Gokhale

et al.34 used entangled measurements to measure commuting Pauli strings and developed a circuit synthesis tool for joint measurement based on the stabilizer. Furthermore, their results have

been demonstrated experimentally in computing the ground state energy of deuteron on the IBM Q Tokyo. Crawford et al.53 proposed taking into account coefficients of Pauli strings for the

grouping to mitigate the covariance effect, whereas we propose an adjustment of the number of samples while taking into account the sizes of groups. A linear reduction of the number of

groups from _O_(_N_4) to _O_(_N_3) for molecular Hamiltonians has been proven in different ways54,55. Izmaylov et al.51 and Huggins et al.52 developed different methods that are not based on

a joint measurement of the Pauli strings. Jiang et al.56 used a Bell measurement on a system and an ancilla to implement a symmetric informationally complete POVM, whereas our proposal uses

a Bell measurement on systems. METHODS ENTANGLED MEASUREMENTS Herein, we introduce entangled measurements. Entanglement is a specific property of quantum theory and an essential concept in

quantum information science and technology. Entanglement is originally defined for quantum states. Bell states are one of the maximally entangled states. Bell states can be defined as

follows: $$\left|{\Phi }^{\pm }\right\rangle =\frac{1}{\sqrt{2}}\left|00\right\rangle \pm \frac{1}{\sqrt{2}}\left|11\right\rangle ,\left|{\Psi }^{\pm }\right\rangle

=\frac{1}{\sqrt{2}}\left|01\right\rangle \pm \frac{1}{\sqrt{2}}\left|10\right\rangle .$$ Entanglement of states can be extended to observables. As entanglement of states can be detected by

the violation of Bell-CHSH inequality57,58, an entanglement of observables can be detected by the violation of the dual Bell-CHSH inequality27. Measurements of entangled observables are

referred to as entangled measurements. Let us introduce examples of entangled measurements. The first example of entangled measurements is Bell measurements defined as the projective

measurements on Bell states. The Bell measurements are used in the quantum teleportation protocol59. A remarkable property of the Bell measurement is that expectation values of _σ__x_ ⊗

_σ__x_, _σ__y_ ⊗ _σ__y_, and _σ__z_ ⊗ _σ__z_ can be calculated from the result of the Bell measurement. This property is based on the following fact: $$\begin{array}{ccc}{\sigma }^{x}\otimes

{\sigma }^{x}&=&\left|{\Psi }^{+}\right\rangle \left\langle {\Psi }^{+}\right|+\left|{\Phi }^{+}\right\rangle \left\langle {\Phi }^{+}\right|-\left|{\Psi }^{-}\right\rangle

\left\langle {\Psi }^{-}\right|-\left|{\Phi }^{-}\right\rangle \left\langle {\Phi }^{-}\right|,\\ {\sigma }^{y}\otimes {\sigma }^{y}&=&\left|{\Psi }^{+}\right\rangle \left\langle

{\Psi }^{+}\right|+\left|{\Phi }^{-}\right\rangle \left\langle {\Phi }^{-}\right|-\left|{\Phi }^{+}\right\rangle \left\langle {\Phi }^{+}\right|-\left|{\Psi }^{-}\right\rangle \left\langle

{\Psi }^{-}\right|,\\ {\sigma }^{z}\otimes {\sigma }^{z}&=&\left|{\Phi }^{+}\right\rangle \left\langle {\Phi }^{+}\right|+\left|{\Phi }^{-}\right\rangle \left\langle {\Phi

}^{-}\right|-\left|{\Psi }^{+}\right\rangle \left\langle {\Psi }^{+}\right|-\left|{\Psi }^{-}\right\rangle \left\langle {\Psi }^{-}\right|.\end{array}$$ CNOT and Hadamard gates are needed to

implement the Bell measurement on a quantum computer. The quantum circuit is shown in Fig. 2. We will describe other useful entangled measurements in Appendix B of the Supplementary

Information. GROUPING ALGORITHM We propose a heuristic algorithm of grouping Pauli strings using TPB and a part of entangled measurements greedily. We first make a Pauli graph as the

grouping with TPB does and then merge nodes with high degrees if they are jointly measurable by given entangled measurements. To check whether a pair of Pauli strings is compatible, we

generate permutations of qubit positions and check if any of the entangled measurements can be applied to the position. The number of resulting groups depends on the order of measurements to

be applied in Algorithm 1. We let _E_ = {Bell, TPB} for ‘TPB+Bell’ and _E_ = {Bell, Omega-XX, Omega-YY, Omega-ZZ, Chi, TPB} for ‘TPB+2Q’ in our experiments. See Algorithms 1 and 2 for

details of the algorithm and Appendix B of the Supplementary Information for the definitions of the omega and chi measurements. DATA AVAILABILITY The data of the plots of VQE that support

the finding of this study are available from the corresponding authors upon reasonable request. CODE AVAILABILITY The software implementation used to group the Pauli strings and perform

entangled measurements is not publicly available. REFERENCES * Preskill, J. Quantum Computing in the NISQ era and beyond. _Quantum_ 2, 79 (2018). Google Scholar  * Kandala, A. et al.

Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. _Nature_ 549, 242–246 (2017). ADS  Google Scholar  * Hempel, C. et al. Quantum chemistry

calculations on a trapped-ion quantum simulator. _Phys. Rev. X_ 8, 031022 (2018). Google Scholar  * Lu, Y. et al. Global entangling gates on arbitrary ion qubits. _Nature_ 572, 363 (2019).

ADS  Google Scholar  * Abraham, H. et al. Qiskit: an open-source framework for quantum computing. https://doi.org/10.5281/zenodo.2562110 (2019). * Smith, R. S., Curtis, M. J. & Zeng, W.

J. A practical quantum instruction set architecture. Preprint at https://arxiv.org/abs/1608.03355 (2016). * Cirq. _Cirq: A python framework for creating, editing, and invoking Noisy

Intermediate Scale Quantum (NISQ) circuits._ https://github.com/quantumlib/Cirq (2018). * Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. _Nat. Commun._

5, 4213 (2014). ADS  Google Scholar  * Yung, M. H. et al. From transistor to trapped-ion computers for quantum chemistry. _Sci. Rep._ 4, 3589 (2014). Google Scholar  * Grimsley, H. R.,

Economou, S. E., Barnes, E. & Mayhall, N. J. An adaptive variational algorithm for exact molecular simulations on a quantum computer. _Nat. Commun._ 10, 3007 (2019). ADS  Google Scholar

  * Farhi, E., Goldstone, J. & Gutmann, S. A Quantum Approximate Optimization Algorithm. Preprint at https://arxiv.org/abs/1411.4028 (2014). * Guerreschi, G. G. & Matsuura, A. Y.

QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. _Sci. Rep._ 9, 6903 (2019). ADS  Google Scholar  * Shaydulin, R. et al. A hybrid approach for solving optimization problems

on small quantum computers. _Computer_ 52, 18–26 (2019). Google Scholar  * Havlíček, V. et al. Supervised learning with quantum-enhanced feature spaces. _Nature_ 567, 209–212 (2019). ADS 

Google Scholar  * Mitarai, K., Negoro, M., Kitagawa, M. & Fujii, K. Quantum circuit learning. _Phys. Rev. A_ 98, 032309 (2018). ADS  Google Scholar  * Schuld, M. & Killoran, N.

Quantum machine learning in feature hilbert spaces. _Phys. Rev. Lett._ 122, 040504 (2019). ADS  Google Scholar  * McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R. & Neven, H.

Barren plateaus in quantum neural network training landscapes. _Nat. Commun._ 9, 4812 (2018). ADS  Google Scholar  * Woerner, S. & Egger, D. J. Quantum risk analysis. _npj Quant. Inf._

5, 15 (2019). ADS  Google Scholar  * Stamatopoulos, N. et al. Option pricing using quantum computers. Preprint at https://arxiv.org/abs/1905.02666 (2019). * Egger, D. J., Gutiérrez, R. G.,

Mestre, J. C. & Woerner, S. Credit risk analysis using quantum computers. Preprint at https://arxiv.org/abs/1907.03044 (2019). * Moll, N. et al. Quantum optimization using variational

algorithms on near-term quantum devices. _Quant. Sci. Technol._ 3, 030503 (2018). ADS  Google Scholar  * McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. & Yuan, X. Quantum

computational chemistry. _Rev. Mod. Phys._ 92, 015003 (2020). ADS  MathSciNet  Google Scholar  * Wecker, D., Hastings, M. B. & Troyer, M. Progress towards practical quantum variational

algorithms. _Phys. Rev. A_ 92, 042303 (2015). ADS  Google Scholar  * Wang, D., Higgott, O. & Brierley, S. Accelerated variational quantum eigensolver. _Phys. Rev. Lett._ 122, 140504

(2019). ADS  Google Scholar  * McClean, J. R., Romero, J., Babbush, R. & Aspuru-Guzik, A. The theory of variational hybrid quantum-classical algorithms. _New J. Phys._ 18, 023023 (2016).

ADS  Google Scholar  * Bravyi, S., Gambetta, J. M., Mezzacapo, A. & Temme, K. Tapering off qubits to simulate fermionic Hamiltonians. Preprint at https://arxiv.org/abs/1701.08213

(2017). * Hamamura, I. Separability criterion for quantum effects. _Phys. Lett. A_ 382, 2573–2577 (2018). ADS  MathSciNet  MATH  Google Scholar  * Jordan, P. & Wigner, E.

ÜberdasPaulischeÄquivalenzverbot. _Z. Phys._ 47, 631–651 (1928). ADS  Google Scholar  * Bravyi, S. B. & Kitaev, A. Y. Fermionic quantum computation. _Ann. Phys._ 298, 210–226 (2002). ADS

  MathSciNet  MATH  Google Scholar  * Seeley, J. T., Richard, M. J. & Love, P. J. The Bravyi-Kitaev transformation for quantum computation of electronic structure. _J. Chem. Phys._ 137,

224109 (2012). ADS  Google Scholar  * Entanglion. https://entanglion.github.io/ (2018). Accessed on 29 Jan 2020. * Jena, A., Genin, S. & Mosca, M. Pauli partitioning with respect to gate

sets. Preprint at https://arxiv.org/abs/1907.07859 (2019). * Yen, T.-C., Verteletskyi, V. & Izmaylov, A. F. Measuring All Compatible Operators in One Series of Single-Qubit Measurements

Using Unitary Transformations. _J. Chem. Theory Comput._ 16, 2400–2409 (2020). Google Scholar  * Gokhale, P. et al. Minimizing state preparations in variational quantum eigensolver by

partitioning into commuting families. Preprint at https://arxiv.org/abs/1907.13623 (2019). * Konc, J. & Janežič, D. An improved branch and bound algorithm for the maximum clique problem.

_MATCH Commun. Math. Comput. Chem._ 58, 569–590 (2007). MathSciNet  MATH  Google Scholar  * Schrijver, A. _Combinatorial Optimization: Polyhedra and Efficiency_ (Springer, 2003). * Temme,

K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. _Phys. Rev. Lett._ 119, 180509 (2017). ADS  MathSciNet  Google Scholar  * Corcoles, A. D. et al.

Challenges and opportunities of near-term quantum computing systems. _Proc. IEEE_ 1–15 (2019). * Spall, J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient

approximation. _IEEE Trans. Autom. Control_ 37, 332–341 (1992). MathSciNet  MATH  Google Scholar  * Chow, J. M. et al. Detecting highly entangled states with a joint qubit readout. _Phys.

Rev. A_ 81, 062325 (2010). ADS  Google Scholar  * Izmaylov, A. F., Yen, T.-C. & Ryabinkin, I. G. 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). Google Scholar  * Nakanishi, K. M., Fujii, K. & Todo, S. Sequential minimal optimization for

quantum-classical hybrid algorithms. Preprint at https://arxiv.org/abs/1903.12166 (2019). * Rubin, N. C., Babbush, R. & McClean, J. Application of fermionic marginal constraints to

hybrid quantum algorithms. _New J. Phys._ 20, 053020 (2018). ADS  MathSciNet  Google Scholar  * Setia, K. & Whitfield, J. D. Bravyi-Kitaev Superfast simulation of electronic structure on

a quantum computer. _J. Chem. Phys._ 148, 164104 (2018). ADS  Google Scholar  * Babbush, R. et al. Low-depth quantum simulation of materials. _Phys. Rev. X_ 8, 011044 (2018). Google Scholar

  * Barkoutsos, P. K. et al. Quantum algorithms for electronic structure calculations: particle-hole Hamiltonian and optimized wave-function expansions. _Phys. Rev. A_ 98, 022322 (2018). ADS

  Google Scholar  * Romero, J. et al. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. _Quant. Sci. Technol._ 4, 014008 (2018). ADS  Google

Scholar  * Gard, B. T. et al. Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm. _npj Quant. Inf._ 6, 10 (2020). ADS  Google Scholar

  * McClean, J. R. et al. OpenFermion: the electronic structure package for quantum computers. _Quantum Sci. Technol._ Preprint at https://arxiv.org/abs/1710.07629 (2017). * Verteletskyi,

V., Yen, T.-C. & Izmaylov, A. F. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. _J. Chem. Phys._ 152, 124114 (2020). Google Scholar  *

Izmaylov, A. F., Yen, T.-C., Lang, R. A. & Verteletskyi, V. Unitary partitioning approach to the measurement problem in the Variational Quantum Eigensolver method. _J. Chem. Theory

Comput._ 16, 190–195 (2020). Google Scholar  * Huggins, W. J. et al. Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers. Preprint at

https://arxiv.org/abs/1907.13117 (2019). * Crawford, O. et al. Efficient quantum measurement of Pauli operators. Preprint at https://arxiv.org/abs/1908.06942 (2019). * Zhao, A. et al.

Measurement reduction in variational quantum algorithms. Preprint at https://arxiv.org/abs/1908.08067 (2019). * Gokhale, P. & Chong, F. T. _O_(_N_3) measurement cost for variational

quantum eigensolver on molecular hamiltonians. Preprint at https://arxiv.org/abs/1908.11857 (2019). * Jiang, Z., Kalev, A., Mruczkiewicz, W. & Neven, H. Optimal fermion-to-qubit mapping

via ternary trees with applications to reduced quantum states learning. _Quantum_ 4, 276 (2020). Google Scholar  * Bell, J. S. On the Einstein Podolsky Rosen paradox. _Physics_ 1, 195–290

(1964). MathSciNet  Google Scholar  * Clauser, J. F., Horne, M. A., Shimony, A. & Holt, R. A. Proposed experiment to test local hidden-variable theories. _Phys. Rev. Lett._ 23, 880–884

(1969). ADS  MATH  Google Scholar  * Bennett, C. H. et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. _Phys. Rev. Lett._ 70, 1895–1899

(1993). ADS  MathSciNet  MATH  Google Scholar  Download references ACKNOWLEDGEMENTS We thank Sergey Bravyi, Antonio Mezzacapo, Rudy Raymond, and Toshinari Itoko for fruitful discussions and

Ryo Takakura, Naixu Guo, and Kazuki Yamaga for helpful comments on the manuscript. I.H. has done part of this study during the internship at IBM Research – Tokyo in 2018. I.H. also

acknowledges support by Grant-in-Aid for JSPS Research Fellow (JP18J10310). AUTHOR INFORMATION AUTHORS AND AFFILIATIONS * Department of Nuclear Engineering, Kyoto University, Kyoto,

615-8540, Japan Ikko Hamamura * IBM Quantum, IBM Research – Tokyo, 19-21, Nihonbashi Hakozaki-cho, Chuo-ku, Tokyo, 103-8510, Japan Ikko Hamamura & Takashi Imamichi Authors * Ikko

Hamamura View author publications You can also search for this author inPubMed Google Scholar * Takashi Imamichi View author publications You can also search for this author inPubMed Google

Scholar CONTRIBUTIONS I.H. and T.I. performed the theoretical analysis and experiments. I.H. proved the theorem about the standard error. I.H. and T.I. contributed to write the paper.

CORRESPONDING AUTHORS Correspondence to Ikko Hamamura or Takashi Imamichi. ETHICS DECLARATIONS COMPETING INTERESTS A part of this work was included in a patent filed with the Japan Patent

Office and that is going to be filed with the US Patent and Trademark office. ADDITIONAL INFORMATION PUBLISHER’S NOTE Springer Nature remains neutral with regard to jurisdictional claims in

published maps and institutional affiliations. SUPPLEMENTARY INFORMATION SUPPLEMENTARY INFORMATION RIGHTS AND PERMISSIONS OPEN ACCESS This article is licensed under a Creative Commons

Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original

author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the

article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use

is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit

http://creativecommons.org/licenses/by/4.0/. Reprints and permissions ABOUT THIS ARTICLE CITE THIS ARTICLE Hamamura, I., Imamichi, T. Efficient evaluation of quantum observables using

entangled measurements. _npj Quantum Inf_ 6, 56 (2020). https://doi.org/10.1038/s41534-020-0284-2 Download citation * Received: 09 October 2019 * Accepted: 06 April 2020 * Published: 19 June

2020 * DOI: https://doi.org/10.1038/s41534-020-0284-2 SHARE THIS ARTICLE Anyone you share the following link with will be able to read this content: Get shareable link Sorry, a shareable

link is not currently available for this article. Copy to clipboard Provided by the Springer Nature SharedIt content-sharing initiative