arxiv: 2604.16578 · v1 · submitted 2026-04-17 · 🪐 quant-ph

Recognition: unknown

Verifying random matrix product states with autoregressive local measurements

Hyunho Cha , Subin Kim , Jungwoo Lee

Authors on Pith no claims yet

Pith reviewed 2026-05-10 07:50 UTC · model grok-4.3

classification 🪐 quant-ph

keywords matrix product statesdirect fidelity estimationautoregressive samplingPauli measurementsquantum verificationtensor networksone-dimensional systems

0 comments

The pith

An autoregressive importance sampler reduces classical overhead for verifying matrix product states to linear scaling in the number of qubits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Verifying that a quantum device has prepared a specific matrix product state has been hindered by the exponential classical cost of sampling suitable local measurement settings for direct fidelity estimation. This paper introduces an autoregressive importance sampler that generates Pauli strings one qubit at a time from conditional distributions that are efficiently computable directly from the MPS. The result is a method whose per-shot classical cost scales linearly with system size. The authors also present a grouped variant that uses a sorting string to identify qubit-wise commuting measurements, allowing multiple expectations to be estimated from one experimental setting and thereby lowering variance. The same ideas apply to matrix product operators for state and observable verification in long one-dimensional systems, with random MPS serving as a benchmark for generic entangled states.

Core claim

We eliminate the exponential classical overhead in direct fidelity estimation for matrix product states by introducing an autoregressive importance sampler that draws Pauli strings sequentially from efficiently computable conditional distributions, reducing the per-shot cost to linear scaling in the number of qubits. We further develop a grouped extension using a sorting string to construct commuting measurement settings and estimate them simultaneously.

What carries the argument

The autoregressive importance sampler that draws Pauli strings sequentially from conditional distributions derived from the matrix product state.

Load-bearing premise

The conditional probability distributions over Pauli strings remain efficiently computable for the target matrix product state without hidden exponential cost.

What would settle it

A calculation showing that the time to sample conditional Pauli distributions for a random MPS of n qubits grows exponentially with n would falsify the linear scaling claim.

Figures

Figures reproduced from arXiv: 2604.16578 by Hyunho Cha, Jungwoo Lee, Subin Kim.

