pith. sign in

arxiv: 2606.05099 · v1 · pith:GITOKVKZnew · submitted 2026-06-03 · 🪐 quant-ph · cs.CC· cs.IT· math.IT

Quantum Time Lower Bounds by Permutation Invariance

Qisheng Wang This is my paper

Pith reviewed 2026-06-28 05:56 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.ITmath.IT
keywords quantum time complexitylower boundspermutation invariancequantum state testingSWAP testsample complexitycircuit sizepurity estimation
0
0 comments X

The pith

Permutation invariance reduces quantum sample complexity lower bounds to matching time complexity lower bounds.

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

The paper introduces a framework that converts lower bounds on the number of samples needed to test permutation-invariant properties of quantum states into lower bounds on the size of quantum circuits that perform the same tests. It applies this reduction to establish that several standard protocols achieve the best possible circuit size. A sympathetic reader would care because prior work had left open whether these protocols could be improved by using fewer gates even when sample counts were already optimal. The result shows that for these tasks the information extraction cost dominates the circuit size.

Core claim

For testing permutation-invariant properties of quantum states, lower bounds on quantum sample complexity imply matching lower bounds on quantum time complexity (circuit size) via a direct reduction that incurs no significant overhead. Applying the reduction shows that the SWAP test is time-optimal for estimating purity and inner products, the Shift test is time-optimal for high-order functionals tr(ρ^k), the productness tester is time-optimal, the LMR protocol is time-optimal for reflection about a pure state, the samplizer is time-optimal for pure states, and the estimator for pure-state trace distance and fidelity is time-optimal.

What carries the argument

The reduction from quantum sample complexity lower bounds to quantum time complexity lower bounds for permutation-invariant properties.

If this is right

  • The SWAP test is time-optimal for estimating tr(ρ²) and tr(ρσ).
  • The Shift test is time-optimal for estimating tr(ρ^k).
  • The productness tester for multipartite pure states is time-optimal.
  • The LMR protocol is time-optimal for implementing the reflection operator about a pure state.
  • The samplizer and pure-state trace-distance estimator are time-optimal.

Where Pith is reading between the lines

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

  • The same reduction technique could be applied to derive time lower bounds for other quantum state properties that are invariant under permutations.
  • The result indicates that the dominant cost in these tasks is the number of independent samples required rather than additional computation per sample.
  • Analogous reductions might exist for properties invariant under other symmetry groups.

Load-bearing premise

A time-efficient quantum circuit for a permutation-invariant testing task can be converted into a sample-efficient procedure without substantial extra cost.

What would settle it

A quantum circuit that solves one of the listed tasks, such as estimating purity via the SWAP test, using fewer gates than the known sample complexity lower bound.

Figures

Figures reproduced from arXiv: 2606.05099 by Qisheng Wang.

