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$ – Peter Shor Sep 27 '20 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 '20 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.