Is quantum computer equivalent to Turing machine with matrix multiplication oracle?

Question

Since quantum computer with $n$ qubits is described by a $2^{n}\times2^{n}$ unitary matrix is it equivalent to an oracle that can do multiplication of large matrix and return $n$ numbers computed from it in a time polynomial by $n$.

And if yes how precise the number representation in the oracle should be, should the precision increase exponentially with $n$?

Edit: as pointed out the oracle should not simply multiply, but should expand $n$ bit string into $2^n$ corresponding to a pure state, work only for unitary matrices, and return n bits corresponding to measurement, and not arbitrary numbers. Are there some other such corrections to make a representation with oracle possible?

Answer 1

The answer is no.

The reason for this is the exponential size of the Hilbert space. Consider a single-tape TM with a matrix multiplication (MM) oracle which calculates the action of any unitary matrix on a vector of complex numbers. We'll define its input format as follows:

$[U][x][\alpha_0 \ldots \alpha_{x-1}]$ where:

• $U$ is some symbol or series of symbols specifying the unitary transformation to perform (easily done in polynomial space)
• $x$ is a binary encoding of the number of complex numbers in the input vector
• $\alpha_0 \ldots \alpha_{x-1}$ is some encoding of $x$ complex numbers separated by a symbol

The MM oracle reads this input format, applies $U$ to $\alpha_0 \ldots \alpha_{x-1}$, then overwrites those numbers with the output $\alpha_0' \ldots \alpha'_{x-1}$ in a single step.

The key here is that for $n$ qbits, $x = 2^n$ because of entanglement. When the qbits become entangled, their product state cannot be factored into $n$ individual qbit states and thus the $2^n$-sized vector must be maintained in memory. This trivially means that our TM takes exponential time to write the input vector for the MM oracle, and would also take exponential time to calculate the effect of measuring the state vector.

Edit: to answer your revised question, if you have tensor expansion, unitary matrix multiplication, and measurement oracles, then yes you have a quantum computer. We know this because this is the exact model used by all quantum programming languages. We write a classical-looking algorithm with these three oracles and all the magic is done under the hood.