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

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?

• I would expect having the matrix multiplication oracle to be more powerful, since e.g. you haven't limited it to unitary matrices and haven't given a limitation on which $n$ outputs you get. It sounds like this would be as powerful as a Post-BQP machine instead of just a quantum computer. – Craig Gidney Feb 11 at 19:49
• Wouldn't the TM also require the ability to manipulate exponential-sized state vectors in polynomial time? Otherwise creating the inputs and using the outputs of the matrix oracle would require exponential time. So would measurement. – ahelwer Feb 12 at 0:57
• @ahelwer TM would pass n bit vector equivalent to pure state, and would get back n bits equivalent to measurement. As far as i understand quantum computer has to start from a pure state as well. – a user Feb 12 at 8:43
• Comments are not for extended discussion; the previous meta-discussion about the suitability of this question on our site has been moved to chat. – Sanchayan Dutta Feb 12 at 16:03
• This paper is relevant. arxiv.org/abs/1604.01384. The authors show that inverting a succicntly-described, well-conditioned matrix is complete for the class of quantum circuits with all measurements deferred to the end. If you're allowed polynomially many qubits, this is basically the same as normal BQP. – Jalex Stark Feb 16 at 11:42

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.

• OK, how about a matrix multiplication oracle and a tensor expansion oracle (duplicate each 2^n slice of a vector in a single step, with n being a parameter)? – John Dvorak Feb 12 at 17:35
• ... actually, I think you'd need a different oracle than the one I proposed – John Dvorak Feb 12 at 17:37
• At this point you're not far from the actual definition of a quantum TM and might as well use that! – ahelwer Feb 12 at 17:41
• @ahelwer thanks for clarification. The reason i am trying to find representation as a turing machine, is to understand if the power of the quantum computer comes only from exponential size of the Hilbert space, or the precision of amplitudes needs to increase exponentially as well. – a user Feb 13 at 20:02
• Scott Aaronson responds to this objection that exponentially-small amplitudes are unphysical here. It's believed that the source of quantum speedups has more to do with the exponential size of the Hilbert space and manipulation of its elements through entanglement, but if you're interested in that question I encourage you to ask about it directly. – ahelwer Feb 13 at 21:10