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$ 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$ Sep 27, 2020 at 11:16
  • $\begingroup$ No, $\mathrm{BQP}$ is already in $\mathrm{PSPACE}$ and representing $\log n$ qubits already requires linear space. $\endgroup$
    – botsina
    Sep 27, 2020 at 13:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.