The Solovay-Kitaev theorem shows that we can approximate arbitrary unitary transformations with polynomially many quantum gates. Can we approximate the resulting state vectors in the same way by specifying the quantum states of pairs (or possibly more) of qubits? I.e. if we have $\psi_{i,j}$ be the approximate state of the qubits $i$ and $j$, is this enough to approximate the entire quantum state?

Cross-posted on physics

  • 2
    $\begingroup$ The Solovay-Kitaev Theorem shows that if you want to approximate a single-qubit gate to accuracy $\epsilon$, you need a sequence of $O(\log(1/\epsilon)^k)$ gates from a finite set such as $H$ and $T$. More modern techniques have show $k=1$. It does not, by itself, talk about many qubits. $\endgroup$
    – DaftWullie
    Mar 6, 2020 at 11:10
  • $\begingroup$ Is this arxiv.org/abs/2203.00811 what you have in mind? $\endgroup$ Mar 7 at 18:10


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.