pith. sign in

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

Verifying random matrix product states with autoregressive local measurements

Hyunho Cha , Subin Kim , Jungwoo Lee This is my paper

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
0 comments X

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 1
Figure 1. Figure 1: FIG. 1: Schematic of our MPS-(G)DFE protocol. Given [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
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. Figure 4: FIG. 4: The [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 3
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. 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. 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.

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)
  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

  1. 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)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

63 extracted references · 63 canonical work pages

  1. [1]

    Takeuchi and T

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

    work page 2018

  2. [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)

    work page 2020

  3. [3]

    Kliesch and I

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

    work page 2021

  4. [4]

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

    work page 2022

  5. [5]

    Pallister, N

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

    work page 2018

  6. [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. [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)

    work page 2024

  8. [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

    work page 2010

  9. [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 Pith review arXiv 2010

  10. [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)

    work page 2010

  11. [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)

    work page 2020

  12. [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)

    work page 2011

  13. [13]

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

    work page 2011

  14. [14]

    Cerezo, A

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

    work page 2020

  15. [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)

    work page 2021

  16. [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)

    work page 2023

  17. [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)

    work page 2020

  18. [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)

    work page 2023

  19. [19]

    Gupta, W

    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. [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)

    work page 2025

  21. [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. [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)

    work page 1992

  23. [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)

    work page 2003

  24. [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)

    work page 2010

  25. [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)

    work page 2011

  26. [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)

    work page 2014

  27. [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)

    work page 2021

  28. [28]

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

    work page 1992

  29. [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)

    work page 2007

  30. [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)

    work page 2007

  31. [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)

    work page 2008

  32. [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)

    work page 2005

  33. [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)

    work page 2007

  34. [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)

    work page 2024

  35. [35]

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

    work page 2023

  36. [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)

    work page 2024

  37. [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)

    work page 2014

  38. [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)

    work page 2010

  39. [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

    work page 2022

  40. [40]

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

    work page 2023

  41. [41]

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

    work page 2024

  42. [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. [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)

    work page 2024

  44. [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. [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)

    work page 2026

  46. [46]

    Baumgratz, D

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

    work page 2013

  47. [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)

    work page 2024

  48. [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)

    work page 2024

  49. [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)

    work page 2020

  50. [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)

    work page 2021

  51. [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)

    work page 2022

  52. [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)

    work page 2025

  53. [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)

    work page 2025

  54. [54]

    Li, Y.-G

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

    work page 2020

  55. [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)

    work page 2025

  56. [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. [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. [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)

    work page 2021

  59. [59]

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

    work page 2024

  60. [60]

    Cioli, E

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

    work page 2025

  61. [61]

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

    work page 2025

  62. [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)

    work page 2025

  63. [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 ...

    work page 2025