It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.
In this work, we show that the Petz recovered state ρ1/2BC(ρ−1/2BρABρ−1/2B⊗IC)ρ1/2BCis continuous regarding its marginals ρABand ρBC. In terms of infidelity 1 −F(ρ, σ) = 1 − tr | √ ρ √ σ| and trace norm ∥ ρ − σ ∥1= tr(|ρ − σ|), we obtain the following dimension-independent estimate 1 −F(ρAB, σAB) ≤ δ, 1 −F(ρBC, σBC) ≤ δ =⇒ 1 −F(ρABC, σABC) ≤ 18δ, ∥ ρAB− σAB∥1≤ ε, ∥ ρBC− σBC∥1≤ ε =⇒∥ ρABC− σABC∥≤ ε + 4ε1/2. As applications, we obtain the following applications in tomography of quantum Markov chains: • The sample complexity of quantum Markov chain tomography, i.e., how many copies of an unknown quantum Markov chain are necessary and sufficient to determine the state, is ˜Θ ((d2A+d2C)d2B/δ), and ˜Θ((d2A+d2C)d2B/ϵ2), where δ denotes infidelity error and ϵ denotes trace distance. • The sample complexity of quantum Markov chain certification, i.e., to certify whether a tripartite state equals a given quantum Markov chain σABCor at least δ-far from σABC, is Θ((dA+dC)dB/δ), and Θ((dA+dC)dB/ϵ2). • Õ(mindAd3Bd3C,d3Ad3BdC/ϵ2) copies of sample are sufficient to certify whether ρABCis a quantum Markov chain or ϵ-far from its Petz recovered state in trace distance. This implies that full state tomography is not always necessary for testing whether ρABCis a quantum Markov chain (equals to its Petz recovered state) or not.
Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.
We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost and still achieves optimal sample complexity. Given measurement data from a known probe state ensemble, we first apply least-squares estimation to produce an unconstrained approximation of the POVM, and then project this estimate onto the set of valid quantum measurements. For a POVM with L outcomes acting on a d -dimensional system, we show that the protocol requires O ( ( d 3 + d 2 L ) / ϵ 2 ) samples to achieve error ϵ in worst-case distance, and O ( d 2 L / ϵ 2 ) samples in average-case distance. We further establish two matching sample complexity lower bounds of Ω ( ( d 3 + d 2 L ) / ϵ 2 ) and Ω ( d 2 L / ϵ 2 ) for any non-adaptive, single-copy POVM tomography protocol. Hence, our projected least squares POVM tomography is sample-optimal in both the dimension and the number of outcomes for both distances. Our method admits an analytic form when using global or local 2-designs as probe ensembles and enables rigorous non-asymptotic error guarantees. Finally, we also complement our findings with empirical performance studies carried out on a noisy superconducting quantum computer with flux-tunable transmon qubits.
We show that n=Ω(rd/ε2) copies are necessary to learn a rank r mixed state ρ∈Cd×d up to error ε in trace distance. This matches the upper bound of n=O(rd/ε2) from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which ρ is promised to be of the form ρ=P/r, where P∈Cd×d is a rank r projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error ε in trace distance to an algorithm which learns to error O(ε) in the more stringent Bures distance.
We prove that learning an unknown mixed fermionic Gaussian state on m modes to trace distance ε requires Ω(m3/ε2) copies when measurements act on one copy at a time, even with arbitrary POVMs, fresh ancillas and classical adaptivity, but without quantum memory between copies. The bound holds for 0<ε≤1/3600 and separates this model from the known collective rate Θ(m2/ε2). It follows from a uniform single-copy Fisher-information budget and a dimension-independent comparison between trace distance and Gaussian parameters. On covariance matrices of operator norm at most 1−c, we prove a Frobenius-to-trace-norm continuity bound with constant [2c(2−c)]−1/2; matchgate shadows then attain O(m3/(cε2)) copies. This also gives explicit error certificates for thermal free-fermion states. For a class of mixed passive bosonic Gaussian states with total mean photon number at most one, a reduction to bounded-block qudit tomography gives a single-copy lower bound Ω(m3/(ε2log(m/ε))), versus collective complexity Θ(m2/ε2). These separations answer the mixed-state measurement-resource question posed by Chen et al. A two-mode example has optimal two-copy Fisher trace 5, versus the separable ceiling 4. An IBM replication gave a pre-registered witness lower bound 4.12 at one-sided 95% shot-noise confidence; its interpretation assumes the prescribed preparations and a common measurement channel and does not bound preparation systematics.