Pith. sign in

REVIEW 2 major objections 4 minor 59 references

The paper establishes that QSZK's complete problems admit two-message quantum interactive proofs whose honest prover runs in quantum linear space, improving the prover's resources from unbounded or polynomial-space to linear.

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 · deepseek-v4-flash

2026-08-03 16:50 UTC pith:OE4646B5

load-bearing objection A modest, honest resource refinement for QSZK's upper bound; the new part is the linear-space Uhlmann transform, but the proof needs one clarifying step in Protocol 3. the 2 major comments →

arxiv 2512.11597 v2 pith:OE4646B5 submitted 2025-12-12 quant-ph cs.CCcs.ITmath.IT

A slightly improved upper bound for quantum statistical zero-knowledge

Fran\c{c}ois Le Gall , Yupan Liu , Qisheng Wang This is my paper
classification quant-ph cs.CCcs.ITmath.IT MSC 68Q1268Q1581P68
keywords QSZKquantum interactive proofsHolevo-Helstrom measurementUhlmann transformquantum singular value transformationspace-bounded quantum computationquantum state distinguishabilityfidelity estimation
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.

This paper revisits the best-known upper bound for the complexity class QSZK — the family of promise problems with statistical zero-knowledge quantum proofs — and asks whether it can be improved even slightly. It establishes that the two complete problems for QSZK, quantum state distinguishability and squared-fidelity estimation, admit two-message quantum interactive proofs whose honest prover runs in quantum space linear in the input size and time singly exponential in it. The class inclusion QSZK ⊆ QIP(2) ∩ co-QIP(2) is unchanged, but the honest prover goes from unbounded (or polynomial-space) to linear-space, making the proof systems genuinely implementable. A similar improvement holds for the non-interactive variant NIQSZK. The advance is that a purely asymptotic inclusion becomes a concrete, resource-efficient protocol.

Core claim

The central claim is that the two optimal prover strategies for QSZK's complete problems—the Holevo–Helstrom measurement (GapQSD) and the Uhlmann transform (GapF²Est)—can be approximated to additive error 2^{-n} using only O(n) quantum space and 2^{O(n)} time. The approximations are built from space-efficient QSVT: a degree-2^{O(n)} sign-function polynomial whose coefficients are computable in O(n) space, applied to exact block-encodings of (ρ0−ρ1)/2 and Tr_A(|ψ0⟩⟨ψ1|). The class-level consequence is QSZK ⊆ QIP(2) ∩ co-QIP(2) with a quantum linear-space honest prover, and NIQSZK ⊆ qq-QAM with the same prover bound.

What carries the argument

The mechanism is a space-efficient quantum singular value transformation (QSVT) that applies an odd polynomial approximating the sign function to a block-encoded operator. The paper supplies two algorithmic primitives built on it: the algorithmic Holevo–Helstrom measurement (Theorem 3.4) and the algorithmic Uhlmann transform (Theorem 4.5). Each requires an exact block-encoding—of (ρ0−ρ1)/2 for the former and of Tr_A(|ψ0⟩⟨ψ1|) for the latter—followed by a sign-polynomial transformation whose coefficients are precomputed in O(n) space while the degree is 2^{O(n)}. This yields additive error 2^{-n} with O(n) qubits and 2^{O(n)} gates.

Load-bearing premise

The linear-space claim rests on two imported, unproved lemmas—the space-efficient QSVT from a to-appear paper by the same authors and the exact block-encoding of the partial-trace operator from a recent paper co-authored by one of the current authors—and if either requires more than O(n) space for degree 2^{O(n)} polynomials, the prover's linear-space bound collapses.

What would settle it

Run the space-efficient QSVT construction of Lemmas 2.9 and 2.10 on an n-qubit example with degree 2^{O(n)} and inspect the classical description length of the resulting circuit; if it grows faster than linearly in n, the honest prover's linear-space claim is wrong. The analogous check on the exact block-encoding of Lemma 4.8 would catch the second imported lemma's failure.

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

If this is right

  • The QSZK upper bound remains QIP(2) ∩ co-QIP(2), but the honest prover’s memory is reduced from unbounded (or polynomial-space) to linear space, making the proof systems simulable with singly-exponential effort.
  • For NIQSZK, the non-interactive proof system can be run with a linear-space honest prover in qq-QAM, tightening the known upper bound in the same way.
  • The algorithmic Uhlmann transform here improves the time complexity in the state dimension to polynomial (2^{O(n)}) compared with earlier polynomial-space implementations whose time was 2^{poly(n)}.
  • The completeness parameters absorb only a 2^{-n} additive loss in both protocols, so the polynomial gap α−β ≥ 1/poly(n) is preserved after standard parallel-repetition error reduction.
  • A byproduct stated in the paper: the space-bounded version GapF²Est_log is BQL-complete, with the containment direction sketched via the same technique (Remark 4.6).

