© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2209.02240 · IEEE Transactions on Information Theory

Optimal Tomography of Quantum Markov Chains via Continuity of Petz Recovery States

Li Gao, Nengkun Yu

Published Jul 1, 2025• 3 citations

Abstract

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.

DOI: 10.1109/tit.2025.3584694

Related papers

Sample-optimal tomography of quantum states

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji +2 more

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.

arXiv:1508.01797•IEEE Transactions on Information Theory•Jan 1, 2017•182 citations

Quantum Markov chains and logarithmic trace inequalities

David Sutter, Mario Berta, Marco Tomamichel

A Markov chain is a tripartite quantum state ρABCwhere there exists a recovery map RB→BCsuch that ρABC= RB→BC(ρAB). More generally, an approximate Markov chain ρABCis a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A : C|B)ρof the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•6 citations

Efficient quantum tomography

Ryan O’Donnell, John Wright

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.

arXiv:1508.01907•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•181 citations

Tomographic Limits of the Petz Recovery Map

Peter Sidajaya, Clive Cenxin Aw, Mingxuan Liu +1 more

The Petz recovery map is considered one of the key candidates for the quantum analogue of Bayesian inference and Jeffrey's conditionalization. Since, there seems to be a natural connection between Bayesian inference and the notion of state tomography, it is natural to ask if the Petz recovery can be used for this latter task. In this paper, we discuss such recent results on iterated Petz recovery and relate them to Bayesian approaches to quantum state tomography. We highlight the limitations of direct Petz iteration and show how an extended Petz construction, by lifting the inference problem to a classical distribution over candidate quantum states, recovers the structure of Bayesian and maximum likelihood tomography. This provides perspective on the modifications or nuances required for a Petz approach to quantum retrodiction to perform quantum state tomography.

quant-pharXiv:2608.21309•Aug 24, 2026•0 citations

Quantum state certification

Costin Bădescu, Ryan O’Donnell, John Wright

We consider the problem of quantum state certification, where one is given n copies of an unknown d-dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω(d2) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O(d/є) copies, and one with respect to trace distance using n = O(d/є2) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.

arXiv:1708.06002•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•66 citations

An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography

Sitan Chen, Jerry Zheng Li, Allen Liu

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.

arXiv:2402.16353•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•11 citations

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.

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.

A Markov chain is a tripartite quantum state ρABCwhere there exists a recovery map RB→BCsuch that ρABC= RB→BC(ρAB). More generally, an approximate Markov chain ρABCis a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A : C|B)ρof the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.

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.

The Petz recovery map is considered one of the key candidates for the quantum analogue of Bayesian inference and Jeffrey's conditionalization. Since, there seems to be a natural connection between Bayesian inference and the notion of state tomography, it is natural to ask if the Petz recovery can be used for this latter task. In this paper, we discuss such recent results on iterated Petz recovery and relate them to Bayesian approaches to quantum state tomography. We highlight the limitations of direct Petz iteration and show how an extended Petz construction, by lifting the inference problem to a classical distribution over candidate quantum states, recovers the structure of Bayesian and maximum likelihood tomography. This provides perspective on the modifications or nuances required for a Petz approach to quantum retrodiction to perform quantum state tomography.

We consider the problem of quantum state certification, where one is given n copies of an unknown d-dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω(d2) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O(d/є) copies, and one with respect to trace distance using n = O(d/є2) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.

There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.