Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.27177

Sample-Efficient Tomography of a Class of Mixed States with Extensive Entanglement and Magic

Pengcheng Liao, Quntao Zhuang

quant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 0 citations
arXivHTMLPDF

Abstract

Full tomography of a generic many-qubit quantum state requires exponentially many copies, while suitable structural constraints can make reconstruction sample-efficient. Existing approaches exploit, for example, limited entanglement structure, low magic, or constrained state-preparation circuits. Here we consider a class of mixed states that can simultaneously exhibit extensive entanglement and extensive magic. Specifically, we introduce Clifford-encoded block-product (CEBP) states, obtained by applying an unknown global Clifford unitary to a tensor product of arbitrary mixed states supported on unknown blocks of bounded size. We show that, for a fixed block size, CEBP states can be reconstructed using polynomially many copies by exploiting Clifford-preserved Pauli correlations to recover the latent structure and reduce the remaining problem to local tomography. Our result demonstrates that sample-efficient tomography can arise from bounded complexity in a latent frame even when the physical state is highly entangled, highly magical, and mixed, and suggests complexity modulo structured transformations as a broader organizing principle for quantum-state learnability.

AI Summary

Can mixed states with extensive entanglement and magic be reconstructed with polynomially many copies? This paper studies Clifford-encoded block-product (CEBP) states, $\rho=U_{\mathrm c}(\bigotimes_a\rho_a)U_{\mathrm c}^\dagger$, where the global Clifford, block partition, and arbitrary mixed block states are unknown; only a maximum block size $d$ is supplied. The class permits extensive entropy and exponentially large rank, alongside extensive entanglement and magic. The main guarantee is reconstruction to trace-norm error $\varepsilon$ with probability at least $1-\delta$, using $\widetilde O(n^9/\varepsilon^8)$ copies for $d=1$, and $\widetilde O[2^{O(d\log d)}(n^{19}/\varepsilon^8+n^{d+5}/\varepsilon^2)]$ for $d\ge2$, suppressing logarithmic factors including failure-probability dependence. Two-copy transversal Bell measurements uniformly estimate squared Pauli expectations, which factor across hidden blocks. Near-stabilizer peeling and score-ranked symplectic recovery identify relevant Pauli sectors; signed measurements of commuting tuples supply bounded-order cumulants for grouping sectors. A learned Clifford localizes the recovered algebras, enabling blockwise tomography. Exact recovery of the original encoder or partition is unnecessary. Simulations for $d=1,2,3$ report approximately quadratic copy scaling over accessible sizes and lower copy requirements than local-Pauli linear inversion. These comparisons do not normalize circuit, computational, or memory costs. The guarantee concerns sample efficiency: explicit all-Pauli searches can require exponential classical time, and the worst-case bounds are conservative. Extensions to Clifford channels or mixtures are left open because the protocol relies on a single invertible Clifford frame with a block-product core.

Little sign of AI-generated textStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
10 page main text; 47 pages Supplemental Material, 3 figures

Related papers

Efficient Learning of Clifford-Scrambled Product States

Tobias Haug

Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.

quant-pharXiv:2609.27128•Sep 24, 2026•1 citation

Efficient learning of Clifford disentanglers and typical $t$-doped unitaries with exponentially more $T$ gates

Gerard Aguilar, Sofiene Jerbi, Jens Eisert +1 more

Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form $\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle$, where $U_C$ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical $t$-doped Clifford unitaries in regimes containing exponentially more $T$ gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when $t\sim n$, and continues to hold for a constant fraction even when $t=2n$. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.

quant-pharXiv:2609.27565•Sep 24, 2026•1 citation

Efficient learning of quantum states and circuits

Sabee Grewal

Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.

•Aug 1, 2026•0 citations

A Unified Framework for Sample Complexity of Structured Quantum State Tomography under Noisy Observations

Zhen Qin

Quantum state tomography (QST) has attracted considerable attention due to its fundamental role in quantum information processing. In this paper, we develop a unified theoretical framework for analyzing the sample complexity of structured QST under noisy observations arising from state preparation noise, measurement noise, and finite-shot statistical noise. The proposed framework applies to a broad family of structured quantum-state classes, including general mixed states, sparse states, low-rank states, matrix product states (MPSs), matrix product operators (MPOs), projected entangled-pair states (PEPSs), and projected entangled-pair operators (PEPOs), while further introducing physically consistent structured models---including low-rank and sparse states, low-rank MPOs (LR-MPOs), and low-rank PEPOs (LR-PEPOs)---that simultaneously exploit low-dimensional structures and preserve the physical constraint. Within this framework, we derive unified non-asymptotic sample complexity guarantees for two constrained least-squares estimators under noisy observations: a noise-aware estimator that incorporates the calibrated noise model and a noise-unaware estimator based on the ideal Born measurement model. For the noise-aware estimator, we derive unified trace-norm recovery guarantees that explicitly characterize the dependence of the sample complexity on three fundamental quantities: the complexity of the underlying structured state class, the complexity of the measurement ensemble, and the state preparation and measurement noise levels. For the noise-unaware estimator, we establish a unified non-asymptotic recovery guarantee consisting of a statistical error term and an additional deterministic bias term arising from the mismatch between the assumed reconstruction model and the noisy observation process.

