pith. sign in

arxiv: 2606.20238 · v1 · pith:7MAOVGLYnew · submitted 2026-06-18 · 🪐 quant-ph

Random Projections for Multi-Copy Quantum Algorithms

Xiaoyu Liu , Jordi Tura , Johannes Kn\"orzer This is my paper

Pith reviewed 2026-06-26 16:55 UTC · model grok-4.3

classification 🪐 quant-ph
keywords random projectionsmulti-copy measurementsnonlinear observablestrace estimationquantum state estimationsampling overheadquantum information
0
0 comments X

The pith

Random projections onto smaller subspaces allow estimating tr(ρ^K) with O(2^{(n-q)(K-1)}) copies after compressing n-qubit states to q qubits.

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

The paper develops a method to estimate nonlinear properties of quantum states such as tr(ρ^K) by first applying random projections to reduce the state to a smaller subspace and then performing collective measurements only in that subspace. This creates an explicit tradeoff where coherent operations on the full space are replaced by a statistical overhead that grows as 2^{(n-q)(K-1)}. Explicit relations are given between the averaged projected moments and the original multivariate traces. The framework is presented as a way to adapt multi-copy protocols to hardware with limited coherent resources. The scaling shows each projected-out qubit multiplies the number of required copies by 2^{K-1}.

Core claim

After random projection of an n-qubit state onto a q-qubit subspace, the Haar-averaged moments in the reduced space relate exactly to the original multivariate traces tr(ρ1⋯ρK), so that estimating tr(ρ^K) requires approximately O(2^{(n-q)(K-1)}) copies, with the projection procedure introducing only a known sampling overhead.

What carries the argument

Random projection onto a lower-dimensional subspace prior to collective measurement, followed by Haar averaging to recover the original traces.

If this is right

  • Multi-copy protocols become feasible on devices whose coherent control is limited to q qubits by accepting the corresponding copy overhead.
  • The overhead is independent of the particular states and depends only on the dimension reduction and K.
  • The formulas give a precise, tunable relation between coherent resources and statistical cost for any chosen q.
  • Collective measurements need only be implemented on the reduced q-qubit space rather than the full n-qubit space.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same projection approach could be combined with classical post-processing to further reduce total resources.
  • Extending the method to non-Haar random projections might lower the overhead for specific state families.
  • The scaling suggests a practical limit on how far dimension reduction can be pushed before the copy cost becomes prohibitive for given K.
  • Hardware platforms with many copies but restricted gate depth could adopt the protocol directly.

Load-bearing premise

The Haar-averaged projected moments relate exactly back to the original multivariate traces through the derived formulas, with projections introducing no uncontrolled errors beyond the stated sampling cost.

What would settle it

A direct numerical or experimental check on small n and K showing whether the measured number of copies needed to reach fixed precision matches the predicted factor of 2^{(n-q)(K-1)}.

Figures

Figures reproduced from arXiv: 2606.20238 by Johannes Kn\"orzer, Jordi Tura, Xiaoyu Liu.

