Nearly Optimal Measurement Scheduling for Partial Tomography of Quantum States

Many applications of quantum simulation require one to prepare and then characterize quantum states by efficiently estimating $k$-body reduced density matrices ($k$-RDMs), from which observables of interest may be obtained. For instance, the fermionic 2-RDM contains the energy, charge density, and energy gradients of an electronic system, while the qubit 2-RDM contains the spatial correlation functions of magnetic systems. Naive estimation of such RDMs requires repeated state preparations for each matrix element, which makes for prohibitively large computation times. However, commuting matrix elements may be measured simultaneously, allowing for a significant cost reduction. In this work, we design schemes for such a parallelization with near-optimal complexity in the system size $N$. We first describe a scheme to sample all elements of a qubit $k$-RDM using only $\mathcal{O}(3^k{\log }^{k-1}N)$ unique measurement circuits, an exponential improvement over prior art. We then describe a scheme for sampling all elements of the fermionic 2-RDM using only $\mathcal{O}(N^2)$ unique measurement circuits, each of which requires only a local $\mathcal{O}(N)$-depth measurement circuit. We prove a lower bound of $\mathrm{\Omega }({\epsilon }^{-2}{N}^k)$ on the number of state preparations, Clifford circuits, and measurement in the computational basis required to estimate all elements of a fermionic $k$-RDM, making our scheme for sampling the fermionic 2-RDM asymptotically optimal. We finally construct circuits to sample the expectation value of a linear combination of $\omega$ anticommuting two-body fermionic operators with only $\mathcal{O}(\omega )$ gates on a linear array. These circuits allows for sampling any linear combination of fermionic 2-RDM elements in $\mathcal{O}(N^4/\omega )$ time, with a significantly lower measurement circuit complexity than prior art. Our results improve the viability of near-term quantum simulation of molecules and strongly correlated material systems.

Popular Summary

In quantum computing, one often extracts information by repeatedly preparing a quantum state and measuring certain parameters such as polarization or spin. However, as espoused in Heisenberg’s uncertainty principle, certain pairs of observables (such as position and momentum) cannot be measured simultaneously. New measurements must be made for each such “noncommuting” observable, which is an incredibly costly process. Here, we analyze one approach to streamlining noncommuting measurements and provide estimates for how much time it requires in certain quantum computing applications.

To save time on measurements of quantum states, one can group the observables of interest into mutually commuting subsets, or cliques, which together form a “clique cover.” However, minimizing the size of the clique cover (and thus minimizing the number of measurements required to estimate all observables) is, in general, a computationally complex problem. In this work, we prove asymptotic bounds on the size of clique covers and find schemes to achieve these bounds for the set of observables in fermionic and qubit systems, which are the most commonly required sets for quantum computing applications. We further use quantum circuits to perform measurements of such cliques and investigate various other measurement schemes.

This work gives critical bounds on the time required for near-term quantum computing applications, such as the variational quantum eigensolver, and gives explicit schemes to achieve these bounds.

Figure 1

Scaling of our Majorana partitioning scheme in the presence of between 0 and 4 symmetry constraints on the system. Dashed lines are from Eq. (6).

Figure 2

Schematics of the binary partition strategy described in the main text. (a) Scheme to construct $\mathcal{O}(\log N)$ cliques that contain all two-qubit operators. (b) Extension of the top scheme to a set of $\mathcal{O}({\log }^{2}N)$ cliques that contain all three-qubit operators.

Figure 3

Schematic of the fermionic partition strategy for generating cliques that contain all local fermionic operators. (a) A scheme to pair all indices in $\{1,\dots ,N\}$ in $\mathcal{O}(N)$ time steps. (b) The two cases to consider in our strategy to contain all 4-Majorana operators in only $\mathcal{O}(N^2)$ cliques.