Plaintext
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49
www.theoryofcomputing.org
Span Programs and Quantum Space
Complexity
Stacey Jefferyโ
Received October 7, 2020; Revised November 3, 2021; Published May 24, 2022
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 ๐ with one-sided error to the logarithm of its span program size
over the reals, 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 (i. e., an algorithm that makes no measurements
until the final step) to compute ๐ with bounded (two-sided) error is at least the
logarithm of its approximate span program size. Approximate span programs have been
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.
A conference version of this paper appeared in the Proceedings of the 11th Innovations in Theoretical Computer
Science Conference, 2020 [17].
โ Supported by an NWO WISE Fellowship, an NWO Veni Innovational Research Grant under project number
639.021.752, and QuantERA project QuantAlgo 680-91-03. SJ is a CIFAR Fellow in the Quantum Information Science
Program.
ACM Classification: F.1.1, F.1.3
AMS Classification: 81P68
Key words and phrases: quantum computing, quantum space complexity, span programs
ยฉ 2022 Stacey Jeffery
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018.a011
S TACEY J EFFERY
While no non-trivial lower bound is known on the span program size (or
approximate span program size) of any explicit function, a number of lower bounds
are known on the monotone span program size. We show that the approximate
monotone span program size of ๐ is a lower bound on the space needed by quantum
algorithms of a particular form, called monotone phase estimation algorithms, to compute
๐ . We then give the first non-trivial lower bound on the approximate monotone span
program size of an explicit function.
1 Introduction
While quantum computers hold the promise of significant speedups for a number of problems,
building them is a serious technological challenge, and it is expected that early quantum
computers will have quantum memories of very limited size. This motivates the theoretical
question: what problems could we solve faster on a quantum computer with limited space?
Or similarly, what is the minimum number of qubits needed to solve a given problem (and
hopefully still get a speedup)?
We take a modest step towards answering such questions, by relating the space complexity
of a function ๐ to its span program size (see Definition 3.3), which is a measure that has received
significant attention in theoretical computer science over the past few decades. Span programs
are a model of computation introduced by Karchmer and Wigderson [20] in an entirely classical
setting; they defined the span program size of a function in order to lower bound the size of
counting branching programs. Some time later, Reichardt and ล palek [28] related span programs
to quantum algorithms, and introduced the new measure of span program complexity (see
Definition 3.4). The importance of span programs in quantum algorithms stems from the ability
to compile any span program for a function ๐ into a bounded error quantum algorithm for ๐
[27]. In particular, there is a tight correspondence between the span program complexity of ๐ ,
and its quantum query complexityโa rather surprising and beautiful connection for a model
originally introduced outside the realm of quantum computing. In contrast, the classical notion
of span program size had received no attention in the quantum computing literature before now.
Ref. [15] defined the notion of an approximate span program for a function ๐ , and showed
that even an approximate span program for ๐ can be compiled into a bounded error quantum
algorithm for ๐ . In this paper, we further relax the definition of an approximate span program
for ๐ , making analysis of such algorithms significantly easier (see Definition 3.6).
Let S๐ ( ๐ ) denote the bounded error unitary space complexity of ๐ , or the minimum space needed
by a unitary quantum algorithmโi. e., an algorithm that makes no measurements until the final
stepโthat computes ๐ with bounded error (see Definition 2.3). In [10] and [12], independently,
it was shown that S๐ ( ๐ ) = S( ๐ ) (up to constants), where S( ๐ ) denotes the bounded error space
complexity of ๐ , without the restriction to algorithms that are unitary. Our results are proven for
S๐ ( ๐ ), but the results of [10, 12] imply that they also apply to S( ๐ ). A similar statement is not
known for the one-sided error unitary quantum space complexity, S๐ 1
( ๐ ), though we suspect that
it also holds, and a proof of this would strengthen our results about S๐ 1
( ๐ ) to also hold for S1 ( ๐ ).
๐
For a function ๐ : {0, 1} โ {0, 1}, we can assume that the input is accessed by queries, so
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 2
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
that we do not need to store the full ๐-bit input in working memory, but we need at least log ๐
bits of memory to store an index into the input. Thus, a lower bound of ๐(log ๐) on S( ๐ ) for
some ๐ would be considered non-trivial.
Letting SP( ๐ ) denote the minimum size of a span program deciding ๐ , and SP f ( ๐ ) the
minimum size of a span program approximating ๐ (see Definition 3.7), we have the following
(see Theorem 4.1):
Theorem 1.1 (Informal). For any Boolean function ๐ , if S( ๐ ) denotes its bounded error quantum space
f ( ๐ ) its approximate span program size, then
complexity, and SP
S( ๐ ) โฅ log SP
f ( ๐ ).
Similarly, if S๐
1
( ๐ ) denotes its one-sided error unitary space complexity, and SP( ๐ ) its span program size,
then
1
S๐ ( ๐ ) โฅ log SP( ๐ ).
In the case of bounded (two-sided) error, this lower bound is tight in the following sense
(corollary of Theorem 3.1 and 3.2):
Theorem 1.2 (Informal). The class of languages decidable in bounded error by a quantum algorithm
with space ๐(๐) and 2๐(๐) queries1 is equal to the class of languages approximated by a span program of
size and complexity 2๐(๐) .
The relationship between span program size and quantum space complexity is rather natural,
as the span program size of ๐ is known to lower bound the minimum size of a symmetric
branching program for ๐ , and the logarithm of the branching program size of a function ๐
characterizes its classical deterministic space complexity.
The inequality S๐ 1
( ๐ ) โฅ log SP( ๐ ) in Theorem 1.1 follows from a construction of [27] for
converting a one-sided error quantum algorithm for ๐ into a span program for ๐ . We adapt this
construction to show how to convert a bounded (two-sided) error unitary quantum algorithm
for ๐ with query complexity ๐ and space complexity ๐ โฅ log ๐ into an approximate span
program for ๐ with complexity ฮ(๐) and size 2ฮ(๐) , proving S๐ ( ๐ ) โฅ ฮฉ(log SP f ( ๐ )), and thus
S( ๐ ) โฅ ฮฉ(log SP( ๐ )). The connection between S( ๐ ) and log SP( ๐ ) is tight up to an additive term
f f
of the logarithm of the minimum complexity of any span program for ๐ with optimal size,
yielding Theorem 1.2. This follows from the fact that an approximate span program can be
compiled into a quantum algorithm in a way that similarly preserves the correspondence between
space complexity and (logarithm of) span program size, as well as the correspondence between
query complexity and span program complexity (see Theorem 3.1). While the preservation of
1Depending on the precise model of computation, it is without loss of generality to assume that the space is at
least logarithmic in the number of queries. In our model of unitary quantum algorithms (see Section 2), this is a
reasonable assumption since we would need to use a counter of size at least logarithmic in the query complexity to
know which unitary to apply. In the case of a quantum Turing machine that halts absolutely, if there is ever a pair of
time steps ๐ก โ ๐ก 0 such that the state of the machine at step ๐ก and the state at step ๐ก 0 are non-orthogonal, then some
(exponentially decreasing) branch of the computation will run forever, which is a contradiction.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 3
S TACEY J EFFERY
the correspondence between query complexity and span program complexity (in both directions)
is not necessary for our results, it may be useful in future work for studying lower bounds on
time and space simultaneously.
The significance of Theorem 1.1 is that span program size has received extensive attention in
theoretical computer science. Using results from [5], the connection in Theorem 1.1 immediately
implies the following (Theorem 4.2):
Theorem 1.3. For almost all Boolean functions ๐ on ๐ bits, S๐
1
( ๐ ) = ฮฉ(๐).
If we make a uniformity assumption that the quantum space complexity of an algorithm is at
least the logarithm of its time complexity, then Theorem 1.3 would follow from a lower bound of
ฮฉ(2๐ ) on the quantum time complexity of almost all ๐-bit Boolean functions. Notwithstanding,
the proof via span program size is evidence of the power of the technique.
In the pursuit of lower bounds on span program size of explicit functions, several nice
expressions lower bounding SP( ๐ ) have been derived. By adapting one such lower bound on
SP( ๐ ) to SP
f ( ๐ ), we get the following (see Lemma 4.6):
Theorem 1.4 (Informal). For any Boolean function ๐ , and partial matrix2 ๐ โ (โ โช {โ
}) ๐
โ1 (0)ร ๐ โ1 (1)
with k๐ k โ โค 1: !!
1
-rank(๐)
S( ๐ ) โฅ ฮฉ log 2
,
max๐โ[๐] rank(๐ โฆ ฮ๐ )
where โฆ denotes the entrywise product, and ฮ๐ [๐ฅ, ๐ฆ] = 1 if ๐ฅ ๐ โ ๐ฆ ๐ and 0 else.
Above, 12 -rank denotes the approximate rank, or the minimum rank of any matrix ๐ e such
that |๐[๐ฅ, ๐ฆ] โ ๐[๐ฅ,
e ๐ฆ]| โค for each ๐ฅ, ๐ฆ such that ๐[๐ฅ, ๐ฆ] โ โ
. If we replace -rank(๐) with
1
2
1
2
rank(๐), we get the logarithm of an expression called the rank measure, introduced by Razborov
[25]. The rank measure was shown by Gร l to be a lower bound on span program size, SP [11],
and thus, our results imply that the log of the rank measure is a lower bound on S๐ 1
. It is
straightforward to extend this proof to the approximate case to get Theorem 1.4.
Theorem 1.4 seems to give some hope of proving a non-trivialโthat is, ๐(log ๐)โlower
bound on the quantum space complexity of some explicit ๐ , by exhibiting a matrix ๐ for which
the (approximate) rank measure is 2๐(log ๐) . In [25], Razborov showed that the rank measure is a
lower bound on the Boolean formula size of ๐ , motivating significant attempts to prove lower
bounds on the rank measure of explicit functions. The bad news is, circuit lower bounds have
been described as โComplexity theoryโs Waterlooโ [4]. Despite significant effort, no non-trivial
lower bound on span program size for any ๐ is known.
Due to the difficulty of proving explicit lower bounds on span program size, earlier work has
considered the easier problem of lower bounding monotone span program size, mSP( ๐ ). For a
monotone function ๐ , the monotone span program size of ๐ , mSP( ๐ ) is the minimum size of any
monotone span program for ๐ (see Definition 5.1). We can similarly define the approximate monotone
span program size of ๐ , mSP
f ( ๐ ) (see Definition 5.1). Although log mSP
f ( ๐ ) is not a lower bound
2Note that ๐ depends on ๐ in that it is indexed by the 0- and 1-inputs of ๐ .
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 4
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
on S( ๐ ), even for monotone ๐ , it is a lower bound on the space complexity of any algorithm
obtained by compiling a monotone span program. We show that such algorithms are equivalent
to a more natural class of algorithms called monotone phase estimation algorithms. Informally, a
phase estimation algorithm is an algorithm that works by performing phase estimation of some
unitary that makes one query to the input, and estimating the amplitude on a 0 in the phase
register (see Definition 5.12). Any quantum algorithm can be put into this form in a way that
preserves its space, query, and even time complexity. A monotone phase estimation algorithm
is a phase estimation algorithm where, loosely speaking, adding 0s to the input can only make
the algorithm more likely to reject (see Definition 5.13). This includes, for example, the phase
estimation variant of Groverโs algorithm. We can then prove the following (see Theorem 5.14):
Theorem 1.5 (Informal). For any Boolean function ๐ , any bounded error monotone phase estimation
algorithm for ๐ has space complexity at least log mSP f ( ๐ ), and any one-sided error monotone phase
estimation algorithm for ๐ has space complexity at least log mSP( ๐ ).
Fortunately, non-trivial lower bounds for the monotone span program complexity are
known for explicit functions. In Ref. [5], Babai, Gร l and Wigderson showed a lower bound
of mSP( ๐ ) โฅ 2ฮฉ(log (๐)/log log(๐)) for some explicit function ๐ , which was later improved to
2
๐
mSP( ๐ ) โฅ 2ฮฉ(log (๐)) by Gร l [11]. In Ref. [29], a function ๐ was exhibited with mSP( ๐ ) โฅ 2๐
2
for some constant ๐ โ (0, 1), and in the strongest known result, Pitassi and Robere exhibited a
function ๐ with mSP( ๐ ) โฅ 2ฮฉ(๐) [24]. Combined with our results, each of these implies a lower
bound on the space complexity of one-sided error monotone phase estimation algorithms. For
example, the result of [24] implies a lower bound of ฮฉ(๐) on the space complexity of one-sided
error monotone phase estimation algorithms for a certain satisfiability problem ๐ . This lower
bound, and also the one in [29], are proven by choosing ๐ based on a constraint satisfaction
problem with high refutation width, which is a measure related to the space complexity of certain
classes of SAT solvers, so it is intuitively not surprising that these problems should require a
large amount of space to solve with one-sided error.
For the case of bounded error space complexity, we also prove the following (see Theorem 5.3,
Corollary 5.15):
Theorem 1.6 (Informal). There exists a function ๐ : {0, 1} ๐ โ {0, 1} such that any bounded error
monotone phase estimation algorithm for ๐ has space complexity (log ๐)2โ๐(1) .
This lower bound is non-trivial, although much less so than the best known lower bound
of ฮฉ(๐) for the one-sided case. The approximate monotone span program lower bound
from which Theorem 1.6 follows also implies a new lower bound of 2(log ๐)
2โ๐(1)
on the (non-
approximate) monotone span program size of the function ๐ in Theorem 1.6 (although, as
previously mentioned, there are much better lower bounds for monotone span program size of
other explicit functions).
To prove the lower bound in Theorem 1.6, we apply a new technique that leverages the
best possible gap between the certificate complexity and approximate polynomial degree of a
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 5
S TACEY J EFFERY
function, employing a function ๐ : {0, 1} ๐
2+๐(1)
โ {0, 1} from [8],3 whose certificate complexity
is ๐ 1+๐(1) , and whose approximate degree is ๐ 2โ๐(1) . Following a strategy of [29], we use this ๐
to construct a pattern matrix [30] (see Definition 5.8) and use this matrix in a monotone version
of Theorem 1.4 (see Theorem 5.4). The fact that certificate complexity and approximate degree
g (๐) โค ๐ถ(๐)2 for all ๐ is a barrier to proving a lower bound
of total functions are related by deg 1/3
better than (log ๐)2 using this technique, but we also give a generalization that has the potential
to prove significantly better lower bounds (see Lemma 5.11).
Discussion and open problems The most conspicuous open problem of this work is to prove
a lower bound of ๐(log ๐) on S( ๐ ) or even S๐ 1
( ๐ ) for some explicit decision function ๐ . It is
known that any space ๐ quantum Turing machine can be simulated by a deterministic classical
algorithm in space ๐ 2 [31], so a lower bound of ๐(log2 ๐) on classical space complexity would
also give a non-trivial lower bound on quantum space complexity. If anything, the relationship
to span program size is evidence that this task is extremely difficult.
We have shown a lower bound of 2(log ๐)
2โ๐(1)
on the approximate monotone span program
complexity of an explicit monotone function ๐ , which gives a lower bound of (log ๐)2โ๐(1) on
the bounded error space complexity needed by a quantum algorithm of a very specific form: a
monotone phase estimation algorithm. This is much worse than the best bound we can get in
the one-sided case: a lower bound of ฮฉ(๐) for some explicit function. An obvious open problem
is to try to get a better lower bound on the approximate monotone span program complexity of
some explicit function.
Our lower bound of (log ๐)2โ๐(1) only applies to the space complexity of monotone phase
estimation algorithms and does not preclude the existence of a more space-efficient algorithm
of a different form for ๐ . We do know that phase estimation algorithms are fully general, in
the sense that every function has a space-optimal phase estimation algorithm. Does something
similar hold for monotone functions and monotone phase estimation algorithms? This would
imply that log mSP f ( ๐ ) is a lower bound on S( ๐ ) for all monotone functions ๐ .
In this paper, we define an approximate version of the rank method, and monotone rank
method, and in case of the monotone rank method, give an explicit non-trivial lower bound. The
rank method is known to give lower bounds on formula size, and the monotone rank method
on monotone formula size. An interesting question is whether the approximate rank method
also gives lower bounds on some complexity theoretic quantity related to (classical) formulas.
Our results are a modest first step towards understanding unitary quantum space complexity,
but even if we could lower bound the unitary quantum space complexity of an explicit function,
there are several obstacles limiting the practical consequences of such a result. First, while an
early quantum computer will have a small quantum memory, it is simple to augment it with
a much larger classical memory. Thus, in order to achieve results with practical implications,
we would need to study computational models that make a distinction between quantum and
classical memories. We leave this as an important challenge for future work.
3An earlier version of this paper used a function described in [1] with a 7/6-separation between certificate
complexity and approximate degree. We thank Robin Kothari for pointing us to the improved result of [8].
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 6
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Second, we are generally only interested in running quantum algorithms when we get an
advantage over classical computers in the time complexity, so results that give a lower bound on
the quantum space required if we wish to keep the time complexity small, such as time-space
lower bounds, are especially interesting. While we do not address time-space lower bounds in
this paper, one advantage of the proposed quantum space lower bound technique, via span
programs, is that span programs are also known to characterize quantum query complexity,
which is a lower bound on time complexity. We leave exploration of this connection for future
work.
We mention two previous characterizations of S( ๐ ). Ref. [19] showed that S( ๐ ) is equal to
the logarithm of the minimum width of a matchgate circuit computing ๐ , and thus our results
imply that this minimum matchgate width is approximately equal to the approximate span
program size of ๐ . Separately, in Ref. [9], Fefferman and Lin showed that for every function
๐, inverting 2 ๐(๐) ร 2 ๐(๐) matrices is complete for the class of problems ๐ such that S( ๐ ) โค ๐(๐).
Our results imply that evaluating an approximate span program of size 2 ๐(๐) (for some suitable
definition of the problem) is similarly complete for this class. Evaluating an approximate span
program boils down to deciding if k๐ด(๐ฅ)+ |๐ค0 ik, for some matrix ๐ด(๐ฅ) partially determined by
the input ๐ฅ, and some initial state |๐ค 0 i, is below a certain threshold, so these results are not
unrelated.4 We leave exploring these connections as future work.
Organization The remainder of this paper is organized as follows. In Section 2, we present
the necessary notation and quantum algorithmic preliminaries, and define quantum space
complexity. In Section 3, we define span programs, and describe how they correspond to
quantum algorithms. In particular, we describe how a span program can be โcompiledโ into
a quantum algorithm (Section 3.2), and how a quantum algorithm can be turned into a span
program (Section 3.3), with both transformations more or less preserving the relationships
between span program size and algorithmic space, and between span program complexity and
query complexity. From this correspondence, we obtain, in Section 4, expressions that lower
bound the quantum space complexity of a function. While we do not know how to instantiate
any of these expressions to get a non-trivial lower bound for an explicit function, in Section 5, we
consider to what extent monotone span program lower bounds are meaningful lower bounds
on variants of quantum space complexity, and give the first non-trivial lower bound on the
approximate monotone span program size of a function.
2 Preliminaries
We begin with some miscellaneous notation. For a vector |๐ฃi, we let k|๐ฃik denote its โ2 -norm. In
the following, let ๐ด be a matrix with ๐ and ๐ indexing its rows and columns. Define:
k๐ดk โ = max |๐ด ๐,๐ |, and k๐ดk = max{k๐ด|๐ฃik : k|๐ฃik = 1}.
๐,๐
4Here, ๐ด(๐ฅ) = ๐ดฮ ๐ป(๐ฅ) , where ๐ด is as in Definition 3.3, |๐ค 0 i = ๐ด+ |๐i for |๐i as in Definition 3.3, and ๐ป(๐ฅ) is as
in Definition 3.4. ๐ด(๐ฅ)+ denotes the pseudo-inverse of ๐ด(๐ฅ). Then one can verify that ๐ค + (๐ฅ) = k๐ด(๐ฅ)+ |๐ค 0 ik 2 (see
Definition 3.4).
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 7
S TACEY J EFFERY
Following [2], define the ๐-rank of a matrix ๐ด as the minimum rank of any matrix ๐ต such that
k๐ด โ ๐ตk โ โค ๐. For a matrix ๐ด with singular value decomposition ๐ด = ๐ ๐ ๐ |๐ฃ ๐ ih๐ข ๐ |, where we
ร
assume โ๐, ๐ ๐ > 0, define:
ร 1
col(๐ด) = span{|๐ฃ ๐ i} ๐ , row(๐ด) = span{|๐ข ๐ i} ๐ , ker(๐ด) = row(๐ด)โฅ , ๐ด+ = |๐ข ๐ ih๐ฃ ๐ |.
๐๐
๐
The following lemma, from [22], is useful in the analysis of quantum algorithms.
Lemma 2.1 (Effective spectral gap lemma). Fix orthogonal projectors ฮ ๐ด and ฮ ๐ต . Let ๐ =
(2ฮ ๐ด โ ๐ผ)(2ฮ ๐ต โ ๐ผ), and let ฮ ฮ be the orthogonal projector onto the e๐๐ -eigenspaces of ๐ such that
|๐| โค ฮ. Then if ฮ ๐ด |๐ขi = 0, then kฮ ฮ ฮ ๐ต |๐ขik โค ฮ2 k|๐ขik.
In general, we will let ฮ ๐ denote the orthogonal projector onto ๐, for a subspace ๐.
Unitary quantum algorithms and space complexity A unitary quantum algorithm ๐ = {๐ ๐ } ๐โโ
(๐) (๐)
is a family (parametrized by ๐) of sequences of 2๐ (๐) -dimensional unitaries ๐1 , . . . , ๐๐(๐) , for
some ๐ (๐) โฅ log ๐ and ๐(๐). (We will generally dispense with the explicit parametrization by ๐).
For ๐ฅ โ {0, 1} ๐ , let ๐ช๐ฅ be the unitary that acts as ๐ช๐ฅ | ๐i = (โ1)๐ฅ ๐ | ๐i for ๐ โ [๐], and ๐ช๐ฅ |0i = |0i.
We let ๐(๐ฅ) denote the random variable obtained from measuring
๐๐ ๐ช๐ฅ ๐๐โ1 . . . ๐ช๐ฅ ๐1 |0i
with some two-outcome measurement that should be clear from context. We call ๐(๐) the
query complexity of the algorithm, and ๐(๐) = ๐ (๐) + log ๐(๐) the space complexity. By including
a log ๐(๐) term in the space complexity, we are implicitly assuming that the algorithm must
maintain a counter to know which unitary to apply next. This is a fairly mild uniformity
assumption (that is, any uniformly generated algorithm uses ฮฉ(log ๐) space), and it will make
the statement of our results much simpler. The requirement that ๐ (๐) โฅ log ๐ is to ensure that
the algorithm has enough space to store an index ๐ โ [๐] into the input.
Remark 2.2. Since ๐ is the number of queries made by the algorithm, we may be tempted to
assume that it is at most ๐, however, while every ๐-bit function can be computed in ๐ queries,
this may not be the case when space is restricted. For example, it is difficult to imagine an
algorithm that uses ๐(log ๐) space and ๐(๐ 3/2 ) quantum queries to solve the following problem
on [๐]๐ โก {0, 1} ๐ log ๐ : Decide whether there exist distinct ๐, ๐, ๐ โ [๐] such that ๐ฅ ๐ + ๐ฅ ๐ + ๐ฅ ๐ = 0
mod ๐.
For a (partial) function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ , we say that ๐ computes ๐ with
bounded error if for all ๐ฅ โ ๐ท, ๐(๐ฅ) = ๐ (๐ฅ) with probability at least 2/3. We say that ๐
computes ๐ with one-sided error if in addition, for all ๐ฅ such that ๐ (๐ฅ) = 1, ๐(๐ฅ) = ๐ (๐ฅ) with
probability 1.
Definition 2.3 (Unitary Quantum Space). For a family of functions ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ ,
the unitary space complexity of ๐ , S๐ ( ๐ ), is the minimum ๐(๐) such that there is a family of
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 8
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
unitary quantum algorithms with space complexity ๐(๐) that computes ๐ with bounded error.
Similarly, S๐
1
( ๐ ) is the minimum ๐(๐) such that there is a family of unitary quantum algorithms
with space complexity ๐(๐) that computes ๐ with one-sided error.
In general, quantum algorithms need not be of the strict unitary form described above, as a
quantum computer is not restricted to only measure at the end of the algorithm. If one only cares
about time complexity, then it is without loss of generality to assume that all measurements
happen in the final step of the algorithm, because one can simply set aside any register that
is to be measured, to be used as a โread-onlyโ register (that is, strictly as a control) for the
remainder of the computation. However, it is not obvious that this would not increase the space
complexity, since any register that should have been measured is not available for re-use. It
was recently shown that, in fact, even for space complexity, there is no loss of generality in
considering unitary quantum algorithms [10, 12]; if we let S( ๐ ) denote the minimum space
complexity of any quantum algorithm that computes ๐ with bounded error, S( ๐ ) = S๐ ( ๐ ). Thus,
we can restrict our attention to unitary quantum algorithms for the remainder of this article but
all of our results in the bounded error setting also hold for non-unitary algorithms [10, 12]. At
the time of writing, there is no analogous result for S๐
1
( ๐ ), but we suspect it holds along similar
lines.
Phase estimation For a unitary ๐ acting on ๐ป and a state |๐i โ ๐ป, we will say we perform ๐
steps of phase estimation of ๐ on |๐i when we compute
๐โ1
1 ร
โ |๐กi๐ ๐ก |๐i,
๐ ๐ก=0
and then perform a quantum Fourier transform over โค/๐ โค on the first register, called the phase
register. This procedure was introduced in [21]. It is easy to see that the complexity (either query
or time) of phase estimation is ๐(๐) times the complexity of implementing a controlled call to
๐. The space complexity of phase estimation is log ๐ + log dim(๐ป).
Informally: we will use the fact that if ๐ |๐i = |๐i, then performing ๐ steps of phase
estimation of ๐ on |๐i and measuring the phase register results in outcome 0 with probability
1; and if ๐ |๐i = e๐๐ |๐i for some ๐ โ (โ๐, ๐] with |๐| > 0, then performing sufficiently large
๐ = ฮฉ(1/|๐|) steps of phase estimation results in outcome 0 with probability bounded by a
constant below 1. Formally: for the results in Section 3.2, we refer to the proof of [15, Lemma
3.2] where formal results about phase estimation are exploited; for the results in Section 5.2,
we prove the specific properties of phase estimation needed for our purposes in Lemma 5.18
and 5.19.
We note that we can increase the success probability to any constant by adding some constant
number ๐ of phase registers, and doing phase estimation ๐ times in parallel, still using a single
register for ๐, and taking the majority. This still has space complexity log dim ๐ป + ๐(log ๐).
Amplitude estimation For a unitary ๐ acting on ๐ป, a state |๐i โ ๐ป, and an orthogonal
projector ฮ on ๐ป, we will say we perform ๐ steps of amplitude estimation of ๐ on |๐i with respect
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 9
S TACEY J EFFERY
to ฮ when we perform ๐ steps of phase estimation of
๐(2|๐ih๐| โ ๐ผ)๐ โ (2ฮ โ ๐ผ)
๐๐ก
on ๐ |๐i, then, if the phase register contains some ๐ก โ {0, . . . , ๐ โ 1}, compute ๐ห = sin2 2๐ ,
2
which is an estimate of kฮ ๐ |๐ik in a new register. The (time or query) complexity of this is
๐(๐) times the complexity of implementing a controlled call to ๐, implementing a controlled
call to 2ฮ โ ๐ผ, and generating |๐i. The space complexity is log ๐ + log dim ๐ป + ๐(1). We have
the following guarantee [7]:
Lemma 2.4. Let ๐ = kฮ ๐ |๐ik 2 . There exists ฮ = ฮ(1/๐) such that when ๐ห is obtained as above from
๐ steps of amplitude estimation, with probability at least 1/2, | ๐ห โ ๐| โค ฮ.
We will thus also refer to ๐ steps of amplitude estimation as amplitude estimation to precision 1/๐.
3 Span programs and quantum algorithms
In Section 3.1, we will define a span program, its size and complexity, and what it means for a
span program to approximate a function ๐ . In Section 3.2, we will prove the following, which
implies that the first part of Theorem 1.1 is essentially tight.
Theorem 3.1. Let ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ , and let ๐ be a span program that ๐
-approximates
๐ with size ๐พ and complexity ๐ถ, for some constant ๐
โ (0, 1). Then there exists a unitary quantum
algorithm ๐ ๐ that decides ๐ with bounded error in space ๐ = ๐(log ๐พ + log ๐ถ) using ๐ = ๐(๐ถ) queries
to ๐ฅ.
Finally, in Section 3.3, we prove the following theorem, which implies Theorem 1.1:
Theorem 3.2. Let ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ and let ๐ be a unitary quantum algorithm using ๐
queries, and space ๐ to compute ๐ with bounded error. Then for any constant ๐
โ (0, 1), there is a span
program ๐๐ with size ๐ (๐๐ ) โค 2๐(๐) that ๐
-approximates ๐ with complexity ๐ถ๐
โค ๐(๐). If ๐ decides
๐ with one-sided error, then ๐๐ decides ๐ .
A statement similar to Theorem 3.1 for the case of exact (๐
= 1) span programs5 was proven in
[27]. Later this was generalized to the case of approximate span program [15], but a slightly more
constrained notion of approximation was used, which would not allow us to prove Theorem 3.2.
Neither of these works explicitly mentioned space complexity, although the analysis of the space
complexity follows easily.
Theorem 3.2 is proven by exhibiting a construction that maps a bounded-error quantum
algorithm for ๐ to a span program that approximates it. This is based on a similar construction
in [27] that maps a one-sided error quantum algorithm for ๐ to a span program that decides
it exactly. Interestingly, the fact that span program complexity is a lower bound on query
complexity was known even without a mapping from bounded-error quantum algorithms to
5See Section 3.1 for definitions of exact and approximate span programs.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 10
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
span programs. This was proven by showing [27] that the semidefinite minimization problem
whose solution is the minimum span program complexity of a span program that decides ๐ is
the dual of a semidefinite program that was known to be a lower bound on quantum query
complexity [3, 6, 14].
3.1 Span programs
Span programs were first introduced in the context of classical complexity theory in [20], where
they were used to study counting classes for nondeterministic logspace machines. While span
programs can be defined with respect to any field, we will consider span programs over โ (or
equivalently, โ, when convenient, see Remark 3.10). We use the following definition, slightly
modified from [20]:
Definition 3.3 (Span Program and Size). A span program on {0, 1} ๐ consists of:
โข Finite inner product spaces {๐ป ๐,๐ } ๐โ[๐],๐โ{0,1} โช {๐ปtrue , ๐ปfalse }. We define ๐ป = ๐,๐ ๐ป ๐,๐ โ
ร
๐ปtrue โ ๐ปfalse , and for every ๐ฅ โ {0, 1} ๐ , ๐ป(๐ฅ) = ๐ป1,๐ฅ1 โ ยท ยท ยท โ ๐ป๐,๐ฅ ๐ โ ๐ปtrue .6
โข A vector space ๐.
โข A target vector |๐i โ ๐.7
โข A linear map ๐ด : ๐ป โ ๐.
We specify this span program by ๐ = (๐ป, ๐ , |๐i, ๐ด), and leave the decomposition of ๐ป implicit.
The size of the span program is ๐ (๐) = dim ๐ป.
To recover the classical definition from [20], we can view ๐ด as a matrix, with each of its
columns labelled by some (๐, ๐) โ [๐] ร {0, 1} (or โtrueโ or โfalseโ).
Span programs were introduced to the study of quantum query complexity in [28]. In the
context of quantum query complexity, ๐ (๐) is no longer the relevant measure of the complexity
of a span program. Instead, [28] introduce the following measures:
Definition 3.4 (Span Program Complexity and Witnesses). For a span program ๐ = (๐ป, ๐ , |๐i, ๐ด)
on {0, 1} ๐ and input ๐ฅ โ {0, 1} ๐ , we say ๐ฅ is accepted by the span program if there exists |๐คi โ ๐ป(๐ฅ)
such that ๐ด|๐คi = |๐i, and otherwise we say ๐ฅ is rejected by the span program. Let ๐0 and ๐1 be
respectively the set of rejected and accepted inputs to ๐. For ๐ฅ โ ๐1 , define the positive witness
complexity of ๐ฅ as:
๐ค + (๐ฅ, ๐) = ๐ค+ (๐ฅ) = min{k|๐คik 2 : |๐คi โ ๐ป(๐ฅ), ๐ด|๐คi = |๐i}.
6We remark that while ๐ปtrue and ๐ปfalse may be convenient in constructing a span program, they are not necessary.
We can always consider a partial function ๐ 0 defined on (๐ + 1)-bit strings of the form (๐ฅ, 1) for ๐ฅ in the domain of ๐ ,
as ๐ (๐ฅ), and let ๐ป๐+1,1 = ๐ปtrue and ๐ป๐+1,0 = ๐ปfalse .
7Although ๐ has no meaningful inner product, we use Dirac notation, such as |๐i and h๐| for the sake of our
fellow quantum computing researchers.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 11
S TACEY J EFFERY
Such a |๐คi is called a positive witness for ๐ฅ. For a domain ๐ท โ {0, 1} ๐ , we define the positive
complexity of ๐ (with respect to ๐ท) as:
๐+ (๐, ๐ท) = ๐+ = max ๐ค + (๐ฅ, ๐).
๐ฅโ๐1 โฉ๐ท
For ๐ฅ โ ๐0 , define the negative witness complexity of ๐ฅ as:
๐ค โ (๐ฅ, ๐) = ๐ค โ (๐ฅ) = min{kh๐|๐ดk 2 : h๐| โ โ(๐ , โ), h๐|๐i = 1, h๐|๐ดฮ ๐ป(๐ฅ) = 0}.
Above, โ(๐ , โ) denotes the set of linear functions from ๐ to โ. Such an h๐| is called a negative
witness for ๐ฅ. We define the negative complexity of ๐ (with respect to ๐ท) as:
๐โ (๐, ๐ท) = ๐โ = max ๐คโ (๐ฅ, ๐).
๐ฅโ๐0 โฉ๐ท
โ
Finally, we define the complexity of ๐ (with respect to ๐ท) by ๐ถ(๐, ๐ท) = ๐+๐โ .
For ๐ : ๐ท โ {0, 1}, we say a span program ๐ decides ๐ if ๐ โ1 (0) โ ๐0 and ๐ โ1 (1) โ ๐1 .
Definition 3.5. We define the span program size of a function ๐ , denoted SP( ๐ ), as the minimum
๐ (๐) over families of span programs that decide ๐ .
We note that originally, in [20], span program size was defined
ร ร
๐ 0(๐) = dim(col(๐ดฮ ๐ป ๐,๐ )) = dim(row(๐ดฮ ๐ป ๐,๐ )).
๐,๐ ๐,๐
This could differ from ๐ (๐) = dim(๐ป) = ๐,๐ dim(๐ป ๐,๐ ), because dim(๐ป ๐,๐ ) might be much larger
ร
than dim(row(๐ดฮ ๐ป ๐,๐ )). However, if a span program has dim(๐ป ๐,๐ ) > dim(row(๐ดฮ ๐ป ๐,๐ )) for
some ๐, ๐, then it is a simple exercise to show that the dimension of dim(๐ป ๐,๐ ) can be reduced
without altering the witness size of any ๐ฅ โ {0, 1} ๐ , so the definition of SP( ๐ ) is the same as
if we had used ๐ 0(๐) instead of ๐ (๐). In any case, we will not be relying on previous results
about the span program size as a black-box, and will rather prove all required statements, so
this difference has no impact on our results.
While span program size has only previously been relevant outside the realm of quantum
algorithms, the complexity of a span program deciding ๐ has a fundamental correspondence
with the quantum query complexity of ๐ . Specifically, a span program ๐ can be turned into a
quantum algorithm for ๐ with query complexity ๐ถ(๐, ๐ท), and moreover, for every ๐ , there exists
a span program such that the algorithm constructed in this way is optimal [27]. This second
direction is not constructive: there is no known method for converting a quantum algorithm with
query complexity ๐ to a span program with complexity ๐ถ(๐, ๐ท) = ฮ(๐). However, if we relax
the definition of which functions are decided by a span program, then such a construction is
possible, as we will show in Section 3.3. The following is a slight relaxation of [15, Definition 2.6].8
8Which was already a relaxation of the notion of a span program deciding a function.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 12
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Definition 3.6 (A Span Program that Approximately Decides a Function). Let ๐ : ๐ท โ {0, 1}
for ๐ท โ {0, 1} ๐ and ๐
โ (0, 1). We say that a span program ๐ on {0, 1} ๐ ๐
-approximates ๐ if
๐ โ1 (0) โ ๐0 , and for every ๐ฅ โ ๐ โ1 (1), there exists an approximate positive witness | ๐คi
ห such that
๐
๐ด| ๐คi
ห = |๐i, and ฮ ๐ป(๐ฅ)โฅ | ๐คi
2
ห โค ๐โ . We define the approximate positive complexity as
๐
๐
๐+ = ๐+ (๐, ๐ท) = max min k| ๐คik : ๐ด| ๐คi
ห = |๐i, ฮ ๐ป(๐ฅ)โฅ | ๐คi .
2 2
b b ห ห โค
๐ฅโ ๐ โ1 (1) ๐โ
q
If ๐ ๐
-approximates ๐ , we define the complexity of ๐ (wrt. ๐ท and ๐
) as ๐ถ๐
(๐, ๐ท) = ๐
b+๐โ .
If ๐
= 0, the span program in Definition 3.6 decides ๐ (exactly), and ๐
b+ = ๐+ . By [15,
Theorem 2.10], for any ๐ฅ,
n o 1
ฮ ๐ป(๐ฅ)โฅ | ๐คi : ๐ด| ๐คi .
2
min ห ห = |๐i =
๐คโ (๐ฅ)
Thus, since ๐โ = max๐ฅโ ๐ โ1 (0) ๐ค โ (๐ฅ), for every ๐ฅ โ ๐ โ1 (0), there does not exist an approximate
positive witness with ฮ ๐ป(๐ฅ)โฅ | ๐คi < ๐1โ . Thus, when a span program ๐
-approximates ๐ , there
2
ห
๐โ between the smallest positive witness error ฮ ๐ป(๐ฅ) | ๐คi of ๐ฅ โ ๐ โ1 (1), the
2
is a gap of size 1โ๐
โฅ ห
smallest positive witness error of ๐ฅ โ ๐ (0).
โ1
Definition 3.7. We define the ๐
-approximate span program size of a function ๐ , denoted SPf ๐
( ๐ ), as
the minimum ๐ (๐) over families of span programs that ๐
-approximate ๐ . We let SP f ( ๐ ) = SP
f 1/4 ( ๐ ).
We note that the choice of ๐
= 1/4 in SPf ( ๐ ) is arbitrary, as it is possible to modify a span
program to reduce any constant ๐
to any other constant without changing the complexity or the
logarithm of the size asymptotically. This convenient observation is formalized in the following
claim.
Claim 3.8. Let ๐ be a span program that ๐
-approximates ๐ : ๐ท โ {0, 1} for some constant ๐
. For any
constant ๐
0 โค ๐
, there exists a span program ๐ 0 that ๐
0-approximates ๐ with
log(1/๐
0 )
๐ (๐ 0) = (๐ (๐) + 2) log(1/๐
) ,
2
(3.1)
and ๐ถ๐
0 (๐ 0 , ๐ท) โค ๐ (๐ถ๐
(๐, ๐ท)).
We prove Claim 3.8 shortly in Section 3.1.1. We have the following corollary that will be
f ๐
is the monotone approximate span program size, defined in Definition 5.1:
useful later, where mSP
Corollary 3.9. For any ๐
, ๐
0 โ (0, 1) with ๐
0 < ๐
, and any Boolean function ๐ ,
1 log(1/๐
)
f ๐
( ๐ ) โฅ SP
SP f ๐
0 ( ๐ ) 2 log(1/๐
0) โ 2.
If ๐ is monotone, we also have
1 log(1/๐
)
f ๐
( ๐ ) โฅ mSP
mSP f ๐
0 ( ๐ ) 2 log(1/๐
0) โ 2.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 13
S TACEY J EFFERY
Remark 3.10. It can sometimes be useful to construct a span program over โ. However, for
any span program over โ, ๐, there is a span program over โ, ๐ 0, such that for all ๐ฅ โ ๐0 ,
๐ค โ (๐ฅ, ๐ 0) โค ๐คโ (๐ฅ, ๐), for all ๐ฅ โ ๐1 , ๐ค + (๐ฅ, ๐ 0) โค ๐ค + (๐ฅ, ๐), and ๐ (๐ 0) โค 2๐ (๐). We define ๐ 0
as follows. Without loss of generality, suppose ๐ป ๐,๐ = spanโ {| ๐, ๐, ๐i : ๐ โ ๐ ๐,๐ }. Define
๐ป 0๐,๐ = spanโ {| ๐, ๐, ๐, ๐i : ๐ โ ๐ ๐,๐ , ๐ โ {0, 1}}. Define
๐ด0 | ๐, ๐, ๐, 0i = Re (๐ด| ๐, ๐, ๐i) |0i + Im (๐ด| ๐, ๐, ๐i) |1i
๐ด0 | ๐, ๐, ๐, 1i = Re (๐ด| ๐, ๐, ๐i) |1i โ Im (๐ด| ๐, ๐, ๐i) |0i.
Finally, let |๐0i = |๐i|0i.
Suppose |๐คi is a witness in ๐. Then
|๐i = ๐ด|๐คi = ๐ดRe(|๐คi) + ๐๐ดIm(|๐คi)
= Re(๐ดRe(|๐คi)) + ๐Im(๐ดRe(|๐คi)) + ๐Re(๐ดIm(|๐คi)) โ Im(๐ดIm(|๐คi)).
Since we can assume |๐i is real, we have
|๐i = Re(๐ดRe(|๐คi)) โ Im(๐ดIm(|๐คi)) and Im(๐ดRe(|๐คi)) + Re(๐ดIm(|๐คi)) = 0.
Define |๐ค 0i = Re(|๐คi)|0i + Im(|๐คi)|1i. Then
๐ด0 |๐ค 0i = Re(๐ดRe(|๐คi))|0i+Im(๐ดRe(|๐คi))|1i+Re(๐ดIm(|๐คi))|1iโIm(๐ดIm(|๐คi))|0i = |๐i|0i = |๐0i.
Note that we have k|๐คik = k|๐ค 0ik. A similar argument holds for negative witnesses.
Thus, we will restrict our attention to real span programs, but still allow constructions of
span programs over โ (in particular, in Section 3.3 and Section 5.2.1).
3.1.1 Proof of Claim 3.8
In this section, we prove Claim 3.8. The proof is somewhat technical, and may be skipped
without compromising the readerโs understanding of the remainder of the paper. We restate
Claim 3.8 below.
Claim 3.8. Let ๐ be a span program that ๐
-approximates ๐ : ๐ท โ {0, 1} for some constant
๐
. For any constant ๐
0 โค ๐
, there exists a span program ๐ 0 that ๐
0-approximates ๐ with
log(1/๐
0 )
๐ (๐ 0) = (๐ (๐) + 2) log(1/๐
) , and ๐ถ๐
0 (๐ 0 , ๐ท) โค ๐ (๐ถ๐
(๐, ๐ท)).
2
Let |๐ค0 i = ๐ด+ |๐i. We say a span program is normalized if k|๐ค 0 ik = 1. A span program can
easily be normalized by scaling |๐i, which also scales all positive witnesses and inverse scales
all negative witnesses. However, we sometimes want to normalize a span program, while also
keeping all negative witness sizes bounded by a constant. We can accomplish this using the
following construction, from [15].
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 14
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Theorem 3.11. Let ๐ = (๐ป, ๐ , |๐i, ๐ด) be a span program on {0, 1} ๐ , and let ๐ = k|๐ค0 ik 2 . For a
positive real number ๐ฝ, define a span program ๐ ๐ฝ = (๐ป ๐ฝ , ๐ ๐ฝ , |๐๐ฝ i, ๐ด๐ฝ ) as follows, where | 0i
ห and | 1i
ห are
not in ๐ป or ๐:
๐ฝ ๐ฝ ห ๐ฝ ห
๐ป ๐,๐ = ๐ป ๐,๐ , ๐ปtrue = ๐ปtrue โ span{| 1i}, ๐ปfalse = ๐ปfalse โ span{| 0i}
p
๐ฝ ๐ฝ ๐ฝ2 + ๐
ห
๐ = ๐ โ span{| 1i}, ห +
๐ด = ๐ฝ๐ด + |๐ih0| | 1ih ห |๐๐ฝ i = |๐i + | 1i.
ห 1|, ห
๐ฝ
Then we have the following:
โข (๐ด๐ฝ )+ |๐๐ฝ i = 1;
โข for all ๐ฅ โ ๐1 , ๐ค + (๐ฅ, ๐ ๐ฝ ) = ๐ฝ12 ๐ค + (๐ฅ, ๐) + 2;
โข for all ๐ฅ โ ๐0 , ๐ค โ (๐ฅ, ๐ ๐ฝ ) = ๐ฝ 2 ๐ค โ (๐ฅ, ๐) + 1.
Corollary 3.12. Let ๐ be a span program on {0, 1} ๐ , and ๐ ๐ฝ be defined as above for ๐ฝ = โ 1 . If ๐
๐โ (๐)
๐ฝ
โ ๐ฝ ๐ฝ
๐
-approximates ๐ , then ๐ ๐
-approximates ๐ , with ๐โ (๐ ) โค 2, ๐+ (๐ ) โค ๐โ (๐)๐+ (๐) + 2 and
b b
๐ฝ
๐ (๐ ) โค ๐ (๐) + 2.
Proof. First note that by Theorem 3.11, ๐โ (๐ ๐ฝ ) โค 2. Let |๐คi be an approximate positive witness
for ๐ฅ in ๐, with ฮ ๐ป(๐ฅ)โฅ |๐คi โค ๐โ๐
(๐) and k|๐คik 2 โค ๐
2
b+ (๐). Define
๐ฝ
|๐ค 0i =
1
|๐คi + p ห + ๐
| 0i.
| 1i ห
๐ฝ(1 + ๐
) ๐ฝ +๐
2 1+๐
One can check that ๐ด๐ฝ |๐ค 0i = |๐๐ฝ i.
1 ๐
2 1 ๐
๐
2
ฮ ๐ป ๐ฝ (๐ฅ)โฅ |๐ค 0i
2 2
= ฮ ๐ป(๐ฅ) โฅ |๐คi + โค +
๐ฝ 2 (1 + ๐
)2 (1 + ๐
)2 ๐ฝ 2 (1 + ๐
)2 ๐โ (๐) (1 + ๐
)2
โ
๐
+ ๐
2 2๐
(1 + ๐
) 1 2๐
๐
= โค = โค ,
(1 + ๐
) 2 ๐ฝ
๐โ (๐ )(1 + ๐
) 2 ๐โ (๐ ) 1 + ๐
๐ฝ ๐โ (๐ ๐ฝ )
where we have used ๐โ (๐ ๐ฝ ) โค 2. We upper bound ๐
b+ (๐ ๐ฝ ) by noting that:
b+ (๐) + ๐ฝ ๐
2
2
1
k|๐ค 0ik 2 โค ๐ +
๐ฝ2 (1 + ๐
)2 ๐ฝ2 + ๐ (1 + ๐
)2
โค ๐โ (๐)๐
b+ (๐) + 2.
Finally, ๐ (๐ ๐ฝ ) = ๐ (๐) + 2 because of the two extra degrees of freedom | 0i
ห and | 1i.
ห
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 15
S TACEY J EFFERY
Proof of Claim 3.8. We will first show how, given a span program ๐ such that k|๐ค0 ik 2 โค 1, and ๐
๐
-approximates ๐ , we can get a span program ๐ 0 such that |๐ค 00 i โค 1, ๐โ (๐ 0) โค ๐โ (๐)2 , ๐ 0
2
๐
2 -approximates ๐ , ๐
b+ (๐ 0) โค 4๐
b+ (๐), and ๐ (๐ 0) = ๐ (๐)2 .
Define ๐ as follows, where ๐ is a swap operator, which acts as ๐(|๐ขi|๐ฃi) = |๐ฃi|๐ขi for all
0
|๐ขi, |๐ฃi โ ๐ป:
๐ผ๐ปโ๐ป + ๐
๐ป 0๐,๐ = ๐ป ๐,๐ โ ๐ป, 0
๐ด = (๐ด โ ๐ด) , |๐0i = |๐i|๐i.
2
Observe that for any |๐ขi, |๐ฃi โ ๐ป, we have
๐ด0(|๐ขi|๐ฃi โ |๐ฃi|๐ขi) = 0, and ๐ด0 |๐ขi|๐ขi = ๐ด|๐ขi โ ๐ด|๐ขi.
Note that ๐ด0(|๐ค0 i|๐ค 0 i) = |๐0i, so ๐ด0+ |๐0i โค k|๐ค 0 i|๐ค 0 ik โค 1.
If h๐| is a negative witness for ๐ฅ in ๐, it is easily verified that h๐0 | = h๐| โ h๐| is a negative
witness in ๐ 0, and
2
1 1
kh๐0 |๐ด0 k 2 = (h๐|๐ด) โ (h๐|๐ด) + (h๐|๐ด) โ (h๐|๐ด) = kh๐|๐ดk 4 ,
2 2
so ๐ค โ (๐ฅ, ๐ 0) โค ๐ค โ (๐ฅ, ๐)2 , and ๐โ (๐ 0) โค ๐โ (๐)2 .
If |๐คi is an approximate positive witness for ๐ฅ in ๐, then define
|๐ค 0i = |๐คi|๐คi โ ฮ ๐ป(๐ฅ)โฅ |๐คiฮ ๐ป(๐ฅ) |๐คi + ฮ ๐ป(๐ฅ) |๐คiฮ ๐ป(๐ฅ)โฅ |๐คi โ ฮ ๐ป(๐ฅ) |๐คiฮ ker(๐ด) |๐คi.
We have
1
๐ด0 |๐ค 0i = ๐ด|๐คi๐ด|๐คi โ ๐ดฮ ๐ป(๐ฅ) |๐คi โ ๐ดฮ ker(๐ด) |๐คi + ๐ดฮ ker(๐ด) |๐คi โ ๐ดฮ ๐ป(๐ฅ) |๐คi = |๐i|๐i = |๐0i.
2
We can bound the error as:
ฮ ๐ป 0(๐ฅ)โฅ |๐ค 0i = (ฮ ๐ป(๐ฅ)โฅ โ ๐ผ)|๐ค 0i
2 2 2
= ฮ ๐ป(๐ฅ)โฅ |๐คi|๐คi โ ฮ ๐ป(๐ฅ)โฅ |๐คiฮ ๐ป(๐ฅ) |๐คi
๐
2 ๐
2
.
2
= ฮ ๐ป(๐ฅ)โฅ |๐คiฮ ๐ป(๐ฅ)โฅ |๐คi โค โค
๐โ (๐)2 ๐โ (๐ 0)
Next, observe that
(ฮ ๐ป(๐ฅ) + ฮ ๐ป(๐ฅ)โฅ ) โ (ฮ ๐ป(๐ฅ) + ฮ ๐ป(๐ฅ)โฅ ) โ ฮ ๐ป(๐ฅ)โฅ โ ฮ ๐ป(๐ฅ) + ฮ ๐ป(๐ฅ) โ ฮ ๐ป(๐ฅ)โฅ
= ฮ ๐ป(๐ฅ) โ ฮ ๐ป(๐ฅ) + ฮ ๐ป(๐ฅ) โ ฮ ๐ป(๐ฅ)โฅ + ฮ ๐ป(๐ฅ)โฅ โ ฮ ๐ป(๐ฅ)โฅ + ฮ ๐ป(๐ฅ) โ ฮ ๐ป(๐ฅ)โฅ
= ฮ ๐ป(๐ฅ) โ ๐ผ + ๐ผ โ ฮ ๐ป(๐ฅ)โฅ
0
so |๐ค i = ฮ ๐ป(๐ฅ) |๐คi โ |๐คi + |๐คi โ ฮ ๐ป(๐ฅ)โฅ |๐คi โ ฮ ๐ป(๐ฅ) |๐คi โ ฮ ker(๐ด) |๐คi.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 16
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Thus, using the assumption k|๐ค 0 ik โค 1, and the fact that ฮ row(๐ด) |๐คi = |๐ค0 i:
k|๐ค 0ik 2 = ฮ ๐ป(๐ฅ) |๐คi|๐คi + |๐คiฮ ๐ป(๐ฅ)โฅ |๐คi โ ฮ ๐ป(๐ฅ) |๐คiฮ ker(๐ด) |๐คi
2
2
= ฮ ๐ป(๐ฅ) |๐คiฮ row(๐ด) |๐คi + |๐คiฮ ๐ป(๐ฅ)โฅ |๐คi
2 2 2
= ฮ ๐ป(๐ฅ) |๐คi|๐ค0 i + |๐คiฮ ๐ป(๐ฅ)โฅ |๐คi + 2 ฮ ๐ป(๐ฅ) |๐คi h๐ค 0 |ฮ ๐ป(๐ฅ)โฅ |๐คi
๐
๐
โ
r
โค๐
b+ (๐) + ๐
b+ (๐) + 2๐
b+ (๐) โค (1 + ๐
+ 2 ๐
)๐ b+ (๐).
๐โ (๐) ๐โ (๐)
Note that we could assume that ๐ bโ (๐) โฅ 1 because k๐ค0 k โค 1.
We complete the proof by extending to the general case. Let ๐ be any span program that
๐
-approximates ๐ . By applying Theorem 3.11 and Corollary 3.12, we can get a span program, ๐0 ,
โ
with k|๐ค 0 ik = 1, ๐โ (๐0 ) โค 2, ๐
b+ (๐0 ) โค ๐ถ(๐)2 + 2, and ๐ (๐0 ) = ๐ (๐) + 2, that ๐
-approximates ๐ .
We can then apply the construction described above, iteratively, ๐ times, to get a span program
โ 2๐ ๐โ1
๐๐ that ๐
= ๐
2 -approximates ๐ , with
๐ ๐
๐ (๐๐ ) = ๐ (๐0 )2 = (๐ (๐) + 2)2 ,
๐
๐โ (๐๐ ) โค 22 , and b+ (๐๐ ) โค 4๐ ๐
๐ b+ (๐0 ) โค 4๐ ๐ถ(๐)2 + 2 ยท 4๐ .
log(1/๐
0 )
Setting ๐ = log log(1/๐
)
+ 1 gives the desired ๐
0.
3.2 From span programs to quantum algorithms
In this section, we will prove Theorem 3.1, which states that if a span program approximately
decides a function ๐ , then we can compile it to a quantum algorithm for ๐ . While we hope that
Theorem 3.1 will have applications in designing span program algorithms, its only relevance
to the contents of this paper are its implications with respect to the tightness of the first lower
bound expression in Theorem 4.1, and so this section can be safely skipped.
Theorem 3.1 is similar to [15, Lemma 3.6], the difference here is we let an approximate
positive witness for ๐ฅ be any witness with error, ฮ ๐ป(๐ฅ)โฅ |๐คi , at most ๐
/๐โ , whereas in [15], it
2
is required to have error as small as possible. This relaxation could potentially decrease the
positive complexity ๐ b+ , since we now have more freedom in selecting positive witnesses, but
more importantly, it makes it easier to analyze a span program, because we need not find the
approximate positive witness with the smallest possible error. Importantly, this change in how
we define a span program that approximates ๐ does not change the most important property of
such a span program: that it can be compiled into a quantum algorithm for ๐ . To show this,
we now modify the proof of [15, Lemma 3.6] to fit the new definition. We will restrict to span
programs on binary strings {0, 1} ๐ , but the proof also works for span programs on [๐]๐ for ๐ > 2.
Proof of Theorem 3.1. For a span program ๐ on {0, 1} ๐ and ๐ฅ โ {0, 1} ๐ , define
๐(๐, ๐ฅ) = (2ฮ ker(๐ด) โ ๐ผ)(2ฮ ๐ป(๐ฅ) โ ๐ผ),
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 17
S TACEY J EFFERY
which acts on ๐ป. To prove Theorem 3.1, we will show that by performing phase estimation of
๐(๐, ๐ฅ) on initial state |๐ค 0 i = ๐ด+ |๐i, and estimating the amplitude on having |0i in the phase
register, we can distinguish 1- and 0-inputs of ๐ with bounded error.
By Corollary 3.12 and Claim 3.8, we can assume without loss of generality that ๐ has been
scaled so that it ๐
-approximates ๐ for some ๐
< 1/4, |๐ค 0 i = ๐ด+ |๐i is a unit vector, and ๐โ โค 2.
The scaled span program still has size ๐พ ๐(1) and complexity ๐(๐ถ).
We first modify the proof of [15, Lemma 3.2] to get the following lemma:
Lemma 3.13. Let ๐ be a span program that ๐
-approximates ๐ , with k|๐ค0 ik 2 = 1. Fix any ฮ โ (0, ๐),
and let ฮ ฮ be the projector onto the e๐๐ -eigenspaces of ๐(๐, ๐ฅ) with |๐| โค ฮ. For any ๐ฅ โ ๐ โ1 (1),
4๐
kฮ ฮ |๐ค 0 ik 2 โค ฮ 2๐
b+ + .
๐โ
Proof. Suppose ๐ฅ โ ๐ โ1 (1) and let | ๐คห ๐ฅ i be an approximate positive witness with ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i โค
2
๐
๐โ and k| ๐ค
ห ๐ฅ ik 2 โค ๐
b+ . Note that since ๐ด| ๐คห ๐ฅ i = |๐i, ฮ row(๐ด) | ๐คห ๐ฅ i = ๐ด+ ๐ด| ๐คห ๐ฅ i = ๐ด+ |๐i = |๐ค0 i, so
ฮ row(๐ด) ฮ ๐ป(๐ฅ) | ๐คห ๐ฅ i + ฮ row(๐ด) ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i = |๐ค 0 i.
Since ฮ ๐ป(๐ฅ)โฅ ฮ ๐ป(๐ฅ) | ๐คห ๐ฅ i = 0, we have, by the effective spectral gap lemma (Lemma 2.1):
ฮ2
ฮ ฮ ฮ row(๐ด) ฮ ๐ป(๐ฅ) | ๐คห ๐ฅ i ฮ ๐ป(๐ฅ) | ๐คห ๐ฅ i
2 2
โค
4
2 ฮ2
ฮ ฮ |๐ค0 i โ ฮ row(๐ด) ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i โค k| ๐คห ๐ฅ ik
2
4
ฮ2 b
kฮ ฮ |๐ค0 ik 2 + ฮ ฮ ฮ row(๐ด) ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i โ 2h๐ค 0 |ฮ ฮ ฮ row(๐ด) ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i โค ๐+
2
4
ฮ2 b
kฮ ฮ |๐ค0 ik 2 โ 2 kฮ ฮ |๐ค0 ik ฮ ๐ป(๐ฅ)โฅ | ๐คห ๐ฅ i โค ๐+
4
๐
r
ฮ2 b
kฮ ฮ |๐ค 0 ik 2 โ 2 kฮ ฮ |๐ค 0 ik โค ๐+ .
๐โ 4
This is satisfied only when
r r
๐
๐
๐
r
ฮ2 b ฮ2 b
kฮ ฮ |๐ค 0 ik โค + + ๐+ โค 2 ๐+ +
๐โ ๐โ 4 4 ๐โ
b+ + 4๐
.
kฮ ฮ |๐ค0 ik 2 โค ฮ 2๐
๐โ
We will let ฮ 2 = 1โ4๐
. Then when ๐ (๐ฅ) = 0, we have
2๐
b+ ๐โ
1 1
kฮ 0 |๐ค0 ik 2 = โฅ =: ๐0 ,
๐ค โ (๐ฅ) ๐โ
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 18
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
by [15, Lemma 3.3]. On the other hand, when ๐ (๐ฅ) = 1, we have
๐
1 โ 4๐
4๐
1 + 4๐
kฮ ฮ |๐ค0 ik 2 โค ฮ 2๐
b+ + 4 = + = =: ๐1 .
๐โ 2๐โ ๐โ 2๐โ
We want to distinguish these two cases using 1/ฮ steps of phase estimation, and then estimating
the amplitude on having an estimate of 0 in the phase register to precision:
๐0 โ ๐1 1 โ 4๐
ฮ= = .
2 4๐โ
This will allow us to distinguish between amplitude โฅ ๐0 and amplitude โค ๐1 . Since ๐
< 14
is a constant, ฮ = ฮฉ(1/๐โ ), and thus we use ๐(1/ฮ) = ๐(๐โ ) = ๐(1) (recall that we are
assuming the span program
has been scaled) calls to phase estimation, each of which requires
q
๐(1/ฮ) = ๐ ๐
b+๐โ = ๐(๐ถ) controlled calls to ๐ (for more details, see the nearly identical
proof of [15, Lemma 3.2]). Since ๐(๐, ๐ฅ) can be implemented in cost one query, the query
complexity of this algorithm is ๐(๐ถ).
The algorithm needs a single register of dimension dim ๐ป = ๐พ ๐(1) to apply ๐(๐, ๐ฅ), ๐(1)
registers of dimension 1/ฮ to act as phase registers in phase estimation, and ๐(1) registers
of dimension ๐(1/ฮ) to act as phase registers in the amplitude estimation, for a total space
requirement of
1 1
log dim ๐ป + ๐ log + ๐ log = ๐(log ๐พ) + ๐(log ๐ถ).
ฮ ฮ
To complete the proof, we note that the algorithm is unitary, since it consists of phase estimation,
composed unitarily with amplitude estimation.
3.3 From quantum algorithms to span programs
In this section, we will show how to turn a unitary quantum algorithm into a span program,
proving Theorem 3.2, which implies Theorem 1.1. The construction we use to prove Theorem 3.2
is based on a construction of Reichardt for turning any one-sided error quantum algorithm
into a span program whose complexity matches the algorithmโs query complexity [27, arXiv
version]. We observe that a similar construction also works for two-sided error algorithms,9 but
the resulting span program only approximately decides ๐ .
The algorithm Fix a function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ , and a unitary quantum algorithm
๐ such that on input ๐ฅ โ ๐ โ1 (0), Pr[๐(๐ฅ) = 1] โค 13 , and on input ๐ฅ โ ๐ โ1 (1), Pr[๐(๐ฅ) = 1] โฅ 1โ ๐,
for ๐ โ {0, 13 }, depending on whether we want to consider a one-sided error or a bounded error
algorithm. Let ๐0 (๐ฅ) = Pr[๐(๐ฅ) = 0], so if ๐ (๐ฅ) = 0, ๐0 (๐ฅ) โฅ 2/3, and if ๐ (๐ฅ) = 1, ๐ 0 (๐ฅ) โค ๐.
9A preliminary version of this result appeared in [16], but there was an error in the proof, which is fixed by our
new definition of approximate span programs.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 19
S TACEY J EFFERY
We can suppose ๐ acts on three registers: a query register span{| ๐i : ๐ โ [๐] โช {0}}; a
workspace register span{|๐งi : ๐ง โ ๐ต} for some finite set of symbols ๐ต that contains 0; and an
answer register span{|๐i : ๐ โ {0, 1}}. The query operator ๐ช๐ฅ acts on the query register as
๐ช๐ฅ | ๐i = (โ1)๐ฅ ๐ | ๐i if ๐ โฅ 1, and ๐ช๐ฅ |0i = |0i. If ๐ makes ๐ queries, the final state of ๐ is:
|ฮจ2๐+1 (๐ฅ)i = ๐2๐+1 ๐ช๐ฅ ๐2๐โ1 . . . ๐3 ๐ช๐ฅ ๐1 |0, 0, 0i
for some unitaries ๐2๐+1 , . . . , ๐1 . The output bit of the algorithm, ๐(๐ฅ), is obtained by measuring
the answer register of |ฮจ2๐+1 (๐ฅ)i. We have given the input-independent unitaries odd indicies
so that we may refer to the ๐ก-th query as ๐2๐ก .
Let |ฮจ0 (๐ฅ)i = |ฮจ0 i = |0, 0, 0i denote the starting state, and for ๐ก โ {1, . . . , 2๐ + 1}, let
|ฮจ๐ก (๐ฅ)i = ๐๐ก . . . ๐1 |ฮจ0 i denote the state after ๐ก steps.
The span program We now define a span program ๐๐ from ๐. The space ๐ป will represent
all three registers of the algorithm, with an additional time counter register, and an additional
register to represent a query value ๐.
๐ป = span{|๐ก, ๐, ๐, ๐ง, ๐i : ๐ก โ {0, . . . , 2๐ + 1}, ๐ โ {0, 1}, ๐ โ [๐] โช {0}, ๐ง โ ๐ต, ๐ โ {0, 1}}.
We define ๐ and ๐ด as follows, where ๐ is some constant to be chosen later:
๐ = span{|๐ก, ๐, ๐ง, ๐i : ๐ก โ {0, . . . , 2๐ + 1}, ๐ โ [๐] โช {0}, ๐ง โ ๐ต, ๐ โ {0, 1}}
๏ฃฑ
๏ฃด |๐ก, ๐, ๐ง, ๐i โ |๐ก + 1i๐๐ก+1 | ๐, ๐ง, ๐i if ๐ก โ {0, . . . , 2๐} is even
๏ฃด |๐ก, ๐, ๐ง, ๐i โ (โ1)๐ |๐ก + 1, ๐, ๐ง, ๐i if ๐ก โ {0, . . . , 2๐} is odd (i. e., ๐๐ก+1 = ๐ช๐ฅ )
๏ฃด
๏ฃด
๏ฃด
|๐ก, ๐, ๐ง, ๐i if ๐ก = 2๐ + 1, ๐ = 1, and ๐ = 0
๏ฃฒ
๏ฃด
๐ด|๐ก, ๐, ๐, ๐ง, ๐i = โ
๐๐ |๐ก, ๐, ๐ง, ๐i if ๐ก = 2๐ + 1, ๐ = 0, and ๐ = 0
๏ฃด
๏ฃด
๏ฃด
๏ฃด
if ๐ก = 2๐ + 1 and ๐ = 1.
๏ฃด
๏ฃด 0
๏ฃณ
For ๐ก โค 2๐, ๐ด|๐ก, ๐, ๐, ๐ง, ๐i should be intuitively understood as applying ๐๐ก+1 to | ๐, ๐ง, ๐i, and
incrementing the counter register from |๐กi to |๐ก + 1i. When ๐ก is even, this correspondence is
clear (in that case, the value of ๐ is ignored). When ๐ก is odd, so ๐๐ก+1 = ๐ช๐ฅ , then as long as ๐ = ๐ฅ ๐ ,
(โ1)๐ |๐ก + 1, ๐, ๐ง, ๐i = |๐ก + 1i๐๐ก+1 | ๐, ๐ง, ๐i. We thus define
๐ป ๐,๐ = span{|๐ก, ๐, ๐, ๐ง, ๐i : ๐ก โ {0, . . . , 2๐} is odd, ๐ง โ ๐ต, ๐ โ {0, 1}}.
For even ๐ก, applying ๐๐ก+1 is independent of the input, so we make the corresponding states
available to every input; along with states where the query register is set to ๐ = 0, meaning ๐ช๐ฅ
acts input-independently; and accepting states, whose answer register is set to 1 at time 2๐ + 1:
๐ปtrue = span{|๐ก, ๐, ๐, ๐ง, ๐i : ๐ก โ {0, . . . , 2๐} is even, ๐ โ {0, 1}, ๐ โ [๐], ๐ง โ ๐ต, ๐ โ {0, 1}}
โ span{|๐ก, ๐, 0, ๐ง, ๐i : ๐ก โ {0, . . . , 2๐}, ๐ โ {0, 1}, ๐ง โ ๐ต, ๐ โ {0, 1}}
โ span{|2๐ + 1, ๐, ๐, ๐ง, 1i : ๐ โ {0, 1}, ๐ โ [๐] โช {0}, ๐ง โ ๐ต}.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 20
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
The remaining part of ๐ป will be assigned to ๐ปfalse :
๐ปfalse = span{|2๐ + 1, ๐, ๐, ๐ง, 0i : ๐ โ {0, 1}, ๐ โ [๐] โช {0}, ๐ง โ ๐ต}.
โ
Note that in defining ๐ด, we have put a large factor of ๐๐ in front of ๐ด|2๐ + 1, 0, ๐, ๐ง, 0i, making
the vectors in ๐ปfalse very โcheapโ to use. These vectors are โnever in ๐ป(๐ฅ), but will be used as
the error part of approximate positive witnesses, and the ๐๐ ensures they only contribute
relatively small error.
Finally, we define:
|๐i = |0, 0, 0, 0i = |0i|ฮจ0 i.
Intuitively, we can construct |๐i, the initial state, using a final state that has 1 in the answer
register, and using the transitions |๐ก, ๐, ๐ง, ๐i โ |๐ก + 1i๐๐ก+1 | ๐, ๐ง, ๐i to move from the final state to
the initial state. In the following analysis, we make this idea precise.
Analysis of ๐๐ We will first show that for every ๐ฅ there is an approximate positive witness
with error depending on its probability of being rejected by ๐, ๐0 (๐ฅ).
Lemma 3.14. For any ๐ฅ โ {0, 1} ๐ , there exists an approximate positive witness |๐คi for ๐ฅ in ๐๐ such
that:
๐ 0 (๐ฅ)
.
2
k|๐คik 2 โค 2๐ + 2, and ฮ ๐ป(๐ฅ)โฅ |๐คi โค
๐๐
In particular, if ๐ (๐ฅ) = 1,
๐
.
2
ฮ ๐ป(๐ฅ)โฅ |๐คi โค
๐๐
Proof. Let ๐ ๐ฅ be the linear isometry that acts as
๐ ๐ฅ | ๐, ๐ง, ๐i = |๐ฅ ๐ , ๐, ๐ง, ๐i โ๐ โ [๐] โช {0}, ๐ง โ ๐ต, ๐ โ {0, 1},
where we interpret ๐ฅ 0 as 0. Note that for all | ๐, ๐ง, ๐i, and ๐ก โ {0, . . . , 2๐}, we have
๐ด(|๐กi๐ ๐ฅ | ๐, ๐ง, ๐i) = |๐ก, ๐, ๐ง, ๐i โ |๐ก + 1i๐๐ก+1 | ๐, ๐ง, ๐i.
Let ฮ ๐ = ๐โ[๐]โช{0},๐งโ๐ต | ๐, ๐ง, ๐ih๐, ๐ง, ๐| be the orthogonal projector onto states of the algorithm
ร
with answer register set to ๐. We will construct a positive witness for ๐ฅ from the states of the
algorithm on input ๐ฅ, as follows:
2๐
ร 1
|๐คi = |๐กi๐ ๐ฅ |ฮจ๐ก (๐ฅ)i + |2๐ + 1i|0iฮ 1 |ฮจ2๐+1 (๐ฅ)i + โ |2๐ + 1i|0iฮ 0 |ฮจ2๐+1 (๐ฅ)i.
๐ก=0 ๐๐
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 21
S TACEY J EFFERY
To see that this is a positive witness, we compute ๐ด|๐คi, using the fact that ๐๐ก+1 |ฮจ๐ก (๐ฅ)i = |ฮจ๐ก+1 (๐ฅ)i.
2๐
ร
๐ด|๐คi = (|๐กi|ฮจ๐ก (๐ฅ)i โ |๐ก + 1i๐๐ก+1 |ฮจ๐ก (๐ฅ)i) + |2๐ + 1iฮ 1 |ฮจ2๐+1 (๐ฅ)i + |2๐ + 1iฮ 0 |ฮจ2๐+1 (๐ฅ)i
๐ก=0
2๐
ร 2๐
ร
= |๐กi|ฮจ๐ก (๐ฅ)i โ |๐ก + 1i|ฮจ๐ก+1 (๐ฅ)i + |2๐ + 1i|ฮจ2๐+1 (๐ฅ)i
๐ก=0 ๐ก=0
2๐+1
ร 2๐+1
ร
= |๐กi|ฮจ๐ก (๐ฅ)i โ |๐กi|ฮจ๐ก (๐ฅ)i = |0i|ฮจ0 (๐ฅ)i = |๐i.
๐ก=0 ๐ก=1
We next consider the error of |๐คi for ๐ฅ, given by ฮ ๐ป(๐ฅ)โฅ |๐คi . Since ๐ ๐ฅ | ๐, ๐ง, ๐i โ ๐ป(๐ฅ) for
2
all ๐, ๐ง, ๐, and |2๐ + 1, 0iฮ 1 |ฮจ2๐+1 (๐ฅ)i โ ๐ปtrue โ ๐ป(๐ฅ), ฮ ๐ป(๐ฅ)โฅ |๐คi = โ1 |2๐ + 1i|0iฮ 0 |ฮจ2๐+1 (๐ฅ)i,
๐๐
so
1 ๐ 0 (๐ฅ)
.
2
ฮ ๐ป(๐ฅ)โฅ |๐คi = kฮ 0 |ฮจ2๐+1 (๐ฅ)ik 2 =
๐๐ ๐๐
Finally, we compute an upper bound on the positive witness complexity of |๐คi.
2๐
ร 1
k|๐คik 2 = k๐ ๐ฅ |ฮจ๐ก (๐ฅ)ik 2 + kฮ 1 |ฮจ2๐+1 (๐ฅ)ik 2 + kฮ 0 |ฮจ2๐+1 (๐ฅ)ik 2
๐๐
๐ก=0
2๐
ร
โค k|ฮจ๐ก (๐ฅ)ik 2 + k|ฮจ2๐+1 (๐ฅ)ik 2 = 2๐ + 2.
๐ก=0
Next, we compute an upper bound on ๐คโ (๐ฅ) whenever ๐ (๐ฅ) = 0.
Lemma 3.15. For any ๐ฅ that is rejected by ๐ with probability ๐ 0 (๐ฅ) > 0,
(๐ + 4)๐
๐คโ (๐ฅ) โค .
๐0 (๐ฅ)
In particular, if ๐ (๐ฅ) = 0, ๐ค โ (๐ฅ) โค ๐+4
2/3
๐, so ๐โ โค ๐+4
2/3
๐.
Proof. We will define a negative witness for ๐ฅ as follows. First, define
|ฮจ02๐+1 (๐ฅ)i = ฮ 0 |ฮจ2๐+1 (๐ฅ)i,
the rejecting part of the final state. This is non-zero whenever ๐ 0 (๐ฅ) > 0. Then for ๐ก โ {0, . . . , 2๐},
define
โ โ
|ฮจ0๐ก (๐ฅ)i = ๐๐ก+1 . . . ๐2๐+1 |ฮจ02๐+1 (๐ฅ)i.
From this we can define
2๐+1
ร
h๐| = h๐ก|hฮจ0๐ก (๐ฅ)|.
๐ก=0
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 22
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
We first observe that
h๐|๐i = hฮจ00 (๐ฅ)|0, 0, 0i = hฮจ02๐+1 (๐ฅ)|๐2๐+1 . . . ๐1 |0, 0, 0i = hฮจ02๐+1 (๐ฅ)|ฮจ2๐+1 (๐ฅ)i = ๐0 (๐ฅ).
Thus
1
h ๐|
ยฏ = h๐|
๐ 0 (๐ฅ)
is a negative witness. Next, we show that h๐|๐ดฮ ๐ป(๐ฅ) = 0. First, for |๐ก, ๐ฅ ๐ , ๐, ๐ง, ๐i โ ๐ป ๐,๐ฅ ๐ (so
๐ก < 2๐ is odd), we have
h๐|๐ด|๐ก, ๐ฅ ๐ , ๐, ๐ง, ๐i = h๐|(|๐ก, ๐, ๐ง, ๐i โ (โ1)๐ฅ ๐ |๐ก + 1i| ๐, ๐ง, ๐i)
= hฮจ0๐ก (๐ฅ)| ๐, ๐ง, ๐i โ (โ1)๐ฅ ๐ hฮจ0๐ก+1 (๐ฅ)| ๐, ๐ง, ๐i
= hฮจ0๐ก+1 (๐ฅ)|๐๐ก+1 | ๐, ๐ง, ๐i โ (โ1)๐ฅ ๐ hฮจ0๐ก+1 (๐ฅ)| ๐, ๐ง, ๐i
= hฮจ0๐ก+1 (๐ฅ)|๐ช๐ฅ | ๐, ๐ง, ๐i โ (โ1)๐ฅ ๐ hฮจ0๐ก+1 (๐ฅ)| ๐, ๐ง, ๐i = 0.
The same argument holds for |๐ก, 0, 0, ๐, ๐ง, ๐i โ ๐ปtrue . Similarly, for any |๐ก, ๐, ๐, ๐ง, ๐i โ ๐ปtrue with
๐ก โค 2๐ even, we have
h๐|๐ด|๐ก, ๐, ๐, ๐ง, ๐i = h๐|(|๐ก, ๐, ๐ง, ๐i โ |๐ก + 1i๐๐ก+1 | ๐, ๐ง, ๐i)
= hฮจ0๐ก (๐ฅ)| ๐, ๐ง, ๐i โ hฮจ0๐ก+1 (๐ฅ)|๐๐ก+1 | ๐, ๐ง, ๐i = 0.
Finally, for any |2๐ + 1, ๐, ๐, ๐ง, 1i โ ๐ปtrue , we have
h๐|๐ด|2๐ + 1, ๐, ๐, ๐ง, 1i = h๐|2๐ + 1, ๐, ๐ง, 1i = hฮจ02๐+1 (๐ฅ)| ๐, ๐ง, 1i = 0.
Thus h๐|๐ดฮ ๐ป(๐ฅ) = 0 and so h๐|๐ดฮ ยฏ ๐ป(๐ฅ) = 0, and h ๐|
ยฏ is a negative witness for ๐ฅ in ๐. To compute
its witness complexity, first observe that h๐|๐ด = h๐|๐ดฮ ๐ป(๐ฅ)โฅ , and
๐
ร ร
๐ดฮ ๐ป(๐ฅ)โฅ = (|2๐ โ 1, ๐, ๐ง, ๐i + (โ1)๐ฅ ๐ |2๐ , ๐, ๐ง, ๐i)h2๐ โ 1, ๐ฅยฏ ๐ , ๐, ๐ง, ๐|
๐ =1 ๐โ[๐]โช{0},๐งโ๐ต,๐โ{0,1}
ร โ
+ ๐๐ |2๐ + 1, ๐, ๐ง, 0ih2๐ + 1, 0, ๐, ๐ง, 0|
๐โ[๐]โช{0},๐งโ๐ต
so, using hฮจ02๐ โ1 (๐ฅ)| ๐, ๐ง, ๐i = hฮจ02๐ (๐ฅ)|๐2๐ | ๐, ๐ง, ๐i = (โ1)๐ฅ ๐ hฮจ02๐ (๐ฅ)| ๐, ๐ง, ๐i, we have:
๐
ร ร
h๐|๐ดฮ ๐ป(๐ฅ)โฅ = (hฮจ02๐ โ1 (๐ฅ)| ๐, ๐ง, ๐i + (โ1)๐ฅ ๐ hฮจ02๐ (๐ฅ)| ๐, ๐ง, ๐i)h2๐ โ 1, ๐ฅยฏ ๐ , ๐, ๐ง, ๐|
๐ =1 ๐โ[๐]โช{0},๐งโ๐ต,๐โ{0,1}
ร โ
+ ๐๐ hฮจ02๐+1 (๐ฅ)| ๐, ๐ง, 0ih2๐ + 1, 0, ๐, ๐ง, 0|
๐โ[๐]โช{0},๐งโ๐ต
๐
ร ร
= 2(โ1)๐ฅ ๐ hฮจ02๐ (๐ฅ)| ๐, ๐ง, ๐i)h2๐ โ 1, ๐ฅยฏ ๐ , ๐, ๐ง, ๐|
๐ =1 ๐โ[๐]โช{0},๐งโ๐ต,๐โ{0,1}
ร โ
+ ๐๐ hฮจ02๐+1 (๐ฅ)| ๐, ๐ง, 0ih2๐ + 1, 0, ๐, ๐ง, 0|.
๐โ[๐]โช{0},๐งโ๐ต
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 23
S TACEY J EFFERY
Thus, the complexity of h ๐|
ยฏ is:
1
kh๐|๐ดk 2 2
ยฏ = h๐|๐ดฮ ๐ป(๐ฅ)โฅ
๐ 0 (๐ฅ)2
๐
1 ร ร 2 1 ร 2
= 4 hฮจ02๐ (๐ฅ)| ๐, ๐ง, ๐i + ๐๐ hฮจ02๐+1 (๐ฅ)| ๐, ๐ง, 0i
๐ 0 (๐ฅ)2 ๐ =1 ๐ 0 (๐ฅ)2
๐โ[๐]โช{0}, ๐โ[๐]โช{0},
๐งโ๐ต, ๐งโ๐ต
๐โ{0,1}
๐
4 ร 2 ๐๐ 2
= |ฮจ02๐ (๐ฅ)i + |ฮจ02๐+1 (๐ฅ)i .
๐ 0 (๐ฅ)2 ๐ =1 ๐ 0 (๐ฅ)2
Because each ๐๐ก is unitary, we have |ฮจ02๐ (๐ฅ)i = ๐ 0 (๐ฅ), thus:
2 2
= |ฮจ02๐+1 (๐ฅ)i
4๐ ๐๐ 4+๐
kh ๐|๐ดk
ยฏ 2
= + โค ๐ when ๐ (๐ฅ) = 0.
๐ 0 (๐ฅ) ๐ 0 (๐ฅ) 2/3
We conclude the proof of Theorem 3.2 with the following corollary, from which Theorem 3.2
follows immediately, by appealing to Claim 3.8 with ๐
= 10
9
and ๐
0 any constant in (0, 1).
Corollary 3.16. Let ๐ = 5, in the definition of ๐๐ . Then:
โข ๐ (๐๐ ) = 2๐+๐(1)
โข If ๐ decides ๐ with one-sided error, then ๐๐ decides ๐ with complexity ๐ถ โค ๐(๐).
โข If ๐ decides ๐ with bounded error, then ๐๐ 10
9
-approximates ๐ with complexity ๐ถ๐
โค ๐(๐).
Proof. We first compute ๐ (๐๐ ) = dim ๐ป using the fact that the algorithm uses space
๐ = log dim span{| ๐, ๐ง, ๐i : ๐ โ [๐] โช {0}, ๐ง โ ๐ต, ๐ โ {0, 1}} + log ๐.
We have:
dim ๐ป = (dim span{|๐ก, ๐i : ๐ก โ {0, . . . , 2๐ + 1}, ๐ โ {0, 1}})2๐โlog ๐ = 2๐+๐(1) .
We prove the third statement, as the second is similar. By Lemma 3.15, using ๐ = 5, we have
5+4 27
๐โ โค ๐ = ๐.
2/3 2
By Lemma 3.14, we can see that for every ๐ฅ such that ๐ (๐ฅ) = 1, there is an approximate positive
witness |๐คi for ๐ฅ with error at most
๐ 1 2๐
27
1/3 9 1
= โค = .
๐๐ 5๐ 15๐ ๐โ 10 ๐โ
q p
Furthermore, k|๐คik โค 2๐ + 2, so ๐
2 b+ โค 2๐ + 2. Observing ๐ถ๐
= ๐โ๐
b+ โค 27๐(๐ + 1)
completes the proof.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 24
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
4 Span programs and space complexity
Using the transformation from algorithms to span programs from Section 3.3, we immediately
have the following connections between span program size and space complexity.
Theorem 4.1. For any ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ , we have
S๐ ( ๐ ) โฅ ฮฉ log SP
f( ๐ ) ( ๐ ) โฅ ฮฉ log SP( ๐ ) .
1
and S๐
Theorem 4.1 is a corollary of Theorem 3.2. Theorem 3.1 shows that the lower bound for S๐ ( ๐ ) in
Theorem 4.1 is part of a tight correspondence between space complexity and log ๐ (๐) + log ๐ถ(๐).
Theorem 2.9 of [5] gives a lower bound of SP( ๐ ) โฅ ฮฉ(2๐/3 /(๐ log ๐)1/3 ) for almost all ๐-bit
Boolean functions. Combined with Theorem 4.1, we immediately have:
Theorem 4.2. For almost all Boolean functions ๐ : {0, 1} ๐ โ {0, 1}, S๐
1
( ๐ ) = ฮฉ(๐).
Ideally, we would like to use the lower bound in Theorem 4.1 to prove a non-trivial lower
bound for S๐ ( ๐ ) or S๐
1
( ๐ ) for some explicit function ๐ . Fortunately, there are somewhat nice
expressions lower bounding SP( ๐ ) [25, 11], which we extend to lower bounds of SP f ( ๐ ) in the
remainder of this section. However, on the unfortunate side, there has already been significant
motivation to instantiate these expressions to non-trivial lower bounds for explicit ๐ , with no
success. There has been some success in monotone versions of these lower bounds, which we
discuss more in Section 5.
For a function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ , and an index ๐ โ [๐], we let ฮ ๐ ,๐ โ
{0, 1} ๐ (0)ร ๐ (1) be defined by ฮ ๐ ,๐ [๐ฆ, ๐ฅ] = 1 if and only if ๐ฅ ๐ โ ๐ฆ ๐ . When ๐ is clear from context,
โ1 โ1
we simply denote this by ฮ ๐ . The following tight characterization of SP( ๐ ) may be found in, for
example, [23].
Lemma 4.3. For any ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ ,
ร
SP( ๐ ) = minimize rank(ฮ ๐ )
๐โ[๐]
subject to โ๐ โ [๐], ฮ ๐ โ โ ๐
โ1 (0)ร ๐ โ1 (1)
ร
ฮ ๐ โฆ ฮ ๐ = ๐ฝ,
๐โ[๐]
where ๐ฝ is the ๐ โ1 (0) ร ๐ โ1 (1) all-ones matrix.
By Theorem 4.1, the logarithm of the above is a lower bound on S๐
1
( ๐ ). We modify Lemma 4.3
to get the following approximate version, whose logarithm lower bounds S๐ ( ๐ ) when ๐
= 14 .
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 25
S TACEY J EFFERY
Lemma 4.4. For any ๐
โ [0, 1), and ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ ,
ร
f ๐
( ๐ ) โฅ minimize
SP rank(ฮ ๐ ) (4.1)
๐โ[๐]
subject to โ๐ โ [๐], ฮ ๐ โ โ ๐
โ1 (0)ร ๐ โ1 (1)
ร โ
ฮ๐ โฆ ฮ๐ โ ๐ฝ โค ๐
.
๐โ[๐]
โ
Proof. Fix a span program that ๐
-approximates ๐ with ๐ (๐) = SP f ๐
( ๐ ), and let {h๐ ๐ฆ | : ๐ฆ โ ๐ โ1 (0)}
be optimal negative witnesses, and {|๐ค ๐ฅ i : ๐ฅ โ ๐ (1)} be approximate positive witnesses with
โ1
ฮ ๐ป(๐ฅ) |๐ค ๐ฅ i โค ๐๐
โ . Letting ฮ ๐,๐ denote the projector onto ๐ป ๐,๐ , define
2
! !
ร ร
ฮ๐ = |๐ฆih๐ ๐ฆ |๐ดฮ ๐, ๐ฆยฏ ๐ ฮ ๐,๐ฅ ๐ |๐ค ๐ฅ ih๐ฅ| ,
๐ฆ ๐ฅ
so ฮ ๐ has rank at most dim ๐ป ๐ , and so ๐โ[๐] rank(ฮ ๐ ) โค ๐ (๐) = SP f ๐
( ๐ ).
ร
We now show that {ฮ ๐ } ๐ is a feasible solution. Let | err(๐ฅ)i be the positive witness error of
|๐ค ๐ฅ i, | err(๐ฅ)i = ฮ ๐ป(๐ฅ)โฅ |๐ค ๐ฅ i = ๐๐=1 ฮ ๐, ๐ฅยฏ ๐ |๐ค ๐ฅ i. Then we have:
ร
๐
ร ร ร
h๐ฆ| ฮ ๐ โฆ ฮ ๐ |๐ฅi = h๐ ๐ฆ |๐ด ฮ ๐,๐ฅ ๐ |๐ค ๐ฅ i = h๐ ๐ฆ |๐ด ยญ |๐ค ๐ฅ i โ ฮ ๐,๐ฅ ๐ |๐ค ๐ฅ i โ | err(๐ฅ)i ยฎ
ยฉ ยช
๐=1 ๐:๐ฅ ๐ โ ๐ฆ ๐ ยซ ๐:๐ฅ ๐ =๐ฆ ๐ ยฌ
ร
= h๐ ๐ฆ |๐i โ h๐ ๐ฆ |๐ด ฮ ๐ป(๐ฆ) ฮ ๐,๐ฅ ๐ |๐ค ๐ฅ i โ h๐ ๐ฆ |๐ด| err(๐ฅ)i
๐:๐ฅ ๐ =๐ฆ ๐
= 1 โ 0 โ h๐ ๐ฆ |๐ด| err(๐ฅ)i
๐
๐
โ
ร r
1 โ h๐ฆ| ฮ ๐ โฆ ฮ ๐ |๐ฅi โค h๐ ๐ฆ |๐ด k| err(๐ฅ)ik = ๐ค โ (๐ฆ) โค ๐
.
๐โ
๐=1
Above we used the fact that h๐ ๐ฆ |๐ดฮ ๐ป(๐ฆ) = 0. Thus, {ฮ ๐ } ๐ is a feasible solution with objective
f ๐
( ๐ ), so the result follows.
value โค SP
As a corollary of the above, and the connection between span program size and unitary
quantum space complexity stated in Theorem 4.1, the logarithm of the expression in (4.1) with
๐
= 41 is a lower bound on S๐ ( ๐ ), and with ๐
= 0, it is a lower bound on S๐
1
( ๐ ). However, as
stated, it is difficult to use this expression to prove an explicit lower bound, because it is a
minimization problem. We will shortly give a lower bound in terms of a maximization problem,
making it possible to obtain explicit lower bounds by exhibiting a feasible solution.
A partial matrix is a matrix ๐ โ (โ โช {โ
}) ๐ (0)ร ๐ (1) . A completion of ๐ is any ๐ โ
โ1 โ1
โ ๐ (0)ร ๐ (1) such that ๐[๐ฆ, ๐ฅ] = ๐[๐ฆ, ๐ฅ] whenever ๐[๐ฆ, ๐ฅ] โ โ
. For a partial matrix ๐, define
โ1 โ1
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 26
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
rank(๐) to be the smallest rank of any completion of ๐, and ๐-rank(๐) to be the smallest rank
of any ๐ห such that |๐[๐ฆ, ๐ฅ] โ ๐[๐ฆ,
ห ๐ฅ]| โค ๐ for all ๐ฆ, ๐ฅ such that ๐[๐ฆ, ๐ฅ] โ โ
. Let ๐ โฆ ฮ๐ to be
the partial matrix defined:
๐[๐ฆ, ๐ฅ] if ฮ๐ [๐ฆ, ๐ฅ] = 1
๐ โฆ ฮ๐ [๐ฆ, ๐ฅ] =
0 if ฮ๐ [๐ฆ, ๐ฅ] = 0.
Then we have the following corollary of [11, Lemma 3.2, Theorem 3.4] and Theorem 4.1:
Lemma 4.5. For all Boolean functions ๐ : ๐ท โ {0, 1}, with ๐ท โ {0, 1} ๐ , and all partial matrices
๐ โ (โ โช {โ
}) ๐ (0)ร ๐ (1) such that max{|๐[๐ฆ, ๐ฅ]| : ๐[๐ฆ, ๐ฅ] โ โ
} โค 1:
โ1 โ1
rank(๐)
1
S๐ (๐) โฅ ฮฉ log .
max๐โ[๐] rank(๐ โฆ ฮ๐ )
In [25], Razborov showed that the expression on the right-hand side in Lemma 4.5 is a lower
bound on the logarithm of the formula size of ๐ (Ref. [11] related this to SP( ๐ )). Later, in [26],
Razborov noted that when restricted to non-partial matrices, this can never give a better bound
than ๐. Thus, to prove a non-trivial lower bound on S๐1
( ๐ ) using this method, one would need
to use a partial matrix. We prove the following generalization to the approximate case.
Lemma 4.6. For all Boolean functions ๐ : ๐ท โ {0, 1}, with ๐ท โ {0, 1} ๐ , and all partial matrices
๐ โ (โ โช {โ
}) ๐ (0)ร ๐ (1) such that max{|๐[๐ฆ, ๐ฅ]| : ๐[๐ฆ, ๐ฅ] โ โ
} โค 1:
โ1 โ1
!!
2 -rank(๐)
1
S๐ ( ๐ ) โฅ ฮฉ log .
max๐โ[๐] rank(๐ โฆ ฮ๐ )
Proof. Let {ฮ ๐ } ๐ be an optimal feasible solution for the expression from Lemma 4.4, so
ร ร โ
f ๐
( ๐ ) โฅ
SP rank(ฮ ๐ ), and ฮ๐ โฆ ฮ๐ โ ๐ฝ โค ๐
.
๐โ[๐] ๐โ[๐]
โ
Let ๐ ๐ be a completion of ๐ โฆ ฮ ๐ with rank(๐ โฆ ฮ ๐ ) = rank(๐ ๐ ). Then for any ๐ฅ, ๐ฆ such that
๐[๐ฆ, ๐ฅ] โ โ
:
ยฉร ร
๐ ๐ โฆ ฮ ๐ ยฎ [๐ฆ, ๐ฅ] โ ๐[๐ฆ, ๐ฅ] = ๐[๐ฆ, ๐ฅ]ฮ ๐ [๐ฆ, ๐ฅ]ฮ ๐ [๐ฆ, ๐ฅ] โ ๐[๐ฆ, ๐ฅ]
ยช
ยญ
ยซ ๐โ[๐] ยฌ ๐โ[๐]
ร โ
โค |๐[๐ฆ, ๐ฅ]| ฮ๐ โฆ ฮ๐ โ ๐ฝ โค ๐
.
๐โ[๐]
โ
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 27
S TACEY J EFFERY
Thus
โ ยฉร ร
๐
-rank(๐) โค rank ยญ ๐ ๐ โฆ ฮ๐ ยฎ โค rank(๐ ๐ โฆ ฮ ๐ ).
ยช
ยซ ๐โ[๐] ยฌ ๐โ[๐]
Using the fact that for any matrices ๐ต and ๐ถ, rank(๐ต โฆ ๐ถ) โค rank(๐ต)rank(๐ถ), we have
โ ร
๐
-rank(๐) โค f ๐
( ๐ ) max rank(๐ โฆ ฮ ๐ ).
rank(ฮ ๐ )rank(๐ ๐ ) โค SP
๐โ[๐]
๐โ[๐]
Setting ๐
= 14 , and noting that by Theorem 4.1, S๐ ( ๐ ) โฅ log SP
f ( ๐ ) = log SP
f 1/4 ( ๐ ) completes the
proof.
Unfortunately, as far as we are aware, nobody has used this lower bound to successfully
prove any explicit, non-trivial formula size lower bound of 2๐(log ๐) , so it seems to be quite
difficult. However, there has been some success proving lower bounds in the monotone span
program case, even without resorting to partial matrices, which we discuss in the next section.
5 Monotone span programs and monotone algorithms
A monotone function is a Boolean function in which ๐ฆ โค ๐ฅ implies ๐ (๐ฆ) โค ๐ (๐ฅ), where ๐ฆ โค ๐ฅ
should be interpreted bitwise. In other words, flipping 0s to 1s either keeps the function value
the same, or changes it from 0 to 1. A monotone span program is a span program in which
๐ป๐,0 = {0} for all ๐, so only 1-valued queries contribute to ๐ป(๐ฅ), hence ๐ป(๐ฆ) โ ๐ป(๐ฅ) whenever
๐ฆ โค ๐ฅ. A monotone span program can only decide or approximate a monotone function.
Definition 5.1. For a monotone function ๐ , define the monotone span program size, denoted mSP( ๐ ),
as the minimum ๐ (๐) over (families of) monotone span programs ๐ such that ๐ decides ๐ ; and
the approximate monotone span program size, denoted mSPf ๐
( ๐ ), as the minimum ๐ (๐) over (families
of) monotone span programs ๐ such that ๐ ๐
-approximates ๐ . We let mSP f ( ๐ ) = mSP
f 1/4 ( ๐ ).
In contrast to SP( ๐ ), there are non-trivial lower bounds for mSP( ๐ ) for explicit monotone
functions ๐ . However, this does not necessarily give a lower bound on SP( ๐ ), and in particular,
may not be a lower bound on the one-sided error quantum space complexity of ๐ . However, lower
bounds on log mSP( ๐ ) or log mSP f ( ๐ ) do give lower bounds on the space complexity of quantum
algorithms obtained from monotone span programs, and as we will soon see, log mSP( ๐ ) and
f ( ๐ ) are lower bounds on the space complexity of monotone phase estimation algorithms,
log mSP
described in Section 5.2. The strongest known lower bound on mSP( ๐ ) is the following:
Theorem 5.2 ([24]). There is an explicit Boolean function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ such that
log mSP( ๐ ) โฅ ฮฉ(๐).
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 28
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
We will adapt some of the techniques used in existing lower bounds on mSP to show a lower
bound on mSPf ( ๐ ) for some explicit ๐ :
Theorem 5.3. There is an explicit Boolean function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ such that for any
constant ๐
,
f ๐
( ๐ ) โฅ (log ๐)2โ๐(1) .
log mSP
In particular, this implies a lower bound of 2(log ๐) on mSP( ๐ ) for the function ๐ in
2โ๐(1)
Theorem 5.3. We prove Theorem 5.3 in Section 5.1. Theorem 5.3 implies that any quantum
algorithm for ๐ obtained from a monotone span program must have space complexity (log ๐)2โ๐(1) ,
which is slightly better than the trivial lower bound of ฮฉ(log ๐). In Section 5.2, we describe
a more natural class of algorithms called monotone phase estimation algorithms such that
f ( ๐ ) is a lower bound on the quantum space complexity of any such algorithm computing
log mSP
๐ with bounded error. Then for the specific function ๐ from Theorem 5.3, any monotone phase
estimation algorithm for ๐ must use space (log ๐)2โ๐(1) .
5.1 Monotone span program lower bounds
Our main tool in proving Theorem 5.3 will be the following.
Theorem 5.4. For any Boolean function ๐ : ๐ท โ {0, 1}, ๐ท โ {0, 1} ๐ , and any constant ๐
โ [0, 1):
โ
f ๐
( ๐ ) โฅ ๐
-rank(๐)
mSP max ,
๐โโ ๐ (0)ร ๐ (1) :k๐ k โ โค1 max ๐โ[๐] rank(๐ โฆ ฮ ๐,1 )
โ1 โ1
where ฮ ๐,1 [๐ฆ, ๐ฅ] = 1 if ๐ฆ ๐ = 0 and ๐ฅ ๐ = 1, and 0 else.
When, ๐
= 0, the right-hand side of the equation in Theorem 5.4 is the (monotone) rank
measure, defined in [25], and shown in [11] to lower bound monotone span program size. We
extend the proof for the ๐
= 0 case to get a lower bound on approximate span program size. We
could also allow for partial matrices ๐, as in the non-monotone case (Lemma 4.6) but unlike
the non-monotone case, it is not necessary to consider partial matrices to get non-trivial lower
bounds.
Proof. Fix a monotone span program that ๐
-approximates ๐ with size mSP f ๐
( ๐ ). Let {h๐ ๐ฆ | :
๐ฆ โ ๐ (0)} be optimal negative witnesses, and let {|๐ค ๐ฅ i : ๐ฅ โ ๐ (1)} be approximate positive
โ1 โ1
witnesses with ฮ ๐ป(๐ฅ)โฅ |๐ค ๐ฅ i โค ๐๐
โ . Letting ฮ ๐,๐ denote the projector onto ๐ป ๐,๐ , define
2
ร ร ร ร
ฮ๐ = |๐ฆih๐ ๐ฆ |๐ดฮ ๐, ๐ฆยฏ ๐ ฮ ๐,๐ฅ ๐ |๐ค ๐ฅ ih๐ฅ| = |๐ฆih๐ ๐ฆ |๐ดฮ ๐,1 ฮ ๐,1 |๐ค ๐ฅ ih๐ฅ|,
๐ฆโ ๐ โ1 (0) ๐ฅโ ๐ โ1 (1) ๐ฆโ ๐ โ1 (0): ๐ฅโ ๐ โ1 (1):
๐ฆ ๐ =0 ๐ฅ ๐ =1
so ฮ ๐ has rank at most dim๐ป ๐ , and so ๐โ[๐] rank(ฮ ๐ ) โค ๐ (๐) = mSP f ๐
( ๐ ). Furthermore, ฮ ๐ is
ร
only supported on (๐ฆ, ๐ฅ) such that ๐ฆ ๐ = 0 and ๐ฅ ๐ = 1, so ฮ ๐ โฆ ฮ ๐,1 = ฮ ๐ . Denoting the error of
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 29
S TACEY J EFFERY
ร
|๐ค ๐ฅ i as | err(๐ฅ)i = ฮ ๐ป(๐ฅ)โฅ |๐ค ๐ฅ i = ๐:๐ฅ ๐ =0 ฮ ๐,1 |๐ค ๐ฅ i, we have
ร ร ร ร
h๐ฆ| ฮ ๐ |๐ฅi = h๐ ๐ฆ |๐ดฮ ๐,1 |๐ค ๐ฅ i = h๐ ๐ฆ |๐ด ฮ ๐,1 ฮ ๐,1 |๐ค ๐ฅ i
๐โ[๐] ๐:๐ฆ ๐ =0,๐ฅ ๐ =1 ๐:๐ฆ ๐ =0 ๐:๐ฅ ๐ =1
= h๐ ๐ฆ |๐ด(|๐ค ๐ฅ i โ | err(๐ฅ)i) = h๐ ๐ฆ |๐ด|๐ค ๐ฅ i โ h๐ ๐ฆ |๐ด| err(๐ฅ)i
๐
โ
ร p r
1 โ h๐ฆ| ฮ ๐ |๐ฅi โค 1 โ 1 + h๐ ๐ฆ |๐ด k| err(๐ฅ)ik โค ๐โ = ๐
.
๐โ
๐โ[๐]
Then for any ๐ โ โ ๐
โ1 (0)ร ๐ โ1 (1)
with k๐ k โ โค 1, we have:
ร ร โ
๐โ๐โฆ ฮ๐ โค k๐ k โ ๐ฝ โ ฮ๐ โค ๐
.
๐โ[๐] ๐โ[๐]
โ โ
Thus
โ ร ร
๐
-rank(๐) โค rank ยญ ๐ โฆ ฮ๐ ยฎ โค rank(๐ โฆ ฮ ๐ )
ยฉ ยช
๐โ[๐] ๐โ[๐]
ร ยซ ยฌ ร
= rank(๐ โฆ ฮ ๐,1 โฆ ฮ ๐ ) โค rank(๐ โฆ ฮ ๐,1 )rank(ฮ ๐ )
๐โ[๐] ๐โ[๐]
f ๐
( ๐ ) max rank(๐ โฆ ฮ ๐,1 ).
โค mSP
๐โ[๐]
To show a lower bound on mSP f ( ๐ ) for some explicit ๐ : {0, 1} ๐ โ {0, 1}, it turns out to be
sufficient to find some high approximate rank matrix ๐ โ โ๐ร๐ for finite sets ๐ and ๐, and
a rectangle cover of ๐, ฮ1 , . . . , ฮ๐ , where each ฮ๐ โฆ ๐ has low rank. Specifically, we have the
following lemma, which, with rank in place of approximate rank, has been used extensively in
previous monotone span program lower bounds.
Lemma 5.5. Let ๐ โ โ๐ร๐ with k๐ k โ โค 1, for some finite sets ๐ and ๐ and ๐1 , . . . , ๐๐ โ ๐,
๐1 , . . . , ๐๐ โ ๐ be such that for all (๐ฅ, ๐ฆ) โ ๐ ร ๐, there exists ๐ โ [๐] such that (๐ฅ, ๐ฆ) โ ๐ ๐ ร ๐๐ .
Define ฮ ๐ โ {0, 1}๐ร๐ by ฮ ๐ [๐ฆ, ๐ฅ] = 1 if and only if (๐ฆ, ๐ฅ) โ ๐๐ ร ๐ ๐ . There exists a monotone function
๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ such that for any constant ๐
โ [0, 1):
โ
f ๐
( ๐ ) โฅ ๐
-rank(๐)
mSP .
max ๐โ[๐] rank(๐ โฆ ฮ ๐ )
Proof. For each ๐ฆ โ ๐, define ๐ก ๐ฆ โ {0, 1} ๐ by:
0 if ๐ฆ โ ๐๐
๐ฆ
๐ก๐ =
1 else.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 30
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Similarly, for each ๐ฅ โ ๐, define ๐ ๐ฅ โ {0, 1} ๐ by
1 if ๐ฅ โ ๐ ๐
๐ ๐๐ฅ =
0 else.
For every (๐ฆ, ๐ฅ) โ ๐ ร ๐, there is some ๐ such that ๐ฆ ๐ โ ๐๐ and ๐ฅ ๐ โ ๐ ๐ , so it cannot be the case
that ๐ ๐ฅ โค ๐ก ๐ฆ . Thus, we can define ๐ as the unique monotone function such that ๐ (๐ ) = 1 for
every ๐ โ {0, 1} ๐ such that ๐ ๐ฅ โค ๐ for some ๐ฅ โ ๐, and ๐ (๐ก) = 0 for all ๐ก โ {0, 1} ๐ such that
๐ก โค ๐ก ๐ฆ for some ๐ฆ โ ๐. Then we can define a matrix ๐ 0 โ โ ๐ (0)ร ๐ (1) by ๐ 0[๐ก ๐ฆ , ๐ ๐ฅ ] = ๐[๐ฆ, ๐ฅ]
โ1 โ1
for all (๐ฆ, ๐ฅ) โ ๐ ร ๐, and 0 elsewhere. We have ๐-rank(๐ 0) = ๐-rank(๐) for all ๐, and
rank(๐ 0 โฆ ฮ ๐,1 ) = rank(๐ โฆ ฮ ๐ ) for all ๐. The result then follows from Theorem 5.4.
We will prove Theorem 5.3 by constructing an ๐ with high approximate rank, and a good
rectangle cover. Following [29] and [24], we will make use of a technique due to Sherstov for
proving communication lower bounds, called the pattern matrix method [30]. We begin with
some definitions.
Definition 5.6 (Fourier spectrum). For a real-valued function ๐ : {0, 1} ๐ โ โ, its Fourier
coefficients are defined, for each ๐ โ [๐]:
1 ร
๐(๐)
ห = ๐(๐ง)๐๐ (๐ง),
2๐
๐งโ{0,1} ๐
where ๐๐ (๐ง) = (โ1) ๐โ๐ ๐ง ๐ . It is easily verified that ๐ = ๐โ[๐] ๐(๐)๐
ร ร
ห ๐.
Definition 5.7 (Degree and approximate degree). The degree of a function ๐ : {0, 1} ๐ โ โ is
defined deg(๐) = max{|๐| : ๐(๐)
ห โ 0}. For any ๐ โฅ 0, deg
g (๐) = min{deg(๐)
๐ ห : k๐ โ ๐k
ห โ โค ๐}.
Pattern matrices, defined by Sherstov in [30], are useful for proving lower bounds in
communication complexity, because their rank and approximate rank are relatively easy to
lower bound. In [29], Robere, Pitassi, Rossman and Cook first used this analysis to give lower
bounds on mSP( ๐ ) for some ๐ . We now state the definition, using the notation from [24], which
differs slightly from [30].
Definition 5.8 (Pattern matrix). For a real-valued function ๐ : {0, 1} ๐ โ โ, and a positive integer
๐๐ ๐ ๐
๐, the (๐, ๐, ๐)-pattern matrix is defined as ๐น โ โ {0,1} ร([๐] ร{0,1} ) where for ๐ฆ โ {0, 1}๐๐ ,
๐ฅ โ [๐]๐ , and ๐ค โ {0, 1} ๐ ,
๐น[๐ฆ, (๐ฅ, ๐ค)] = ๐(๐ฆ| ๐ฅ โ ๐ค),
where by ๐ฆ| ๐ฅ , we mean the ๐-bit string containing one bit from each ๐-sized block of ๐ฆ as
(1) (2) (๐)
specified by the entries of ๐ฅ: (๐ฆ ๐ฅ1 , ๐ฆ ๐ฅ2 , . . . , ๐ฆ ๐ฅ ๐ ), where ๐ฆ (๐) โ {0, 1}๐ is the ๐-th block of ๐ฆ.
For comparison, what [30] calls an (๐, ๐ก, ๐)-pattern matrix would be a (๐ก, ๐/๐ก, ๐)-pattern
matrix in our notation. As previously mentioned, a pattern matrix has the nice property that
its rank (or even approximate rank) can be bounded from below in terms of properties of the
Fourier spectrum of ๐. In particular, the following is proven in [30]:
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 31
S TACEY J EFFERY
Lemma 5.9. Let ๐น be the (๐, ๐, ๐)-pattern matrix for ๐ : {0, 1} ๐ โ {โ1, +1}. Then for any ๐ โ [0, 1]
and ๐ฟ โ [0, ๐], we have:
ร (๐ โ ๐ฟ)2
rank(๐น) = ๐ |๐| and ๐ฟ-rank(๐น) โฅ ๐deg๐ (๐) .
g
(1 + ๐ฟ)2
๐โ[๐]:๐(๐)โ 0
ห
This shows that we can use functions ๐ of high approximate degree to construct pattern
๐๐ ๐ ๐
matrices ๐น โ โ {0,1} ร([๐] ร{0,1} ) of high approximate rank. To apply Lemma 5.5, we also need
to find a good rectangle cover of some ๐น.
A ๐-certificate for a function ๐ on {0, 1} ๐ is an assignment ๐ผ : ๐ โ {0, 1} for some ๐ โ [๐]
such that for any ๐ฅ โ {0, 1} ๐ such that ๐ฅ ๐ = ๐ผ(๐) for all ๐ โ ๐, ๐ (๐ฅ) = ๐. The size of a certificate is
|๐|. The following shows how to use the certificates of ๐ to construct a rectangle cover of its
pattern matrix.
Lemma 5.10. Let ๐ : {0, 1} ๐ โ {โ1, +1}, and suppose there is a set of โ certificates for ๐ of size at
most ๐ถ such that every input satisfies at least one certificate. Then for any positive integer
โ ๐, there exists
๐ ๐ถ
a function ๐ : {0, 1} โ {0, 1} for ๐ = โ (2๐) such that for any ๐
โ (0, 1) and ๐ โ [ ๐
, 1]:
โ
f ๐
( ๐ ) โฅ ฮฉ (๐ โ
mSP ๐
)2 ๐deg๐ (๐) .
g
Proof. For ๐ = 1, . . . , โ , let ๐ผ ๐ : ๐ ๐ โ {0, 1} for ๐ ๐ โ [๐] of size |๐ ๐ | โค ๐ถ be one of the โ certificates.
That is, for each ๐, there is some ๐ฃ ๐ โ {โ1, +1} such that for any ๐ฅ โ {0, 1} ๐ , if ๐ฅ ๐ = ๐ผ ๐ (๐) for all
๐ โ ๐ ๐ , then ๐(๐ฅ) = ๐ฃ ๐ (so ๐ผ ๐ is a ๐ฃ ๐ -certificate).
We let ๐น be the (๐, ๐, ๐)-pattern matrix, which has k๐นk โ = 1 since ๐ has range {โ1, +1}. We
will define a rectangle cover as follows. For every ๐ โ [โ ], ๐ โ [๐]๐๐ , and ๐ โ {0, 1} ๐๐ , define:
๐๐,๐,๐ = {(๐ฅ, ๐ค) โ [๐]๐ ร {0, 1} ๐ : โ๐ โ ๐ ๐ , ๐ค ๐ = ๐ ๐ , ๐ฅ ๐ = ๐ ๐ }
(๐)
๐๐,๐,๐ = {๐ฆ โ {0, 1}๐๐ : โ๐ โ ๐ ๐ , ๐ฆ ๐ = ๐ ๐ โ ๐ผ ๐ (๐)}.
๐
We first note that this is a rectangle cover. Fix any ๐ฆ โ {0, 1}๐๐ , ๐ฅ โ [๐]๐ and ๐ค โ {0, 1} ๐ . First
note that for any ๐, if we let ๐ be the restriction of ๐ค to ๐ ๐ , and ๐ the restriction of ๐ฅ to ๐ ๐ , we
have (๐ฅ, ๐ค) โ ๐๐,๐,๐ . This holds in particular for ๐ such that ๐ผ ๐ is a certificate for ๐ฆ| ๐ฅ โ ๐ค, and by
(๐)
assumption there is at least one such ๐. For such an ๐, we have ๐ฆ ๐ฅ ๐ โ ๐ค ๐ = ๐ผ(๐) for all ๐ โ ๐ ๐ , so
๐ฆ โ ๐๐,๐,๐ . Thus, we can apply Lemma 5.5.
(๐)
Note that if (๐ฅ, ๐ค) โ ๐๐,๐,๐ , and ๐ฆ โ ๐๐,๐,๐ , then (๐ฆ| ๐ฅ โ ๐ค)[๐] = ๐ฆ ๐ฅ ๐ โ ๐ค ๐ = ๐ผ ๐ (๐) for all ๐ โ ๐ ๐ ,
so ๐(๐ฆ| ๐ฅ โ ๐ค) = ๐ฃ ๐ . Letting ฮ๐,๐,๐ [๐ฆ, (๐ฅ, ๐ค)] = 1 if ๐ฆ โ ๐๐,๐,๐ and (๐ฅ, ๐ค) โ ๐๐,๐,๐ , and 0 else, we
have that if ๐ฆ โ ๐๐,๐,๐ and (๐ฅ, ๐ค) โ ๐๐,๐,๐ , (๐น โฆ ฮ๐,๐,๐ )[๐ฆ, (๐ฅ, ๐ค)] = ๐(๐ฆ| ๐ฅ โ ๐ค) = ๐ฃ ๐ , and otherwise,
(๐น โฆ ฮ๐,๐,๐ )[๐ฆ, (๐ฅ, ๐ค)] = 0. Thus rank(๐น โฆ ฮ๐,๐,๐ ) = rank(๐ฃ ๐ ฮ๐,๐,๐ ) = 1. Then by Lemma 5.5, there
exists ๐ : {0, 1} ๐ โ {0, 1} where ๐ = โ๐=1 (2๐)|๐๐ | โค โ (2๐)๐ถ such that:
ร
โ
f ๐
( ๐ ) โฅ ๐
-rank(๐น)
mSP
โ 2
g (๐) (๐ โ ๐
)
โฅ๐ deg ๐ โ , by Lemma 5.9.
(1 + ๐
)2
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 32
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
We now prove Theorem 5.3, restated below.
Theorem 5.3. There is an explicit Boolean function ๐ : ๐ท โ {0, 1} for ๐ท โ {0, 1} ๐ such that for
any constant ๐
,
f ๐
( ๐ ) โฅ ฮฉ((log ๐)2โ๐(1) ).
log mSP
Proof. By [8, Theorem 38], there is a function ๐ with deg
g (๐) โฅ ๐ถ(๐)2โ๐(1) , which is, up to the
1/3
๐(1) in the exponent, the best possible separation between these two quantities. In particular, this
g (๐) โฅ ๐ 2โ๐(1) , and ๐ถ(๐) โค ๐ 1+๐(1) , where ๐ถ(๐) is the certificate complexity
function has deg 1/3
of ๐, for some parameter ๐ (see [8] equations (64) and (65), where ๐ is referred to as ๐น), and ๐ is
a function on ๐ 2+๐(1) variables (see [8], discussion above equation (64)). Thus, there are at most
๐ 2+๐(1) ๐ 1+๐(1)
๐ 1+๐(1) 2 possible certificates of size ๐ 1+๐(1) such that each input satisfies at least one of
them.
๐ 2+๐(1) ๐ 1+๐(1)
Then by Lemma 5.10 there exists a function ๐ : {0, 1} ๐ โ {0, 1} for ๐ โค (2๐)๐
1+๐(1)
๐ 1+๐(1) 2
such that for constant ๐
< 1/36 and constant ๐,
f ๐
( ๐ ) โฅ ฮฉ(deg
log mSP g (๐) log ๐) โฅ ๐ 2โ๐(1) .
1/3
Then we have
๐ 2+๐(1)
log ๐ โค log + log 2๐ + ๐ 1+๐(1) log(2๐) = ๐(๐ 1+๐(1) log ๐) = ๐ 1+๐(1) .
1+๐(1)
๐ 1+๐(1)
f ๐
( ๐ ) โฅ (log ๐)2โ๐(1) , and the result for any ๐
follows using Corollary 3.9.
Thus, log mSP
Since for all total functions ๐, deg
g (๐) โค ๐ถ(๐)2 , where ๐ถ(๐) is the certificate complexity
1/3
of ๐, Lemma 5.10 cannot prove a lower bound better than log mSP f (๐) โฅ (log ๐)2 for any ๐-bit
function. We state a more general version of Lemma 5.10 that might have the potential to prove
a better bound, but we leave this for future work.
Lemma 5.11. Fix ๐ : {0, 1} ๐ โ {โ1, +1}. For ๐ = 1, . . . , โ , let ๐ผ ๐ : ๐ ๐ โ {0, 1} for ๐ ๐ โ [๐] be a
partial assignment such that every ๐ง โ {0, 1} ๐ satisfies at least one of the assignments. Let ๐ ๐ denote the
restriction of ๐ to strings ๐ง satisfying the assignment ๐ผ ๐ . Then for every positive integer ๐, there
โ exists a
function ๐ : {0, 1} ๐ โ {0, 1}, where ๐ = โ๐=1 (2๐)|๐๐ | such that for any ๐
โ (0, 1) and ๐ โ [ ๐
, 1]:
ร
โ !
(๐ โ ๐
)2 ๐deg๐ (๐)
g
f ๐
( ๐ ) โฅ ฮฉ
mSP .
๐โ[๐]\๐ ๐ :๐ห ๐ (๐)โ 0 ๐
|๐|
ร
max๐โ[โ ]
To make use of this lemma, one needs a function ๐ of high approximate degree, such
that for every input, there is a small assignment that lowers the degree to something small.
This generalizes Lemma 5.10 because a certificate is an assignment that lowers the degree
of the remaining sub-function to constant. However, we note that a ๐ with these conditions
is necessary but may not be sufficient for proving a non-trivial lower bound, because while
๐: ๐ห ๐ (๐)โ 0 ๐
ร |๐| โฅ ๐deg(๐ ๐ ) , it may also be much larger if ๐ has a dense Fourier spectrum.
๐
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 33
S TACEY J EFFERY
Proof. Let ๐น be the (๐, ๐, ๐)-pattern matrix. Let {๐๐,๐,๐ ร ๐๐,๐,๐ } ๐,๐,๐ be the same rectangle covered
defined in the proof of Lemma 5.10, with the difference that since the ๐ผ ๐ are no longer certificates,
the resulting submatrices of ๐น may not have constant rank.
Let ฮ๐,๐,๐ = ๐ฆโ๐๐,๐,๐ |๐ฆi (๐ฅ,๐ค)โ๐๐,๐,๐ h๐ฅ, ๐ค|. Then
ร ร
ร
๐น โฆ ฮ๐,๐,๐ = ๐(๐ฆ| ๐ฅ โ ๐ค)|๐ฆih๐ฅ, ๐ค|.
๐ฆโ๐๐,๐,๐ ,(๐ฅ,๐ค)โ๐๐,๐,๐
Note that when ๐ฆ โ ๐๐,๐,๐ and (๐ฅ, ๐ค) โ ๐๐,๐,๐ , ๐ฆ| ๐ฅ โ ๐ค satisfies ๐ผ ๐ , so ๐(๐ฆ| ๐ฅ โ ๐ค) = ๐ ๐ (๐ฆ 0 | ๐ฅ0 โ ๐ค 0),
where ๐ฆ 0, ๐ฅ 0 and ๐ค 0 are restrictions of ๐ฆ โ ({0, 1}๐ )๐ , ๐ฅ โ [๐]๐ and ๐ค โ {0, 1} ๐ to [๐] \ ๐ ๐ . Thus,
continuing from above, and rearranging registers, we have:
ร ร ร
๐น โฆ ฮ๐,๐,๐ = ๐ ๐ (๐ฆ 0 | ๐ฅ0 โ ๐ค 0)|๐ฆ 0ih๐ฅ 0 , ๐ค 0 | โ | ๐ฆih๐,
ยฏ ๐|
๐ )๐ ๐ :
๐ฆ 0 โ({0,1}๐ )[๐]\๐ ๐ ๐ฅ 0 โ[๐][๐]\๐ ๐ , ๐ฆโ({0,1}
ยฏ
๐ค 0 โ{0,1}[๐]\๐ ๐ ๐ฆ|
ยฏ ๐ =๐โ๐ผ ๐
= ๐น๐ โ ๐ฝ2(๐โ1)|๐๐ | ,1
where ๐น๐ is the (๐, ๐, ๐ ๐ )-pattern matrix, and ๐ฝ๐,๐ is the all-ones matrix of dimension ๐ by ๐,
which always has rank 1 for ๐, ๐ > 0. Thus
ร
rank(๐น โฆ ฮ๐,๐,๐ ) = rank(๐น๐ )rank(๐ฝ2(๐โ1)|๐๐ | ,1 ) = rank(๐น๐ ) = ๐ |๐| ,
๐โ[๐]\๐ ๐ :๐ห ๐ (๐)โ 0
by [30]. This part of the proof follows [29, Lemma IV.6].
Then by Lemma 5.5 and Lemma 5.9, we have:
โ 2
โ ๐โ ๐
๐
-rank(๐น) ยฉ โ
1+ ๐
๐deg๐ (๐)
ยช
mSP๐
( ๐ ) โฅ ฮฉ
f โฅ ฮฉยญ
ยญ ยฎ.
max๐,๐,๐ rank(๐น โฆ ฮ๐,๐,๐ ) max๐ ๐โ[๐]\๐๐ :๐ห ๐ (๐)โ 0 ๐ ยฎ
|๐|
ร
ยซ ยฌ
5.2 Monotone algorithms
In Theorem 5.3, we showed a non-trivial lower bound on log mSP f ( ๐ ) for some explicit monotone
function ๐ . Unlike lower bounds on log SP f ( ๐ ), this does not give us a lower bound on the
quantum space complexity of ๐ , however, at the very least it gives us a lower bound on the
quantum space complexity of a certain type of quantum algorithm. Of course, this is naturally the
case, since a lower bound on mSP f ( ๐ ) gives us a lower bound on the quantum space complexity
of any algorithm for ๐ that is obtained from a monotone span program. However, this is not the
most satisfying characterization, as it is difficult to imagine what this class of algorithms looks
like.
In this section, we will consider a more natural class of algorithms whose space complexity is
shown to be at least mSPf ( ๐ ), and in some cases mSP( ๐ ). We will call a quantum query algorithm
a phase estimation algorithm if it works by estimating the amplitude on |0i in the phase register
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 34
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
after running phase estimation of a unitary that makes one query. We assume that the unitary
for which we perform phase estimation is of the form ๐ ๐ช๐ฅ . This is without loss of generality,
because the most general form is a unitary ๐2 ๐ช๐ฅ ๐1 , but we have (๐2 ๐ช๐ฅ ๐1 )๐ก |๐0 i = ๐1โ (๐ ๐ช๐ฅ )๐ก |๐00 i
where |๐00 i = ๐1 |๐0 i, and ๐ = ๐1๐2 . The weight on a phase of |0i is not affected by this global
(๐ก-independent) ๐1โ . Thus, we define a phase estimation algorithm as follows:
Definition 5.12. A phase estimation algorithm ๐ = (๐ , |๐0 i, ๐ฟ, ๐, ๐) for ๐ : ๐ท โ {0, 1}, ๐ท โ
{0, 1} ๐ , is defined by (families of):
โข a unitary ๐ acting on โ = span{| ๐, ๐งi : ๐ โ [๐], ๐ง โ ๐ต} for some finite set ๐ต;
โข an initial state |๐0 i โ โ ;
โข a bound ๐ฟ โ [0, 1/2);
โข positive integers ๐ and ๐ โค โ1 ;
๐ฟ
such that for any ๐ 0 โฅ ๐ and ๐ 0 โฅ ๐, the following procedure computes ๐ with bounded error:
1. Let ฮฆ(๐ฅ) be the algorithm that runs phase estimation of ๐ ๐ช๐ฅ on |๐0 i for ๐ 0 steps, and then
computes a bit |๐i๐ด in a new register ๐ด, such that ๐ = 0 if and only if the phase estimate
is 0.
2. Run ๐ 0 steps of amplitude estimation to estimate the amplitude on |0i๐ด after application
of ฮฆ(๐ฅ). Output 0 if the amplitude is > ๐ฟ.
The query complexity of the algorithm is ๐(๐๐), and, the space complexity of the algorithm is
log dim โ + log ๐ + log ๐ + 1.
We insist that the algorithm work not only for ๐ and ๐ but for any larger integers as well,
because we want to ensure that the algorithm is successful because ๐ and ๐ are large enough,
and not by some quirk of the particular chosen values. When ๐ฟ = 0, the algorithm has one-sided
error (see Lemma 5.18).
We remark on the generality of this form of algorithm. Any algorithm can be put into this
form by first converting it to a span program using the construction of Section 3.3 (Theorem 3.2),
and then compiling that into an algorithm using the construction of Section 3.2 (Theorem 3.1),
preserving both the time and space complexity, asymptotically. However, we will consider a
special case of this type of algorithm that is not fully general.
Definition 5.13. A monotone phase estimation algorithm is a phase estimation algorithm such
that if ฮ 0 (๐ฅ) denotes the orthogonal projector onto the (+1)-eigenspace of ๐ ๐ช๐ฅ , then for any
๐ฅ โ {0, 1} ๐ , ฮ 0 (๐ฅ)|๐0 i is in the (+1)-eigenspace of ๐ช๐ฅ .
Let us consider what is โmonotoneโ about this definition. The algorithm outputs 0 if |๐0 i
has high overlap with the (+1)-eigenspace of ๐ ๐ช๐ฅ , i. e., ฮ 0 (๐ฅ)|๐0 i is large. In a monotone phase
estimation algorithm, we know that the only contribution to ฮ 0 (๐ฅ)|๐0 i is in the (+1)-eigenspace
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 35
S TACEY J EFFERY
of ๐ช๐ฅ , which is exactly the span of | ๐, ๐งi such that ๐ฅ ๐ = 0. Thus, only queries that return 0 can
contribute to the algorithm rejecting.
As a simple example, Groverโs algorithm is a monotone phase estimation algorithm.
Specifically, let |๐0 i = โ1๐ ๐๐=1 | ๐i and ๐ = (2|๐0 ih๐0 | โ ๐ผ). Then ๐ ๐ช๐ฅ is the standard Grover
ร
iterate, and |๐0 i is in the span of e๐๐ -eigenvectors of ๐ ๐ช๐ฅ with sin |๐| = |๐ฅ|/๐, so phase
p
estimation can be used to distinguish the case |๐ฅ| = 0 from |๐ฅ| โฅ 1. So ฮ 0 (๐ฅ)|๐0 i is either 0,
when |๐ฅ| โ 0, or |๐0 i, when |๐ฅ| = 0. In both cases, it is in the (+1)-eigenspace of ๐ช๐ฅ .
It is clear that a monotone phase estimation algorithm can only decide a monotone function.
However, while any quantum algorithm can be converted to a phase estimation algorithm, it is
not necessarily the case that any quantum algorithm for a monotone function can be turned into
a monotone phase estimation algorithm (see Remark 5.17). Thus lower bounds on the quantum
space complexity of any monotone phase estimation algorithm for a monotone ๐ do not imply
lower bounds on S๐ ( ๐ ). Nevertheless, if we let mS๐ ( ๐ ) represent the minimum quantum space
complexity of any monotone phase estimation algorithm for ๐ , then a lower bound on mS๐ ( ๐ )
at least tells us that if we want to compute ๐ with space less than said bound, we must use a
non-monotone phase estimation algorithm.
Similarly, we let mS๐ 1
( ๐ ) denote the minimum quantum space complexity of any monotone
phase estimation algorithm with ๐ฟ = 0 that computes ๐ (with one-sided error).
The main theorem of this section states that any monotone phase estimation algorithm for ๐
with space ๐ can be converted to a monotone span program of size 2ฮ(๐) that approximates ๐ , so
that lower bounds on mSP f ( ๐ ) imply lower bounds on mS๐ ( ๐ ); and that any monotone phase
estimation algorithm with ๐ฟ = 0 and space ๐ can be converted to a monotone span program
of size 2ฮ(๐) that decides ๐ (exactly) so that lower bounds on mSP( ๐ ) imply lower bounds on
mS๐ 1
( ๐ ). These conversions also preserve the query complexity. We now formally state this
main result.
Theorem 5.14. Let ๐ = (๐ , |๐0 i, ๐ฟ, ๐, ๐) be a monotone phase estimation algorithm for ๐ with space
complexity ๐ = log dim โ + log ๐ + log ๐ + 1 and query complexity ๐(๐ ๐). Then there is a monotone
span program with complexity ๐(๐ ๐) and size 2 dim โ โค 2๐ that approximates ๐ . If ๐ฟ = 0, then this
span program decides ๐ (exactly). Thus
mS๐ ( ๐ ) โฅ log mSP
f( ๐ ) and 1
mS๐ ( ๐ ) โฅ log mSP( ๐ ).
We prove this theorem in Section 5.2.1. As a corollary, lower bounds on mSP( ๐ ), such as the
one from [24], imply lower bounds on mS๐ 1
( ๐ ); and lower bounds on mSP
f ( ๐ ) such as the one in
Theorem 5.3, imply lower bounds on mS๐ ( ๐ ). In particular:
Corollary 5.15. Let ๐ : {0, 1} ๐ โ {0, 1} be the function described in Theorem 5.3. Then mS๐ ( ๐ ) โฅ
(log ๐)2โ๐(1) . Let ๐ : {0, 1} ๐ โ {0, 1} be the function described in Theorem 5.2. Then mS๐
1
(๐) โฅ ฮฉ(๐).
We emphasize that while this does not give a lower bound on the quantum space complexity
of ๐ , or the one-sided quantum space complexity of ๐, it does show that any algorithm that uses
(log ๐)๐ space to solve ๐ with bounded error, for ๐ < 2, or ๐(๐) space to solve ๐ with one-sided
error, must be of a different form than that described in Definition 5.13.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 36
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
In a certain sense, monotone phase estimation algorithms completely characterize those
that can be derived from monotone span programs, because the algorithm we obtain from
compiling a monotone span program is a monotone phase estimation algorithm, as stated below
in Lemma 5.16. However, not all monotone phase estimation algorithms can be obtained by
compiling monotone span programs, and similarly, we might hope to show that an even larger
class of algorithms can be converted to monotone span programs, in order to give more strength
to lower bounds on mS๐ ( ๐ ).
Lemma 5.16. Let ๐ be an approximate monotone span program for ๐ with size ๐ and complexity ๐ถ. Then
there is a monotone phase estimation algorithm for ๐ with query complexity ๐(๐ถ) and space complexity
๐(log ๐ + log ๐ถ).
Proof. Fix a monotone span program, and assume it has been appropriately scaled. Without
loss of generality, we can let ๐ป ๐ = ๐ป ๐,1 = span{| ๐, ๐งi : ๐ง โ ๐ต๐ } for some finite set ๐ต๐ . Then,
๐ช๐ฅ = ๐ผ โ 2ฮ ๐ป(๐ฅ) , which is only true because the span program is monotone. Let ๐ = 2ฮ row(๐ด) โ ๐ผ.
Then ๐ ๐ช๐ฅ = (2ฮ ker(๐ด) โ ๐ผ)(2ฮ ๐ป(๐ฅ) โ ๐ผ) is the span program unitary, described in Section 3.2.
Then it is simple to verify that the algorithm described in [15, Lemma 3.6] (and referred to
in Section 3.2) is a phase estimation algorithm for ๐ with query complexity ๐(๐ถ) and space
complexity ๐(log ๐ + log ๐ถ).
The algorithm is a monotone phase estimation algorithm because ๐ = 2ฮ row(๐ด) โ ๐ผ is
a reflection, and |๐0 i = |๐ค 0 i = ๐ด+ |๐i is in the (+1)-eigenspace of ๐, row(๐ด). Since ๐ is a
reflection, the (+1)-eigenspace of ๐ ๐ช๐ฅ is exactly (ker(๐ด) โฉ ๐ป(๐ฅ)) โ (row(๐ด) โฉ ๐ป(๐ฅ)โฅ ), and so
ฮ 0 (๐ฅ)|๐ค 0 i โ row(๐ด) โฉ ๐ป(๐ฅ)โฅ โ ๐ป(๐ฅ)โฅ .
Remark 5.17. We mention an example of monotone functions for which the best known quantum
algorithm, in terms of space complexity, is not a monotone phase estimation algorithm. Every
function can be expressed as a Boolean formula, and every monotone function can be expressed
as a monotone Boolean formula (a formula with no negation gates), but this might be much
larger than the smallest (non-monotone) formula for the function. For example, the function
XOR-SAT, defined in [13], can be computed by a circuit of depth ๐((log ๐)2 ), which means it has
๐
a formula of size 2๐((log ๐) ) , but its monotone formula complexity is 2ฮฉ(๐ ) for some constant ๐.10
2
โFor any Boolean formula of size ๐, there exists a quantum algorithm that can evaluate it using
๐( ๐) queries, and ๐(log ๐) space [27, 18]. Since this algorithm is designed via span programs,
it is a phase estimation algorithm, and it is monotone if and only if the formula is monotone. For
a function for which there is a separation between the monotone and non-monotone formula
complexities, the smallest space quantum algorithm of this type will not be monotone. For
example, for XOR-SAT, we could use a quantum algorithm that evaluates a monotone formula
and has space complexity ๐ ๐ . This is a monotone phase estimation algorithm, but it is not
optimal. If we instead evaluate the optimal non-monotone formula, we get a quantum algorithm
(that is not monotone) with space complexity (log ๐)2 . Of course, this does not rule out that
10If we pad XOR-SAT with 0s so that the input length goes from ๐ to ๐ = 2๐(log ๐) for some appropriate constant
2
๐, then โthe formula size becomes linear in ๐, while the monotone formula size is still superpolynomial in ๐, scaling
๐ log ๐
like 22 . We thank Robert Robere for this observation.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 37
S TACEY J EFFERY
there could be some other space-optimal quantum algorithm for this problem that is a monotone
phase estimation algorithm.
5.2.1 Monotone algorithms to (approximate) monotone span programs
In this section, we prove Theorem 5.14. Throughout this section, we fix a phase estimation
algorithm ๐ = (๐ , |๐0 i, ๐ฟ, ๐, ๐) that computes ๐ , with ๐ acting on โ . For any ๐ฅ โ {0, 1} ๐ and
ฮ โ [0, ๐], we let ฮ ฮ (๐ฅ) denote the orthogonal projector onto the span of e๐๐ -eigenvectors of
๐ ๐ช๐ฅ for |๐| โค ฮ. We will let ฮ ๐ฅ = ๐โ[๐],๐งโ๐ต:๐ฅ ๐ =1 | ๐, ๐งih๐, ๐ง|.
ร
We begin by drawing some conclusions about the necessary relationship between the
eigenspaces of ๐ ๐ช๐ฅ and a function ๐ whenever a monotone phase estimation computes ๐ . The
proofs are somewhat dry and are deferred to Section 5.2.2.
Lemma 5.18. Fix a phase estimation algorithm with ๐ฟ = 0 that solves ๐ with bounded error. Then if
๐ (๐ฅ) = 0,
1
kฮ 0 (๐ฅ)|๐0 ik 2 โฅ 2 ,
๐
โ
and for any ๐ < 8/๐, if ๐ (๐ฅ) = 1, then
2
ฮ ๐๐/๐ (๐ฅ)|๐0 i = 0,
and the algorithm always outputs 1, so it has one-sided error.
Lemma 5.19. Fix a phase estimation algorithm with ๐ฟ โ 0 that solves ๐ with bounded error. Then there
is some constant ๐ > 0 such that if ๐ (๐ฅ) = 0,
kฮ 0 (๐ฅ)|๐0 ik 2 โฅ max{๐ฟ(1 + ๐), 1/๐ 2 }
โ
and if ๐ (๐ฅ) = 1, for any ๐ < 8/๐,
๐ฟ
.
2
ฮ ๐๐/๐ (๐ฅ)|๐0 i โค
1 โ ๐ 8๐
2 2
To prove Theorem 5.14, we will define a monotone span program ๐๐ as follows:
๐ปtrue = span{| ๐, ๐งi : ๐ โ [๐], ๐ง โ ๐ต} = โ
๐ป ๐,1 = ๐ป ๐ = span{| ๐, ๐ง, 1i : ๐ง โ ๐ต}
1
๐ด| ๐, ๐ง, 1i = (| ๐, ๐งi โ (โ1)1 | ๐, ๐งi) = | ๐, ๐งi
2
๐ด| ๐, ๐งi = (๐ผ โ ๐ โ )| ๐, ๐งi
|๐i = |๐0 i. (5.1)
We first show that ฮ 0 (๐ฅ)|๐0 i is (up to scaling) a negative witness for ๐ฅ, whenever it is
nonzero:
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 38
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Lemma 5.20. For any ๐ฅ โ {0, 1} ๐ , we have
1
๐คโ (๐ฅ) = .
kฮ 0 (๐ฅ)|๐0 ik 2
In particular, ฮ 0 (๐ฅ)|๐0 i/kฮ 0 (๐ฅ)|๐0 ik 2 is an optimal negative witness for ๐ฅ when ฮ 0 (๐ฅ)|๐0 i โ 0.
Proof. Suppose ฮ 0 (๐ฅ)|๐0 i โ 0, and let |๐i = ฮ 0 (๐ฅ)|๐0 i/kฮ 0 (๐ฅ)|๐0 ik 2 . We will first show that
this is a negative witness, and then show that no negative witness can have better complexity.
First, we notice that
h๐0 |ฮ 0 (๐ฅ)|๐0 i
h๐|๐i = h๐|๐0 i = = 1.
kฮ 0 (๐ฅ)|๐0 ik 2
Next, we will see that h๐|๐ดฮ ๐ป(๐ฅ) = 0. By the monotone phase estimation property, ๐ช๐ฅ ฮ 0 (๐ฅ)|๐0 i =
ฮ 0 (๐ฅ)|๐0 i, and so ๐ช๐ฅ |๐i = |๐i, and thus ฮ ๐ฅ |๐i = 0, where ฮ ๐ฅ is the projector onto | ๐, ๐งi such
that ๐ฅ ๐ = 1. Note that ๐ป(๐ฅ) = span{| ๐, ๐ง, 1i : ๐ฅ ๐ = 1, ๐ง โ ๐ต} โ span{| ๐, ๐งi : ๐ โ [๐], ๐ง โ ๐ต}. Thus
ฮ ๐ป(๐ฅ) = ฮ ๐ปtrue + ฮ ๐ฅ โ |1ih1|. We have:
h๐|๐ด(ฮ ๐ฅ โ |1ih1|) = h๐|ฮ ๐ฅ = 0.
Since |๐i is in the (+1)-eigenspace of ๐ ๐ช๐ฅ , we have ๐ ๐ช๐ฅ |๐i = |๐i so since ๐ช๐ฅ |๐i = |๐i,
๐ |๐i = |๐i. Thus
h๐|๐ดฮ ๐ปtrue = h๐|(๐ผ โ ๐ โ ) โ h1| = (h๐| โ h๐|) โ h1| = 0.
Thus |๐i is a zero-error negative witness for ๐ฅ. Next, we argue that it is optimal.
Suppose |๐i is any optimal negative witness for ๐ฅ, with size ๐ค โ (๐ฅ). Then since h๐|ฮ ๐ฅ =
h๐|๐ด(ฮ ๐ฅ โ |1ih1|) must be 0, ๐ช๐ฅ |๐i = (๐ผ โ 2ฮ ๐ฅ )|๐i = |๐i, and since h๐|๐ดฮ ๐ปtrue = h๐|(๐ผ โ ๐ โ )
must be 0, ๐ |๐i = |๐i. Thus |๐i is a 1-eigenvector of ๐ ๐ช๐ฅ , so
2
|๐ih๐| |h๐|๐0 i| 2 1
2
kฮ 0 (๐ฅ)|๐0 ik โฅ 2
|๐0 i = 2
= .
k|๐ik k|๐ik k|๐ik 2
We complete the proof by noticing that since h๐|๐ดฮ ๐ปtrue = 0, we have h๐|๐ด = h๐|h1|, and
๐ค โ (๐ฅ) = kh๐|๐ดk 2 = k|๐ik 2 .
Next we find approximate positive witnesses.
Lemma 5.21. For any ฮ โฅ 0, the span program ๐๐ has approximate positive witnesses for any ๐ฅ with
5๐2
error at most kฮ ฮ (๐ฅ)|๐0 ik 2 and complexity at most 4ฮ 2.
Proof. We first define a vector |๐ฃi by:
|๐ฃi = (๐ผ โ (๐ ๐ช๐ฅ )โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 39
S TACEY J EFFERY
Note that ๐ผ โ (๐ ๐ช๐ฅ )โ is supported everywhere except the (+1)-eigenvectors of (๐ ๐ช๐ฅ )โ , which
are exactly the (+1)-eigenvectors of ๐ ๐ช๐ฅ . Thus, (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i is contained in this support.
Next we define
|๐คi = |๐0 i โ (๐ผ โ ๐ โ )|๐ฃi |1i + |๐ฃi.
Then we have:
๐ด|๐คi = |๐0 i โ (๐ผ โ ๐ โ )|๐ฃi + (๐ผ โ ๐ โ )|๐ฃi = |๐0 i = |๐i.
So |๐คi is a positive witness, and we next compute its error for ๐ฅ:
2
= ฮ ๐ฅยฏ |๐0 i โ (๐ผ โ ๐ โ )|๐ฃi
2
ฮ ๐ป(๐ฅ)โฅ |๐คi
2
= ฮ ๐ฅยฏ |๐0 i โ ฮ ๐ฅยฏ (๐ผ โ ๐ โ )(๐ผ โ (๐ ๐ช๐ฅ )โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i .
Above, ฮ ๐ฅยฏ = ๐ผ โ ฮ ๐ฅ . We now observe that
ฮ ๐ฅยฏ (๐ผ โ ๐ช๐ฅ ๐ โ ) = ฮ ๐ฅยฏ ฮ ๐ฅยฏ โ (ฮ ๐ฅยฏ โ ฮ ๐ฅ )๐ โ = ฮ ๐ฅยฏ (๐ผ โ ๐ โ ).
Thus, continuing from above, we have:
2
= ฮ ๐ฅยฏ |๐0 i โ ฮ ๐ฅยฏ (๐ผ โ ๐ช๐ฅ ๐ โ )(๐ผ โ ๐ช๐ฅ ๐ โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i
2
ฮ ๐ป(๐ฅ)โฅ |๐คi
= kฮ ๐ฅยฏ |๐0 i โ ฮ ๐ฅยฏ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 ik 2 = kฮ ๐ฅยฏ ฮ ฮ (๐ฅ)|๐0 ik 2
โค kฮ ฮ (๐ฅ)|๐0 ik 2 .
๐๐ ๐
Now we compute the complexity of |๐คi. First, let ๐ ๐ช๐ฅ =
ร
๐e |๐ ๐ ih๐ ๐ | be the eigenvalue
decomposition of ๐ ๐ช๐ฅ . Then
ร 1
(๐ผ โ (๐ ๐ช๐ฅ )โ )+ = |๐ ๐ ih๐ ๐ |
๐:๐ ๐ โ 0
1 โ eโ๐๐๐
ร
and ๐ผ โ ฮ ฮ (๐ฅ) = |๐ ๐ ih๐ ๐ |.
๐:|๐ ๐ |>ฮ
We can thus bound k|๐ฃik 2 :
2
2
ร 1
k|๐ฃik = (๐ผ โ (๐ ๐ช๐ฅ )โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i
2
= h๐ ๐ |๐0 i|๐ ๐ i
๐:|๐ ๐ |>ฮ
1 โ eโ๐๐๐
ร 1 ๐2
= ๐
|h๐ ๐ |๐0 i| 2 โค .
2 ๐ 4ฮ 2
๐:|๐ ๐ |>ฮ 4 sin 2
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 40
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
Next, using ๐ช๐ฅ + 2ฮ ๐ฅ = ๐ผ โ 2ฮ ๐ฅ + 2ฮ ๐ฅ = ๐ผ, we compute
2 2
|๐0 i โ (๐ผ โ ๐ โ )|๐ฃi = |๐0 i โ (๐ผ โ ๐ช๐ฅ ๐ โ โ 2ฮ ๐ฅ ๐ โ )(๐ผ โ ๐ช๐ฅ ๐ โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i
2
= |๐0 i โ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i + 2ฮ ๐ฅ ๐ โ (๐ผ โ (๐ ๐ช๐ฅ )โ )+ (๐ผ โ ฮ ฮ (๐ฅ))|๐0 i
2
ร 1
โค ยญ kฮ ฮ (๐ฅ)|๐0 ik + 2 ฮ ๐ฅ ๐ โ h๐ ๐ |๐0 i|๐ ๐ i ยฎ
ยฉ ยช
โ๐๐ ๐
๐:|๐ ๐ |>ฮ
1โe
ยซ ยฌ
v 2
t ร
1
โค ยญ kฮ ฮ (๐ฅ)|๐0 ik + 2 |h๐ ๐ |๐0 i| 2 ยฎ
ยฉ ยช
2 ๐ ๐
ยซ ๐:|๐ ๐ |>ฮ 4 sin 2 ยฌ
๐ 2 ๐ 2
โค kฮ ฮ (๐ฅ)|๐0 ik + k(๐ผ โ ฮ ฮ (๐ฅ))|๐0 ik โค .
ฮ ฮ2
Then we have the complexity of |๐คi,
2
k|๐คik 2 = |๐0 i โ (๐ผ โ ๐ โ )|๐ฃi + k|๐ฃik 2
๐2 ๐2 5๐2
โค + = .
ฮ 2 4ฮ 2 4ฮ 2
We conclude with the following two corollaries, whose combination gives Theorem 5.14.
Corollary 5.22. Let ๐ = (๐ , |๐0 i, 0, ๐, ๐) be a monotone phase estimation algorithm for ๐ with space
complexity ๐ = log dim โ + log ๐ + log ๐ + 1 and query complexity ๐(๐ ๐). Then there is a monotone
span program that decides ๐ (exactly) whose size is 2 dim โ โค 2๐ and whose complexity is ๐(๐ ๐).
Proof. If ๐ (๐ฅ) = 0, then by Lemma 5.18, we have kฮ 0 (๐ฅ)|๐0 ik 2 โฅ ๐1 2 , so by Lemma 5.20,
๐ค โ (๐ฅ) โค ๐ 2 . Thus ๐โ โค ๐ 2 .
If ๐ (๐ฅ) = 1, then by Lemma 5.18, we have ฮ 2/๐ (๐ฅ)|๐0 i = 0, so by Lemma 5.21, thereโs an
2
exact positive witness for ๐ฅ with complexity ๐(๐ 2 ). Thus ๐+ โค ๐(๐ 2 ), and so the span program
๐๐ from (5.1) has complexity ๐(๐ ๐). The size of the span program ๐๐ is dim ๐ป = 2 dim โ .
Corollary 5.23. Let ๐ = (๐ , |๐0 i, ๐ฟ, ๐, ๐) be a monotone phase estimation algorithm for ๐ with
space complexity ๐ = log dim โ + log ๐ + log ๐ + 1 and query complexity ๐(๐ ๐). Then there is a
constant ๐
โ (0, 1) such that there exists a monotone span program that ๐
-approximates ๐ whose size is
2 dim โ โค 2๐ and whose complexity is ๐(๐ ๐).
Proof. If ๐ (๐ฅ) = 0, then by Lemma 5.19, we have kฮ 0 (๐ฅ)|๐0 ik 2 > ๐ฟ(1 + ๐) for some constant ๐ > 0.
Thus, by Lemma 5.20, ๐โ โค (1+๐)๐ฟ1
.
๐
If ๐ (๐ฅ) = 1, then by Lemma 5.21, setting ฮ = ๐๐/๐ for ๐ = ๐2 1+๐ , (where ๐ is the constant
p
from above), by Lemma 5.21 there is an approximate positive witness for ๐ฅ with error
2
๐ ๐ฅ = ฮ 2โ ๐ /๐ (๐ฅ)|๐0 i
1+๐
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 41
S TACEY J EFFERY
and complexity ๐(๐ 2 ). By Lemma 5.19, we have
๐ฟ ๐ฟ ๐ฟ(1 + ๐) 1 1
๐๐ฅ โค = ๐ = โค .
1 โ ๐ 8๐
2 2
1 โ 2(1+๐) 1 + ๐ โ ๐/2 1 + ๐/2 ๐โ
Thus, letting ๐
= 1+๐/2
1
< 1, we have that ๐๐ ๐
-approximates ๐ . Since the positive witness
complexity is ๐(๐ 2 ), and by Lemma 5.19, we also have ๐โ โค ๐(๐ 2 ), the complexity of ๐๐ is
๐(๐ ๐). The size of ๐๐ is dim ๐ป = 2 dim โ .
5.2.2 Proofs of Lemma 5.18 and Lemma 5.19
We will prove the lemmas as a collection of claims. Fix ๐ 0 โฅ ๐ and p ๐ 0 โฅ ๐ with which to
โ
run the algorithm. Suppose ฮฆ(๐ฅ) outputs |๐(๐ฅ)i = ๐ ๐ฅ |0i๐ด |ฮฆ0 (๐ฅ)i + 1 โ ๐ ๐ฅ |1i๐ด |ฮฆ1 (๐ฅ)i, and
let ๐ห denote the estimate output by the algorithm. We will let ๐ ๐ช๐ฅ = ๐ e๐๐ ๐ (๐ฅ) |๐ ๐ฅ๐ ih๐ ๐ฅ๐ | be an
ร
eigenvalue decomposition.
Claim 5.24. If ๐ (๐ฅ) = 0 then kฮ 0 (๐ฅ)|๐0 ik 2 โฅ ๐1 2 .
Proof. Since the algorithm computes ๐ with bounded error, the probability of accepting ๐ฅ is at
most 1/3, so ๐ห โค ๐ฟ with probability at most 1/3.
Amplitude estimation is just phase estimation of a unitary ๐ฮฆ such that |๐(๐ฅ)i is in the
span of eยฑ2๐๐๐ฅ -eigenvectors of ๐ฮฆ , where ๐ ๐ฅ = sin2 ๐๐ฅ , ๐๐ฅ โ [0, ๐/2) [7]. One can show that the
probability of outputting an estimate ๐ห = 0 is sin2 (๐ 0 ๐๐ฅ )/(๐ 02 sin2 (๐๐ฅ )), so
1 sin2 (๐ 0 ๐๐ฅ )
โฅ .
3 ๐ 02 sin2 (๐๐ฅ )
If ๐ 0 ๐๐ฅ โค ๐2 , then this would give:
1 (2๐ 0 ๐๐ฅ /๐)2 4
โฅ = 2,
3 ๐ ๐๐ฅ0 2 2 ๐
which is a contradiction. Thus, we have:
๐ 2๐๐ฅ 1 1 โ 1
๐ 0 ๐๐ฅ > โ > 0 โ sin ๐๐ฅ > โ ๐๐ฅ > .
2 ๐ ๐ ๐0 ๐0
Since ฮฆ(๐ฅ) is the result of running phase estimation, we have
ร sin2 (๐ 0 ๐ ๐ (๐ฅ)/2) ๐2
๐๐ฅ = |h๐ ๐ฅ๐ |๐0 i| 2 โค kฮ ฮ (๐ฅ)|๐0 ik 2 + ,
๐
๐ 02 sin2 (๐ ๐ (๐ฅ)/2) ๐ 02 ฮ2
for any ฮ. In particular, if ฮ is less than the spectral gap of ๐ ๐ช๐ฅ , we have kฮ ฮ (๐ฅ)|๐0 ik =
kฮ 0 (๐ฅ)|๐0 ik, so
1 ๐2
< kฮ 0 (๐ฅ)|๐ 0 ik 2
+ .
๐ 02 ๐ 02 ฮ2
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 42
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
This is true for any choices ๐ 0 โฅ ๐ and ๐ 0 โฅ ๐, so we must have:
1
โค kฮ 0 (๐ฅ)|๐0 ik 2 .
๐2
โ
Claim 5.25. If ๐ (๐ฅ) = 1 and ๐ฟ = 0, then for any ๐ < ๐8 , ฮ ๐๐/๐ (๐ฅ)|๐0 i
2
= 0.
Proof. Suppose towards a contradiction that ฮ ๐๐/๐ (๐ฅ)|๐0 i > 0. Then ๐ ๐ฅ > 0, and some
2
sufficiently large ๐ 0 โฅ ๐ would detect this and cause the algorithm to output 0, so we must
actually have ฮ ๐๐/๐ (๐ฅ)|๐0 i = 0. In fact, in order to sure that no large enough value ๐ 0 detects
2
amplitude > 0 on |0i๐ด , we must have ๐ ๐ฅ = 0 whenever ๐ (๐ฅ) = 1. That means that when ๐ (๐ฅ) = 1,
the algorithm never outputs 0, so the algorithm has one-sided error.
Claim 5.26. There is some constant ๐ such that if ๐ (๐ฅ) = 0 and ๐ฟ > 0 then kฮ 0 (๐ฅ)|๐0 ik 2 > ๐ฟ(1 + ๐).
Proof. Recall that ๐ห โ {sin2 (๐๐/๐ 0) : ๐ = 0, . . . , ๐ 0 โ 1}. We will restrict our attention to
choices ๐ 0 such that for some integer ๐,
๐๐ (๐ + 1/3)๐
sin2 โค ๐ฟ < sin2 .
๐0 ๐0
To see that such a choice exists, let ๐ be such that ๐ฟ = sin2 ๐, and note that the condition holds as
long as ๐ โค ๐๐
0 3๐๐ 0
๐ < ๐ + 1/3 for some ๐, which is equivalent to saying that b ๐ c = 0 mod 3. If
๐
๐พ = b 21 3๐ c, then for any ๐ 0 โฅ ๐, and โ โฅ 0, define:
๐โ = ๐ 0 + โ ๐พ.
Then for any โ > 0,
3๐ 3๐ 3๐ 1 3๐ 1
๐โ โ ๐โ โ1 = ๐พโ โ , ,
๐ ๐ ๐ 2 ๐ 2
so there must be one โ โ {0, . . . , 6} such that b 3๐
๐ ๐โ e = 0 mod 3. In particular, there is some
choice ๐โ satisfying the condition such that (using some ๐ 0 โค โ1 ):
๐ฟ
โ โ ๐ ๐ sin ๐
1
๐ฟ๐โ โค ๐ฟ โ +6 =1+ โค 1 + ๐. (5.2)
๐ฟ 6๐ ๐
We will use this value as our ๐ 0 for the remainder of this proof.
๐
Let ๐ ๐ฅ = sin2 ๐๐ฅ for ๐๐ฅ โ [0, ๐/2]. Let ๐ง be an integer such that ฮ = ๐๐ฅ โ ๐๐ง/๐ 0 has |ฮ| โค 2๐ 0.
2 ๐๐ง
Then the outcome ๐ห = sin ๐ 0 has probability:
๐ 0 โ1 2 ๐ 0 โ1 2
1 ร
๐2๐ก(๐๐ฅ โ๐๐ง/๐ 0 ) 1 ร sin2 (๐ 0ฮ) 4
e = e๐2๐กฮ = โฅ ,
๐ 02 ๐ก=0 ๐ 02 ๐ก=0 ๐ 02 sin2 ฮ ๐2
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 43
S TACEY J EFFERY
since |๐ 0ฮ| โค ๐2 . Thus, by correctness, we must have sin2 (๐๐ง/๐ 0) > ๐ฟ โฅ sin2 ๐
๐๐
0 . Thus ๐ง > ๐, so
(๐ + 1)๐ ๐ง๐ ๐
โค 0 = ๐๐ฅ โ ฮ โค ๐๐ฅ + .
๐ 0 ๐ 2๐ 0
Thus:
(๐ + 1/3)๐ 2๐ ๐
+ โค ๐๐ฅ +
๐ 0 3๐ 0 2๐ 0
๐
(๐ + 1/3)๐
sin + โค sin ๐๐ฅ
๐ 0 6๐ 0
๐ ๐
(๐ + 1/3)๐ (๐ + 1/3)๐ โ
sin cos + cos sin โค ๐๐ฅ
๐ 0 6๐ 0 ๐ 0 6๐ 0
โ ๐ โ ๐
r
โ
๐ฟ 1 โ sin2 + 1 โ ๐ฟ sin โค ๐๐ฅ
6๐ 0 6๐ 0
๐ 2 ๐
When sin2 6๐ 0 โค 1 โ ๐ฟ, which we can assume, the above expression is minimized when sin 6๐ 0
is as small as possible. We have, using ๐ 0 โค 1+๐
โ , from (5.2):
๐ฟ
๐ 4 ๐ฟ
sin2 โฅ โฅ .
6๐ 0
36๐ 0 2 9(1 + ๐)2
Thus, continuing from above, letting ๐ = 9(1+๐)
1
2 , we have:
โ โ โ โ โ
๐ฟ 1 โ ๐๐ฟ + 1 โ ๐ฟ ๐๐ฟ โค ๐ ๐ฅ
p
๐ฟ(1 โ ๐๐ฟ) + (1 โ ๐ฟ)๐๐ฟ + 2๐ฟ ๐(1 โ ๐ฟ)(1 โ ๐๐ฟ) โค ๐ ๐ฅ
Next, notice that (1 โ ๐๐ฟ)(1 โ ๐ฟ) is minimized when ๐ฟ = 1+๐
2๐ , but ๐ฟ โค 2 < 2๐ , so we have, using
1 1+๐
๐ < 1 and ๐ฟ โค 1/2:
โ p
๐ฟ(1 + ๐(1 โ 2๐ฟ) + 2 ๐ (1 โ ๐/2)(1 โ 1/2)) โค ๐ ๐ฅ
โ
๐ฟ(1 + 0 + ๐) โค ๐ ๐ฅ .
Since ฮฆ(๐ฅ) is the result of running phase estimation of ๐ ๐ช๐ฅ for ๐ 0 โฅ ๐ steps, we have:
๐ 0 ๐ ๐ (๐ฅ)
ร sin2 ( 2 )
๐๐ฅ = |h๐ ๐ฅ๐ |๐0 i| 2 ,
๐ ๐ (๐ฅ)
๐ (๐ 0)2 sin2 ( 2 )
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 44
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
so in particular, for any ฮ โ [0, ๐), we have
ร 1
๐ ๐ฅ โค kฮ ฮ (๐ฅ)|๐0 ik 2 + |h๐ ๐ฅ๐ |๐0 i| 2 .
๐:|๐ ๐ (๐ฅ)|>ฮ
(๐ 0)2 sin2 ( ฮ2 )
๐2
โค kฮ ฮ (๐ฅ)|๐0 ik 2 + k(๐ผ โ ฮ ฮ (๐ฅ))|๐0 ik 2 .
(๐ 0)2 ฮ2
In particular, for any ฮ < ฮ where ฮ is the spectral gap of ๐ ๐ช๐ฅ , we have kฮ ฮ (๐ฅ)|๐0 ik =
kฮ 0 (๐ฅ)|๐0 ik, so for any ๐ 0 โฅ ๐, we have
๐2 โ
kฮ 0 (๐ฅ)|๐0 ik 2 + 0
โฅ ๐ ๐ฅ โฅ ๐ฟ(1 + ๐).
(๐ ) ฮ
2 2
Since this holds for any ๐ 0 โฅ ๐, we get
โ
kฮ 0 (๐ฅ)|๐0 ik 2 โฅ ๐ฟ(1 + ๐).
โ
The proof is completed by letting ๐ = ๐.
Claim 5.27. If ๐ (๐ฅ) = 1 and ๐ฟ > 0 then ฮ ๐๐/๐ (๐ฅ)|๐0 i (1 โ ๐ 2 ๐2 /8) โค ๐ฟ.
2
โ
Proof. If |๐i is an e๐๐ -eigenvector of ๐ ๐ช๐ฅ for some |๐| โค ๐๐/๐ < 8/๐, then the probability of
measuring 0 in the phase register upon performing ๐ steps of phase estimation is:
๐โ1 2
1 ร ๐๐ก๐ sin2 ๐๐
๐ ๐ฅ (๐) := 2 e = 2
.
๐ ๐ก=0 ๐ 2 sin2 ๐2
Let ๐(๐ฅ) = 1 โ sin๐ฅ 2 ๐ฅ for any ๐ฅ. It is simple to verify that ๐(๐ฅ) โค ๐ฅ 2 /2 for any ๐ฅ, and ๐(๐ฅ) โ [0, 1]
2
for any ๐ฅ. So we have:
(๐๐/2)2 (1 โ ๐(๐๐/2)) ๐ 2 ๐2
๐ ๐ฅ (๐) โฅ โฅ 1 โ ๐(๐๐/2) โฅ 1 โ .
๐ 2 (๐/2)2 (1 โ ๐(๐/2)) 8
Thus, we conclude that
๐ 2 ๐ 2 ๐2 ๐ 2 ๐2
๐ ๐ฅ โฅ ฮ ๐๐/๐ (๐ฅ)|๐0 i .
2 2
1โ = ฮ ๐๐/๐ (๐ฅ)|๐ i 1 โ
8 ๐2
0
8
If this is > ๐ฟ, then with some sufficiently large ๐ 0 โฅ ๐, amplitude estimation would detect this
and cause the algorithm to output 0 with high probability.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 45
S TACEY J EFFERY
Acknowledgements
I am grateful to Tsuyoshi Ito for discussions that led to the construction of approximate span
programs from two-sided error quantum algorithms presented in Section 3.3, and to Alex
B. Grilo and Mario Szegedy for insightful comments. I am grateful to Robin Kothari for pointing
out the improved separation between certificate complexity and approximate degree in [8],
which led to an improvement in from (log ๐)7/6 (using [1]) to (log ๐)2โ๐(1) in Theorem 5.3. I thank
Robert Robere for pointing me to a separation between formula size and monotone formula
size for XOR-SAT. Finally, I thank the anonymous reviewers, whose feedback has improved the
presentation of these results.
References
[1] Scott Aaronson, Shalev Ben-David, and Robin Kothari: Separations in query com-
plexity using cheat sheets. In Proc. 48th STOC, pp. 863โ876. ACM Press, 2016.
[doi:10.1145/2897518.2897644, arXiv:1511.01937, ECCC:TR15-175] 6, 46
[2] Noga Alon, Troy Lee, Adi Schraibman, and Santosh Vempala: The approximate rank of a
matrix and its algorithmic applications. In Proc. 45th STOC, pp. 675โ684. ACM Press, 2013.
[doi:10.1145/2488608.2488694, ECCC:TR12-169] 8
[3] Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System
Sci., 64(4):750โ767, 2002. Preliminary version in STOCโ00. [doi:10.1006/jcss.2002.1826,
arXiv:quant-ph/0002066] 11
[4] Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge
Univ. Press, 2009. Book. 4
[5] Lรกszlรณ Babai, Anna Gรกl, and Avi Wigderson: Superpolynomial lower bounds for monotone
span programs. Combinatorica, 19(3):301โ319, 1999. [doi:10.1007/s004930050058] 4, 5, 25
[6] Howard Barnum, Michael E. Saks, and Mario Szegedy: Quantum query complexity and
semi-definite programming. In Proc. 18th IEEE Conf. on Comput. Complexity (CCCโ03), pp.
179โ193. IEEE Comp. Soc., 2003. [doi:10.1109/CCC.2003.1214419] 11
[7] Gilles Brassard, Peter Hรธyer, Michele Mosca, and Alain Tapp: Quantum amplitude
amplification and estimation. In Samual J. Lomonaca and Howard E. Brandt, editors,
Quantum Computation and Quantum Information: A Millennium Volume, pp. 53โ74. Amer.
Math. Soc., 2002. [doi:10.1090/conm/305, arXiv:quant-ph/0005055] 10, 42
[8] Mark Bun and Justin Thaler: A nearly optimal lower bound on the approximate
degree of ๐ด๐ถ 0 . SIAM J. Comput., 49(4):59โ96, 2020. Preliminary version in FOCSโ17.
[doi:10.1137/17M1161737, arXiv:1703.05784, ECCC:TR17-051] 6, 33, 46
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 46
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
[9] Bill Fefferman and Cedric Yen-Yu Lin: A complete characterization of unitary quan-
tum space. In Proc. 9th Innovations in Theoret. Comp. Sci. Conf. (ITCSโ18), pp. 4:1โ21.
Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.4,
arXiv:1604.01384] 7
[10] Bill Fefferman and Zachary Remscrim: Eliminating intermediate measurements in space-
bounded quantum computation. In Proc. 53rd STOC, pp. 1343โ1356. ACM Press, 2021.
[doi:10.1145/3406325.3451051, arXiv:2006.03530, ECCC:TR20-088] 2, 9
[11] Anna Gรกl: A characterization of span program size and improved lower bounds for
monotone span programs. Comput. Complexity, 10(4):277โ296, 2001. Preliminary version in
STOCโ98. [doi:10.1007/s000370100001] 4, 5, 25, 27, 29
[12] Uma Girish, Ran Raz, and Wei Zhan: Quantum logspace algorithm for powering matrices
with bounded norm. In Proc. 48th Internat. Colloq. on Automata, Languages, and Program-
ming (ICALPโ21), pp. 73:1โ20. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2021.
[doi:10.4230/LIPIcs.ICALP.2021.73, arXiv:2006.04880, ECCC:TR20-087] 2, 9
[13] Mika Gรถรถs, Pritish Kamath, Robert Robere, and Dmitry Sokolov: Adventures in
monotone complexity and TFNP. In Proc. 10th Innovations in Theoret. Comp. Sci.
Conf. (ITCSโ19), pp. 38:1โ19. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2019.
[doi:10.4230/LIPIcs.ITCS.2019.38, ECCC:TR18-163] 37
[14] Peter Hรธyer, Troy Lee, and Robert ล palek: Negative weights make adversaries stronger.
In Proc. 39th STOC, pp. 526โ535. ACM Press, 2007. [doi:10.1145/1250790.1250867] 11
[15] Tsuyoshi Ito and Stacey Jeffery: Approximate span programs. Algorithmica, 81(6):2158โ2195,
2019. Preliminary version in ICALPโ16. [doi:10.1007/s00453-018-0527-1, arXiv:1507.00432]
2, 9, 10, 12, 13, 14, 17, 18, 19, 37
[16] Stacey Jeffery: Frameworks for Quantum Algorithms. Ph. D. thesis, University of Waterloo,
2014. Available at http://uwspace.uwaterloo.ca/handle/10012/8710. 19
[17] Stacey Jeffery: Span programs and quantum space complexity. In Proc. 11th Innovations
in Theoret. Comp. Sci. Conf. (ITCSโ20), pp. 4:1โ37. Schloss DagstuhlโLeibniz-Zentrum fuer
Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.4, arXiv:1908.04232] 1
[18] Stacey Jeffery and Shelby Kimmel: Quantum algorithms for graph connectivity and formula
evaluation. Quantum, 1:26:1โ40, 2017. [doi:10.22331/q-2017-08-17-26, arXiv:1704.00765] 37
[19] Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous: Matchgate and space-
bounded quantum computations are equivalent. Proc. Royal Soc. A, 466(2115):809โ830, 2010.
[doi:10.1098/rspa.2009.0433] 7
[20] Mauricio Karchmer and Avi Wigderson: On span programs. In Proc. 8th IEEE
Conf. Structure in Complexity Theory (SCTโ93), pp. 102โ111. IEEE Comp. Soc., 1993.
[doi:10.1109/SCT.1993.336536] 2, 11, 12
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 47
S TACEY J EFFERY
[21] Alexei Y. Kitaev: Quantum measurements and the Abelian stabilizer problem. Electron.
Colloq. Comput. Complexity, TR96-003, 1996. [ECCC, arXiv:quant-ph/9511026] 9
[22] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert ล palek, and Mario Szegedy: Quantum
query complexity of state conversion. In Proc. 52nd FOCS, pp. 344โ353. IEEE Comp. Soc.,
2011. [doi:10.1109/FOCS.2011.75] 8
[23] Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Found. Trends
Theor. Comp. Sci., 4(1โ2):1โ155, 2009. [doi:10.1561/0400000011] 25
[24] Toniann Pitassi and Robert Robere: Strongly exponential lower bounds for monotone com-
putation. In Proc. 49th STOC, pp. 1246โ1255. ACM Press, 2017. [doi:10.1145/3055399.3055478,
ECCC:TR16-188] 5, 28, 31, 36
[25] Alexander A. Razborov: Applications of matrix methods to the theory of lower bounds in
computational complexity. Combinatorica, 10(1):81โ93, 1990. [doi:10.1007/BF02122698] 4,
25, 27, 29
[26] Alexander A. Razborov: On submodular complexity measures. In Proc. London Math. Soc.
Symposium on Boolean Function Complexity, pp. 76โ83, 1992. Authorโs website. 27
[27] Ben W. Reichardt: Span programs and quantum query complexity: The general adversary
bound is nearly tight for every Boolean function. In Proc. 50th FOCS, pp. 544โ551. IEEE
Comp. Soc., 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759] 2, 3, 10, 11, 12, 19, 37
[28] Ben W. Reichardt and Robert ล palek: Span-program-based quantum algorithm for
evaluating formulas. Theory of Computing, 8(13):291โ319, 2012. Preliminary version in
STOCโ08. [doi:10.4086/toc.2012.v008a013] 2, 11
[29] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook: Exponential
lower bounds for monotone span programs. In Proc. 57th FOCS, pp. 406โ415. IEEE Comp.
Soc., 2016. [doi:10.1109/FOCS.2016.51, ECCC:TR16-064] 5, 6, 31, 34
[30] Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969โ2000,
2011. [doi:10.1137/080733644, arXiv:0906.4291] 6, 31, 34
[31] John Watrous: Space-bounded quantum complexity. J. Comput. System Sci., 59(2):281โ326,
1999. [doi:10.1006/jcss.1999.1655] 6
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 48
S PAN P ROGRAMS AND Q UANTUM S PACE C OMPLEXITY
AUTHOR
Stacey Jeffery
Senior researcher
CWI & QuSoft
Amsterdam
The Netherlands
jeffery cwi nl
https://homepages.cwi.nl/~jeffery/
ABOUT THE AUTHOR
Stacey Jeffery started her academic career as an undergraduate philosophy student
at McMaster University, before reading the book Gรถdel, Escher, Bach: An Eternal
Golden Braid, after which she transfered to a Computer Science program at
the University of Waterloo. She got her Ph. D. in Computer Science from the
University of Waterloo under the supervision of Michele Mosca in 2014, before
spending two and a half years as a postdoc at Caltech at the Insitute for Quantum
Information and Matter. She now lives in Amsterdam with her husband and
two-year-old daughter, who enjoys bedtime stories read from Theory of Computing.
T HEORY OF C OMPUTING, Volume 18 (11), 2022, pp. 1โ49 49