In quantum computing, operation by 2 subsequent gates counts as O(1) step, however, if we have to simulate the same operation using a classical computer, we will need to multiply 2 unitary matrices. If classically, each element of the two n x n unitary matrices is represented by m bits, what is the complexity?

  • $\begingroup$ I think the question is unclear: You should at minimum specify your model of computation over the reals. Are you thinking of Blum–Shub–Smale, type 1, or type 2 computability, or something else? $\endgroup$ yesterday


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.