quant-pharXiv:2608.05526•Aug 7, 2026•1 citation

Mixed state tomography reduces to pure state tomography

Angelos Pelecanos, Jack Spilecki, Ewin Tang +1 more

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 $|ρ\rangle$; run a pure state tomography algorithm to produce an estimate of $|ρ\rangle$; 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/δ))/\varepsilon)$ samples to output an estimate which is $\varepsilon$-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.

quant-pharXiv:2511.15806•Nov 21, 2025•57 citations

An Exponential Advantage for Adaptive Tomography of Structured States under Pauli Basis Measurements

Alireza Goldar, Zhen Qin, Zhihui Zhu +2 more

Broad claims about whether adaptivity helps in quantum state tomography can be misleading unless the state family, measurement architecture, and error metric are specified carefully. We study a restricted but physically important regime: single-copy quantum state tomography under local Pauli basis measurements, where the allowed measurement settings are tensor-product measurement operators built from local single-qubit Pauli operators, and performance is measured in trace distance with high probability in a minimax sense over a known structured family. We construct an explicit discrete prefix/tree family of states for which adaptive measurement selection achieves polynomial copy complexity, while every non-adaptive design requires exponentially many copies in the worst case. The adaptive upper bound comes from stagewise prefix recovery using hierarchical breadcrumb information revealed by partial prefix matches. The non-adaptive lower bound is based on a rare-prefix mechanism: every fixed design under-samples some deep prefix subset, and outside that subset the competing hypotheses induce identical one-shot laws, so only an exponentially small fraction of the measurement budget contributes to the KL divergence between the full data distributions. The result isolates a concrete regime in which adaptivity provably changes the sample-complexity scaling under the experimentally common local Pauli measurement architecture.

