Pith. sign in

REVIEW 4 minor 62 references

Operator-norm distance between quantum states can be estimated with rank-independent quantum queries, and optimally when one state is pure.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-11 23:07 UTC pith:PP4K36DO

load-bearing objection Clean rank-independent estimators for operator-norm distance, optimal when one state is pure, with full proofs and only a square-root gap left open.

arxiv 2607.03905 v1 pith:PP4K36DO submitted 2026-07-04 quant-ph cs.DScs.ITmath.IT

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu , Qisheng Wang , Zhan Yu This is my paper
classification quant-ph cs.DScs.ITmath.IT
keywords operator norm distancetrace distancequantum state testingquery complexityBQP-completenessqubitizationmaximum phase estimationstate-preparation circuits
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper shows that the operator-norm distance between two n-qubit states can be estimated from their preparation circuits with a number of queries that does not grow with rank or dimension. When one state is pure the cost is optimal, Theta(1/epsilon), and the same procedure also estimates the ordinary trace distance, because the two distances differ only by a factor of two in that case. For arbitrary mixed states the cost rises only to roughly 1/epsilon to the 3/2. The resulting algorithms run in polynomial time for constant precision whenever the preparation circuits are polynomial size, placing the corresponding decision problems in BQP and proving them BQP-complete. The advance rests on a structural observation: a pure state already overlaps the top eigenvector of the difference operator by at least one half, supplying a free warm start that earlier methods lacked.

Core claim

Given preparation circuits for two n-qubit states, the operator-norm distance can be estimated to additive error epsilon with O~(1/epsilon^{3/2}) queries in general and with the optimal Theta(1/epsilon) queries when one state is pure; the pure-state case simultaneously yields a rank-independent estimator for the trace distance.

What carries the argument

The single-pure-state warm-start lemma: a pure state |psi> has squared overlap at least 1/2 with the unique top eigenvector of (|psi><psi|-rho)/2, which, after unitary dilation and qubitization, lets maximum-phase estimation recover the largest singular value with constant success probability.

Load-bearing premise

The algorithms stand only if an efficient unitary dilation of the difference of the two states can be built from the given preparation oracles and if maximum-phase estimation achieves the query bounds claimed for it.

What would settle it

Implement the claimed estimator on a pair of pure states whose exact operator-norm (or trace) distance is known analytically, measure the observed query count versus 1/epsilon, and check whether the measured distance agrees with the analytic value within the stated additive error for a sequence of decreasing epsilon.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies the quantum query complexity of estimating the operator norm distance T_∞(ρ₀,ρ₁) = (1/2)∥ρ₀−ρ₁∥_∞ given poly(n)-size state-preparation circuits for n-qubit states. When one state is pure it gives an optimal Θ(1/ε) estimator that simultaneously estimates the trace distance (via the identity T = 2 T_∞), independent of rank. For general mixed states it gives an Õ(1/ε^{3/2}) estimator, establishing BQP-completeness of the corresponding promise problem QSD_∞ and improving a prior QMA upper bound, while leaving only a square-root gap to the Ω(1/ε) lower bound inherited from the pure-state case. The algorithms rest on a unitary dilation of (ρ₀−ρ₁)/2, a custom qubitization, and maximum-phase estimation, powered by two structural lemmas: a constant-overlap warm-start when one state is pure, and an eigenvalue-scaled overlap for the general case.

Significance. If correct, the results close an open question left in prior work on quantum ℓ_α distances by supplying the first rank-independent (hence dimension-independent) estimators for the operator-norm endpoint. The pure-state case is optimal and exponentially improves the best previous rank-dependent bounds; the general case is already super-quadratically better than known bounds for finite α>1 and yields clean BQP-completeness corollaries for the whole hierarchy of OnePureQSD_α problems. The proofs are elementary spectral arguments plus standard primitives (LCU, qubitization, amplitude amplification), so the contribution is both technically clean and practically relevant for quantum property testing and verification whenever state-preparation circuits are available.

