0
$\begingroup$

The Solovay-Kitaev algorithm gives a construction to $\epsilon$-approximate any $m$-qubit unitary $U$ with $O(m \log(m/\epsilon))$ elementary gates, provided $m$ is a constant.

My question is: if the dimension of $U$ is polynomial in the input size, is it possible to approximate it in polynomial time?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Do you mean $m$ is polynomial in the input size? Because the dimension of $U$ is exponential in $m$. $\endgroup$ Commented Feb 29, 2024 at 23:29
  • $\begingroup$ @ChrisD no, I mean that the dimension is polynomial, meaning that $m$ is logarithmic in the input size. If $m$ is polynomial then it should not be possible to approximate any unitary efficiently. $\endgroup$ Commented Mar 1, 2024 at 10:42
  • 1
    $\begingroup$ The algorithm assumes you have a lookup table of initial approximations to some fixed precision, which in turn requires you to enumerate all possible gate sequences up to some fixed length which scales as $\mathrm{dim}(U)^2$. This enumeration is exponential in this length, so rapidly becomes impractical as $\mathrm{dim}(U)$ increases. $\endgroup$ Commented Mar 1, 2024 at 19:52

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.