5
$\begingroup$

In this paper there is this sentence:

[...] the description of a $2^n\times2^n$ unitary matrix $U$ (which is a poly($n$)-size quantum circuit)

According to the meaning of "which" in English, in contrast to "that", the sentence means that the effect of any unitary matrix $U$ can be done by a quantum circuit composed by $m$ quantum gates, with $m$ polynomial in the number of qubits $n$. I assume that the quantum gates act on 1 or 2 qubits (or a fixed number of qubit), else the sentence is trivial ($U$ is a quantum gate itself).

However, I think that this is not true. In particular, I think that an $m$ exponential in $n$ is needed for preparing an arbitrary state, which is a simpler task than simulating the effect of an arbitrary $U$. Can you confirm and suggest a reference?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ I think they meant a circuit U that is poly(n)-size. Here's the intuition as to why you would need an exponential number of qubits for an arbitrary U: even if you only had 1s and 0s in U, then there are still $2^n!$ possible $2^n$ x $2^n$ unitaries that you can have. However, there are only poly(n)! possible poly(n)-size quantum circuits you can build. Therefore, there cannot possibly exist a one-to-one mapping between the two which means you can't build an arbitrary U with a poly(n)-size quantum circuit even under the condition that U only consists of 1s and 0s. $\endgroup$
    – Dani007
    Dec 27, 2021 at 21:23

2 Answers 2

Reset to default
2
$\begingroup$

I believe this Q&A answers your question about decomposition in detail: Minimum number of 2 qubit gates to build any unitary

In short, you are correct that the lower bound for a number of 2-qubit gates necessary to implement an arbitrary unitary $U$ is $\Omega(4^n)$ where $n$ is the number of qubits.

I am not entirely sure what authors meant, but perhaps it is a statement of assumption, vs a general assertion (i.e. the input is an unitary $U$ that can be described by a circuit that is $poly(n)$. I'd definitely recommend reaching out to the authors for clarification!

Improve this answer
$\endgroup$
3
$\begingroup$

A canonical reference for gate decompositions is

Barenco et al., Elementary gates for quantum computation.

In particular, it also contains recipes to decompose an arbitrary $n$-qubit unitary into elementary gates (which, by parameter counting, requires about $4^n$ gates, assuming each gate has one real parameter.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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