Sample efficient tomography via Pauli Measurements

It is increasingly important to understand how the cost scales of learning useful information as the experiments can control larger and larger quantum systems. Quantum state tomography refers to a procedure of reconstructing the density matrix of a quantum state from various measurements on multiple copies of the state. This fundamental task is crucial for quantum information experiments and theoretically goes back at least to the work of Helstrom, Holevo, and others from around 1970.

In quantum state tomography, one is given $k$ copies of an $n$-qubit quantum state $\rho$ and is required to output a classical description of density matrix $\hat{\rho}$ close to $\rho$ by performing quantum measurements on $\rho^{\otimes k}$. Broadly speaking, there are three categories of measurements: one consists of joint (entangled) measurements on $\rho^{\otimes k}$, as in Bagan et al. (2004); Keyl (2006); Guţă and Kahn (2008). In Haah et al. (2016); O’Donnell and Wright (2016, 2017), the authors showed that the optimal scaling of the sample number $k$ as a function of trace distance goal $\epsilon$ is $n\propto\frac{4^{n}}{\epsilon^{2}}$. The second category consists of measurements on each copy of the state $\rho$, whose results are to be combined to reconstruct the density matrix, as in Flammia et al. (2012a). Ref. Kueng et al. (2017) showed that if one can perform many-outcome measurements, tomography is possible using $n\propto 8^{n}/\delta^{2}$ copies, and this is optimal if the measurements on every copy are independent as showed in Haah et al. (2016). The third category local measurements consists of measurements on each qubit of each copy of the state $\rho$, whose results are to be combined to reconstruct the density matrix Guţă et al. (2020). Generally, joint measurements over several copies of the state can usually achieve lower sampling rates Haah et al. (2016); O’Donnell and Wright (2016, 2017), but are much more challenging to implement. On the other hand, Pauli measurements are experimental friendly, therefore, extremely important both theoretically and experimentally. If one is restricted to use Pauli measurements, Flammia, Gross, Liu and Eisert observed that the quantum state tomography can be accomplished using ${\mathcal{O}}(\frac{n\cdot 16^{n}}{\epsilon^{2}})$ copies in Flammia et al. (2012b). This was improved the bound to ${\mathcal{O}}(\frac{n\cdot 12^{n}}{\epsilon^{2}})$ in Guţă et al. (2020).

In Cotler and Wilczek (2020), Cotler and Wilczek introduced the problem called quantum overlapping tomography problem. The goal is to output the classical description of all $k$-qubit reduced density matrix of an $n$-qubit system. This problem is also of great importance in quantum information science, because many important physical quantities, for instance, energy and entropy, depend on very small parts of the whole system only, in other words, depends on the set of local reduced density matrices. By using the perfect hash families, they showed that one only needs to use $e^{\mathcal{O}(k)}\log^{2}n$ rounds of parallel measurements to achieve this goal. Ref. García-Pérez et al. (2020) proposed a measurement scheme to perform two-qubit tomography of all pairs. Later Ref. Evans et al. (2019) provided an algorithm to estimate the expectation value of $m$ Pauli operators with weight $\leq k$ using $\mathcal{O}(3^{k}\log m)$ measurements for small $k$. All of these bounds can be achieved using Pauli measurements.

A positive-operator valued measure (POVM) on a finite dimensional Hilbert space $\mathcal{H}$ is a set of positive semi-definite matrices $\mathcal{M}=\{M_{i}\}$ such that

We need the concept of the informationally complete POVM as follows,

Equaivalently, a POVM $\mathcal{M}=\{M_{i}\}$ on $d$-dimensional $\mathcal{H}$ is informationally complete if the linear span of $\{M_{i}\}$ equals to the whole $d\times d$ matrix space. In qubit system, it means $\sigma_{I},\sigma_{X},\sigma_{Y}$ and $\sigma_{Z}$ all live in the linear span of $\{M_{i}\}$, where $\sigma_{I}$, $\sigma_{X},\sigma_{Y}$ and $\sigma_{Z}$ are Pauli matrices,

It is direct to observe that $\mathcal{M}=\frac{1}{6}\{\sigma_{I}+\sigma_{X},\sigma_{I}-\sigma_{X},\sigma_{I}+\sigma_{Y},\sigma_{I}-\sigma_{Y},\sigma_{I}+\sigma_{Z},\sigma_{I}-\sigma_{Z}\}$ is an informationally complete measurement.

