A longstanding belief in quantum tomography is that estimating a mixed state is far harder than estimating a pure state. This is borne out in the mathematics, where mixed state algorithms have always required more sophisticated techniques to design and analyze than pure state algorithms. We present a new approach to tomography demonstrating that, contrary to this belief, state-of-the-art mixed state tomography follows easily and naturally from pure state algorithms.
We analyze the following strategy: given
n copies of an unknown state
ρ, convert them into copies of a purification
∣ρ⟩; run a pure state tomography algorithm to produce an estimate of
∣ρ⟩; and output the resulting estimate of
ρ. The purification subroutine was recently discovered via the "acorn trick" of Tang, Wright, and Zhandry. With this strategy, we obtain the first tomography algorithm which is sample-optimal in all parameters. For a rank-
r d-dimensional state, it uses
n=O((rd+log(1/δ))/ε) samples to output an estimate which is
ε-close in fidelity with probability at least
1−δ. This algorithm also uses poly
(n) gates, making it the first gate-efficient tomography algorithm which is sample-optimal even in terms of the dimension
d alone. Moreover, with this method we recover essentially all results on mixed state tomography, including its applications to tomography with limited entanglement, classical shadows, and quantum metrology. Our proofs are simple, closing the gap in conceptual difficulty between mixed and pure tomography. Our results also clarify the role of entangled measurement in mixed state tomography: the only step of the algorithm which requires entanglement across copies is the purification step, suggesting that, for tomography, the reason entanglement is useful is for consistent purification.
We study the problem of tomography for
k-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning
n-qubit
k-sparse pure quantum states, obtaining fidelity at least
1−ε with high probability using
O~(k/ε) copies of the state and
O~(kn/ε) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal
O~(kr/ε) sample complexity for learning
k-sparse rank-
r mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for
r>1, remains an important open question.
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.
Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of
n-qubit system can be accomplished with
O(ε210n) copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is
O(ε210k⋅log((kn)/δ))) for quantum overlapping tomography of
k-qubit reduced density matrices among
n is quantum system, where
1−δ is the confidential level, and
ε is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that
Ω(ε2log(n/δ)) copies are needed. In other words, for constant
k, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.
Quantum state cloning is the task of approximately producing additional copies of an unknown quantum state from a finite number of input copies. The optimal cloning fidelity is known exactly for pure states, but no comparable characterization is known for general mixed states. We determine the optimal asymptotic copy complexity for
d-dimensional states of rank at most
r: producing
M additional copies with worst-case fidelity at least
1−ε requires and is achievable with
N=Θ(Mrd/ε) input copies. Remarkably, the lower bound already holds for a family of states with a fixed flat spectrum, while the matching upper bound is achieved by random purification followed by optimal pure-state cloning. For
M=1, we further show that high-fidelity tomography can be coherently converted into cloning with comparable error, revealing an operational origin of the matching cloning and tomography complexities.
Quantum state tomography (QST) aims at estimating a quantum state from averaged quantum measurements made on copies of that state. Most quantum algorithms rely on QST at some point and it is a well-explored topic in the literature, mostly for mixed states. In this paper we focus on the QST of a pure quantum state using parallel unentangled measurements. Pure states are a small but useful subset of all quantum states, and their tomography requires fewer measurements and is essentially a phase recovery problem. Parallel unentangled measurements are easy to implement in practice because they allow the user to measure each qubit individually, e.g., using one-qubit Pauli measurements. We propose two sets of quantum measurements that one can make on a pure state as well as the algorithms that use the measurement outcomes in order to identify the state. We also discuss how those estimates can be fine tuned by finding the state that maximizes the likelihood of the measurements with different variants of the likelihood. The performances of the proposed three types of QST methods are validated by means of detailed numerical tests, including for mixed states that are close to being pure.