Figure 1
Figure 1. Figure 1: Diagram of relationships amongst our results. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Quantum circuit for tester T . 16 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
read the original abstract

Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(\rho^2)$ and the inner product $\operatorname{tr}(\rho\sigma)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(\rho^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.

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

2 major / 2 minor

Summary. The manuscript introduces a framework that reduces known quantum sample-complexity lower bounds for permutation-invariant properties of quantum states to quantum circuit-size (time-complexity) lower bounds. It applies the framework to obtain matching lower bounds establishing time-optimality of the SWAP test for purity and inner-product estimation, the Shift test for tr(ρ^k), the Harrow-Montanaro productness tester, the LMR reflection protocol, the Wang-Zhang samplizer, and the Wang-Zhang trace-distance/fidelity estimator.

Significance. If the reduction is shown to be overhead-free, the result would be significant: it supplies the first systematic method for proving tight quantum time lower bounds and supplies matching optimality statements for six well-known protocols whose upper bounds were previously known only in the sample or query model.

major comments (2)
  1. [§3] §3 (Framework), reduction theorem: the claim that symmetrization over the symmetric group maps an Ω(f(n)) sample lower bound to an Ω(f(n)) time lower bound with no polynomial or super-constant overhead is load-bearing for all matching claims; the argument must explicitly bound the cost of averaging or embedding, because a linear-in-k or poly(d) factor would make the derived time lower bound strictly weaker than the cited constant-size or polylog upper bounds.
  2. [Abstract] Abstract, items 1–6, and §4–§9 (applications): each optimality statement (“time-optimal”) rests on the reduction being tight; if the symmetrization step introduces even a logarithmic overhead, the “matching” language is no longer supported and the statements must be weakened to “nearly matching up to log factors.”
minor comments (2)
  1. The 2025 citation for the samplizer and the 2026 citation for the trace-distance estimator should be replaced by arXiv numbers or updated publication details if they have appeared.
  2. Notation for the symmetric-group averaging operator is introduced without an explicit equation number; adding an equation label would improve readability when the reduction is invoked in later sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The concerns about potential overhead in the symmetrization step are important for validating the tightness of the derived time lower bounds. We address both major comments below and will revise the manuscript to include an explicit overhead analysis in §3. This clarification supports rather than weakens the matching claims.

read point-by-point responses

  1. Referee: [§3] §3 (Framework), reduction theorem: the claim that symmetrization over the symmetric group maps an Ω(f(n)) sample lower bound to an Ω(f(n)) time lower bound with no polynomial or super-constant overhead is load-bearing for all matching claims; the argument must explicitly bound the cost of averaging or embedding, because a linear-in-k or poly(d) factor would make the derived time lower bound strictly weaker than the cited constant-size or polylog upper bounds.

    Authors: We agree that an explicit bound on the symmetrization cost is required to rigorously support the no-overhead claim. In the framework of §3, the reduction proceeds by embedding the sample lower bound into a permutation-invariant circuit and then averaging over S_n via a fixed-size quantum circuit that implements the group action without repetition or dependence on k or d. The averaging is realized by a constant-depth circuit whose size is independent of the input parameters (using the fact that the property is fully symmetric). We will add a dedicated lemma in the revised §3 that formally bounds the total circuit-size overhead by a universal constant C (independent of n, k, d). This preserves the Ω(f(n)) time lower bound exactly as stated. revision: yes

  2. Referee: [Abstract] Abstract, items 1–6, and §4–§9 (applications): each optimality statement (“time-optimal”) rests on the reduction being tight; if the symmetrization step introduces even a logarithmic overhead, the “matching” language is no longer supported and the statements must be weakened to “nearly matching up to log factors.”

    Authors: Because the revised §3 will establish that the symmetrization overhead is a fixed constant (not logarithmic or polynomial), the time lower bounds remain asymptotically tight against the known constant-size or polylog upper bounds. Consequently the six optimality statements in the abstract and applications sections require no weakening. The language “time-optimal” continues to be justified once the explicit bound is supplied. revision: no

Circularity Check

0 steps flagged

No significant circularity; reduction framework is independent of target bounds

full rationale

The paper introduces a reduction from known quantum sample-complexity lower bounds to quantum time-complexity lower bounds for permutation-invariant properties. The listed matching results rely on external sample lower bounds (from 2001–2014 literature for most cases) paired with explicit upper-bound protocols; the two Wang–Zhang citations (2025/2026) supply sample bounds that are treated as independent inputs rather than derived inside this manuscript. No equations in the abstract or described framework equate a time lower bound to a fitted parameter or to a self-citation by construction. The derivation chain therefore remains non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; central claim rests on standard quantum circuit model and the validity of the reduction step.

axioms (2)
  • domain assumption Quantum circuits are the model for time complexity
    Implicit in all quantum complexity claims; abstract assumes standard circuit model.
  • ad hoc to paper Permutation-invariant properties admit a reduction from sample to time complexity
    Core of the framework; stated in abstract but not derived here.

pith-pipeline@v0.9.1-grok · 5871 in / 1192 out tokens · 27863 ms · 2026-06-28T05:56:23.044748+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

70 extracted references · 55 canonical work pages

  1. [1]

    , title =

    Helstrom, Carl W. , title =. Information and Control , volume =. doi:10.1016/S0019-9958(67)90302-6 , year =

    work page doi:10.1016/s0019-9958(67)90302-6

  2. [2]

    , title =

    Holevo, Alexander S. , title =. Journal of Multivariate Analysis , volume =. doi:10.1016/0047-259X(73)90028-6 , year =

    work page doi:10.1016/0047-259x(73)90028-6

  3. [3]

    and van de Graaf, Jeroen , title =

    Fuchs, Christopher A. and van de Graaf, Jeroen , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/18.761271 , year =

    work page doi:10.1109/18.761271

  4. [4]

    IEEE Transactions on Information Theory , volume =

    Chen, Kean and Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2026.3697790 , eprint =

    work page doi:10.1109/tit.2026.3697790 2026

  5. [5]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Testing matrix product states , author =. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. doi:10.1137/1.9781611977073.68 , year =

    work page doi:10.1137/1.9781611977073.68 2022

  6. [6]

    Quantum fingerprinting

    Buhrman, Harry and Cleve, Richard and Watrous, John and de Wolf, Ronald , title =. Physical Review Letters , volume =. doi:10.1103/PhysRevLett.87.167902 , year =

    work page Pith review doi:10.1103/physrevlett.87.167902

  7. [7]

    and Alves, Carolina Moura and Oi, Daniel K

    Ekert, Artur K. and Alves, Carolina Moura and Oi, Daniel K. L. and Horodecki, Micha. Direct estimations of linear and nonlinear functionals of a quantum state , journal =. doi:10.1103/PhysRevLett.88.217901 , year =

    work page doi:10.1103/physrevlett.88.217901

  8. [8]

    and Montanaro, Ashley , title =

    Harrow, Aram W. and Montanaro, Ashley , title =. Journal of the ACM , volume =. doi:10.1145/2432622.2432625 , year =

    work page doi:10.1145/2432622.2432625

  9. [9]

    Quantum principal component analysis.Nature Physics, 10(9):631–633, 2014.doi:10.1038/nphys3029

    Lloyd, Seth and Mohseni, Masoud and Rebentrost, Patrick , journal =. Quantum principal component analysis , volume =. doi:10.1038/nphys3029 , year =

    work page doi:10.1038/nphys3029

  10. [10]

    , title =

    Kimmel, Shelby and Lin, Cedric Yen-Yu and Low, Guang Hao and Ozols, Maris and Yoder, Theodore J. , title =. npj Quantum Information , volume =. doi:10.1038/s41534-017-0013-7 , year =

    work page doi:10.1038/s41534-017-0013-7

  11. [11]

    IEEE Transactions on Information Theory , volume =

    Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2025.3576137 , year =

    work page doi:10.1109/tit.2025.3576137 2025

  12. [12]

    Theory of Computing Library , series =

    Montanaro, Ashley and de Wolf, Ronald , title =. Theory of Computing Library , series =. 2016 , publisher =. doi:10.4086/toc.gs.2016.007 , pages =

    work page doi:10.4086/toc.gs.2016.007 2016

  13. [13]

    SIAM Journal on Computing , volume =

    Bernstein, Ethan and Vazirani, Umesh , title =. SIAM Journal on Computing , volume =. doi:10.1137/S0097539796300921 , year =

    work page doi:10.1137/s0097539796300921

  14. [14]

    SIAM Journal on Computing , volume =

    Ambainis, Andris , title =. SIAM Journal on Computing , volume =. doi:10.1137/S0097539705447311 , year =

    work page doi:10.1137/s0097539705447311

  15. [15]

    2209.14146 , howpublished =

    Jeffery, Stacey , title =. 2209.14146 , howpublished =

    arXiv

  16. [16]

    Quantum , volume =

    Belovs, Aleksandrs and Jeffery, Stacey and Yolcu, Duyal , title =. Quantum , volume =. doi:10.22331/q-2024-08-23-1444 , year =

    work page doi:10.22331/q-2024-08-23-1444 2024

  17. [17]

    and Jeffery, Stacey and Kothari, Robin and Magniez, Frédéric , title =

    Belovs, Aleksandrs and Childs, Andrew M. and Jeffery, Stacey and Kothari, Robin and Magniez, Frédéric , title =. Proceedings of the 40th International Colloquium on Automata, Languages, and Programming , pages =. doi:10.1007/978-3-642-39206-1_10 , year =

    work page doi:10.1007/978-3-642-39206-1_10

  18. [18]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =

    Jeffery, Stacey and Zur, Sebastian , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/3564246.3585158 , year =

    work page doi:10.1145/3564246.3585158

  19. [19]

    Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science , pages =

    Cornelissen, Arjan and Jeffery, Stacey and Ozols, Maris and Piedrafita, Alvaro , title =. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science , pages =. doi:10.4230/LIPIcs.MFCS.2020.26 , year =

    work page doi:10.4230/lipics.mfcs.2020.26 2020

  20. [20]

    2311.16401 , year =

    Allcock, Jonathan and Bao, Jinge and Belovs, Aleksandrs and Lee, Troy and Santha, Miklos , title =. 2311.16401 , year =

    arXiv

  21. [21]

    and Harrow, Aram W

    Bacon, Dave and Chuang, Isaac L. and Harrow, Aram W. , title =. Physical Review Letters , volume =. doi:10.1103/PhysRevLett.97.170502 , year =

    work page doi:10.1103/physrevlett.97.170502

  22. [22]

    and Harrow, Aram W

    Bacon, Dave and Chuang, Isaac L. and Harrow, Aram W. , title =. Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. doi:, url =

  23. [23]

    and Harrow, Aram W

    Childs, Andrew M. and Harrow, Aram W. and Wocjan, Pawe. Weak. Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science , pages =. doi:10.1007/978-3-540-70918-3_51 , year =

    work page doi:10.1007/978-3-540-70918-3_51

  24. [24]

    , title =

    Nguyen, Quynh T. , title =. 2310.01613 , year =

    arXiv

  25. [25]

    2310.02252 , year =

    Grinko, Dmitry and Burchardt, Adam and Ozols, Maris , title =. 2310.02252 , year =

    arXiv

  26. [26]

    , title =

    Go, Byeongseon and Kwon, Hyukjoon and Park, Siheon and Patel, Dhrumil and Wilde, Mark M. , title =. 2412.02134 , year =

    arXiv

  27. [27]

    and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =

    Haah, Jeongwan and Harrow, Aram W. and Ji, Zhengfeng and Wu, Xiaodi and Yu, Nengkun , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2017.2719044 , year =

    work page doi:10.1109/tit.2017.2719044 2017

  28. [28]

    Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages =

    O'Donnell, Ryan and Wright, John , title =. Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/2897518.2897544 , year =

    work page doi:10.1145/2897518.2897544

  29. [29]

    Efficient quantum to- mography II

    O'Donnell, Ryan and Wright, John , title =. Proceedings of the 49th Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/3055399.3055454 , year =

    work page doi:10.1145/3055399.3055454

  30. [30]

    Quantum state certification , booktitle =

    B. Quantum state certification , booktitle =. doi:10.1145/3313276.3316344 , year =

    work page doi:10.1145/3313276.3316344

  31. [31]

    Communications in Mathematical Physics , volume =

    O'Donnell, Ryan and Wright, John , title =. Communications in Mathematical Physics , volume =. doi:10.1007/s00220-021-04180-1 , year =

    work page doi:10.1007/s00220-021-04180-1

  32. [32]

    IEEE Transactions on Information Theory , volume =

    Wang, Qisheng and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2023.3321121 , year =

    work page doi:10.1109/tit.2023.3321121 2023

  33. [33]

    and Wagner, Aaron B

    Acharya, Jayadev and Issa, Ibrahim and Shende, Nirmal V. and Wagner, Aaron B. , title =. IEEE Journal on Selected Areas in Information Theory , volume =. doi:10.1109/JSAIT.2020.3015235 , year =

    work page doi:10.1109/jsait.2020.3015235 2020

  34. [34]

    Bavarian, Mohammad and Mehraban, Saeed and Wright, John , title =

  35. [35]

    Quantum lower bounds by polynomials

    Beals, Robert and Buhrman, Harry and Cleve, Richard and Mosca, Michele and de Wolf, Ronald , title =. Journal of the ACM , volume =. doi:10.1145/502090.502097 , year =

    work page doi:10.1145/502090.502097

  36. [36]

    Journal of Computer and System Sciences , volume =

    Ambainis, Andris , title =. Journal of Computer and System Sciences , volume =. doi:10.1006/jcss.2002.1826 , year =

    work page doi:10.1006/jcss.2002.1826 2002

  37. [37]

    A fast quantum mechanical algorithm for database search

    Grover, Lov K. , title =. Proceedings of the 28th Annual ACM Symposium on Theory of Computing , pages =. doi:10.1145/237814.237866 , year =

    work page doi:10.1145/237814.237866

  38. [38]

    and Bernstein, Ethan and Brassard, Gilles and Vazirani, Umesh , title =

    Bennett, Charles H. and Bernstein, Ethan and Brassard, Gilles and Vazirani, Umesh , title =. SIAM Journal on Computing , volume =. doi:10.1137/S0097539796300933 , year =

    work page doi:10.1137/s0097539796300933

  39. [39]

    Tight bounds on quantum searching , journal =

    Boyer, Michel and Brassard, Gilles and H. Tight bounds on quantum searching , journal =. doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P , year =

    work page doi:10.1002/(sici)1521-3978(199806)46:4/5

  40. [40]

    Physical Review A , volume =

    Zalka, Christof , title =. Physical Review A , volume =. doi:10.1103/PhysRevA.60.2746 , year =

    work page doi:10.1103/physreva.60.2746

  41. [41]

    , title =

    Grover, Lov K. , title =. Physical Review A , volume =. doi:10.1103/PhysRevA.66.052314 , year =

    work page doi:10.1103/physreva.66.052314

  42. [42]

    Quantum Information and Computation , volume =

    Arunachalam, Srinivasan and de Wolf, Ronald , title =. Quantum Information and Computation , volume =. doi:10.26421/QIC17.3-4-4 , year =

    work page doi:10.26421/qic17.3-4-4

  43. [43]

    IEEE Transactions on Information Theory , volume=

    Unitarity estimation for quantum channels , author=. IEEE Transactions on Information Theory , volume=. doi:10.1109/TIT.2023.3263645 , year=

    work page doi:10.1109/tit.2023.3263645 2023

  44. [44]

    2410.12712 , howpublished =

    Gong, Weiyuan and Haferkamp, Jonas and Ye, Qi and Zhang, Zhihan , title =. 2410.12712 , howpublished =

    arXiv

  45. [45]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Anshu, Anurag and Landau, Zeph and Liu, Yunchao , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =. doi:10.1145/3519935.3519974 , year =

    work page doi:10.1145/3519935.3519974

  46. [46]

    IEEE Transactions on Information Theory , volume =

    Chen, Kean and Wang, Qisheng and Yu, Zhan and Zhang, Zhicheng , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2026.3699531 , year =

    work page doi:10.1109/tit.2026.3699531 2026

  47. [47]

    Physical Review Letters , volume =

    Mintert, Florian and Kuś, Marek and Buchleitner, Andreas , title =. Physical Review Letters , volume =. doi:10.1103/PhysRevLett.95.260502 , year =

    work page doi:10.1103/physrevlett.95.260502

  48. [48]

    Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming , pages =

    Wang, Qisheng and Zhang, Zhicheng , title =. Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming , pages =. doi:, eprint =

  49. [49]

    IEEE Transactions on Information Theory , volume=

    Optimal trace distance and fidelity estimations for pure quantum states , author=. IEEE Transactions on Information Theory , volume=. 2024 , doi=

    2024

  50. [50]

    2018 , doi =

    Watrous, John , title =. 2018 , doi =

    2018

  51. [51]

    Proceedings of the 35th Computational Complexity Conference , pages =

    Aaronson, Scott and Chia, Nai-Hui and Lin, Han-Hsuan and Wang, Chunhao and Zhang, Ruizhe , title =. Proceedings of the 35th Computational Complexity Conference , pages =. doi:10.4230/LIPIcs.CCC.2020.16 , year =

    work page doi:10.4230/lipics.ccc.2020.16 2020

  52. [52]

    Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science , pages =

    Buhrman, Harry and Patro, Subhasree and Speelman, Florian , title =. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science , pages =. doi:10.4230/LIPIcs.STACS.2021.19 , year =

    work page doi:10.4230/lipics.stacs.2021.19 2021

  53. [53]

    Symmetries in Physics: Philosophical Reflections , volume =

    French, Steven and Rickles, Dean , title =. Symmetries in Physics: Philosophical Reflections , volume =. doi:10.1017/CBO9780511535369.013 , publisher =

    work page doi:10.1017/cbo9780511535369.013

  54. [54]

    and Wieczorek, W

    Tóth, G. and Wieczorek, W. and Gross, D. and Krischek, R. and Schwemmer, C. and Weinfurter, H. , title =. Physical Review Letters , volume =. doi:10.1103/PhysRevLett.105.250403 , year =

    work page doi:10.1103/physrevlett.105.250403

  55. [55]

    Linear Algebra and its Applications , volume =

    Pollatsek, Harriet and Ruskai, Mary Beth , title =. Linear Algebra and its Applications , volume =. doi:10.1016/j.laa.2004.06.014 , year =

    work page doi:10.1016/j.laa.2004.06.014 2004

  56. [56]

    Physical Review A , volume =

    Ouyang, Yingkai , title =. Physical Review A , volume =. doi:10.1103/PhysRevA.90.062317 , year =

    work page doi:10.1103/physreva.90.062317

  57. [57]

    Theory of Computing , volume =

    Aaronson, Scott and Ambainis, Andris , title =. Theory of Computing , volume =. doi:10.4086/toc.2014.v010a006 , year =

    work page doi:10.4086/toc.2014.v010a006 2014

  58. [58]

    Proceedings of the 10th Innovations in Theoretical Computer Science Conference , pages =

    Chailloux, André , title =. Proceedings of the 10th Innovations in Theoretical Computer Science Conference , pages =. doi:10.4230/LIPIcs.ITCS.2019.19 , year =

    work page doi:10.4230/lipics.itcs.2019.19 2019

  59. [59]

    and Gilyén, András and Kretschmer, William and Podder, Supartha and Wang, Daochen , title =

    Ben-David, Shalev and Childs, Andrew M. and Gilyén, András and Kretschmer, William and Podder, Supartha and Wang, Daochen , title =. SIAM Journal on Computing , volume =. doi:10.1137/23M1573975 , year =

    work page doi:10.1137/23m1573975

  60. [60]

    IEEE Transactions on Information Theory , volume =

    Guan, Ziyi and Huang, Yunqi and Yao, Penghui and Ye, Zekun , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2025.3534920 , year =

    work page doi:10.1109/tit.2025.3534920 2025

  61. [61]

    IEEE Transactions on Information Theory , volume=

    On estimating the trace of quantum state powers , author=. IEEE Transactions on Information Theory , volume=. 2026 , doi=

    2026

  62. [62]

    IEEE Transactions on Information Theory , volume =

    New quantum algorithms for computing quantum entropies and distances , author =. IEEE Transactions on Information Theory , volume =. 2024 , doi =

    2024

  63. [63]

    Physical Review A , volume =

    Subramanian, Sathyawageeswar and Hsieh, Min-Hsiu , title =. Physical Review A , volume =. doi:10.1103/PhysRevA.104.022428 , year =

    work page doi:10.1103/physreva.104.022428

  64. [64]

    IEEE Transactions on Information Theory , volume =

    Wang, Xinzhao and Zhang, Shengyu and Li, Tongyang , title =. IEEE Transactions on Information Theory , volume =. doi:10.1109/TIT.2024.3382037 , year =

    work page doi:10.1109/tit.2024.3382037 2024

  65. [65]

    Proceedings of the 38th Annual Conference on Learning Theory , pages =

    Chen, Kean and Wang, Qisheng , title =. Proceedings of the 38th Annual Conference on Learning Theory , pages =. doi:, url =

  66. [66]

    2505.09563v2 , year =

    Chen, Kean and Liu, Yupan and Wang, Qisheng , title =. 2505.09563v2 , year =

    arXiv

  67. [67]

    SIAM Journal on Computing , volume =

    Wang, Qisheng and Zhang, Zhicheng , title =. SIAM Journal on Computing , volume =. doi:10.1137/24M1638616 , year =

    work page doi:10.1137/24m1638616

  68. [68]

    Foundations of Physics , volume =

    Brassard, Gilles , title =. Foundations of Physics , volume =. doi:10.1023/A:1026009100467 , year =

    work page doi:10.1023/a:1026009100467

  69. [69]

    Proceedings of the 31st Annual European Symposium on Algorithms , pages =

    Tight bounds for quantum phase estimation and related problems , author =. Proceedings of the 31st Annual European Symposium on Algorithms , pages =. doi:10.4230/LIPIcs.ESA.2023.81 , year =

    work page doi:10.4230/lipics.esa.2023.81 2023

  70. [70]

    Nielsen and Isaac L

    Nielsen, Michael A. and Chuang, Isaac L. , title =. doi:10.1017/CBO9780511976667 , year =

    work page doi:10.1017/cbo9780511976667