  Evaluating an expectation value of an arbitrary observable $A\in{\mathbb
C}^{2^n\times 2^n}$ through na\"ive Pauli measurements requires a large number
of terms to be evaluated. We approach this issue using a method based on Bell
measurement, which we refer to as the extended Bell measurement method. This
analytical method quickly assembles the $4^n$ matrix elements into at most
$2^{n+1}$ groups for simultaneous measurements in $O(nd)$ time, where $d$ is
the number of non-zero elements of $A$. The number of groups is particularly
small when $A$ is a band matrix. When the bandwidth of $A$ is $k=O(n^c)$, the
number of groups for simultaneous measurement reduces to $O(n^{c+1})$. In
addition, when non-zero elements densely fill the band, the variance is
$O((n^{c+1}/2^n)\,{\rm tr}(A^2))$, which is small compared with the variances
of existing methods. The proposed method requires a few additional gates for
each measurement, namely one Hadamard gate, one phase gate and at most $n-1$
CNOT gates. Experimental results on an IBM-Q system show the computational
efficiency and scalability of the proposed scheme, compared with existing
state-of-the-art approaches. Code is available at
https://github.com/ToyotaCRDL/extended-bell-measurements.