minor comments (4)
  1. [§1.1, Theorem 1.1] In the statement of Theorem 1.1 and the surrounding discussion it would help the reader to recall explicitly that the lower bound is inherited from the pure-vs-pure case of Wang (TIT 2024) and Liu–Wang (ESA 2025); a one-sentence pointer would make the optimality claim self-contained.
  2. [§3.2, Lemma 3.2] Lemma 3.2 (qubitization) produces a different rotation angle from the standard Low–Chuang version; a short remark comparing the two would prevent confusion for readers familiar with the literature.
  3. [§3.3.1 / §4.2] In Algorithms 1 and 2 the global phase −W_Ak is introduced without a one-line justification that it merely shifts all eigenphases by π while preserving the ordering needed for maximum-phase estimation; adding that sentence would improve readability.
  4. [§2.4, Lemma 2.7] The sample-complexity corollaries (Theorems 3.6 and 4.3) rely on the sample-to-query lifting of Tang–Wright–Zhandry / Chen–Wang–Zhang; citing the precise statement used (rather than only the arXiv numbers) would make the reduction easier to verify.

Circularity Check

0 steps flagged

No significant circularity: algorithmic upper bounds rest on elementary spectral lemmas and standard black-box primitives, not on self-definitional or fitted constructions.

full rationale

The paper's central claims are query-complexity upper bounds for estimating the operator-norm distance T_∞(ρ0,ρ1) (and, when one state is pure, also the trace distance). These bounds are obtained by (i) constructing an explicit unitary dilation of Δ=(ρ0−ρ1)/2 via LCU and purified density matrices (Lemma 2.6), (ii) applying a qubitization that converts eigenvalues of Δ into eigenphases (Lemma 3.2), and (iii) feeding a state whose overlap with the top eigenspace is guaranteed by two elementary spectral lemmas (single-pure-state warm-start Lemma 3.1 and top-eigenspace overlap Lemma 4.1) into the maximum-phase-estimation black box of Mande–de Wolf (Lemma 3.3). Both structural lemmas are proved from first principles (positive-semidefiniteness of density operators, rank-one perturbation, and the projection identity ΠΔΠ=λmaxΠ) without reference to the target distance being estimated; the dilation and qubitization are standard constructions whose query cost is constant; and the phase-estimation primitive is invoked only with the overlap and precision parameters supplied by those lemmas. Self-citations appear only as black-box hardness statements (e.g., the Ω(1/ε) lower bound for pure-versus-pure instances) or as previously published upper bounds that the present work improves upon; none of them is used to define a fitted parameter that is later re-labeled a prediction. Consequently the derivation chain is self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper works entirely inside standard quantum information and query complexity. No free parameters are fitted; the only external black boxes are previously published phase-estimation and sample-to-query lifting results whose assumptions are stated. No new physical entities are postulated.

axioms (3)
  • domain assumption Existence of efficient unitary dilations of density operators via purified density-matrix technique and LCU (Lemma 2.6).
    Standard construction from LC19 and CW12; invoked throughout Sections 3–4.
  • domain assumption Correctness and query bounds of maximum-phase estimation (Mande–de Wolf Lemma 3.3).
    Black-box primitive used in Algorithms 1–2; paper does not re-prove it.
  • domain assumption Quantum sample-to-query lifting (Lemma 2.7 from TWZ25/CWZ25).
    Used only to convert query bounds into sample bounds in Theorems 3.6 and 4.3.

pith-pipeline@v1.1.0-grok45 · 32310 in / 2258 out tokens · 19959 ms · 2026-07-11T23:07:03.481105+00:00 · methodology

