1
$\begingroup$

I have a unitary matrix of dimension $N$, and I want to approximate it using a quantum circuit.

I know that the Solovay-Kitaev theorem gives an algorithm that takes $2^{O(N^2)}$ steps. Is this the best possible solution? Are there lower bounds for it?

My guess is that it may be possible to approximate it with a polynomial (in $N$) number of gates, as preparing a quantum state of dimension $N$ is doable in $O(\text{poly}(N))$ time.

$\endgroup$
2
  • $\begingroup$ Are you looking for some sort of Quantum Approximate Optimization Algorithm (QAOA)? Generally, the number of parameters to account for will be quite large for large N. $\endgroup$ Apr 2 at 17:39
  • $\begingroup$ @Zarathustra not exactly. I have a unitary matrix given as input (so its dimension is polynomial) and I want to implement such transformation. $\endgroup$
    – NYG
    Apr 3 at 7:02

2 Answers 2

3
$\begingroup$

I'm not sure where you are getting an exponential number of steps. Let $\mathcal{G}$ be a finite set of generators for $SU(N)$ that is closed under inverses. The Solovay-Kitaev theorem says that for any $N\times N$ unitary $U$ there exists a word $G_1\cdots G_\ell$ of $N\times N$ unitary (gates) from $\mathcal{G}$ (of length $\ell$) that approximates $U$ with error $\epsilon$ (in operator norm). Where not only is $\ell$ at most $O(\log^c(1/\epsilon)$ (for universal constant $c>0$), but the algorithm for finding the word is efficient (that is it runs in time $poly(\log^c(1/\epsilon)$). The difficulty is finding a universal gate-set $\mathcal{G}$ for arbitrary $N$. For $N=2$ the Clifford+T gate set works rather nicely, but indeed I don't know of universal gate sets for $N>2$.

$\endgroup$
2
  • $\begingroup$ This quite confuses me... Also Childs in his lecture notes cs.umd.edu/~amchilds/qa/qa.pdf says that you need an exponential number of steps in $N^2$ to synthesize the circuit $\endgroup$
    – NYG
    Apr 4 at 8:41
  • $\begingroup$ Perhaps he is referring to unitaries acting on $n$-qubits, which have dimension $2^n$, so the algorithm would be exponential in the number of qubits, not the dimension of the space. If this is not the source confusion, please let me know which page of the notes you are referring to. $\endgroup$
    – Condo
    Apr 6 at 22:24
1
$\begingroup$

A line of research might be, if you have a way to write your unitary as $U = e^{A}$ for some complex matrix $A$. Then you can use the Lie-Trotter or Suzuki-Trotter decomposition to approximate your unitary with an arbitrary precision (depending on the number of gates you want to use).

That is what is usually done in QAOA where one tries to approximate a unitary evolution $U= e^{-iH}$ by rotation gates $R_x,R_y,R_z$.

$\endgroup$
1
  • $\begingroup$ An alternative (similar to this approach) is to block-encode $H$ in some way and then implement $U = e^{iH}$ using quantum singular value transformation. The concern at this point would be whether block encoding an Hamiltonian $H$ of polynomial size is always possible in polynomial time $\endgroup$
    – NYG
    Apr 4 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.