  Quantum computations promise the ability to solve problems intractable in the
classical setting. Restricting the types of computations considered often
allows to establish a provable theoretical advantage by quantum computations,
and later demonstrate it experimentally. In this paper, we consider
space-restricted computations, where input is a read-only memory and only one
(qu)bit can be computed on. We show that $n$-bit symmetric Boolean functions
can be implemented exactly through the use of quantum signal processing as
restricted space quantum computations using $O(n^2)$ gates, but some of them
may only be evaluated with probability $1/2 + O(n/\sqrt{2}^n)$ by analogously
defined classical computations. We experimentally demonstrate computations of
$3$-, $4$-, $5$-, and $6$-bit symmetric Boolean functions by quantum circuits,
leveraging custom two-qubit gates, with algorithmic success probability
exceeding the best possible classically. This establishes and experimentally
verifies a different kind of quantum advantage -- one where quantum scrap space
is more valuable than analogous classical space -- and calls for an in-depth
exploration of space-time tradeoffs in quantum circuits.
