Computationally Efficient Quantum Expectation with Extended Bell Measurements

Abstract

Evaluating an expectation value of an arbitrary observable $A\in {\mathbb{C}}^{2^n\times 2^n}$ through naïve 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)\mathrm{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.

33 pages, 12 figures; most of the details of section 2 have been moved to the Appendix; added variance analysis and comparison with the classical shadow; code is available at https://github.com/ToyotaCRDL/extended-bell-measurements

References in corpus (4)

• A Quantum Approximate Optimization Algorithm
• Efficient estimation of Pauli observables by derandomization
• Variational quantum algorithm based on the minimum potential energy for solving the Poisson equation
• Pauli Partitioning with Respect to Gate Sets

Cited by in corpus (7)

• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Classical shadows based on locally-entangled measurements
• Variational quantum algorithm for generalized eigenvalue problems and its application to the finite element method
• Hardware-efficient entangled measurements for variational quantum algorithms
• Quantum topology optimization of ground structures using noisy intermediate-scale quantum devices
• Photonic variational quantum eigensolver using entanglement measurements
• A variational quantum eigensolver tailored to multi-band tight-binding simulations of electronic structures