  We introduce an approach for estimating the expectation values of arbitrary
$n$-qubit matrices $M \in \mathbb{C}^{2^n\times 2^n}$ on a quantum computer. In
contrast to conventional methods like the Pauli decomposition that utilize
$4^n$ distinct quantum circuits for this task, our technique employs at most
$2^n$ unique circuits, with even fewer required for matrices with limited
bandwidth. Termed the \textit{partial Pauli decomposition}, our method involves
observables formed as the Kronecker product of a single-qubit Pauli operator
and orthogonal projections onto the computational basis. By measuring each such
observable, one can simultaneously glean information about $2^n$ distinct
entries of $M$ through post-processing of the measurement counts. This
reduction in quantum resources is especially crucial in the current noisy
intermediate-scale quantum era, offering the potential to accelerate quantum
algorithms that rely heavily on expectation estimation, such as the variational
quantum eigensolver and the quantum approximate optimization algorithm.
