If I understand correctly, there must exist unitary operations that can be approximated to a distance $\epsilon$ only by an exponential number of quantum gates and no less.

However, by the Solovay-Kitaev theorem, any arbitrary unitary operation in $n$ qubits, with $n$ fixed, can be approximated to a distance of $\epsilon$ using poly(log(1/$\epsilon$)) universal gates.

Don't these two statements appear contradictory? What am I missing?

  • 2
    $\begingroup$ In your statement, the number of gate is exponential with respect to what? The precision? $\endgroup$ – Nelimee Jul 26 '18 at 17:33
  • 1
    $\begingroup$ I guess the number of qubits. I think I get it now. Keeping the precision fixed, there can be unitaries requiring an exponential number of gates to simulate, with respect to the number of qubits. In contrast, by the Solovay Kitaev theorem, keeping the number of qubits fixed, the number of universal quantum gates for simulation scales polynomially with respect to the precision. Is that what it is? $\endgroup$ – BlackHat18 Jul 26 '18 at 17:43
  • 3
    $\begingroup$ Yes, exactly - you’re comparing scaling with respect to two different parameters: achievable accuracy for a single qubit gate as a function of the number of gates for some finite universal set, and the number of gates required to achieve a given accuracy for unitaries as a function of the number of qubits the unitary acts on. $\endgroup$ – DaftWullie Jul 26 '18 at 18:00
  • $\begingroup$ If the question is no longer being asked, @BlackHat18 could explain why as an answer themselves. What is the policy on this? $\endgroup$ – AHusain Jul 27 '18 at 21:52
  • 1
    $\begingroup$ @AHusain BlackHat18 self-answering is allowed and encouraged $\endgroup$ – glS Jul 30 '18 at 10:05

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.