Lower bounds for learning quantum states with single-copy measurements
- URL: http://arxiv.org/abs/2207.14438v2
- Date: Mon, 1 Aug 2022 22:03:52 GMT
- Title: Lower bounds for learning quantum states with single-copy measurements
- Authors: Angus Lowe and Ashwin Nayak
- Abstract summary: We study the problems of quantum tomography and shadow tomography using measurements performed on individual copies of an unknown $d$-dimensional state.
In particular, this rigorously establishes the optimality of the folklore Pauli tomography" algorithm in terms of its complexity.
- Score: 3.2590610391507444
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problems of quantum tomography and shadow tomography using
measurements performed on individual, identical copies of an unknown
$d$-dimensional state. We first revisit a known lower bound due to Haah et al.
(2017) on quantum tomography with accuracy $\epsilon$ in trace distance, when
the measurements choices are independent of previously observed outcomes (i.e.,
they are nonadaptive). We give a succinct proof of this result. This leads to
stronger lower bounds when the learner uses measurements with a constant number
of outcomes. In particular, this rigorously establishes the optimality of the
folklore ``Pauli tomography" algorithm in terms of its sample complexity. We
also derive novel bounds of $\Omega(r^2 d/\epsilon^2)$ and $\Omega(r^2
d^2/\epsilon^2)$ for learning rank $r$ states using arbitrary and
constant-outcome measurements, respectively, in the nonadaptive case.
In addition to the sample complexity, a resource of practical significance
for learning quantum states is the number of different measurements used by an
algorithm. We extend our lower bounds to the case where the learner performs
possibly adaptive measurements from a fixed set of $\exp(O(d))$ measurements.
This implies in particular that adaptivity does not give us any advantage using
single-copy measurements that are efficiently implementable. We also obtain a
similar bound in the case where the goal is to predict the expectation values
of a given sequence of observables, a task known as shadow tomography. Finally,
in the case of adaptive, single-copy measurements implementable with
polynomial-size circuits, we prove that a straightforward strategy based on
computing sample means of the given observables is optimal.
Related papers
- An optimal tradeoff between entanglement and copy complexity for state
tomography [24.737530909081915]
We study tomography in the natural setting where one can make measurements of $t$ copies at a time.
This is the first smooth entanglement-copy protocol known for any quantum learning task.
A key insight is to use SchurilonWeyl sampling not to estimate the spectrum of $rho$, but to estimate the deviation of $rho$ from the maximally mixed state.
arXiv Detail & Related papers (2024-02-26T07:18:57Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data.
We show how one can disprove faked data, and apply this to a classical count algorithm.
arXiv Detail & Related papers (2022-11-07T12:00:45Z) - Quantum state tomography with tensor train cross approximation [84.59270977313619]
We show that full quantum state tomography can be performed for such a state with a minimal number of measurement settings.
Our method requires exponentially fewer state copies than the best known tomography method for unstructured states and local measurements.
arXiv Detail & Related papers (2022-07-13T17:56:28Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Distributed quantum inner product estimation [14.222887950206658]
A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers.
No quantum communication can be performed between the two physical platforms due to hardware constraints.
We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
arXiv Detail & Related papers (2021-11-05T05:35:03Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function.
We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
arXiv Detail & Related papers (2021-06-29T12:49:54Z) - Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies.
We show that these errors decrease exponentially with decay rates given by the measured relative entropies between the two states.
arXiv Detail & Related papers (2021-04-30T00:52:48Z) - Quantum data hiding with continuous variable systems [8.37609145576126]
We investigate data hiding in the context of continuous variable quantum systems.
We look at the case where $mathcalM=mathrmLOCC$, the set of measurements implementable with local operations and classical communication.
We perform a rigorous quantitative analysis of the error introduced by the non-ideal Braunstein-Kimble quantum teleportation protocol.
arXiv Detail & Related papers (2021-02-01T19:00:14Z) - Efficient computation of the Nagaoka--Hayashi bound for multi-parameter
estimation with separable measurements [16.53410208934304]
We introduce a tighter bound for estimating multiple parameters simultaneously when performing separable measurements on finite copies of the probe.
We show that this bound can be efficiently computed by casting it as a semidefinite program.
arXiv Detail & Related papers (2020-08-06T12:43:31Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator)
We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$.
We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
arXiv Detail & Related papers (2020-05-26T17:53:18Z) - Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
We show that with independent measurements, $Omega(d4/3/epsilon2)$ is necessary, even if the measurements are chosen adaptively.
We develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing.
arXiv Detail & Related papers (2020-04-16T18:28:39Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.