5
$\begingroup$

I'm very curious to know more about bounds of number of measurements (or number of independent copies of state) required to reconstruct full density matrix $\rho$ such that it is $\epsilon$-close (trace distance) to the target density matrix $\sigma$.

What is the best-known lower bound on the number of measurements required so far? The answer seems to be $O((dr^2/\epsilon)\log(d/\epsilon))$ given by Haah et al, where $d$ is dimension of Hilbert space and $r$ is a rank of $\sigma$. Is there a tighter bound?

$\endgroup$
1

3 Answers 3

3
$\begingroup$

This preprint is just submitted a few days ago:

An Improved Sample Complexity Lower Bound for Quantum State Tomography by Henry Yuen.

It shows that $\Omega(rd/\epsilon)$ copies of an unknown rank-$r$, dimension-$d $ quantum mixed state are necessary in order to learn a classical description with $1 - \epsilon$ fidelity.

$\endgroup$
1
$\begingroup$

The 'number of states' needed to estimate some property is known as the sample complexity of the estimation. To the best of my knowledge the results that have the best sample complexity for tomography and for spectrum testing, are these ones:

  1. Efficient Quantum Tomography and Efficient Quantum Tomography II
  2. An efficient quantum algorithm for spectral estimation

These references have had a great impact in the property testing community.

$\endgroup$
0
$\begingroup$

Another recent lower bound was recently given by Lower and Nayak in https://arxiv.org/abs/2207.14438. They show that $\Omega(r^2 d^2/\epsilon^2)$ measurements are needed to reconstruct $d$-dimensional states with rank $r$ within trace distance error $\epsilon$ (with high probability), using single-copy non-adaptive measurements with a fixed number of outcomes. More precisely, they prove the lower bound $\Omega(r^2 d^2/\ell\epsilon^2)$ on the number of necessary states, when the used measurements have $\ell$ outcomes.

This result is also optimal, as it matches the corresponding upper bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.