Directly, $\mathcal{M}^{\otimes n}=\mathcal{M}=\frac{1}{6^{n}}\{\sigma_{I}+\sigma_{X},\sigma_{I}-\sigma_{X},\sigma_{I}+\sigma_{Y},\sigma_{I}-\sigma_{Y},\sigma_{I}+\sigma_{Z},\sigma_{I}-\sigma_{Z}\}^{\otimes n}$ is an informationally complete POVM of $n$-qubit system.

The following McDiarmid’s inequality McDiarmid (1989) will be used in this paper.

We start from the following observation:

When we measure an element of Pauli group, for instance $\sigma_{X}\sigma_{Y}$, on a two-qubit state $\rho$, the outcome is a sample from a $4$-dimensional probability distribution, says $(p_{00},p_{01},p_{10},p_{11})$, such that

One can easily observe that

In other words, by measuring $XY$, we actually obtained a sample of $\sigma_{X}\sigma_{I}$, a sample of $\sigma_{Y}\sigma_{I}$, and a sample of $\sigma_{I}\sigma_{I}$.

This is also true for general $n$-qubit system as the following observation shows,

Our measurement scheme is as follows: For any $\epsilon>0$, fix an integer $m=16\cdot\frac{10^{n}\log\frac{1}{\delta}}{3^{n}\cdot\epsilon^{2}}$.

For any $P\in\{\sigma_{X},\sigma_{Y},\sigma_{Z}\}^{\otimes n}$, one performs $m$ times $P$ on $\rho$, and records the $m$ samples of the $2^{n}$ dimensional outcome distribution.

According to the key observation, this measurement scheme provides $m\cdot 3^{n-w}$ samples of the expectation $\operatorname{tr}(\rho P)$, says $\frac{\mu_{P}}{m\cdot 3^{n-w}}$ for each Pauli operator $P\in\{\sigma_{I},\sigma_{X},\sigma_{Y},\sigma_{Z}\}^{\otimes n}$ with weight $w$, where $-m\cdot 3^{n-w}\leq\mu_{P}\leq m\cdot 3^{n-w}$.

Output

Using this scheme, we obtained $m\cdot 3^{n}$ independent samples,

where each $0\leq X_{i}\leq 2^{n}-1$.

Fruthermore, $X_{1},X_{2},\cdots,X_{m}$ corresponds to the measurement $\sigma_{X}^{\otimes n}$; $X_{m+1},X_{m+2},\cdots,X_{2m}$ corresponds to the measurement $\sigma_{X}^{\otimes n-1}\otimes\sigma_{Y}$; $\cdots$

It is direct to observe that, for any $P$ of weight $w$, $\mu_{P}=\sum_{j=0}^{m\cdot 3^{n-w}-1}Z_{j}$, where $Z_{j}$ are independent samples from distribution $Z$

Furthermore, $Z_{j}$ can be obtained from samples

Therefore,

is defined according to samples

It is direct to verify that

where the expectation is taken over the probabilistic distribution according to the measurements.

For any

we can define the function $f:X_{1}\times X_{2}\times\cdots\times X_{m\cdot 3^{n}}\mapsto\mathbb{R}$

According to Cauchy inequality, we have

For any sample $X_{i}$ corresponding to $P\in\{\sigma_{X},\sigma_{Y},\sigma_{Z}\}^{\otimes n}$. If only $X_{i}$ is changed, it would only change $\mu_{Q}$ for those $Q\in\{\sigma_{I},\sigma_{X},\sigma_{Y},\sigma_{Z}\}^{\otimes n}$ where $Q$ is obtained by replacing some $\{\sigma_{X},\sigma_{Y},\sigma_{Z}\}$s of $P$ by $\sigma_{I}$. Moreover, those $\mu_{Q}$ would change at most $2$. According to triangle inequality, $f$ would change at most

where $Q$ ranges over all Paulis which corresponds to $P$, and $\delta\mu_{Q}$ denotes the difference of $\mu_{Q}$ when $X_{i}$ is changed.

For $\epsilon>0$, let $\epsilon^{\prime}=\frac{\epsilon}{\sqrt{2^{n}}}$. We have

