Pith. sign in

REVIEW 5 minor 23 references

Span Programs and Quantum Space Complexity

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the minimum space of a unitary quantum algorithm for any Boolean function is at least the logarithm of the size of its smallest approximate span program.

desk verdict A careful, honest paper that proves the SU(f) ≥ log ~SP(f) connection and a modest but real (log n)^{2-o(1)} monotone lower bound; the math holds and it deserves serious refereeing. read the letter →

arxiv 1908.04232 v2 pith:PA5CXN2U submitted 2019-08-12 quant-ph cs.CC

Stacey Jeffery This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1281P68
keywords spanprogramsquantumspacecomplexityapproximatemonotonephaseestimationalgorithmslowerboundsrankmeasurequery
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper ties quantum memory to a classical linear-algebraic measure called span program size, and to its approximate variant. It proves that any unitary quantum algorithm computing a Boolean function $f$ with bounded error must use space at least $\Omega(\log \widetilde{SP}(f))$, where $\widetilde{SP}(f)$ is the size of the smallest approximate span program for $f$; the one-sided-error version gives $S^1_U(f)\ge\Omega(\log SP(f))$. An approximate span program relaxes the accepting-witness condition by allowing a small leakage into forbidden subspaces, and that relaxation is exactly what lets two-sided-error algorithms be converted into span programs. Because span program size is a classical quantity long studied as a route to formula-size lower bounds, this gives a new, structured way to attack quantum space lower bounds. The paper also proves a non-trivial lower bound for an explicit monotone function in a restricted but natural model: any monotone phase estimation algorithm for it requires $(\log n)^{2-o(1)}$ space.

What carries the argument

The load-bearing object is the span program, a linear-algebraic decision certificate: a target vector $|\tau\rangle$, a linear map $A$, and input-dependent subspaces $H_{j,b}$ labelled by input bits, with $x$ accepted exactly when $|\tau\rangle\in A(H(x))$; its size is $\dim H$. The argument runs on two translations. From algorithm to span program, the algorithm's full history is kept in states $|t,b,j,z,a\rangle$ with a time counter $t$ and a query-value bit $b$; the map $A$ records each unitary transition and splits accepting from rejecting final states, producing a span program of size $2^{S+O(1)}$ whose approximate positive witness is allowed leakage proportional to the algorithm's rejection probability. From span program to algorithm, phase estimation on the reflection unitary $U(x)=(2\Pi_{\ker A}-I)(2\Pi_{H(x)}-I)$ separates accepted from rejected inputs using $O(\log K+\log C)$ space. In the monotone case, setting $H_{j,0}=\{0\}$ gives monotone span programs, and the lower bound is driven by an approximate-rank inequality relating $m\widetilde{SP}_\kappa(f)$ to $\sqrt{\kappa}$-rank of a matrix $M$ divided by the largest rank of $M\circ\Delta_{j,1}$.

What would settle it

A decisive test would be to exhibit a function family $f_n$ with a bounded-error unitary algorithm using $S(n)=O(\log n)$ space and a proof that $\widetilde{SP}(f_n)$ is superpolynomial; the theorem predicts $S_U(f_n)\ge\Omega(\log\widetilde{SP}(f_n))$, so such a pair is a counterexample. Concretely, one can evaluate the rank program of Lemma 4.4 for any candidate $f_n$ and compare the resulting approximate span program size with the space used by an explicit algorithm.

Watch

Extended reading notes

Core claim

The central claim is a two-way correspondence between unitary quantum algorithms and span programs. Given a unitary algorithm with $T$ queries and space $S$, the paper constructs a span program of size $2^{O(S)}$ and complexity $O(T)$ that approximates the function computed by the algorithm; if the algorithm has one-sided error, the span program decides the function exactly. Conversely, any span program of size $K$ and complexity $C$ compiles into a unitary algorithm using $O(\log K+\log C)$ space and $O(C)$ queries. Therefore $S_U(f)\ge\Omega(\log\widetilde{SP}(f))$ and $S^1_U(f)\ge\Omega(\log SP(f))$, with the pairing tight up to the logarithmic cost of the span program's query complexity. For monotone functions, the same conversion restricted to monotone span programs lower-bounds the space of monotone phase estimation algorithms, and an explicit function is shown to have approximate monotone span program size $2^{(\log n)^{2-o(1)}}$, yielding a $(\log n)^{2-o(1)}$ space lower bound for that class.

Load-bearing premise

The load-bearing assumption is the algorithmic model: a unitary algorithm with no intermediate measurements that pays $\log T$ qubits for a counter; if a machine can measure and reuse qubits under classical control, the history-to-span-program conversion behind the lower bound may not go through.

