<p>Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much of the entanglement information is lost by approximation on average for each individual gate and changing which qubits are hashed and not is a unitary transformation without subsequent loss of information.) Does unitarity provide a barrier to the accumulation of errors over many quantum gates such that errors in probability amplitudes at most add up (since unitary transformations preserve inner products), implying that <span class="math-container">$\mathrm{BPP}=\mathrm{BQP}$</span>?</p>

CC BY-SA 4.0
2020-09-27T11:16:33.920Z
So you're trying to represent the action of $n$ quantum bits by $\mathrm{polylog} n$ quantum bits. Isn't this impossible because of the [space hierarchy theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem)?
Peter Shor 
CC BY-SA 4.0
2020-09-27T13:40:49.477Z
No, $\mathrm{BQP}$ is already in $\mathrm{PSPACE}$ and representing $\log n$ qubits already requires linear space.
botsina
<quantum-computing>
Does the approximatibility of individual gates together with unitarity imply BPP=BQP
botsina
# Does the approximatibility of individual gates together with unitarity imply BPP=BQP

(Asked by: username_0 on 2020-09-27)

Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much of the entanglement information is lost by approximation on average for each individual gate and changing which qubits are hashed and not is a unitary transformation without subsequent loss of information.) Does unitarity provide a barrier to the accumulation of errors over many quantum gates such that errors in probability amplitudes at most add up (since unitary transformations preserve inner products), implying that $\mathrm{BPP}=\mathrm{BQP}$?

**Tags:** quantum-computing

> **Comments:**
> **username_1**: So you're trying to represent the action of $n$ quantum bits by $\mathrm{polylog} n$ quantum bits. Isn't this impossible because of the [space hierarchy theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem)?  
> **username_0**: No, $\mathrm{BQP}$ is already in $\mathrm{PSPACE}$ and representing $\log n$ qubits already requires linear space.  

---

## 0 answers