0 comments
read the original abstract

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(\rho_0,\rho_1)$, defined via the operator norm $\|A\|_{\infty} = \sigma_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $\rho_0$ and $\rho_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $\Theta(1/\epsilon)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $\epsilon=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|\psi\rangle\!\langle\psi|,\rho)$ is exactly half of the trace distance ${\rm T}(|\psi\rangle\!\langle\psi|,\rho)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{\'{e}}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(\rho)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/\epsilon^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $\Omega(1/\epsilon)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|\psi\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|\psi\rangle\!\langle\psi|-\rho$, reflecting a structural feature specific to the operator norm distance.

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

62 extracted references · 18 canonical work pages · 16 internal anchors

  1. [1]

    Quantum tomography using state-preparation unitaries

    Joran Apeldoorn v an Apeldoorn, Arjan Cornelissen, Andr \' a s Gily \' e n, and Giacomo Nannicini. Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1265--1318, 2023. https://arxiv.org/abs/2207.08800 arXiv:2207.08800 , https://doi.org/10.1137/1.9781611977554.ch47 doi:1...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611977554.ch47 2023

  2. [2]

    Quantum SDP-Solvers: Better upper and lower bounds

    Joran Apeldoorn v an Apeldoorn, Andr \' a s Gily \' e n, Sander Gribling, and Ronald Wolf d e Wolf. Quantum SDP -solvers: better upper and lower bounds. Quantum , 4:230, 2020. https://arxiv.org/abs/1705.01843 arXiv:1705.01843 , https://doi.org/10.22331/q-2020-02-14-230 doi:10.22331/q-2020-02-14-230

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.22331/q-2020-02-14-230 2020

  3. [3]

    Guillaume Aubrun and Stanis aw J. Szarek. Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory , volume 223 of Mathematical Surveys and Monographs . American Mathematical Society, 2017. https://doi.org/10.1090/surv/223 doi:10.1090/surv/223

    doi:10.1090/surv/223 2017

  4. [4]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters , 114(9):090502, 2015. https://arxiv.org/abs/1412.4687 arXiv:1412.4687 , https://doi.org/10.1103/PhysRevLett.114.090502 doi:10.1103/PhysRevLett.114.090502

    Pith/arXiv arXiv doi:10.1103/physrevlett.114.090502 2015

  5. [5]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science , pages 792--809, 2015. https://arxiv.org/abs/1501.01715 arXiv:1501.01715 , https://doi.org/10.1109/FOCS.2015.54 doi:10.1109/FOCS.2015.54

    Pith/arXiv arXiv doi:10.1109/focs.2015.54 2015

  6. [6]

    Quantum fingerprinting

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald Wolf d e Wolf. Quantum fingerprinting. Physical Review Letters , 87(16):167902, 2001. https://arxiv.org/abs/quant-ph/0102001 arXiv:quant-ph/0102001 , https://doi.org/10.1103/PhysRevLett.87.167902 doi:10.1103/PhysRevLett.87.167902

    Pith/arXiv arXiv doi:10.1103/physrevlett.87.167902 2001

  7. [7]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information , volume 305 of Contemporary Mathematics , pages 53--74. AMS, 2002. https://arxiv.org/abs/quant-ph/0005055 arXiv:quant-ph/0005055 , https://doi.org/10.109...

    Pith/arXiv arXiv doi:10.1090/conm/305/05215 2002

  8. [8]

    Leung, Dominic Mayers, and Jonathan Oppenheim

    Michael Ben-Or, Micha Horodecki, Debbie W. Leung, Dominic Mayers, and Jonathan Oppenheim. The universal composable security of quantum key distribution. In Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings , pages 386--406. Springer, 2005. https://arxiv.org/abs/quant-ph/040907...

    Pith/arXiv arXiv doi:10.1007/978-3-540-30576-7_21 2005

  9. [9]

    Quantum state certification

    Costin B a descu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 503--514, 2019. https://arxiv.org/abs/1708.06002 arXiv:1708.06002 , https://doi.org/10.1145/3313276.3316344 doi:10.1145/3313276.3316344

    Pith/arXiv arXiv doi:10.1145/3313276.3316344 2019

  10. [10]

    Cl \'e ment L. Canonne. A survey on distribution testing: your data is big. but is it blue? In Theory of Computing Library , number 9 in Graduate Surveys, pages 1--100. University of Chicago, 2020. 20 15 063 . https://doi.org/10.4086/toc.gs.2020.009 doi:10.4086/toc.gs.2020.009

    doi:10.4086/toc.gs.2020.009 2020

  11. [11]

    Coles, Marco Cerezo, and Lukasz Cincio

    Patrick J. Coles, Marco Cerezo, and Lukasz Cincio. Strong bound between trace distance and Hilbert-Schmidt distance for low-rank states. Physical Review A , 100(2):022103, 2019. https://arxiv.org/abs/1903.11738 arXiv:1903.11738 , https://doi.org/10.1103/physreva.100.022103 doi:10.1103/physreva.100.022103

    Pith/arXiv arXiv doi:10.1103/physreva.100.022103 2019

  12. [12]

    Optimal Algorithms for Testing Closeness of Discrete Distributions

    Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete Algorithms , pages 1193--1203. SIAM, 2014. https://arxiv.org/abs/1308.3946 arXiv:1308.3946 , https://doi.org/10.1137/1.9781611973402.88 doi:10.1137/...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611973402.88 2014

  13. [13]

    When does adaptivity help for quantum state learning? In Proceedings of the 64th Annual Symposium on Foundations of Computer Science , pages 391--404

    Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. When does adaptivity help for quantum state learning? In Proceedings of the 64th Annual Symposium on Foundations of Computer Science , pages 391--404. IEEE, 2023. https://arxiv.org/abs/2206.05265 arXiv:2206.05265 , https://doi.org/10.1109/FOCS57990.2023.00029 doi:10.1109/FOCS57990.2023.00029

    Pith/arXiv arXiv doi:10.1109/focs57990.2023.00029 2023

  14. [14]

    Optimal large-scale quantum state tomography with Pauli measurements

    Tony Cai, Donggyu Kim, Yazhen Wang, Ming Yuan, and Harrison H Zhou. Optimal large-scale quantum state tomography with Pauli measurements. The Annals of Statistics , 44(2):682--712, 2016. https://arxiv.org/abs/1603.07559 arXiv:1603.07559 , https://doi.org/10.1214/15-AOS1382 doi:10.1214/15-AOS1382

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1214/15-aos1382 2016

  15. [15]

    Childs and Nathan Wiebe

    Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation , 12(11--12):901--924, 2012. https://arxiv.org/abs/1202.5822 arXiv:1202.5822 , https://doi.org/10.26421/QIC12.11-12-1 doi:10.26421/QIC12.11-12-1

    Pith/arXiv arXiv doi:10.26421/qic12.11-12-1 2012

  16. [16]

    A list of complexity bounds for property testing by quantum sample-to-query lifting, 2025

    Kean Chen, Qisheng Wang, and Zhicheng Zhang. A list of complexity bounds for property testing by quantum sample-to-query lifting, 2025. ArXiv preprint. https://arxiv.org/abs/2512.01971 arXiv:2512.01971

    arXiv 2025

  17. [17]

    Ekert, Carolina Moura Alves, Daniel K

    Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Micha Horodecki, Pawe Horodecki, and Leong Chuan Kwek. Direct estimations of linear and nonlinear functionals of a quantum state. Physical Review Letters , 88(21):217901, 2002. https://arxiv.org/abs/quant-ph/0203016 arXiv:quant-ph/0203016 , https://doi.org/10.1103/physrevlett.88.217901 doi:10.1103/phy...

    Pith/arXiv arXiv doi:10.1103/physrevlett.88.217901 2002

  18. [18]

    Quantum certification and benchmarking

    Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics , 2(7):382--390, 2020. https://arxiv.org/abs/1910.06343 arXiv:1910.06343 , https://doi.org/10.1038/s42254-020-0186-4 doi:10.1038/s42254-020-0186-4

    Pith/arXiv arXiv doi:10.1038/s42254-020-0186-4 2020

  19. [19]

    Fuchs and Jeroen Graaf v an de Graaf

    Christopher A. Fuchs and Jeroen Graaf v an de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory , 45(4):1216--1227, 1999. https://arxiv.org/abs/quant-ph/9712042 arXiv:quant-ph/9712042 , https://doi.org/10.1109/18.761271 doi:10.1109/18.761271

    Pith/arXiv arXiv doi:10.1109/18.761271 1999

  20. [20]

    Query-Optimal and Sample-Optimal Quantum Algorithms for Estimating Fidelity to a Pure State

    Wang Fang and Qisheng Wang. Optimal quantum algorithm for estimating fidelity to a pure state. In Proceedings of the 33rd Annual European Symposium on Algorithms (ESA) , volume 351 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 4:1--4:12. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2025. https://arxiv.org/abs/2506.23650 a...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.esa.2025.4 2025

  21. [21]

    M a d a lin Gu t a , Jonas Kahn, Richard Kueng, and Joel A. Tropp. Fast state tomography with optimal error bounds. Journal of Physics A: Mathematical and Theoretical , 53(20):204001, 2020. https://arxiv.org/abs/1809.11162 arXiv:1809.11162 , https://doi.org/10.1088/1751-8121/ab8111 doi:10.1088/1751-8121/ab8111

    Pith/arXiv arXiv doi:10.1088/1751-8121/ab8111 2020

  22. [22]

    Distributional property testing in a quantum world

    Andr \'a s Gily \'e n and Tongyang Li. Distributional property testing in a quantum world. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference , pages 25:1--25:19, 2020. https://arxiv.org/abs/1902.00814 arXiv:1902.00814 , https://doi.org/10.4230/LIPIcs.ITCS.2020.25 doi:10.4230/LIPIcs.ITCS.2020.25

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.itcs.2020.25 2020

  23. [23]

    Langford, and Michael A

    Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and ideal quantum processes. Physical Review A , 71:062310, 2005. https://arxiv.org/abs/quant-ph/0408063 arXiv:quant-ph/0408063 , https://doi.org/10.1103/PhysRevA.71.062310 doi:10.1103/PhysRevA.71.062310

    Pith/arXiv arXiv doi:10.1103/physreva.71.062310 2005

  24. [24]

    Improved quantum algorithms for fidelity estimation

    Andr\' a s Gily\' e n and Alexander Poremba. Improved quantum algorithms for fidelity estimation. ArXiv e-prints, 2022. https://arxiv.org/abs/2203.15993 arXiv:2203.15993

    Pith/arXiv arXiv 2022

  25. [25]

    Recovering low-rank matrices from few coefficients in any basis

    David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory , 57(3):1548--1566, 2011. https://arxiv.org/abs/0910.1879 arXiv:0910.1879 , https://doi.org/10.1109/TIT.2011.2104999 doi:10.1109/TIT.2011.2104999

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2011.2104999 2011

  26. [26]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr\' a s Gily\' e n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 193--204, 2019. https://arxiv.org/abs/1806.01838 arXiv:1806.01838 , https://doi.org/10.1145/3313276...

    Pith/arXiv arXiv doi:10.1145/3313276.3316366 2019

  27. [27]

    Helstrom

    Carl W. Helstrom. Detection theory and quantum mechanics. Information and Control , 10(3):254--291, 1967. https://doi.org/10.1016/S0019-9958(67)90302-6 doi:10.1016/S0019-9958(67)90302-6

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

  28. [28]

    Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu

    Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory , 63(9):5628--5641, 2017. STOC 2016 . https://arxiv.org/abs/1508.01797 arXiv:1508.01797 , https://doi.org/10.1109/TIT.2017.2719044 doi:10.1109/TIT.2017.2719044

    Pith/arXiv arXiv doi:10.1109/tit.2017.2719044 2017

  29. [29]

    Hastings, Robin Kothari, and Guang Hao Low

    Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice Hamiltonians . SIAM Journal on Computing , 52(6):S18--250, 2023. FOCS 2018 . https://arxiv.org/abs/1801.03922 arXiv:1801.03922 , https://doi.org/10.1137/18M1231511 doi:10.1137/18M1231511

    Pith/arXiv arXiv doi:10.1137/18m1231511 2023

  30. [30]

    Query-optimal estimation of unitary channels in diamond distance

    Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023) , pages 363--390. IEEE , 2023. https://arxiv.org/abs/2302.14066 arXiv:2302.14066 , https://doi.org/10.1109/FOCS57990.2023.00028 doi:10...

    Pith/arXiv arXiv doi:10.1109/focs57990.2023.00028 2023

  31. [31]

    Alexander S. Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis , 3(4):337--394, 1973. https://doi.org/10.1016/0047-259X(73)90028-6 doi:10.1016/0047-259X(73)90028-6

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

  32. [32]

    Minimax Estimation of the $L_1$ Distance

    Jiantao Jiao, Yanjun Han, and Tsachy Weissman. Minimax estimation of the l_ 1 distance. IEEE Transactions on Information Theory , 64(10):6672--6706, 2018. https://arxiv.org/abs/1705.00807 arXiv:1705.00807 , https://doi.org/10.1109/TIT.2018.2846245 doi:10.1109/TIT.2018.2846245

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2018.2846245 2018

  33. [33]

    A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv e-prints, 1995. https://arxiv.org/abs/quant-ph/9511026 arXiv:quant-ph/9511026

    Pith/arXiv arXiv 1995

  34. [34]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum , 3:163, 2019. https://arxiv.org/abs/1610.06546 arXiv:1610.06546 , https://doi.org/10.22331/q-2019-07-12-163 doi:10.22331/q-2019-07-12-163

    Pith/arXiv arXiv doi:10.22331/q-2019-07-12-163 2019

  35. [35]

    Universal low-rank matrix recovery from Pauli measurements

    Yi - Kai Liu. Universal low-rank matrix recovery from Pauli measurements. In Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS 2011) , pages 1638--1646, 2011. URL: https://proceedings.neurips.cc/paper/2011/hash/e820a45f1dfc7b95282d10b6087e11c0-Abstract.html, https://arxiv.org/abs/1103.2816 arXiv:1103.2816

    Pith/arXiv arXiv 2011

  36. [36]

    Space-bounded quantum state testing via space-efficient quantum singular value transformation

    Fran c ois Le Gall , Yupan Liu, and Qisheng Wang. Space-bounded quantum state testing via space-efficient quantum singular value transformation. To appear in computational complexity , 2026. https://arxiv.org/abs/2308.05079 arXiv:2308.05079 , https://doi.org/10.1007/s00037-025-00284-5 doi:10.1007/s00037-025-00284-5

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00037-025-00284-5 2026

  37. [37]

    On estimating Schatten norm and power distances between quantum states

    Yupan Liu and Qisheng Wang. On estimating the quantum _ distance. In Proceedings of the 33rd Annual European Symposium on Algorithms ( ESA 2025) , volume 351 of LIPIcs , pages 105:1--105:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025. https://arxiv.org/abs/2505.00457 arXiv:2505.00457 , https://doi.org/10.4230/LIPIcs.ESA.2025.105 doi:10.4...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.esa.2025.105 2025

  38. [38]

    On estimating the trace of quantum state powers

    Yupan Liu and Qisheng Wang. On estimating the trace of quantum state powers. IEEE Transactions on Information Theory , pages 1--1, 2026. SODA 2025 . https://arxiv.org/abs/2410.13559 arXiv:2410.13559 , https://doi.org/10.1109/TIT.2026.3683891 doi:10.1109/TIT.2026.3683891

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2026.3683891 2026

  39. [39]

    A survey of quantum property testing

    Ashley Montanaro and Ronald Wolf d e Wolf. A survey of quantum property testing. In Theory of Computing Library , number 7 in Graduate Surveys, pages 1--81. University of Chicago, 2016. https://arxiv.org/abs/1310.2035 arXiv:1310.2035 , https://doi.org/10.4086/toc.gs.2016.007 doi:10.4086/toc.gs.2016.007

    Pith/arXiv arXiv doi:10.4086/toc.gs.2016.007 2016

  40. [40]

    Mande and Ronald Wolf d e Wolf

    Nikhil S. Mande and Ronald Wolf d e Wolf. Tight B ounds for Q uantum P hase E stimation and R elated P roblems. Quantum , 10:2140, 2026. ESA 2023 . https://arxiv.org/abs/2305.04908 arXiv:2305.04908 , https://doi.org/10.22331/q-2026-06-15-2140 doi:10.22331/q-2026-06-15-2140

    Pith/arXiv arXiv doi:10.22331/q-2026-06-15-2140 2026

  41. [41]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667 doi:10.1017/CBO9780511976667

    doi:10.1017/cbo9780511976667 2010

  42. [42]

    Efficient quantum tomography

    Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing ( STOC 2016) , pages 899--912. ACM , 2016. https://arxiv.org/abs/1508.01907 arXiv:1508.01907 , https://doi.org/10.1145/2897518.2897544 doi:10.1145/2897518.2897544

    Pith/arXiv arXiv doi:10.1145/2897518.2897544 2016

  43. [43]

    Security in quantum cryptography

    Christopher Portmann and Renato Renner. Security in quantum cryptography. Reviews of Modern Physics , 94:025008, 2022. https://arxiv.org/abs/2102.00021 arXiv:2102.00021 , https://doi.org/10.1103/RevModPhys.94.025008 doi:10.1103/RevModPhys.94.025008

    Pith/arXiv arXiv doi:10.1103/revmodphys.94.025008 2022

  44. [44]

    Mixed state tomography reduces to pure state tomography

    Angelos Pelecanos, Jack Spilecki, Ewin Tang, and John Wright. Mixed state tomography reduces to pure state tomography. ArXiv preprint, 2025. https://arxiv.org/abs/2511.15806 arXiv:2511.15806

    arXiv 2025

  45. [45]

    The debiased Keyl's algorithm: A new unbiased estimator for full state tomography

    Angelos Pelecanos, Jack Spilecki, and John Wright. The debiased Keyl's algorithm: A new unbiased estimator for full state tomography. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1266--1277, 2026. https://arxiv.org/abs/2510.07788 arXiv:2510.07788 , https://doi.org/10.1145/3798129.3800837 doi:10.1145/3798129.3800837

    work page doi:10.1145/3798129.3800837 2026

  46. [46]

    Soorya Rethinasamy, Rochisha Agarwal, Kunal Sharma, and Mark M. Wilde. Estimating distinguishability measures on quantum computers. Physical Review A , 108(1):012409, 2023. https://arxiv.org/abs/2108.08406 arXiv:2108.08406 , https://doi.org/10.1103/PhysRevA.108.012409 doi:10.1103/PhysRevA.108.012409

    Pith/arXiv arXiv doi:10.1103/physreva.108.012409 2023

  47. [47]

    Universally composable privacy amplification against quantum adversaries

    Renato Renner and Robert K \"o nig. Universally composable privacy amplification against quantum adversaries. In Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings , pages 407--425. Springer, 2005. https://arxiv.org/abs/quant-ph/0403133 arXiv:quant-ph/0403133 , https://doi.org/...

    Pith/arXiv arXiv doi:10.1007/978-3-540-30576-7_22 2005

  48. [48]

    Optimal lower bounds for quantum state tomography

    Thilo Scharnhorst, Jack Spilecki, and John Wright. Optimal lower bounds for quantum state tomography. ArXiv preprint, 2025. https://arxiv.org/abs/2510.07699 arXiv:2510.07699

    arXiv 2025

  49. [49]

    A complete problem for statistical zero knowledge

    Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM , 50(2):196--249, 2003. FOCS 1997 . 20 00 084 . https://doi.org/10.1145/636865.636868 doi:10.1145/636865.636868

    work page doi:10.1145/636865.636868 2003

  50. [50]

    Conjugate queries can help

    Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. ArXiv preprint, 2025. https://arxiv.org/abs/2510.07622 arXiv:2510.07622

    Pith/arXiv arXiv 2025

  51. [51]

    Estimating the unseen: Improved estimators for entropy and other properties

    Gregory Valiant and Paul Valiant. Estimating the unseen: Improved estimators for entropy and other properties. Journal of the ACM , 64(6):37:1--37:41, 2017. NIPS 2013 . https://doi.org/10.1145/3125643 doi:10.1145/3125643

    doi:10.1145/3125643 2017

  52. [52]

    $\ell_p$ Testing and Learning of Discrete Distributions

    Bo Waggoner. _p testing and learning of discrete distributions. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science , pages 347--356, 2015. https://arxiv.org/abs/1412.2314 arXiv:1412.2314 , https://doi.org/10.1145/2688073.2688095 doi:10.1145/2688073.2688095

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/2688073.2688095 2015

  53. [53]

    Optimal Trace Distance and Fidelity Estimations for Pure Quantum States

    Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory , 70(12):8791--8805, 2024. https://arxiv.org/abs/2408.16655 arXiv:2408.16655 , https://doi.org/10.1109/TIT.2024.3447915 doi:10.1109/TIT.2024.3447915

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2024.3447915 2024

  54. [54]

    Limits on the power of quantum statistical zero-knowledge

    John Watrous. Limits on the power of quantum statistical zero-knowledge. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science , pages 459--468. IEEE, 2002. https://arxiv.org/abs/quant-ph/0202111 arXiv:quant-ph/0202111 , https://doi.org/10.1109/SFCS.2002.1181970 doi:10.1109/SFCS.2002.1181970

    Pith/arXiv arXiv doi:10.1109/sfcs.2002.1181970 2002

  55. [55]

    Zero-knowledge against quantum attacks

    John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing , 39(1):25--58, 2009. STOC 2006 . https://arxiv.org/abs/quant-ph/0511020 arXiv:quant-ph/0511020 , https://doi.org/10.1137/060670997 doi:10.1137/060670997

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/060670997 2009

  56. [56]

    New quantum algorithms for computing quantum entropies and distances

    Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for computing quantum entropies and distances. IEEE Transactions on Information Theory , 70(8):5653--5680, 2024. https://arxiv.org/abs/2203.13522 arXiv:2203.13522 , https://doi.org/10.1109/TIT.2024.3399014 doi:10.1109/TIT.2024.3399014

    Pith/arXiv arXiv doi:10.1109/tit.2024.3399014 2024

  57. [57]

    Fast Quantum Algorithms for Trace Distance Estimation

    Qisheng Wang and Zhicheng Zhang. Fast quantum algorithms for trace distance estimation. IEEE Transactions on Information Theory , 70(4):2720--2733, 2024. https://arxiv.org/abs/2301.06783 arXiv:2301.06783 , https://doi.org/10.1109/TIT.2023.3321121 doi:10.1109/TIT.2023.3321121

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tit.2023.3321121 2024

  58. [58]

    Quantum lower bounds by sample-to-query lifting

    Qisheng Wang and Zhicheng Zhang. Quantum lower bounds by sample-to-query lifting. SIAM Journal on Computing , 54(5):1294--1334, 2025. https://arxiv.org/abs/2308.01794 arXiv:2308.01794 , https://doi.org/10.1137/24M1638616 doi:10.1137/24M1638616

    doi:10.1137/24m1638616 2025

  59. [59]

    Time-efficient quantum entropy estimator via samplizer

    Qisheng Wang and Zhicheng Zhang. Time-efficient quantum entropy estimator via samplizer. IEEE Transactions on Information Theory , 71(12):9569--9599, 2025. ESA 2024 . https://arxiv.org/abs/2401.09947 arXiv:2401.09947 , https://doi.org/10.1109/TIT.2025.3576137 doi:10.1109/TIT.2025.3576137

    doi:10.1109/tit.2025.3576137 2025

  60. [60]

    Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer

    Qisheng Wang and Zhicheng Zhang. Sample-optimal quantum estimators for pure-state trace distance and fidelity via samplizer. In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming , pages 154:1--154:21, 2026. https://arxiv.org/abs/2410.21201 arXiv:2410.21201 , https://doi.org/10.4230/LIPIcs.ICALP.2026.154 doi:10.4230/L...

    Pith/arXiv arXiv doi:10.4230/lipics.icalp.2026.154 2026

  61. [61]

    Quantum algorithm for fidelity estimation

    Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying. Quantum algorithm for fidelity estimation. IEEE Transactions on Information Theory , 69(1):273--282, 2023. https://arxiv.org/abs/2103.09076 arXiv:2103.09076 , https://doi.org/10.1109/TIT.2022.3203985 doi:10.1109/TIT.2022.3203985

    Pith/arXiv arXiv doi:10.1109/tit.2022.3203985 2023

  62. [62]

    Estimation of low rank density matrices: bounds in Schatten norms and other distances

    Dong Xia and Vladimir Koltchinskii. Estimation of low rank density matrices: Bounds in Schatten norms and other distances. Electronic Journal of Statistics , 10:2717--2745, 2016. https://arxiv.org/abs/1604.04600 arXiv:1604.04600 , https://doi.org/10.1214/16-EJS1192 doi:10.1214/16-EJS1192

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1214/16-ejs1192 2016