<p>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.</p>

<p>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$.</p>

CC BY-SA 3.0
2016-07-26T04:44:01.627Z
2016-07-26T04:44:01.627Z
Craig Gidney
<p>I am going through <a href="https://arxiv.org/abs/0804.3401" rel="nofollow">Quantum Computational Complexity</a> by John Watrous. On page $12$, he said:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p><strong>My question:</strong></p>

<p>Why is it impossible to work with polylogarithmic-length encoding schemes for quantum circuits?</p>

<cc.complexity-theory><quantum-computing><circuit-complexity><quantum-information><physics>
Why is it impossible to work with polylog length encoding schemes for quantum circuits?
Omar Shehab
# Why is it impossible to work with polylog length encoding schemes for quantum circuits?

(Asked by: username_0 on 2016-07-26)

I am going through [Quantum Computational Complexity](https://arxiv.org/abs/0804.3401) 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?

**Tags:** cc.complexity-theory, quantum-computing, circuit-complexity, quantum-information, physics

---

## 1 answers

### Answer by username_1 on 2016-07-26. Score: 6 | Accepted answer

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$.


---

