Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said:
The encoding disallows compression: it is not possible to work with encoding schemes that allow for extremely short (e.g., polylogarithmic-length) encodings of circuits; so for simplicity it is assumed that the length of every encoding of a quantum circuit is at least the size of the circuit.
My question:
Why is it impossible to work with polylogarithmic-length encoding schemes for quantum circuits?
Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time.
But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you don't sneak non-polynomial amounts of work into the encoding. You don't want "repeat the diffusion operator $\sqrt{2}^n$ times" to count as being in BQP with respect to $n$.