**Figure 2.** Figure 2: FIG. 2: (a) The first two steps of our autoregressive sampling procedure. Dashed lines indicate contractions. Here [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4: The [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3: Both the GHZ state and the W state admit open [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 5.** Figure 5: FIG. 5: Numerical results for MPS-DFE and MPS [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗

**Figure 6.** Figure 6: FIG. 6: A single contraction. Connecting an edge corresponds to summing over the associated index. [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗

read the original abstract

Matrix product states (MPS) are a central language for one-dimensional quantum matter and a practical target for near-term quantum simulators and variational algorithms. Yet, while substantial effort has focused on preparing MPS with shallow circuits, scalable methods to \emph{verify} that a many-body device has actually produced the intended state remain underdeveloped. Direct fidelity estimation (DFE) relies only on local Pauli measurements, but in many-body settings it suffers an exponential classical overhead from the preprocessing needed to sample Pauli strings. We eliminate this obstacle by introducing an \emph{autoregressive} importance sampler that draws Pauli strings sequentially from efficiently computable conditional distributions, reducing the per-shot classical overhead to linear scaling in the number of qubits. We further develop a grouped extension that constructs qubit-wise commuting measurement settings via a \emph{sorting string} and simultaneously estimates the entire commuting group from a single setting, significantly reducing estimator variance while preserving efficient postprocessing. Our approach extends naturally to matrix product operators (MPO), enabling scalable verification of tensor-network states and observables in long one-dimensional quantum systems. We utilize random MPS as a natural benchmark for generic 1D entangled states.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a workable autoregressive sampler that cuts classical preprocessing for MPS direct fidelity estimation down to linear in qubit number, with a useful commuting-group extension.

read the letter

The main point is that they have turned the usual exponential cost of choosing Pauli strings for direct fidelity estimation into something linear in the number of qubits for matrix product states. They do this by sampling the strings autoregressively, qubit by qubit, from conditional distributions that the MPS tensors let you compute directly. They also add a sorting-string method that packs commuting Paulis into single measurement settings, which lowers variance without extra post-processing cost. Both pieces extend to matrix product operators, and they test the whole thing on random MPS as a stand-in for generic entangled 1D states. That combination is the actual novelty; it is not just a re-packaging of standard importance sampling or existing grouping tricks from the literature they cite. The approach is concrete and directly targets a known bottleneck in near-term verification of tensor-network states prepared on hardware. The scaling claim rests on the conditional distributions staying cheap to evaluate. For fixed bond dimension the contractions are standard and linear overall, but random MPS benchmarks often let the bond dimension grow, which could push the per-conditional cost higher if the paper does not bound it explicitly. The abstract asserts efficiency, so I assume the full text supplies the contraction algorithm and either fixed-D numerics or a clear statement that D stays moderate. If those details are there, the central result holds; if not, the linear claim needs tightening. This is useful reading for anyone working on quantum state certification or 1D tensor-network experiments. People who already use MPS or MPO representations and need to check fidelity on actual devices will find the sampler and grouping technique immediately applicable. It is not a broad theoretical advance, but it solves a practical scaling issue with a clear algorithmic fix. The work is coherent on its own terms and engages the right prior results on DFE and MPS. I would send it to peer review, asking the referee to verify the contraction complexity for the random-MPS case and to check whether the numerical evidence shows the claimed linear overhead in practice.

Referee Report

1 major / 0 minor

Summary. The paper claims that an autoregressive importance sampler, drawing Pauli strings sequentially from conditional distributions computable from MPS tensors, reduces the classical preprocessing overhead for direct fidelity estimation to linear scaling in the number of qubits; a grouped extension using sorting strings enables simultaneous estimation of commuting groups from single settings while preserving efficiency, with natural extension to MPOs and random MPS as a benchmark for generic 1D entangled states.

Significance. If the efficiency and variance-reduction claims hold with explicit algorithms and scaling bounds, the work would provide a practical route to scalable verification of large-scale 1D tensor-network states on near-term devices, addressing a key bottleneck in DFE for many-body systems.

major comments (1)

The central linear-scaling claim rests on the assertion that each conditional distribution p(P_k | P_<k) is efficiently computable from the MPS tensors with per-step cost independent of n (or O(D^3) for fixed bond dimension D). The manuscript must supply the explicit contraction procedure for the reduced MPS after fixing the first k-1 Paulis and state the bond-dimension scaling for the random-MPS ensemble; without this, it is unclear whether the per-shot overhead remains linear when D grows with n, as is typical for generic 1D states.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive feedback. We address the single major comment below and will revise the manuscript to incorporate the requested details on the contraction procedure and scaling.

read point-by-point responses

Referee: The central linear-scaling claim rests on the assertion that each conditional distribution p(P_k | P_<k) is efficiently computable from the MPS tensors with per-step cost independent of n (or O(D^3) for fixed bond dimension D). The manuscript must supply the explicit contraction procedure for the reduced MPS after fixing the first k-1 Paulis and state the bond-dimension scaling for the random-MPS ensemble; without this, it is unclear whether the per-shot overhead remains linear when D grows with n, as is typical for generic 1D states.

Authors: We agree that an explicit description of the contraction procedure will improve clarity. In the revised manuscript we will add a dedicated paragraph (and pseudocode in an appendix) detailing the following procedure: to evaluate p(P_k | P_<k), the first k-1 Pauli operators are contracted site-by-site into the MPS tensors. Because each Pauli acts locally on a single physical index, this contraction produces a new effective MPS on the remaining n-k+1 sites whose bond dimension remains at most D (no growth occurs). The conditional probability is then obtained by computing the squared norm of the partial contraction of this reduced MPS with the k-th Pauli (a standard O(D^3) matrix contraction) and normalizing against the sum over the four possible choices for P_k. The same reduced MPS is retained for the next step, so the per-step cost stays O(D^3) independent of n. For the random-MPS benchmark ensemble we employ a fixed bond dimension D (independent of system size n) chosen to reproduce generic area-law entanglement; numerical examples in the paper use D=4 and D=8. With this fixed-D regime the total classical preprocessing per shot is therefore strictly linear in n, as claimed. We will also add a short remark clarifying that the method extends to D scaling mildly with n (e.g., D = O(log n)) while preserving overall linear scaling provided D^3 = o(n). revision: yes

Circularity Check

0 steps flagged

No circularity: method is a direct application of autoregressive sampling to MPS structure

full rationale

The paper introduces an autoregressive importance sampler that draws Pauli strings from conditional distributions derived from MPS tensor contractions. This is a standard algorithmic construction whose claimed linear overhead follows from the fixed-bond-dimension contraction cost per conditional step, without any parameter fitting, self-definition of the target quantity, or load-bearing self-citation that reduces the result to its own inputs. The random-MPS benchmark is used only for numerical validation and does not enter the derivation as a fitted or renamed quantity. The derivation chain is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard quantum-information techniques plus one domain-specific computability assumption for MPS; no free parameters or new entities are introduced in the abstract.

axioms (2)

standard math Importance sampling yields unbiased fidelity estimators from local Pauli measurements
Standard technique in quantum state verification.
domain assumption Conditional distributions over Pauli strings are efficiently computable from the MPS tensors
Required for the claimed linear classical overhead.

pith-pipeline@v0.9.0 · 5497 in / 1155 out tokens · 58246 ms · 2026-05-10T07:50:37.985184+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

63 extracted references · 8 canonical work pages

[1]

Takeuchi and T

Y. Takeuchi and T. Morimae, Verification of many-qubit states, Physical Review X8, 021060 (2018)

2018
[2]

Eisert, D

J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum cer- tification and benchmarking, Nature Reviews Physics2, 382 (2020)

2020
[3]

Kliesch and I

M. Kliesch and I. Roth, Theory of quantum system cer- tification, PRX Quantum2, 010201 (2021)

2021
[4]

X.-D. Yu, J. Shang, and O. G¨ uhne, Statistical methods for quantum state verification and fidelity estimation, Advanced Quantum Technologies5, 2100126 (2022)

2022
[5]

Pallister, N

S. Pallister, N. Linden, and A. Montanaro, Optimal ver- ification of entangled states with local measurements, Physical Review Letters120, 170502 (2018)

2018
[6]

Zhu and M

H. Zhu and M. Hayashi, Efficient verification of pure quantum states in the adversarial scenario, arXiv preprint arXiv:1909.01900 (2019)

work page arXiv 1909
[7]

Zambrano, D

L. Zambrano, D. Farina, E. Pagliaro, M. M. Taddei, and A. Acin, Certification of quantum state functions under partial information, Quantum8, 1442 (2024)

2024
[8]

Cramer, M

M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Efficient quantum state tomography, Na- ture Communications1, 149 (2010). 11

2010
[9]

S. T. Flammia, D. Gross, S. D. Bartlett, and R. Somma, Heralded polynomial-time quantum state tomography, arXiv preprint arXiv:1002.3839 (2010)

work page arXiv 2010
[10]

Gross, Y.-K

D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eis- ert, Quantum state tomography via compressed sensing, Physical Review Letters105, 150401 (2010)

2010
[11]

Wang, Z.-Y

J. Wang, Z.-Y. Han, S.-B. Wang, Z. Li, L.-Z. Mu, H. Fan, and L. Wang, Scalable quantum tomography with fidelity estimation, Physical Review A101, 032321 (2020)

2020
[12]

M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Prac- tical characterization of quantum devices without tomog- raphy, Physical Review Letters107, 210404 (2011)

2011
[13]

S. T. Flammia and Y.-K. Liu, Direct fidelity estimation from few Pauli measurements, Physical Review Letters 106, 230501 (2011)

2011
[14]

Cerezo, A

M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles, Variational quantum fidelity estimation, Quantum4, 248 (2020)

2020
[15]

Zhang, M

X. Zhang, M. Luo, Z. Wen, Q. Feng, S. Pang, W. Luo, and X. Zhou, Direct fidelity estimation of quantum states using machine learning, Physical Review Letters127, 130503 (2021)

2021
[16]

Leone, S

L. Leone, S. F. Oliviero, and A. Hamma, Nonstabilizer- ness determining the hardness of direct fidelity estima- tion, Physical Review A107, 022429 (2023)

2023
[17]

Huang, R

H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nature Physics16, 1050 (2020)

2020
[18]

Elben, S

A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The random- ized measurement toolbox, Nature Reviews Physics5, 9 (2023)

2023
[19]

[GHO25] Meghal Gupta, William He, and Ryan O’Donnell

M. Gupta, W. He, and R. O’Donnell, Few single-qubit measurements suffice to certify any quantum state, arXiv preprint arXiv:2506.11355 (2025)

work page arXiv 2025
[20]

Huang, J

H.-Y. Huang, J. Preskill, and M. Soleimanifar, Certifying almost all quantum states with few single-qubit measure- ments, Nature Physics21, 1834 (2025)

2025
[21]

[CLSW26] Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu

A. Coladangelo, J. Li, J. Slote, and E. Wu, The power of two bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements, arXiv preprint arXiv:2602.11616 (2026)

work page arXiv 2026
[22]

Fannes, B

M. Fannes, B. Nachtergaele, and R. F. Werner, Finitely correlated states on quantum spin chains, Communica- tions in Mathematical Physics144, 443 (1992)

1992
[23]

Vidal, Efficient classical simulation of slightly entan- gled quantum computations, Physical Review Letters91, 147902 (2003)

G. Vidal, Efficient classical simulation of slightly entan- gled quantum computations, Physical Review Letters91, 147902 (2003)

2003
[24]

Eisert, M

J. Eisert, M. Cramer, and M. B. Plenio, Colloquium: Area laws for the entanglement entropy, Reviews of Mod- ern Physics82, 277 (2010)

2010
[25]

Schollw¨ ock, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96 (2011)

U. Schollw¨ ock, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96 (2011)

2011
[26]

Or´ us, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics349, 117 (2014)

R. Or´ us, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics349, 117 (2014)

2014
[27]

J. I. Cirac, D. Perez-Garcia, N. Schuch, and F. Ver- straete, Matrix product states and projected entangled pair states: Concepts, symmetries, theorems, Reviews of Modern Physics93, 045003 (2021)

2021
[28]

S. R. White, Density matrix formulation for quantum renormalization groups, Physical Review Letters69, 2863 (1992)

1992
[29]

Perez-Garcia, F

D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Matrix product state representations, Quantum Info. Comput.7, 401–430 (2007)

2007
[30]

Vidal, Classical simulation of infinite-size quantum lattice systems in one spatial dimension, Physical Review Letters98, 070201 (2007)

G. Vidal, Classical simulation of infinite-size quantum lattice systems in one spatial dimension, Physical Review Letters98, 070201 (2007)

2007
[31]

Verstraete, V

F. Verstraete, V. Murg, and J. I. Cirac, Matrix prod- uct states, projected entangled pair states, and varia- tional renormalization group methods for quantum spin systems, Advances in Physics57, 143 (2008)

2008
[32]

Sch¨ on, E

C. Sch¨ on, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf, Sequential generation of entangled multi- qubit states, Physical Review Letters95, 110503 (2005)

2005
[33]

Sch¨ on, K

C. Sch¨ on, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano, Sequential generation of matrix-product states in cavity QED, Physical Review A—Atomic, Molecular, and Optical Physics75, 032311 (2007)

2007
[34]

K. C. Smith, A. Khan, B. K. Clark, S. M. Girvin, and T.- C. Wei, Constant-depth preparation of matrix product states with adaptive quantum circuits, PRX Quantum 5, 030344 (2024)

2024
[35]

A. A. Akhtar, H.-Y. Hu, and Y.-Z. You, Scalable and flex- ible classical shadow tomography with tensor networks, Quantum7, 1026 (2023)

2023
[36]

Bertoni, J

C. Bertoni, J. Haferkamp, M. Hinsche, M. Ioannou, J. Eisert, and H. Pashayan, Shallow shadows: Expecta- tion estimation using low-depth random Clifford circuits, Physical Review Letters133, 020602 (2024)

2024
[37]

Jozsa and M

R. Jozsa and M. Van Den Nest, Classical simulation com- plexity of extended Clifford circuits, Quantum Info. Com- put.14, 633–648 (2014)

2014
[38]

Garnerone, T

S. Garnerone, T. R. de Oliveira, and P. Zanardi, Typi- cality in random matrix product states, Physical Review A—Atomic, Molecular, and Optical Physics81, 032336 (2010)

2010
[39]

Lancien and D

C. Lancien and D. P´ erez-Garc´ ıa, Correlation length in random MPS and PEPS, inAnnales Henri Poincar´ e, Vol. 23 (Springer, 2022) pp. 141–222

2022
[40]

D. Haag, F. Baccari, and G. Styliaris, Typical correlation length of sequentially generated tensor network states, PRX Quantum4, 030330 (2023)

2023
[41]

L. Chen, R. J. Garcia, K. Bu, and A. Jaffe, Magic of random matrix product states, Physical Review B109, 174207 (2024)

2024
[42]

Optimal quantum state tomog- raphy with local informationally complete measurements

C. Jameson, Z. Qin, A. Goldar, M. B. Wakin, Z. Zhu, and Z. Gong, Optimal quantum state tomography with local informationally complete measurements, arXiv preprint arXiv:2408.07115 (2024)

work page arXiv 2024
[43]

D. Malz, G. Styliaris, Z.-Y. Wei, and J. I. Cirac, Prepa- ration of matrix product states with log-depth quantum circuits, Physical Review Letters132, 040404 (2024)

2024
[44]

Leontica and A

S. Leontica and A. G. Green, An unbiased measure over the matrix product state manifold, arXiv preprint arXiv:2505.00073 (2025)

work page arXiv 2025
[45]

Jaderberg, G

B. Jaderberg, G. Pennington, K. V. Marshall, L. W. An- derson, A. Agarwal, L. P. Lindoy, I. Rungger, S. Mensa, and J. Crain, Variational preparation of normal matrix product states on quantum computers, Physical Review Research8, 013081 (2026)

2026
[46]

Baumgratz, D

T. Baumgratz, D. Gross, M. Cramer, and M. B. Plenio, Scalable reconstruction of density matrices, Physical Re- view Letters111, 020401 (2013)

2013
[47]

Guo and S

Y. Guo and S. Yang, Quantum state tomography with lo- cally purified density operators and local measurements, 12 Communications Physics7, 322 (2024)

2024
[48]

Z. Qin, C. Jameson, Z. Gong, M. B. Wakin, and Z. Zhu, Quantum state tomography for matrix product density operators, IEEE Transactions on Information Theory70, 5030 (2024)

2024
[49]

Verteletskyi, T.-C

V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov, Measure- ment optimization in the variational quantum eigensolver using a minimum clique cover, The Journal of Chemical Physics152(2020)

2020
[50]

Crawford, B

O. Crawford, B. Van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley, Efficient quantum measure- ment of Pauli operators in the presence of finite sampling error, Quantum5, 385 (2021)

2021
[51]

Hadfield, S

C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, Measurements of quantum Hamiltonians with locally- biased classical shadows, Communications in Mathemat- ical Physics391, 951 (2022)

2022
[52]

Barber` a-Rodr´ ıguez, M

J. Barber` a-Rodr´ ıguez, M. Navarro, and L. Zambrano, Sampling Groups of Pauli Operators to Enhance Direct Fidelity Estimation, Quantum9, 1784 (2025)

2025
[53]

DalFavero, R

B. DalFavero, R. Sarkar, J. Rowland, D. Camps, N. P. Sawaya, and R. LaRose, Measurement reduction for ex- pectation values via fine-grained commutativity, Physical Review A112, 052407 (2025)

2025
[54]

Li, Y.-G

Z. Li, Y.-G. Han, and H. Zhu, Optimal Verification of Greenberger-Horne-Zeilinger States, Physical Review Applied13, 054002 (2020)

2020
[55]

Cha and J

H. Cha and J. Lee, Efficient sampling for Pauli- measurement-based shadow tomography in direct fidelity estimation, Physical Review A112, 032427 (2025)

2025
[56]

M. Sun, G. Waite, M. Bremner, and C. Ferrie, Efficient Fidelity Estimation with Few Local Pauli Measurements, arXiv preprint arXiv:2510.08155 (2025)

work page arXiv 2025
[57]

H. Cha, S. Hong, and J. Lee, Operator-aware shadow im- portance sampling for accurate fidelity estimation, arXiv preprint arXiv:2511.01608 (2025)

work page arXiv 2025
[58]

Acharya, S

A. Acharya, S. Saha, and A. M. Sengupta, Shadow to- mography based on informationally complete positive operator-valued measure, Physical Review A104, 052418 (2021)

2021
[59]

L. E. Fischer, T. Dao, I. Tavernelli, and F. Tacchino, Dual-frame optimization for informationally complete quantum measurements, Physical Review A109, 062415 (2024)

2024
[60]

Cioli, E

R. Cioli, E. Ercolessi, M. Ippoliti, X. Turkeshi, and L. Piroli, Approximate inverse measurement channel for shallow shadows, Quantum9, 1698 (2025)

2025
[61]

R. M. Farias, R. D. Peddinti, I. Roth, and L. Aolita, Ro- bust ultra-shallow shadows, Quantum Science and Tech- nology10, 025044 (2025)

2025
[62]

H.-Y. Hu, A. Gu, S. Majumder, H. Ren, Y. Zhang, D. S. Wang, Y.-Z. You, Z. Minev, S. F. Yelin, and A. Seif, Demonstration of robust and efficient quantum property learning with shallow shadows, Nature Communications 16, 2943 (2025)

2025
[63]

Zhang, X

S. Zhang, X. Feng, M. Ippoliti, and Y.-Z. You, Holo- graphic classical shadow tomography, Physical Review B 111, 054306 (2025). 13 Appendix A: Tensor networks A Bba i c j Cacij = P b AabiBbcj FIG. 6: A single contraction. Connecting an edge corresponds to summing over the associated index. Tensor networks provide a compact way to represent and manipulate ...

2025