A quantum circuit can use any unitary operator. Its matrix is exponential in the number of input bits. In practice how can this ever be possible (aside from operators which are tensor products), i.e. how can you construct exponential size matrix?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The key is that you don't actually construct a matrix. Yes, if you wanted to simulate a quantum computation on a classical computer, one method is to build the corresponding unitary matrix, and this is essentially why (unless there's special structure) it's impossible to efficiently perform a classical simulation of quantum computation.
However, think on this point: if I have an $n$-qubit quantum system and I do nothing to it, that is described by a $2^n\times 2^n$ identity matrix. So, by your way of thinking, I have constructed a special case of an exponential size matrix. But the point is that we just do some operation. It might be represented by a matrix, but we never look at that matrix, never construct it.
The basic quantum operations that we use are thought about in this way - you only really do anything to one or two qubits at a time and you make it exponential size by adding identities ("do nothing") to all the other qubits. Combining a small number of these acting on different sets of qubits can create some unitary matrices that are not tensor products.
Now, while a quantum computer can in principle implement any unitary operator, universality in that sense doesn't say anything about how long the construction takes. The vast, overwhelming, majority of them do take exponential time to implement. Quantum computation is specifically interested in finding that Goldilocks zone, those small number of instances which can be implemented in polynomial time and give an interesting computation that cannot be computed in polynomial time on a classical computer.
answered Apr 23, 2019 at 7:17
$\begingroup$
$\endgroup$
Note that there is nothing specifically quantum about this.
An arbitrary classical operation over $n$ bits can also be represented as a $2^n\times2^n$ matrix, describing where each input bitstring is sent by the operation. Such matrices are permutation matrices for deterministic operations (in which case using matrices is a bit pointless as there is no notion of "linear combinations of inputs"), or more generally stochastic matrices if one wants to also describe probabilistic processes.
The dimension of these matrices also clearly increases exponentially with the number of bits, but this is a non-issue, as it has no connection with how difficult it actually is to implement the corresponding operation, for the reasons laid out in the other answer.