Editorial extensions

If this is right

  • For almost all Boolean functions on $n$ bits, the one-sided unitary space complexity is $\Omega(n)$, following from the known exponential span program size of almost all functions.
  • The bounded-error lower bound is essentially tight: compiling the smallest approximate span program gives a unitary algorithm whose space is $O(\log\widetilde{SP}(f)+\log C(f))$, so space and span-program size match up to the logarithm of query complexity.
  • For the explicit function constructed in the monotone section, every monotone phase estimation algorithm needs $(\log n)^{2-o(1)}$ space, and for the satisfiability-type function underlying the strongest known monotone span program lower bound, every one-sided monotone phase estimation algorithm needs $\Omega(n)$ space.
  • The same route exports a new classical bound: the explicit function has approximate monotone span program size $2^{(\log n)^{2-o(1)}}$, a non-trivial lower bound for that classical measure.
  • Evaluating an approximate span program of size $2^{k(n)}$ is complete for the class of functions computable in unitary space $k(n)$, paralleling the known completeness of matrix inversion for the same class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: proving a super-logarithmic unitary space lower bound for an explicit function is now equivalent to a concrete linear-algebraic problem, namely showing that some explicit function has superpolynomial approximate span program size; the paper notes that no such span program bound is known, so the open question is largely a classical rank problem in disguise.
  • Inference: if intermediate measurements and classical control are allowed, the lower bound may fail, because the conversion linearizes the complete unitary history and charges for a time counter; testing whether general space-bounded quantum algorithms with qubit reuse also satisfy $S\ge\Omega(\log\widetilde{SP}(f))$ would clarify the true scope of the result.
  • Inference: the certificate-complexity barrier $\widetilde{\deg}_{1/3}(g)\le C(g)^2$ for total functions limits the pattern-matrix technique to $(\log n)^2$; the paper's generalized lemma suggests that using partial assignments with low-degree restrictions, rather than full certificates, is the natural way to try to break that barrier.
  • Inference: if every function had a space-optimal monotone phase estimation algorithm, the monotone lower bound would upgrade to a genuine unitary space lower bound for monotone functions; verifying or refuting that would convert Theorem 5.3 into a stronger statement.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. This paper establishes a two-way quantitative correspondence between unitary quantum space complexity and span program size. For a Boolean function f, Theorem 4.1 states SU(f) = Ω(log ~SP(f)) and S1_U(f) = Ω(log SP(f)); the forward direction (Theorem 3.2) converts a unitary bounded-error algorithm with T queries and space S = s + log T into a κ-approximate span program of size 2^{O(S)} and complexity O(T), and the reverse compiler (Theorem 3.1) shows the bound is tight up to log-complexity terms. The paper also extends the rank method to approximate span programs (Lemmas 4.4 and 4.6) and, for monotone functions, proves lower bounds on approximate monotone span program size, obtaining a (log n)^{2-o(1)} bound for an explicit monotone function and transferring it to monotone phase estimation algorithms (Theorems 5.3 and 5.14).

Significance. The main result is significant because it connects quantum space, a poorly understood resource, to classical span program size, and it does so with an explicit construction rather than a black-box argument. The conversion in Section 3.3 is the key technical contribution and is carefully analyzed; the positive and negative witness lemmas (Lemmas 3.12 and 3.13) are correct and give the claimed size and complexity bounds. The approximate rank lower bound (Lemma 4.6) provides a concrete route to space lower bounds, and the first non-trivial lower bound on approximate monotone span program size for an explicit function is a genuine advance. The main scope limitation --- the model is unitary, space includes log T for the program counter, and the monotone lower bounds apply only to monotone phase estimation algorithms --- is stated explicitly in Section 2 and the Discussion, and is not an internal inconsistency. If the result holds as proved, it constitutes a noteworthy step for space-bounded quantum complexity.