Figure 1
Figure 1. Figure 1: FIG. 1. Comparison between standard multi-copy protocols and the random projection framework introduced in this work. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Estimated third moment ˆp [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: further illustrates the effects of choosing dif￾ferent values of NU and NM. As an example, we con￾sider the estimation of the third moment of a noisy GHZ state ρGHZ(n, w) = (1−w)|GHZn⟩ ⟨GHZn|+ 2−nwI with |GHZn⟩ = 2−1/2 (|0⟩ ⊗n + |1⟩ ⊗n ). We set n = 5 and w = 0.3. For all compression levels, the estimation er￾ror initially decreases approximately as O(N −1/2 ). When NU is limited, the error may plateau bec… view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Average required number of copies [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: shows the resulting trajectory of ∆123 in the complex plane. The dashed curve corresponds to the ex￾act values, while the markers denote estimates obtained from the random projection protocol for different pro￾jection dimensions m = 2q , where q is the number of retained qubits. For each value of q, the three pairwise overlaps enter￾ing Ξ are estimated independently using the two-copy re￾construction formu… view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Standard deviation of the sample mean [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Procedure used to generate explicit projected-moment formulas from the character representation of the coefficients. [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Random projection protocol for estimating [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. The error amplification factor [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10. Fully local randomized measurement protocol for estimating [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11. Mean absolute estimation error [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12. Mean absolute estimation error [PITH_FULL_IMAGE:figures/full_fig_p029_12.png] view at source ↗
read the original abstract

Estimating nonlinear properties of quantum states is a central task in quantum information science. Multivariate traces, $\mathrm{tr}(\rho_1 \cdots \rho_K)$, and nonlinear observables such as $\mathrm{tr}(\rho^K)$, for integer $K$, can be accessed through collective measurements on multiple state copies, but standard protocols based on swap tests require coherent operations on the full Hilbert space and become experimentally unfeasible for large systems. In this work, we introduce a framework for multi-copy measurements based on random projections onto lower-dimensional subspaces prior to the collective measurement, which is then performed only on the reduced Hilbert space. This procedure yields a tunable tradeoff between coherent quantum resources and statistical sampling overhead, allowing the amount of coherent processing to be matched to the capabilities of the underlying hardware. We derive explicit formulas relating the Haar-averaged projected moments to multivariate traces of the original states and analyze the sampling overhead induced by the projection procedure. Specifically, after compressing an $n$-qubit state to a reduced $q$-qubit subspace, estimating $\mathrm{tr}(\rho^K)$ requires approximately $O(2^{(n-q)(K-1)})$ copies of $\rho$, with each qubit projected out increasing the sampling cost by a factor of $2^{K-1}$. Our results establish how coherent multi-copy operations can be traded for additional state copies, enabling multi-copy quantum protocols to be optimized for the available hardware resources.

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 manuscript introduces random projections onto lower-dimensional subspaces prior to collective multi-copy measurements to estimate nonlinear properties such as tr(ρ^K). It derives explicit formulas relating Haar-averaged projected moments to the original multivariate traces and analyzes the induced sampling overhead, claiming that compression from n to q qubits requires O(2^{(n-q)(K-1)}) copies of ρ, with each projected qubit multiplying the cost by 2^{K-1}.

Significance. If the explicit formulas and exact relations hold without hidden state-dependent factors or excess variance, the work supplies a concrete, tunable resource tradeoff between coherent processing depth and sampling cost. This is potentially useful for matching multi-copy protocols to near-term hardware constraints. The provision of closed-form overhead expressions is a concrete strength for quantitative protocol design.

major comments (1)
  1. [Abstract] Abstract and central derivation: the headline overhead O(2^{(n-q)(K-1)}) is asserted to follow from an exact relation between the Haar-averaged projected moment and tr(ρ^K). The manuscript must exhibit the explicit inversion map and demonstrate that it is unbiased (no state-dependent prefactor) and that the variance of the estimator concentrates at the stated rate; any non-constant kernel or additional averaging variance would invalidate the quoted scaling.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We appreciate the recognition of the potential utility of the random projection framework for providing a tunable resource tradeoff in multi-copy estimation protocols. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and central derivation: the headline overhead O(2^{(n-q)(K-1)}) is asserted to follow from an exact relation between the Haar-averaged projected moment and tr(ρ^K). The manuscript must exhibit the explicit inversion map and demonstrate that it is unbiased (no state-dependent prefactor) and that the variance of the estimator concentrates at the stated rate; any non-constant kernel or additional averaging variance would invalidate the quoted scaling.

    Authors: We agree that an explicit inversion map and verification of unbiasedness and variance concentration are essential to substantiate the claimed overhead. The manuscript derives the explicit relation between the Haar-averaged projected moment and tr(ρ^K) (see the central formula relating the two quantities and the subsequent overhead analysis), which takes the form of a state-independent constant prefactor 2^{-(n-q)(K-1)} multiplying tr(ρ^K). Inversion is therefore achieved by simple rescaling with this constant, introducing no state-dependent kernel. The variance analysis establishes that the estimator remains unbiased after inversion and that the variance concentrates at the standard Monte Carlo rate scaled by the overhead factor, without additional excess variance from the projection averaging. To address the referee's request for greater explicitness, the revised manuscript will include a dedicated subsection that isolates the inversion map, provides a self-contained proof of unbiasedness, and restates the variance bound with the concentration rate. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation of overhead follows from explicit Haar-averaged formulas.

full rationale

The abstract states that explicit formulas are derived relating Haar-averaged projected moments to the original multivariate traces, and the O(2^{(n-q)(K-1)}) overhead is presented as a direct consequence of this relation (each projected qubit multiplies cost by 2^{K-1}). No quoted step reduces a claimed prediction to a fitted parameter, self-definition, or load-bearing self-citation. The mapping is described as exact under Haar averaging, with the sampling cost analyzed as induced overhead rather than assumed or renamed. The central claim remains independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard quantum mechanics, the existence of Haar-random projections, and the ability to perform collective measurements in the reduced subspace.

axioms (2)
  • domain assumption Quantum states are described by density operators and collective measurements on multiple copies are possible in principle.
    Invoked throughout the abstract when discussing multi-copy protocols.
  • standard math Averaging over the Haar measure on the projection unitaries yields exact relations to the original traces.
    Central to the claim that projected moments recover the multivariate traces.

pith-pipeline@v0.9.1-grok · 5783 in / 1162 out tokens · 29435 ms · 2026-06-26T16:55:55.262616+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

49 extracted references · 1 canonical work pages

  1. [1]

    Y. Quek, E. Kaur, and M. M. Wilde, Multivariate trace estimation in constant quantum depth, Quantum8, 1220 (2024)

    2024

  2. [2]

    Fernandes, R

    C. Fernandes, R. Wagner, L. Novo, and E. F. Galv˜ ao, Unitary-Invariant Witnesses of Quantum Imaginarity, Physical Review Letters133, 190201 (2024)

    2024

  3. [3]

    A. R´ enyi, On Measures of Entropy and Information, in Proceedings of the Fourth Berkeley Symposium on Math- ematical Statistics and Probability, Volume 1: Contribu- tions to the Theory of Statistics, Vol. 4.1 (University of California Press, 1961) pp. 547–562

    1961

  4. [4]

    M¨ uller-Lennert, F

    M. M¨ uller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, On quantum R´ enyi entropies: A new generalization and some properties, Journal of Mathe- matical Physics54, 122203 (2013)

    2013

  5. [5]

    S. A. Hill and W. K. Wootters, Entanglement of a Pair of Quantum Bits, Physical Review Letters78, 5022 (1997)

    1997

  6. [6]

    Yang, M.-X

    X. Yang, M.-X. Luo, Y.-H. Yang, and S.-M. Fei, Parametrized entanglement monotone, Physical Review A103, 052423 (2021)

    2021

  7. [7]

    Coffman, J

    V. Coffman, J. Kundu, and W. K. Wootters, Distributed entanglement, Physical Review A61, 052306 (2000)

    2000

  8. [8]

    Wong and N

    A. Wong and N. Christensen, Potential multiparticle entanglement measure, Physical Review A63, 044301 (2001)

    2001

  9. [9]

    D. A. Meyer and N. R. Wallach, Global entanglement in multiparticle systems, Journal of Mathematical Physics 43, 4273 (2002)

    2002

  10. [10]

    J. L. Beckey, N. Gigena, P. J. Coles, and M. Cerezo, Computable and Operationally Meaningful Multipartite Entanglement Measures, Physical Review Letters127, 140501 (2021)

    2021

  11. [11]

    X. Liu, J. Kn¨ orzer, Z. J. Wang, and J. Tura, Generalized concentratable entanglement via parallelized permuta- tion tests, Physical Review Research7, L032022 (2025)

    2025

  12. [12]

    Foulds, V

    S. Foulds, V. Kendon, and T. Spiller, The controlled SWAP test for determining quantum entanglement, Quantum Science and Technology6, 035002 (2021)

    2021

  13. [13]

    X. Liu, J. Tura, and A. Rico, Measuring multipartite entanglement efficiently by testing symmetries (2025), arXiv:2511.07537 [quant-ph]

    arXiv 2025

  14. [14]

    Buhrman, R

    H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Quantum Fingerprinting, Physical Review Letters87, 167902 (2001)

    2001

  15. [15]

    A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek, Direct Estimations of Linear and Nonlinear Functionals of a Quantum State, Physical Review Letters88, 217901 (2002)

    2002

  16. [16]

    Subramanian and M.-H

    S. Subramanian and M.-H. Hsieh, Quantum algorithm for estimatingα-Renyi entropies of quantum states, Physical Review A104, 022428 (2021)

    2021

  17. [17]

    Y. Wang, B. Zhao, and X. Wang, Quantum Algorithms for Estimating Quantum Entropies, Physical Review Ap- plied19, 044041 (2023)

    2023

  18. [18]

    M. Shin, J. Lee, S. Lee, and K. Jeong, Resource-efficient algorithm for estimating the trace of quantum state pow- ers, Quantum9, 1832 (2025)

    2025

  19. [19]

    D. A. Abanin and E. Demler, Measuring Entanglement Entropy of a Generic Many-Body System with a Quan- tum Switch, Physical Review Letters109, 020504 (2012)

    2012

  20. [20]

    A. J. Daley, H. Pichler, J. Schachenmayer, and P. Zoller, Measuring Entanglement Growth in Quench Dynamics of Bosons in an Optical Lattice, Physical Review Letters 109, 020505 (2012)

    2012

  21. [21]

    N. M. Linke, S. Johri, C. Figgatt, K. A. Landsman, A. Y. Matsuura, and C. Monroe, Measuring the R´ enyi entropy of a two-site Fermi-Hubbard model on a trapped ion quantum computer, Physical Review A98, 052334 (2018)

    2018

  22. [22]

    Brydges, A

    T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Probing R´ enyi entanglement entropy via random- ized measurements, Science364, 260 (2019)

    2019

  23. [23]

    Elben, B

    A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller, R´ enyi Entropies from Random Quenches in Atomic Hubbard and Spin Models, Physical Review Let- ters120, 050406 (2018)

    2018

  24. [24]

    Vermersch, A

    B. Vermersch, A. Elben, M. Dalmonte, J. I. Cirac, and P. Zoller, Unitaryn-designs via random quenches in atomic hubbard and spin models, Physical Review A97, 023604 (2018)

    2018

  25. [25]

    Elben, R

    A. Elben, R. Kueng, H.-Y. R. Huang, R. Van Bij- nen, C. Kokail, M. Dalmonte, P. Calabrese, B. Kraus, J. Preskill, P. Zoller, and B. Vermersch, Mixed-State Entanglement from Local Randomized Measurements, Physical Review Letters125, 200501 (2020)

    2020

  26. [26]

    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

  27. [27]

    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

  28. [28]

    Brun, Measuring polynomial functions of states, Quantum Information and Computation4, 401 (2004)

    T. Brun, Measuring polynomial functions of states, Quantum Information and Computation4, 401 (2004)

    2004

  29. [29]

    Cotler, S

    J. Cotler, S. Choi, A. Lukin, H. Gharibyan, T. Grover, M. E. Tai, M. Rispoli, R. Schittko, P. M. Preiss, A. M. Kaufman, M. Greiner, H. Pichler, and P. Hayden, Quan- 7 tum Virtual Cooling, Physical Review X9, 031013 (2019)

    2019

  30. [30]

    W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Virtual Distillation for Quantum Error Miti- gation, Physical Review X11, 041036 (2021)

    2021

  31. [31]

    Koczor, Exponential Error Suppression for Near-Term Quantum Devices, Physical Review X11, 031057 (2021)

    B. Koczor, Exponential Error Suppression for Near-Term Quantum Devices, Physical Review X11, 031057 (2021)

    2021

  32. [32]

    Johri, D

    S. Johri, D. S. Steiger, and M. Troyer, Entanglement spectroscopy on a quantum computer, Physical Review B96, 195136 (2017)

    2017

  33. [33]

    Barenco, A

    A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello, Stabilization of Quan- tum Computations by Symmetrization, SIAM Journal on Computing26, 1541 (1997)

    1997

  34. [34]

    Buhrman, D

    H. Buhrman, D. Grinko, P. V. Lunel, and J. Weggemans, Permutation tests for quantum state identity (2026), arXiv:2405.09626 [quant-ph]

    Pith/arXiv arXiv 2026

  35. [35]

    M. Kada, H. Nishimura, and T. Yamakami, The efficiency of quantum identity testing of multiple states, Journal of Physics A: Mathematical and Theoretical41, 395309 (2008)

    2008

  36. [36]

    M. L. LaBorde, S. Rethinasamy, and M. M. Wilde, Quan- tum Algorithms for Realizing Symmetric, Asymmetric, and Antisymmetric Projectors (2024), arXiv:2407.17563 [quant-ph]

    arXiv 2024

  37. [37]

    J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, Sample- Optimal Tomography of Quantum States, IEEE Trans- actions on Information Theory63, 5628 (2017)

    2017

  38. [38]

    Acharya, I

    J. Acharya, I. Issa, N. V. Shende, and A. B. Wagner, Estimating Quantum Entropy, IEEE Journal on Selected Areas in Information Theory1, 454 (2020)

    2020

  39. [39]

    Q. Ye, Z. Liu, and D.-L. Deng, Exponential Advantage from One More Replica in Estimating Nonlinear Proper- ties of Quantum States (2025), arXiv:2509.24000 [quant- ph]

    arXiv 2025

  40. [40]

    Anshu, Z

    A. Anshu, Z. Landau, and Y. Liu, Distributed quantum inner product estimation, inProceedings of the 54th An- nual ACM SIGACT Symposium on Theory of Computing (2022) pp. 44–51, arXiv:2111.03273 [quant-ph]

    arXiv 2022

  41. [41]

    Kn¨ orzer, X

    J. Kn¨ orzer, X. Liu, B. Schiffer, and J. Tura Brugu´ es, Distributed quantum information processing: A re- view of recent progress, Reports on Progress in Physics 10.1088/1361-6633/ae74e0 (2026)

    work page doi:10.1088/1361-6633/ae74e0 2026

  42. [42]

    Arunachalam and L

    S. Arunachalam and L. Schatzki, Distributed inner prod- uct estimation with limited quantum communication (2024), arXiv:2410.12684 [quant-ph]

    arXiv 2024

  43. [43]

    Z. Li, D. Chen, D. Qin, Y. Yang, and Y. Zhou, Quantum Nonlinear Properties from a Single Measurement Setting (2026), arXiv:2605.09958 [quant-ph]

    Pith/arXiv arXiv 2026

  44. [44]

    K¨ ostenberger, Weingarten Calculus (2021), arXiv:2101.00921 [math.PR]

    G. K¨ ostenberger, Weingarten Calculus (2021), arXiv:2101.00921 [math.PR]

    arXiv 2021

  45. [45]

    I. G. Macdonald,Symmetric Functions and Hall Polyno- mials(Oxford University Press, 1995)

    1995

  46. [46]

    F. G. S. L. Brand˜ ao, A. W. Harrow, and M. Horodecki, Local Random Quantum Circuits are Approximate Polynomial-Designs, Communications in Mathematical Physics346, 397 (2016)

    2016

  47. [47]

    Haferkamp, Random Quantum Circuits Are Approxi- mate Unitaryt-Designs in DepthO(nt 5+o(1)), Quantum 6, 795 (2022)

    J. Haferkamp, Random Quantum Circuits Are Approxi- mate Unitaryt-Designs in DepthO(nt 5+o(1)), Quantum 6, 795 (2022)

    2022

  48. [48]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science389, 92 (2025)

    2025

  49. [49]

    L. Cui, T. Schuster, F. Brandao, and H.-Y. Huang, Unitary designs in nearly optimal depth (2025), arXiv:2507.06216 [quant-ph]. END MATTER Example of Bargmann invariant.—Bargmann invari- ants are quantities of the form ∆ = tr(ρ 1 · · ·ρ K). For K⩾3, different cyclic orderings of the density matri- ces are generally coupled through Eq. (2). The simplest non...

    arXiv 2025