Where Pith is reading between the lines

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

  • The improvement is about prover memory, not about the class itself; the central open bound QSZK ⊆ QIP(2) ∩ co-QIP(2) is untouched, so the significance is primarily algorithmic rather than a new separation.
  • The resource bounds hinge on two imported lemmas that are not proved here—Lemmas 2.9 and 2.10 from a to-appear paper by the same authors, and Lemma 4.8 from a paper co-authored by one of the current authors. If either lemma’s space claim fails for degree 2^{O(n)}, the linear-space prover claim collapses; an independent verification of these lemmas ought to accompany any application.
  • A natural generalization, which the authors leave open, is to implement the honest prover in any two-message quantum interactive proof in linear space. Their own discussion of the CITM problem suggests the barrier: constructing a near-optimal input state σ̃ in linear space is unclear, so the technique does not immediately extend.

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

2 major / 4 minor

Summary. The paper revisits Watrous's upper bound QSZK ⊆ QIP(2) ∩ co-QIP(2) and proves that the two proof systems can be run with an honest prover that uses quantum space linear in the transcript size and single-exponential time. The technical core is an algorithmic Holevo–Helstrom measurement (Theorem 3.4) and an algorithmic Uhlmann transform (Theorem 4.5), both built from the space-efficient QSVT of Le Gall–Liu–Wang. From these it derives QIP(2) containment for GapQSD (Theorem 3.5) and GapF²Est (Theorem 4.7) with a linear-space honest prover, and hence the claimed QSZK and NIQSZK corollaries. The error analyses in Sections 3.1 and 4.1 combine polynomial-approximation error, QSVT implementation error, and Hölder-based trace bounds, with parameter choices that close the target 2^{-n} budget.

Significance. If correct, the result does not change the class inclusion QSZK ⊆ QIP(2) ∩ co-QIP(2), but it sharpens the known upper bound by making the honest prover computationally restricted: quantum linear space, hence single-exponential time, instead of computationally unbounded or polynomial-space. The paper gives explicit linear-space algorithms for two basic information-theoretic primitives, and the detailed error accounting in Sections 3.1 and 4.1 is careful and largely checks out. The main caveat is that the crucial space-efficiency lemmas are imported from a to-appear companion paper by the same authors, so the quantitative claim is conditional on that paper being correct and publicly available in the form used here.