minor comments (5)
  1. [Abstract] The final sentence of the abstract says 'we then give the first non-trivial lower bound on the approximate span program size of an explicit function'; since Theorem 5.3 and Corollary 5.15 are about the approximate monotone span program size m~SPκ(f), the abstract should say 'approximate monotone span program size' to avoid overstating the result.
  2. [Lemma 4.4] In the statement of Lemma 4.4, the approximate positive witness condition is written as ||ΠH(x)|wx⟩||^2 ≤ κ/W−, but the proof and Definition 3.6 require the orthogonal complement, i.e., ||ΠH(x)⊥|wx⟩||^2 ≤ κ/W−; this typo should be corrected.
  3. [Lemma 5.16] The proof of Lemma 5.16 uses the identity Ox = I - 2Π_{H(x)}. This is literally true only for monotone span programs with no Htrue register, or under the convention that the one-query operation in Definition 5.12 is the reflection about H(x) rather than the standard oracle Ox|j,z⟩ = (-1)^{x_j}|j,z⟩; the normalization or convention should be stated explicitly to avoid confusion.
  4. [Claim 3.8] The displayed size formula in Claim 3.8 is not typeset unambiguously; the proof, together with Corollary 3.9, implies s(P') = (s(P)+2)^{2 log(1/κ')/log(1/κ)}, and the formula should be corrected to match the proof.
  5. [Definition 5.12] The definition of a phase estimation algorithm requires the procedure to succeed for every M' ≥ M and T' ≥ T, and this condition is used critically in Appendix B (e.g., Claim B.1); this non-obvious uniformity assumption deserves a remark so that readers understand that it is part of the model.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main SU(f) ≥ Ω(log ~SP(f)) theorem is derived by an explicit constructive reduction, not by fitting or self-referential definition.

full rationale

The paper's central claim (Theorem 4.1) is obtained from Theorem 3.2, which converts any bounded-error unitary algorithm A for f with space S = s + log T into an approximate span program P_A whose size is directly counted as dim H = (2T+2)·2·2^s = 2^{S+O(1)} (Corollary 3.14), and whose approximation properties are proven from the algorithm's rejection probability p0(x) in Lemmas 3.12 and 3.13. No parameter is fitted to a data subset and then renamed a prediction; the witness bounds W_- = O(T) and W_+ = O(T) are consequences of the unitary evolution of A, and the constant c = 5 is chosen after the fact only to make the 9/10 gap numerical. The one-sided case follows similarly, and the rank-measure lower bounds (Lemmas 4.4, 4.6, Theorem 5.4) restate the span-program inequalities in matrix form, with external lower bounds from [BT17], [She09], and [PR17] used for instantiation. The relaxation of the approximate-span-program definition from [IJ19] is a definitional choice, and the [IJ19] lemmas invoked for normalization and constant reduction (Theorem A.1, Claim 3.8) are not load-bearing for the main lower bound: even without reducing κ, the 9/10-approximate program would give SU(f) ≥ Ω(log ~SP_{9/10}(f)), and Corollary 3.9 relates constant κ values polynomially. The paper explicitly limits its strongest nontrivial lower bound to monotone phase estimation algorithms, so the scope caveat is stated rather than hidden. No equation in the paper reduces to its own input by construction.

Assumptions & free parameters 2 free parameters · 7 assumptions · 1 invented entities

The paper introduces the relaxed approximate span program definition and a new algorithm class, but the central asymptotic bounds do not depend on any fitted numerical parameter; they rest on standard lemmas and the external BT17 separation.

free parameters (2)
  • kappa (approximation parameter) = 1/4 in ~SP(f); arbitrary constant
    Definition 3.7 sets kappa=1/4; Claim 3.8 and Corollary 3.9 show any constant kappa changes size only polynomially, so asymptotic results are insensitive to this choice.
  • c (constant in span program construction) = 5
    Corollary 3.14 sets c=5 to obtain a 9/10-approximation; any sufficiently large constant works, so it does not affect asymptotics.
assumptions (7)
  • standard math Effective spectral gap lemma (Lemma 2.1)
    Used in Lemma 3.11 to bound the phase-estimation overlap; taken from [LMR+11].
  • standard math Characterization of SP(f) as a rank minimization (Lemma 4.3)
    Used to derive the approximate version and the rank-measure lower bounds; from [Lok09].
  • standard math Pattern matrix rank and approximate rank bounds (Lemma 5.9)
    Used in Lemma 5.10 and Theorem 5.3 to lower bound approximate rank through approximate degree; from [She09].
  • domain assumption Existence of a function p with certificate complexity M^{1+o(1)} and approximate degree M^{2-o(1)} (BT17)
    Load-bearing for the explicit (log n)^(2-o(1)) lower bound; from [BT17].
  • domain assumption Quantum algorithm model (unitary, with space S = s + log T)
    All results are stated for unitary algorithms without intermediate measurements; space includes a counter register (Definition 2.2).
  • standard math Approximate span program witness identity (min error = 1/w_-(x))
    Used to justify the gap between positive and negative witnesses in Definition 3.6; from [IJ19].
  • standard math Amplitude estimation guarantees (Lemma 2.5)
    Used in the compiled algorithm and in the phase estimation lower bound proofs; from [BHMT02].
