  The traditional definition of quantum zero-knowledge stipulates that the
knowledge gained by any quantum polynomial-time verifier in an interactive
protocol can be simulated by a quantum polynomial-time algorithm. One drawback
of this definition is that it allows the simulator to consume significantly
more computational resources than the verifier. We argue that this drawback
renders the existing notion of quantum zero-knowledge not viable for certain
settings, especially when dealing with near-term quantum devices.
  In this work, we initiate a fine-grained notion of post-quantum
zero-knowledge that is more compatible with near-term quantum devices. We
introduce the notion of $(s,f)$ space-bounded quantum zero-knowledge. In this
new notion, we require that an $s$-qubit malicious verifier can be simulated by
a quantum polynomial-time algorithm that uses at most $f(s)$-qubits, for some
function $f(\cdot)$, and no restriction on the amount of the classical memory
consumed by either the verifier or the simulator. We explore this notion and
establish both positive and negative results:
  - For verifiers with logarithmic quantum space $s$ and (arbitrary) polynomial
classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be
achieved based on the existence of post-quantum one-way functions. Moreover,
our protocol runs in constant rounds.
  - For verifiers with super-logarithmic quantum space $s$, assuming the
existence of post-quantum secure one-way functions, we show that
$(s,f)$-space-bounded QZK protocols, with fully black-box simulation (classical
analogue of black-box simulation) can only be achieved for languages in BQP.
