6
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Craig Gidney
    Feb 11, 2019 at 19:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – ahelwer
    Feb 12, 2019 at 0:57
  • $\begingroup$ @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. $\endgroup$
    – a user
    Feb 12, 2019 at 8:43
  • $\begingroup$ Comments are not for extended discussion; the previous meta-discussion about the suitability of this question on our site has been moved to chat. $\endgroup$
    – Sanchayan Dutta
    Feb 12, 2019 at 16:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jalex Stark
    Feb 16, 2019 at 11:42

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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)? $\endgroup$
    – John Dvorak
    Feb 12, 2019 at 17:35
  • $\begingroup$ ... actually, I think you'd need a different oracle than the one I proposed $\endgroup$
    – John Dvorak
    Feb 12, 2019 at 17:37
  • $\begingroup$ At this point you're not far from the actual definition of a quantum TM and might as well use that! $\endgroup$
    – ahelwer
    Feb 12, 2019 at 17:41
  • $\begingroup$ @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. $\endgroup$
    – a user
    Feb 13, 2019 at 20:02
  • $\begingroup$ 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. $\endgroup$
    – ahelwer
    Feb 13, 2019 at 21:10

Your Answer

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

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