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}$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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? $\endgroup$– Peter ShorSep 27 '20 at 11:16
-
$\begingroup$ No, $\mathrm{BQP}$ is already in $\mathrm{PSPACE}$ and representing $\log n$ qubits already requires linear space. $\endgroup$– botsinaSep 27 '20 at 13:40
Add a comment
|