where the first step is by the relation between the trace norm and 2 norm; the third step is by $\mathbb{E}f\leq\frac{\epsilon^{\prime}}{2}$; the fourth step is by Lemma 5 (McDiarmid’s inequality).

The total number of used copies is

In this section, we study the quantum overlapping tomography.

We first analyze Algorithm 1.

Fixing $n$ informationally complete POVM of one-qubit system, says $\mathcal{M}_{1},\mathcal{M}_{2},\cdots,\mathcal{M}_{n}$. For any given unknown $n$-qubit state $\rho$, we perform $\mathcal{M}_{1}\otimes\mathcal{M}_{2}\otimes\cdots\otimes\mathcal{M}_{n}$ on $\rho$ and obtain a string $s_{1}s_{2}\cdots s_{n}$ with $s_{i}$ denoting the measurement outcome of $\mathcal{M}_{i}$. Assume the output probability distribution is $p_{1,2,\cdots,n}$. we know that $s_{1}s_{2}\cdots s_{n}$ obeys the distribution of $p_{1,2,\cdots,n}$.

The key observation is that measuring each qubit independently preserves the local structure. More precisely,

By Algorithm 1, we repeat the measurement $\mathcal{M}_{1}\otimes\mathcal{M}_{2}\otimes\cdots\otimes\mathcal{M}_{n}$ $m$ times to obtain $m$ samples of $p_{1,2,\cdots,n}$. For any sets $S_{1},S_{2},\cdots,S_{M}\subseteq\{1,2,\cdots,n\}$, Obervation 3 implies that we have $m$ samples of the marginal distributions $p_{S_{1}}$, $p_{S_{2}}\cdots$, and $p_{S_{M}}$, not independent. Although, $m$ samples maybe not enough to recover $p_{1,2,\cdots,n}$, but enough to recover $p_{S_{i}}$ for each $S_{i}$ with high accuracy and high confidence using Chernoff bound. According to Observation 1 and Observation 2, this implies one can recover $\rho_{S_{i}}$ with high accuracy, trace distance error $\epsilon$, and sucessful probability at least $1-\delta^{\prime}$ for each $S_{i}$ using $m=\mathcal{O}(g(k)\cdot\frac{\log\delta^{\prime}}{\epsilon^{2}})$.

To successfully recover $\rho_{S_{i}}$ simultaneously, we only need the recovery of each $\rho_{S_{i}}$ with high accuracy and probability at least $1-\frac{\delta}{{{n}\choose{k}}}$ according to union bound.

Therefore, we only need $m=\mathcal{O}(g(k)\cdot\frac{\log{{{n}\choose{k}}}/{\delta}}{\epsilon^{2}})$ copies.

For the general quantum state tomography problem, our measurement scheme is much more efficient than previous schemes in the Pauli measurements setting. Our result raises an important question on the performance of local measurements, in particular Pauli measurements, in which each qubit is measured at a time.

The sample complexity of the quantum overlapping tomography problem is nearly resolved here up to a constant factor.

An independent work Huang et al. (2020) analyzes random Clifford measurement and random Pauli measurement and proves that it only requires $\mathcal{O}(\frac{\log(M)\cdot s}{\epsilon^{2}})$ copies to achieve $\epsilon$ accuracy estimation for $\operatorname{tr}(O_{1}\rho),\cdots,\operatorname{tr}(O_{M}\rho)$, a more general question, where $s$ depends on the structure of $O_{i}$s. They also show that this is tight if only single-copy measurements are allowed. If $O_{i}$s are $k$-qubit Paulis, $\mathcal{O}(\frac{\log(M/\delta)\cdot 3^{k}}{\epsilon^{2}})$ which coinsides with the bound provided in Ref. Evans et al. (2019). These upper bound does not cover ours, because a $4^{k}$ coefficient would be added when we move from Pauli estimation to state tomography, thus, these results would lead to a $\mathcal{O}(\frac{\log(M/\delta)\cdot 12^{k}}{\epsilon^{2}})$ measurement scheme. Also, this lower bound does not imply our lower bound, for the specific quantum overlapping tomography problem, because this bound is not for joint measurement and does not consider the successful probability parameter.

We thank Steve Flammia for the discussion on quantum overlapping tomography. We thank Richard Keung for clasifying their bound in Guţă et al. (2020). This work was supported by DE180100156.