quant-pharXiv:2604.26043•Apr 30, 2026•5 citations
Full tomography of a generic many-qubit quantum state requires exponentially many copies, while suitable structural constraints can make reconstruction sample-efficient. Existing approaches exploit, for example, limited entanglement structure, low magic, or constrained state-preparation circuits. Here we consider a class of mixed states that can simultaneously exhibit extensive entanglement and extensive magic. Specifically, we introduce Clifford-encoded block-product (CEBP) states, obtained by applying an unknown global Clifford unitary to a tensor product of arbitrary mixed states supported on unknown blocks of bounded size. We show that, for a fixed block size, CEBP states can be reconstructed using polynomially many copies by exploiting Clifford-preserved Pauli correlations to recover the latent structure and reduce the remaining problem to local tomography. Our result demonstrates that sample-efficient tomography can arise from bounded complexity in a latent frame even when the physical state is highly entangled, highly magical, and mixed, and suggests complexity modulo structured transformations as a broader organizing principle for quantum-state learnability.
Can mixed states with extensive entanglement and magic be reconstructed with polynomially many copies? This paper studies Clifford-encoded block-product (CEBP) states, ρ=Uc(⨂aρa)Uc†\rho=U_{\mathrm c}(\bigotimes_a\rho_a)U_{\mathrm c}^\daggerρ=Uc​(⨂a​ρa​)Uc†​, where the global Clifford, block partition, and arbitrary mixed block states are unknown; only a maximum block size ddd is supplied. The class permits extensive entropy and exponentially large rank, alongside extensive entanglement and magic.
The main guarantee is reconstruction to trace-norm error ε\varepsilonε with probability at least 1−δ1-\delta1−δ, using O~(n9/ε8)\widetilde O(n^9/\varepsilon^8)O(n9/ε8) copies for d=1d=1d=1, and O~[2O(dlog⁡d)(n19/ε8+nd+5/ε2)]\widetilde O[2^{O(d\log d)}(n^{19}/\varepsilon^8+n^{d+5}/\varepsilon^2)]O[2O(dlogd)(n19/ε8+nd+5/ε2)] for d≥2d\ge2d≥2, suppressing logarithmic factors including failure-probability dependence. Two-copy transversal Bell measurements uniformly estimate squared Pauli expectations, which factor across hidden blocks. Near-stabilizer peeling and score-ranked symplectic recovery identify relevant Pauli sectors; signed measurements of commuting tuples supply bounded-order cumulants for grouping sectors. A learned Clifford localizes the recovered algebras, enabling blockwise tomography. Exact recovery of the original encoder or partition is unnecessary.
Simulations for d=1,2,3d=1,2,3d=1,2,3 report approximately quadratic copy scaling over accessible sizes and lower copy requirements than local-Pauli linear inversion. These comparisons do not normalize circuit, computational, or memory costs. The guarantee concerns sample efficiency: explicit all-Pauli searches can require exponential classical time, and the worst-case bounds are conservative. Extensions to Clifford channels or mixtures are left open because the protocol relies on a single invertible Clifford frame with a block-product core.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn nnn-qubit states prepared by random TTT-doped Clifford circuits with TTT-gate density below one via O(n2)O(n^2)O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn TTT-depth-one circuits using O(n2)O(n^2)O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
Efficient learning of Clifford disentanglers and typical ttt-doped unitaries with exponentially more TTT gates
Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form ∣ψ⟩=UC⨂i∣ψi⟩\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle∣ψ⟩=UC​⨂i​∣ψi​⟩, where UCU_CUC​ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical ttt-doped Clifford unitaries in regimes containing exponentially more TTT gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when t∼nt\sim nt∼n, and continues to hold for a constant fraction even when t=2nt=2nt=2n. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.
Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.
Quantum state tomography (QST) has attracted considerable attention due to its fundamental role in quantum information processing. In this paper, we develop a unified theoretical framework for analyzing the sample complexity of structured QST under noisy observations arising from state preparation noise, measurement noise, and finite-shot statistical noise. The proposed framework applies to a broad family of structured quantum-state classes, including general mixed states, sparse states, low-rank states, matrix product states (MPSs), matrix product operators (MPOs), projected entangled-pair states (PEPSs), and projected entangled-pair operators (PEPOs), while further introducing physically consistent structured models---including low-rank and sparse states, low-rank MPOs (LR-MPOs), and low-rank PEPOs (LR-PEPOs)---that simultaneously exploit low-dimensional structures and preserve the physical constraint. Within this framework, we derive unified non-asymptotic sample complexity guarantees for two constrained least-squares estimators under noisy observations: a noise-aware estimator that incorporates the calibrated noise model and a noise-unaware estimator based on the ideal Born measurement model. For the noise-aware estimator, we derive unified trace-norm recovery guarantees that explicitly characterize the dependence of the sample complexity on three fundamental quantities: the complexity of the underlying structured state class, the complexity of the measurement ensemble, and the state preparation and measurement noise levels. For the noise-unaware estimator, we establish a unified non-asymptotic recovery guarantee consisting of a statistical error term and an additional deterministic bias term arising from the mismatch between the assumed reconstruction model and the noisy observation process.
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 nnn copies of an unknown state ρρρ, convert them into copies of a purification ∣ρ⟩|ρ\rangle∣ρ⟩; run a pure state tomography algorithm to produce an estimate of ∣ρ⟩|ρ\rangle∣ρ⟩; 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-rrr ddd-dimensional state, it uses n=O((rd+log⁡(1/δ))/ε)n = O((rd + \log(1/δ))/\varepsilon)n=O((rd+log(1/δ))/ε) samples to output an estimate which is ε\varepsilonε-close in fidelity with probability at least 1−δ1-δ1−δ. This algorithm also uses poly(n)(n)(n) gates, making it the first gate-efficient tomography algorithm which is sample-optimal even in terms of the dimension ddd 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.
Broad claims about whether adaptivity helps in quantum state tomography can be misleading unless the state family, measurement architecture, and error metric are specified carefully. We study a restricted but physically important regime: single-copy quantum state tomography under local Pauli basis measurements, where the allowed measurement settings are tensor-product measurement operators built from local single-qubit Pauli operators, and performance is measured in trace distance with high probability in a minimax sense over a known structured family. We construct an explicit discrete prefix/tree family of states for which adaptive measurement selection achieves polynomial copy complexity, while every non-adaptive design requires exponentially many copies in the worst case. The adaptive upper bound comes from stagewise prefix recovery using hierarchical breadcrumb information revealed by partial prefix matches. The non-adaptive lower bound is based on a rare-prefix mechanism: every fixed design under-samples some deep prefix subset, and outside that subset the competing hypotheses induce identical one-shot laws, so only an exponentially small fraction of the measurement budget contributes to the KL divergence between the full data distributions. The result isolates a concrete regime in which adaptivity provably changes the sample-complexity scaling under the experimentally common local Pauli measurement architecture.