Quantum Computing Simulation: Possibilities & Limitations

[WhoOrderedThat]

Is it theoretically possible to simulate a quantum computer by a real one (ie a Turing machine equivalent) even approximately? Any comments? Sorry if this has already been discussed.

 

[Physics Monkey]

One can in principle accurately simulate a quantum computer on a classical computer, but it is completely impractical. Imagine a quantum computer with only 100 qubits, the computer has a Hilbert space of dimension 2^{100}, and so a classical computer would have to represent the density matrix of the quantum system as a complex 2^{100} \times 2^{100} matrix. Similarly, quantum logic gates would correspond to mutliplication by matrices of the same size. This is clearly computationally prohibitive on any classical computer.

This shows another reason why a quantum computer would be nice thing to have: it would allow us to simulate quantum systems that are currently intractable on classical computers with quantum computers. This was first pointed out by Feynman.

 

[George Jones]

Papers have been written about quantum "hypercomputers" that can compute things that are not Turing computable.

I do not know if these papers should be taken seriously.

Search on http://arxiv.org/" for "hypercomputation" and/or (author) Kieu.

Regards,
George

 

[Physics Monkey]

Hi guys,

I have heard of this notion of "hypercomputing" in passing, and I have skimmed a few papers before. My knowledge lies more in the area of what these people call "standard quantum computing", so I can't categorically state that what they are talking about it is unphysical. However, it seems to me that in skimming these papers I saw a lot of words like "uncountable" and "infinite", words that make me nervous and ring of unphysical systems. If I had to hazard a guess, I would say that there may be some absract mathematical sense in which such hypercomputations are possible, but I tend to doubt they are physically realizable. It seems clear to me that if you have finite system of qubits interacting through some Hamiltonian, then you can model the dynamics of the quantum state on a classical computer using the method I described above. I would certainly welcome anyone setting me straight on this if I have missed something obvious.

 

[WhoOrderedThat]

Thanks for your thoughts and assistance, they and their creators' efforts are very much appreciated

This is probably going a bit off topic in a sense, but if our brains _were_ Turing machine equivalents, would they then be theoretically capable of conceiving realistic theories about the workings of the above-mentioned non Turing - compatible systems/effects?

Are such theories provable, as it would seem they might not be simulatable on a Turing equivalent machine.

Or, if we can conceive such theories, does that imply our brains are not Turing compatible in some realistic sense?

Is it true that no real world machine can really be 100% Turing compatible? in other words, are real-world machines always subject to quantum error? (i.e. a bit-flip that fails due to quantum effects)

Do we have a theory of computation that takes quantum uncertainty in any real machines into account?

 

[-Job-]

You can model a Quantum computer running on problems of small size n, with a parallel computer with 2^n processors. Suppose you have a Quantum computer that runs only on inputs of size n or less (for no reason :P), then any such computers can be modeled with a network of 2^n parallel processors, albeit probably with some overhead.
Hence you can say that you can model any Quantum Computer running on any input (inputs have finite size) with a massive parallel network. Of course i haven't heard that Quantum Computers have restricted input size, so if a quantum computer can run on inputs of any size, you'd need an infinitely large parallel network to be able to do whatever that Quantum Computer can (as fast).
This means you can model a run of an algorithm on an input of finite size on a Quantum Computer with a Turing Machine, but you can't create a Turing Machine that is a Quantum Computer. The way i picture a Quantum Computer is as a machine that can dynamically allocate a parallel Turing Machine network of of any size, and use it. This is something a Turing Machine can't do, because a Turing Machine is either sequential or finitely parallel, so it may be able to create such a network of any size, but will only be able to use it sequentially or in a finitely parallel manner. However the difference pointed out here is only in speed of execution, which doesn't go against their equivalence.

 

[WhoOrderedThat]

Thanks -Job- for the concrete explanation.

Questions cross my mind regarding the granularity / resolution of the simulation. Is there some limit to the accuracy? (Until we get down to the resolution of the Plank length/time?)

To me it seems that there is likely to be some finite limit to the number of qubits (qN) in any real (manufacturable) quantum computer, just as there practical capacity limits with any manufacturable Turing equivalent computer. Of course, you may not mean 'manufacturable'. And if the universe is a quantum computer, then it may well not be finite.

But this does raise the question "Can you simulate a quantum computer of capacity M by using another quantum computer of capacity N where N < M?

In other words, can you simulate a larger capacity quantum computer with one of less capacity? (that will presumably take longer the run the same program because it is in "emulation mode"?)

Could be achieved by mapping a set of inputs of width N into another set of inputs of width M where some original inputs are woven together into the new smaller set N.

Does this mean a 1-qubit quantum computer can simulate any larger size? Or do we need a 2-qubit or n-qubit machine to do anything useful? Does a quantum computer execute a sequence of operations like a Turing one?

I don't really understand either quantum mechanics (but I'm learning more) or quantum computers, so all this may well be a load of rubbish.

 

[-Job-]

Just as an aside, my mouse has a "thumb button" whose current function is the "back" function when Internet Explorer has the focus, so it has happened to me twice in this thread that after typing a long post i accidently click that button and lose everything
I just wanted to say that when i say that a QC doesn't have a finite # of qubits, i mean that the Theoretical Model for a QC doesn't have this limitation. Or that is at least how i think of it, which is a parallel to TMs. In a TM we generally don't care to restrict the size of the tape, even though in implementation the tape must be finite, but for generality's sake we suppose that if we work hard we can create as long a tape as we like. From this perspective we would need an infinite compilation of Turing Machines to create the theoretical model for a QC with no restriction regarding # of qubits.
Modeling a QC with n-k qubits probably has an exponential slow down relative to a QC with n qubits, seeing as the QC with n-k qubits has [2^n-2^k] less states than the QC with n qubits.
So suppose you have a QC with 100 qubits and another one with 10. The first QC has 1267650600228229401496703205376 states while the other has 1024. Trying to model the first QC with the second one is the equivalent of trying to model a TM with 1267650600228229401496703205376 processors using 1024 processors. The slow down from the first QC to the second QC is exponential relative to k, so it's nothing very efficient.