major comments (2)
  1. [§4.1–4.2, Theorem 4.5, Eq. (4.2), Protocol 3] Theorem 4.5 is stated for the operator \tilde U⋆ = ⟨0|V⋆|0⟩ and proves a bound on |⟨ψ0|(I_A⊗\tilde U⋆)|ψ1⟩|². But in Protocol 3 the honest prover must apply a physical CPTP map to the received register R. If the map is Φ(σ)=Tr_{A'E}(V⋆(σ⊗|0⟩⟨0|)V⋆†), the acceptance probability is Σ_y |⟨ψ1|(I_A⊗(⟨y|V⋆|0⟩))|ψ0⟩|², not the square of the top-left overlap. The proof of Theorem 4.7 jumps from Theorem 4.5 to p_acc ≥ F²−2^{-n} without defining Φ or justifying this inequality. This is repairable: every term in the sum is nonnegative, so p_acc is at least the top-left term, and the claimed completeness follows once this argument is added. The stress-test suggestion of oblivious amplitude amplification is not needed; the paper should simply state the channel and the nonnegativity step.
  2. [§2.3, Lemmas 2.9–2.10] The linear-space claims throughout Theorems 3.4, 3.5, 4.5, and 4.7 inherit the correctness and constants of the space-efficient sign-function approximation and QSVT from [LLW25], a to-appear paper co-authored by the same three authors. The present paper quotes the statements but gives no proofs or proof sketches. This is a legitimate dependency if the companion paper is accepted and available, but as written the main result is conditional on an external manuscript being correct in exactly the form used. I ask the authors to state precisely which corollaries of [LLW25] are being imported and to include a proof sketch or an appendix version, or to confirm the public availability of the final version.
minor comments (4)
  1. [§4.1, Eq. (4.5b) and (4.5d)] The equations appear to use |\bar1⟩_E where |\bar0⟩_E is intended. Please correct the typo.
  2. [§2.4, Protocol 1; §3.2; §4.2] The paper states t0t1 = 16 n³ q³(n), but from t0 := 2lq and t1 := 8lq²t0 one obtains t0t1 = 32 l³ q⁴ (up to notation). The constant does not affect the asymptotic claim, but the arithmetic should be corrected for consistency.
  3. [Theorem 4.7 and Protocol 3] The phrase 'optimal prover strategy' is inaccurate, since the honest prover uses an approximate Uhlmann transform rather than the exact optimal one. Consider rewording to 'honest prover's strategy'.
  4. [§1.5, Footnote 17] The pointer 'Section 7 in the arXiv version of [MY23]' should name the specific theorem or lemma number to help the reader.

Circularity Check

2 steps flagged

No definitional or fitted circularity, but the advertised linear-space honest-prover claim is inherited from two same-author citations ([LLW25] and [UNWT25]) that are load-bearing and not proved in this paper.

specific steps
  1. self citation load bearing [Section 1.3 and Section 2.3 (Lemmas 2.9–2.10), applied in Theorems 3.4 and 4.5]
    "we rely on space-efficient polynomial approximations P d′ from [LLW25], which can be computed simultaneously in poly(d) time and O(log d) space, yielding 2^{O(n)} time and O(n) space. ... Lemma 2.9 ... adapted from [LLW25, Corollary 3.6] ... Lemma 2.10 ... adapted from [LLW25, Corollary 3.25]"

    The paper's central resource improvement — quantum linear space and single-exponential time for the honest prover — is exactly the content of Lemmas 2.9–2.10, which are stated as 'adapted from' the same three authors' to-appear paper [LLW25] and are not proved here. The chain Corollary 1.4 → Theorems 3.5/4.7 → Theorems 3.4/4.5 → Lemmas 2.9–2.10 thus inherits all O(n)-space and 2^{O(n)}-time constants from that same-author citation. The acknowledgment reinforces this: 'A preliminary version of Section 3 ... appeared in Section 5 of the second arXiv version of [LLW25]'. This is load-bearing self-citation rather than a construction-level circularity, but the claimed improvement is not self-contained in this paper.

  2. self citation load bearing [Section 4.1, Lemma 4.8 and proof of Theorem 4.5]
    "Notably, an exact block-encoding W of X_Uhl was recently proposed in [UNWT25, Section 5.1]. Leveraging this key ingredient, our explicit implementation of Φ⋆(·) proceeds as follows: (1) Following [UNWT25, Section 5.1] (see Lemma 4.8), one can implement an exact block-encoding W of Tr_A(|ψ0⟩⟨ψ1|) ... using quantum O(n) space."

    The main new F²Est result (Theorem 4.7) depends on Theorem 4.5's lower bound, whose proof begins with an exact block-encoding of X_Uhl = Tr_A(|ψ0⟩⟨ψ1|). That encoding is not proved here; it is imported from [UNWT25, Section 5.1], a paper co-authored by Qisheng Wang. The current paper supplies the definition of W and the 'adapted from' label but not a derivation. This is another same-author, load-bearing dependency. It is not a restatement of the target fidelity bound, so it is not definitionally circular, but the Uhlmann half of the paper is not self-contained.

full rationale

Most of the derivation is ordinary theorem-proving rather than circular. Theorem 3.4 derives the approximate Holevo–Helstrom measurement from the sign-polynomial approximation, Hölder's inequality, and a POVM check; the completeness and soundness constants in Theorem 3.5, (1+α−2^{-n})/2 and (1+β)/2, come from direct inequalities on Protocol 2, with no fitted parameter renamed as a prediction. Similarly, Theorem 4.5's error analysis in Eqs. (4.3)–(4.6) compares the constructed overlap with the Uhlmann fidelity from [Joz94]/[Wat02], rather than assuming the target value. No step in the paper equates a prediction with an input by construction: the error bounds are derived, not tuned to the promised α, β, and the QSZK inclusion itself is the standard complete-problem route. The external concern that Theorem 4.5 proves only a postselected block-encoding overlap (Eq. 4.2) while Protocol 3 requires a physical CPTP map is a correctness/verification gap, not a circularity, and is not scored here. The score of 4 reflects the two load-bearing same-author citations: the O(n)-space QSVT machinery (Lemmas 2.9–2.10 from [LLW25], same three authors, to appear) and the exact block-encoding of Tr_A(|ψ0⟩⟨ψ1|) (Lemma 4.8 from [UNWT25], co-authored by Qisheng Wang). These supply the quantitative heart of the claimed improvement and are not proved in the manuscript. They are not restatements of the target theorems, so the central class-inclusion claim retains independent content, which keeps the circularity score below 6.

Axiom & Free-Parameter Ledger

5 free parameters · 9 axioms · 0 invented entities

The central claim rests on three kinds of input: standard quantum-information facts (Hölder, Holevo–Helstrom, Uhlmann, Fuchs–van de Graaf, QSD-completeness), routine analytic parameter choices listed as free parameters, and — critically — two imported algorithmic black boxes (LLW25's space-efficient QSVT; UNWT25's exact block-encoding of X_Uhl) that are not proved in this text. The latter two are the true axioms of the paper; note the author overlap with both cited sources. No physical entities are invented.

free parameters (5)
  • target error ε = 2^(−n)
    Additive error target for both algorithmic primitives (Theorems 3.4, 4.5). Chosen by hand; drives degree d' = 2^O(n).
  • sign-approximation dead-zone δ = ε/2^(r+2) (Thm 3.4); ε/2^(r+3) (Thm 4.5)
    Width of the linear region where the approximate sign may deviate; allocated to keep total error ≤ ε.
  • QSVT implementation error ϵ = ε/[2(36Ĉ_sgn+2C_sgn+37)] (Thm 3.4); ε/K with K ≥ (B1+√(B1²+12B0))/3 (Thm 4.5)
    Block-encoding error parameter for Lemma 2.10; chosen to close the quadratic error budget in Eq. (4.7).
  • polynomial degree d' for sign approximation = d' = 2d−1 = 2^O(n)
    Degree of the Chebyshev truncation used in both constructions; inherits the 2^O(n) query/time counts.
  • repetition counts t0, t1 in Protocol 1 = t0 = 2lq, t1 = 8lq²t0, with l = n
    Parallel-repetition parameters for error reduction from Lemma 2.14; set the transcript size n' = O(n^τ).
axioms (9)
  • standard math Matrix Hölder inequality for Schatten norms (Lemma 2.1)
    Used in the error analyses (Eq. (3.4c), (4.6c)) to bound trace terms by operator norm times trace norm; textbook result [Wat18].
  • standard math Fractional/sign decomposition identity T(ρ0,ρ1) = ½(Tr(ρ0 sgn((ρ0−ρ1)/2)) − Tr(ρ1 sgn((ρ0−ρ1)/2))) (Eq. (3.1))
    Fundamental to the explicit Holevo–Helstrom measurement (Proposition 3.3); taken from [WZ24, Eq. (8)].
  • standard math Holevo–Helstrom bound (Theorem 3.2)
    Gives the optimal discrimination probability ½+½T(ρ0,ρ1) and the soundness bound for Protocol 2.
  • standard math Uhlmann's theorem and strong form over channels (Theorem 4.2, Corollary 4.3)
    Gives the fidelity-based completeness/soundness for Protocol 3; Corollary 4.3 is implicit in [Wat02, Theorem 11].
  • standard math Fuchs–van de Graaf inequalities (Lemma 2.4)
    Bridge between trace-distance and fidelity promises in Corollary 4.9.
  • domain assumption Completeness of QSD for QSZK and hardness of QSC/QSCMM for co-QSZK/NIQSZK
    Reduces QSZK upper bounds to the two protocol theorems; cited to [Wat02], [Kob03], [CCKV08].
  • domain assumption Space-efficient sign-function polynomial approximation and QSVT block-encoding (Lemmas 2.9–2.10)
    The load-bearing algorithmic engine of both theorems; imported from [LLW25, Cor. 3.6/3.25], a to-appear paper by the same three authors. Not proved in this text.
  • domain assumption Exact block-encoding W of Tr_A(|ψ0⟩⟨ψ1|) (Lemma 4.8)
    Key ingredient for the algorithmic Uhlmann transform; imported from [UNWT25, Section 5.1], co-authored by Q. Wang (an author here).
  • domain assumption Parallel-repetition error reduction for QIP(2) (Lemma 2.14)
    Converts constant-gap protocols into 1/3-vs-2/3 with linear-space prover preserved; adapted from [JUW09, Section 3.2], not proved here.

pith-pipeline@v1.3.0-alltime-deepseek · 29758 in / 27277 out tokens · 205596 ms · 2026-08-03T16:50:56.596171+00:00 · methodology

0 comments
read the original abstract

The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

Figures

Figures reproduced from arXiv: 2512.11597 by Fran\c{c}ois Le Gall, Qisheng Wang, Yupan Liu.

Figure 1
Figure 1. Figure 1: Algorithmic Holevo–Helstrom measurement. [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Algorithmic Uhlmann transform. quantum states on the register A, each prepared by n-qubit polynomial-size quantum circuits Q0 and Q1 acting on the registers (A, R), respectively, as defined in Problem 4.1. The overall procedure for estimating F 2 (ρ0, ρ1) is presented in [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗

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

59 extracted references · 5 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry.original add.period pagebackref " Appearances:\!" * 'skip if write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION...

  2. [2]

    Statistical zero-knowledge languages can be recognized in two rounds

    William Aiello and Johan H stad. Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences . 42(3):327--345. 1991. https://doi.org/10.1016/0022-0000(91)90006-Q doi:10.1016/0022-0000(91)90006-Q . FOCS 1987 . Appearances:\!

    work page doi:10.1016/0022-0000(91)90006-q 1991

  3. [3]

    A polynomial quantum algorithm for approximating the Jones polynomial

    Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica . 55(3):395--421. 2009. https://doi.org/10.1007/s00453-008-9168-0 doi:10.1007/s00453-008-9168-0 . STOC 2006 . https://arxiv.org/abs/quant-ph/0511096 arXiv:quant-ph/0511096 . Appearances:\!

    Pith/arXiv arXiv 2009

  4. [4]

    Simulating Hamiltonian dynamics with a truncated Taylor series

    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://doi.org/10.1103/PhysRevLett.114.090502 doi:10.1103/PhysRevLett.114.090502 . https://arxiv.org/abs/1412.4687 arXiv:1412.4687 . Appearances:\!

    Pith/arXiv arXiv 2015

  5. [5]

    Statistical difference beyond the polarizing regime

    Itay Berman, Akshay Degwekar, Ron D Rothblum, and Prashant Nalini Vasudevan. Statistical difference beyond the polarizing regime. In Theory of Cryptography Conference . pages 311--332. Springer. 2019. https://doi.org/10.1007/978-3-030-36033-7\_12 doi:10.1007/978-3-030-36033-7\_12 . https://eccc.weizmann.ac.il/report/2019/038 ECCC:TR19-038 . Appearances:\!

    work page doi:10.1007/978-3-030-36033-7 2019

  6. [6]

    Unitary complexity and the Uhlmann transformation problem

    John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary complexity and the Uhlmann transformation problem. To appear in the proceedings of the 17th Innovations in Theoretical Computer Science Conference ( ITCS 2026) . 2026. https://arxiv.org/abs/2306.13073 arXiv:2306.13073 . Appearances:\!

    Pith/arXiv arXiv 2026

  7. [7]

    The polynomial method strikes back: tight quantum query bounds via dual polynomials

    Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: tight quantum query bounds via dual polynomials. Theory of Computing . 16(10):1--71. 2020. https://doi.org/10.4086/toc.2020.v016a010 doi:10.4086/toc.2020.v016a010 . STOC 2018 . https://arxiv.org/abs/1710.09079 arXiv:1710.09079 . Appearances:\!

    Pith/arXiv arXiv 2020

  8. [8]

    Local transformations of bipartite entanglement are rigid

    John Bostanci, Tony Metger, and Henry Yuen. Local transformations of bipartite entanglement are rigid. To appear in the proceedings of the 17th Innovations in Theoretical Computer Science Conference ( ITCS 2026) . 2026. https://arxiv.org/abs/2509.05257 arXiv:2509.05257 . Appearances:\!

    Pith/arXiv arXiv 2026

  9. [9]

    Quantum expanders: Motivation and construction

    Avraham Ben-Aroya , Oded Schwartz, and Amnon Ta-Shma . Quantum expanders: Motivation and construction. Theory of Computing . 6(1):47--79. 2010. https://doi.org/10.4086/toc.2010.v006a003 doi:10.4086/toc.2010.v006a003 . CCC 2008 . Appearances:\!

    work page doi:10.4086/toc.2010.v006a003 2010

  10. [10]

    Interactive and noninteractive zero knowledge are equivalent in the help model

    Andr \'e Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, and Salil Vadhan. Interactive and noninteractive zero knowledge are equivalent in the help model. In Theory of Cryptography Conference . pages 501--534. Springer. 2008. https://doi.org/10.1007/978-3-540-78524-8\_28 doi:10.1007/978-3-540-78524-8\_28 . https://eprint.iacr.org/2007/467 IACR ePrint...

    doi:10.1007/978-3-540-78524-8 2008

  11. [11]

    New results on quantum property testing

    Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald Wolf d e Wolf. New results on quantum property testing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) . volume 8 of LIPIcs . pages 145--156. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik. 2010. https://doi.org/10.4230/LIP...

    Pith/arXiv arXiv 2010

  12. [12]

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

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

    arXiv 2025

  13. [13]

    Cryptographic distinguishability measures for quantum-mechanical states

    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://doi.org/10.1109/18.761271 doi:10.1109/18.761271 . https://arxiv.org/abs/quant-ph/9712042 arXiv:quant-ph/9712042 . Appearances:\!

    Pith/arXiv arXiv 1999

  14. [14]

    A complete characterization of unitary quantum space

    Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference . volume 94. page 4. 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.4 doi:10.4230/LIPIcs.ITCS.2018.4 . https://arxiv.org/abs/1604.01384 arXiv:1604.01384 . Appearances:\!

    Pith/arXiv arXiv 2018

  15. [15]

    The complexity of perfect zero-knowledge

    Lance Fortnow. The complexity of perfect zero-knowledge. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing . pages 204--209. 1987. https://doi.org/10.1145/28395.28418 doi:10.1145/28395.28418 . Appearances:\!

    arXiv 1987

  16. [16]

    Towards a quantum-inspired proof for IP = PSPACE

    Ayal Green, Guy Kindler, and Yupan Liu. Towards a quantum-inspired proof for IP = PSPACE . Quantum Information & Computation . 21(5 & 6):377--386. 2021. https://doi.org/10.26421/QIC21.5-6-2 doi:10.26421/QIC21.5-6-2 . https://arxiv.org/abs/1912.11611 arXiv:1912.11611 . Appearances:\!

    Pith/arXiv arXiv 2021

  17. [17]

    Rothblum

    Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. Journal of the ACM . 62(4):1--64. 2015. https://doi.org/10.1145/2699436 doi:10.1145/2699436 . STOC 2008 . https://eccc.weizmann.ac.il/report/2017/108 ECCC:TR17-108 . Appearances:\!

    work page doi:10.1145/2699436 2015

  18. [18]

    Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems

    Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. Journal of the ACM . 38(3):691--729. 1991. https://doi.org/10.1145/116825.116852 doi:10.1145/116825.116852 . FOCS 1986 . Appearances:\!

    arXiv 1991

  19. [19]

    On doubly-efficient interactive proof systems

    Oded Goldreich. On doubly-efficient interactive proof systems. Foundations and Trends in Theoretical Computer Science . 13(3):158--246. 2018. https://doi.org/10.1561/0400000084 doi:10.1561/0400000084 . https://eccc.weizmann.ac.il/report/2017/017 ECCC:TR17-017 . Appearances:\!

    work page doi:10.1561/0400000084 2018

  20. [20]

    Improved quantum algorithms for fidelity estimation

    Andr \'a s Gily \'e n and Alexander Poremba. Improved quantum algorithms for fidelity estimation. arXiv preprint . 2022. https://arxiv.org/abs/2203.15993 arXiv:2203.15993 . Appearances:\!

    Pith/arXiv arXiv 2022

  21. [21]

    Quantum logspace computations are verifiable

    Uma Girish, Ran Raz, and Wei Zhan. Quantum logspace computations are verifiable. In Proceedings of the 2024 Symposium on Simplicity in Algorithms . pages 144--150. 2024. https://doi.org/10.1137/1.9781611977936.14 doi:10.1137/1.9781611977936.14 . https://arxiv.org/abs/2307.11083 arXiv:2307.11083 . Appearances:\!

    Pith/arXiv arXiv 2024

  22. [22]

    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://doi.org/10.1145/3313276.3316366 doi:10.1145/3313276.3316366 . https://arxiv...

    arXiv 2019

  23. [23]

    Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

    Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2) . computational complexity . 31(2):1--52. 2022. https://doi.org/10.1007/s00037-022-00231-8 doi:10.1007/s00037-022-00231-8 . MFCS 2018 . https://arxiv.org/abs/1805.11139 arXiv:1805.11139 . Appearances:\!

    Pith/arXiv arXiv 2022

  24. [24]

    Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge

    Oded Goldreich, Amit Sahai, and Salil Vadhan. Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing . pages 399--408. 1998. https://doi.org/10.1145/276698.276852 doi:10.1145/276698.276852 . Appearances:\!

    arXiv 1998

  25. [25]

    Quantum detection and estimation theory

    Carl W Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics . 1:231--252. 1969. https://doi.org/10.1007/BF01007479 doi:10.1007/BF01007479 . Appearances:\!

    doi:10.1007/bf01007479 1969

  26. [26]

    Statistical decision theory for quantum systems

    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 . Appearances:\!

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

  27. [27]

    QIP = PSPACE

    Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE . Journal of the ACM . 58(6):1--27. 2011. https://doi.org/10.1145/2049697.2049704 doi:10.1145/2049697.2049704 . STOC 2010 . https://arxiv.org/abs/0907.4737 arXiv:0907.4737 . Appearances:\!

    arXiv 2011

  28. [28]

    Fidelity for mixed quantum states

    Richard Jozsa. Fidelity for mixed quantum states. Journal of modern optics . 41(12):2315--2323. 1994. https://doi.org/10.1080/09500349414552171 doi:10.1080/09500349414552171 . Appearances:\!

    doi:10.1080/09500349414552171 1994

  29. [29]

    Two-message quantum interactive proofs are in PSPACE

    Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science . pages 534--543. IEEE. 2009. https://doi.org/10.1109/FOCS.2009.30 doi:10.1109/FOCS.2009.30 . https://arxiv.org/abs/0905.1300 arXiv:0905.1300 . Appearances:\!

    Pith/arXiv arXiv 2009

  30. [30]

    Tutorial on the quantikz package

    Alastair Kay. Tutorial on the quantikz package. arXiv preprint . 2018. https://arxiv.org/abs/1809.03842 arXiv:1809.03842 . Appearances:\!

    arXiv 2018

  31. [31]

    Quantum measurements and the Abelian stabilizer problem

    Alexei Yu Kitaev. Quantum measurements and the Abelian stabilizer problem. arXiv preprint . 1995. https://arxiv.org/abs/quant-ph/9511026 arXiv:quant-ph/9511026 . Appearances:\!

    Pith/arXiv arXiv 1995

  32. [32]

    Generalized quantum Arthur--Merlin games

    Hirotada Kobayashi, François Le Gall , and Harumichi Nishimura. Generalized quantum Arthur--Merlin games. SIAM Journal on Computing . 48(3):865--902. 2019. https://doi.org/10.1137/17M1160173 doi:10.1137/17M1160173 . CCC 2015 . https://arxiv.org/abs/1312.4673 arXiv:1312.4673 . Appearances:\!

    Pith/arXiv arXiv 2019

  33. [33]

    Non-interactive quantum perfect and statistical zero-knowledge

    Hirotada Kobayashi. Non-interactive quantum perfect and statistical zero-knowledge. In Proceedings of the 14th International Symposium on Algorithms and Computation . pages 178--188. Springer. 2003. https://doi.org/10.1007/978-3-540-24587-2\_20 doi:10.1007/978-3-540-24587-2\_20 . https://arxiv.org/abs/quant-ph/0207158 arXiv:quant-ph/0207158 . Appearances:\!

    Pith/arXiv arXiv 2003

  34. [34]

    Hamiltonian simulation by qubitization

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

    Pith/arXiv arXiv 2019

  35. [36]

    Complexity-theoretic perspectives on quantum state testing

    Yupan Liu. Complexity-theoretic perspectives on quantum state testing . PhD thesis. Nagoya University. 2025. Appearances:\!

    2025

  36. [37]

    Quantum state testing beyond the polarizing regime and quantum triangular discrimination

    Yupan Liu. Quantum state testing beyond the polarizing regime and quantum triangular discrimination. Computational Complexity . 34(11):1--67. 2025. https://doi.org/10.1007/s00037-025-00273-8 doi:10.1007/s00037-025-00273-8 . https://arxiv.org/abs/2303.01952 arXiv:2303.01952 . Appearances:\!

    arXiv 2025

  37. [38]

    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 . 2025. https://arxiv.org/abs/2308.05079 arXiv:2308.05079 . Appearances:\!

    Pith/arXiv arXiv 2025

  38. [39]

    On estimating the quantum _ distance

    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://doi.org/10.4230/LIPIcs.ESA.2025.105 doi:10.4230/LIPIcs.ESA.2025.105 . https://arxiv.org/abs/2505...

    Pith/arXiv arXiv 2025

  39. [40]

    Merlinization of complexity classes above BQP

    Tomoyuki Morimae and Harumichi Nishimura. Merlinization of complexity classes above BQP . Quantum Information & Computation . 17(11 & 12):959--972. 2017. https://doi.org/10.26421/QIC17.11-12-3 doi:10.26421/QIC17.11-12-3 . https://arxiv.org/abs/1704.01514 arXiv:1704.01514 . Appearances:\!

    Pith/arXiv arXiv 2017

  40. [41]

    Quantum Arthur--Merlin games

    Chris Marriott and John Watrous. Quantum Arthur--Merlin games. Computational Complexity . 14(2):122--152. 2005. https://doi.org/10.1007/s00037-005-0194-x doi:10.1007/s00037-005-0194-x . CCC 2004 . https://arxiv.org/abs/cs/0506068 arXiv:cs/0506068 . Appearances:\!

    Pith/arXiv arXiv 2005

  41. [42]

    stateQIP = statePSPACE

    Tony Metger and Henry Yuen. stateQIP = statePSPACE . In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science . pages 1349--1356. IEEE . 2023. https://doi.org/10.1109/FOCS57990.2023.00082 doi:10.1109/FOCS57990.2023.00082 . https://arxiv.org/abs/2301.07730 arXiv:2301.07730 . Appearances:\!

    arXiv 2023

  42. [43]

    Quantum computation and quantum information

    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 . Appearances:\!

    doi:10.1017/cbo9780511976667 2010

  43. [44]

    Rothblum, and Ron D

    Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. SIAM Journal on Computing . 50(3). 2021. https://doi.org/10.1137/16M1096773 doi:10.1137/16M1096773 . STOC 2016 . https://eccc.weizmann.ac.il/report/2016/016 ECCC:TR16-016 . Appearances:\!

    doi:10.1137/16m1096773 2021

  44. [45]

    IP = PSPACE

    Adi Shamir. IP = PSPACE . Journal of the ACM . 39(4):869--877. 1992. https://doi.org/10.1145/146585.146609 doi:10.1145/146585.146609 . FOCS 1990 . Appearances:\!

    arXiv 1992

  45. [46]

    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. https://doi.org/10.1145/636865.636868 doi:10.1145/636865.636868 . FOCS 1997 . https://eccc.weizmann.ac.il/report/2000/084 ECCC:TR00-084 . Appearances:\!

    arXiv 2003

  46. [47]

    Inverting well conditioned matrices in quantum logspace

    Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing . pages 881--890. 2013. https://doi.org/10.1145/2488608.2488720 doi:10.1145/2488608.2488720 . Appearances:\!

    arXiv 2013

  47. [48]

    The ``transition probability'' in the state space of A^* -algebra

    Armin Uhlmann. The ``transition probability'' in the state space of A^* -algebra. Reports on Mathematical Physics . 9(2):273--279. 1976. https://doi.org/10.1016/0034-4877(76)90060-4 doi:10.1016/0034-4877(76)90060-4 . Appearances:\!

    doi:10.1016/0034-4877(76)90060-4 1976

  48. [49]

    Quantum algorithms for U hlmann transformation

    Takeru Utsumi, Yoshifumi Nakata, Qisheng Wang, and Ryuji Takagi. Quantum algorithms for U hlmann transformation. arXiv preprint . 2025. https://arxiv.org/abs/2509.03619 arXiv:2509.03619 . Appearances:\!

    arXiv 2025

  49. [50]

    Quantum proofs

    Thomas Vidick and John Watrous. Quantum proofs. Foundations and Trends in Theoretical Computer Science . 11(1-2):1--215. 2016. https://doi.org/10.1561/0400000068 doi:10.1561/0400000068 . https://arxiv.org/abs/1610.01664 arXiv:1610.01664 . Appearances:\!

    Pith/arXiv arXiv 2016

  50. [51]

    Space-bounded quantum complexity

    John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences . 59(2):281--326. 1999. https://doi.org/10.1006/jcss.1999.1655 doi:10.1006/jcss.1999.1655 . CCC 1998 . Appearances:\!

    arXiv 1999

  51. [52]

    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://doi.org/10.1109/SFCS.2002.1181970 doi:10.1109/SFCS.2002.1181970 . https://arxiv.org/abs/quant-ph/0202111 arXiv:quant-ph/0202111 . Appearances:\!

    Pith/arXiv arXiv 2002

  52. [53]

    Quantum computational complexity

    John Watrous. Quantum computational complexity. Encyclopedia of Complexity and Systems Science . pages 7174--7201. 2009. https://doi.org/10.1007/978-0-387-30440-3\_428 doi:10.1007/978-0-387-30440-3\_428 . https://arxiv.org/abs/0804.3401 arXiv:0804.3401 . Appearances:\!

    Pith/arXiv arXiv 2009

  53. [54]

    Zero-knowledge against quantum attacks

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

    Pith/arXiv arXiv 2009

  54. [55]

    The Theory of Quantum Information

    John Watrous. The Theory of Quantum Information . Cambridge University Press. 1st edition. 2018. https://doi.org/10.1017/9781316848142 doi:10.1017/9781316848142 . Appearances:\!

    doi:10.1017/9781316848142 2018

  55. [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://doi.org/10.1109/TIT.2024.3399014 doi:10.1109/TIT.2024.3399014 . https://arxiv.org/abs/2203.13522 arXiv:2203.13522 . Appearances:\!

    arXiv 2024

  56. [57]

    Quantum Information Theory

    Mark M Wilde. Quantum Information Theory . Cambridge University Press. 1st edition. 2013. https://doi.org/10.1017/9781316809976 doi:10.1017/9781316809976 . Appearances:\!

    doi:10.1017/9781316809976 2013

  57. [58]

    Quantum computing: Lecture notes

    Ronald Wolf d e Wolf. Quantum computing: Lecture notes. arXiv preprint . 2019. https://arxiv.org/abs/1907.09415 arXiv:1907.09415 . Appearances:\!

    Pith/arXiv arXiv 2019

  58. [59]

    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://doi.org/10.1109/TIT.2023.3321121 doi:10.1109/TIT.2023.3321121 . https://arxiv.org/abs/2301.06783 arXiv:2301.06783 . Appearances:\!

    arXiv 2024

  59. [60]

    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://doi.org/10.1109/TIT.2022.3203985 doi:10.1109/TIT.2022.3203985 . https://arxiv.org/abs/2103.09076 arXiv:2103.09076 . Appearances:\!

    arXiv 2023