invented entities (1)
  • Monotone phase estimation algorithms
    purpose: Defines the restricted class of algorithms for which log m~SP(f) lower-bounds space complexity
    A new algorithmic restriction defined in Section 5.2 (Definition 5.13); it is a conceptual entity with no external falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Span Programs and Quantum Space Complexity." pith.science (2026). https://pith.science/paper/PA5CXN2U

@misc{pith2026190804232,
  author       = {Pith},
  title        = {Pith review of: Span Programs and Quantum Space Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PA5CXN2U}},
  note         = {Machine review of arXiv:1908.04232}
}
read the original abstract

While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages

  1. [1]

    Arora and B

    S. Arora and B. Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

    work page 2009

  2. [2]

    Separations in query complexity using cheat sheets

    S. Aaronson, S. Ben-David , and R. Kothari. Separations in query complexity using cheat sheets. In Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing (STOC 2016) , pages 863--876, 2016. arXiv:1511.01937

    work page Pith review arXiv 2016

  3. [3]

    N. Alon, T. Lee, A. Schraibman, and S. Vempala. The approximate rank of a matrix and its algorithmic applications. In Proceedings of the forty-fifth annual ACM Symposium on Theory of Computing (STOC 2013) , pages 675--684, 2013

    work page 2013

  4. [4]

    Babai, A

    L. Babai, A. G \'a l, and A. Wigderson. Superpolynomial lower bounds for monotone span programs. Combinatorica , 19:301--319, 1999

    work page 1999

  5. [5]

    Brassard, P

    G. Brassard, P. H yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In S. J. Lomonaca and H. E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume , volume 305 of AMS Contemporary Mathematics Series Millennium Volume , pages 53--74. AMS, 2002. arXiv:quant-ph/0005055v1

    arXiv 2002

  6. [6]

    A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

    M. Bun and J. Thaler. A nearly optimal lower bound on the approximate degree of AC^0 . In Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017) , 2017. arXiv:1703.05784

    work page Pith review arXiv 2017

  7. [7]

    Fefferman and C

    B. Fefferman and C. Lin. A complete characterization of unitary quantum space. In Proceedings of the 2018 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2018) , pages 4:1--4:21, 2018. arXiv:1604.01384

    arXiv 2018

  8. [8]

    A. G \`a l. A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity , 10(4):277--296, 2001

    work page 2001

Show all 23 references
  1. [9]

    Approximate span programs

    T.\ Ito and S.\ Jeffery. Approximate span programs. Algorithmica , 81(6):2158--2195, 2019. arXiv:1507.00432

    2019 arXiv

  2. [10]

    S. Jeffery. Frameworks for Quantum Algorithms . PhD thesis, University of Waterloo, 2014. Available at http://uwspace.uwaterloo.ca/handle/10012/8710

    2014

  3. [11]

    Jozsa, B

    R. Jozsa, B. Kraus, A. Miyake, and J. Watrous. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A , 466(2115), 2009

    2009

  4. [12]

    Quantum measurements and the A belian stabilizer problem, 1995

    A.\ Kitaev. Quantum measurements and the A belian stabilizer problem, 1995. arXiv:quant-ph/9511026

    1995 arXiv

  5. [13]

    Karchmer and A

    M. Karchmer and A. Wigderson. On span programs. In Proceedings of the IEEE 8th Annual Conference on Structure in Complexity Theory , pages 102--111, 1993

    1993

  6. [14]

    T. Lee, R. Mittal, B. Reichardt, R. S palek, and M. Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011) , pages 344--353, 2011

    2011

  7. [15]

    S. V. Lokam. Complexity Lower Bounds using Linear Algebra . Now Publishers Inc., Hanover, MA, USA, 2009

    2009

  8. [16]

    Pitassi and R

    T. Pitassi and R. Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) , pages 1246--1255, 2017

    2017

  9. [17]

    A. A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica , 10(1):810093, 1990

    1990

  10. [18]

    A. A. Razborov. On submodular complexity measures. In Poceedings of the London Mathematical Society symposium on Boolean function complexity , pages 76 -- 83, 1992

    1992

  11. [19]

    Reichardt

    B. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every B oolean function. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009) , pages 544--551, 2009. arXiv:quant-ph/0904.2759

    2009 arXiv

  12. [20]

    Robere , T

    R. Robere , T. Pitassi , B. Rossman , and S. A. Cook . Exponential lower bounds for monotone span programs. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016) , pages 406--415, 2016

    2016

  13. [21]

    Span-program-based quantum algorithm for evaluating formulas

    B.\ Reichardt and R.\ S palek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing , 8(13):291--319, 2012

    2012

  14. [22]

    Sherstov

    Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing , 40(6):1969–2000, 2009

    1969

  15. [23]

    J. Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences , 59(2):281--326, 1999

    1999

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.