Why are quantum computers faster than classical computers?

[Truecrimson]

Check this definition. The NP class refers to verfiability, not a solution.

The two definitions are equivalent. Although one might prefer the definition based on verifiability because non-deterministic Turing machine is unphysical.

 

[haael]

For a problem in NP class, nondeterministic Turing machine can find the solution in polynomial time and deterministic Turing machine can verify the solution in polynomial time.

And yes, both Turing machines are unphysical.

 

[newjerseyrunner]

Speed can have as much to do with organization than the speed of the underlying hardware. For example, electrical signals travel way faster than chemical signals, but even with 50 years of Moore's law, we still can't make an electrical computer that can perform as many calculations as the three pound chemical computer inside your head.

 

[Truecrimson]

Both Turing machines are unphysical.

Every mathematical model is an idealization. But some can be approximated well enough by reality like deterministic Turing machines, while non-deterministic Turing machines are not meant to be physical from the beginning.

 

[haael]

That depends on what you mean by "approximated well enough". I can make a physical simulation of a nondeterministic Turing machine (that will take exponential physical time to run of course).

Maybe a part of your definition of good approximation is "if the machine runs in polynomial computation time then it must also run in polynomial physical time". Or maybe you want to say that "elementary physical operation" is in some sense equivalent to "elementary computational operation" which is a controversial claim at best.

From computer science we know that the class EXPTIME (problems that need exponential time on deterministic Turing machine) is equal to NEXPTIME (problems that need exponential time on nondeterministic Turing machine).
I can make a physical simulation that solves problems from NEXPTIME and runs in exponential time. Can I say that I just made a physical model of a nondeterministic Turing machine? The class of problems solved is right and the time taken is right.

What I want to say: every mathematical model is an unphysical abstraction and whether we can make a physical simulation of it depends on what we mean by "physical simulation".
For me, deterministic Turing machines are as unphysical as nondeterministic ones.

 

[Truecrimson]

I was not thinking about simulations whether in polynomial or exponential time. The very definition of non-deterministic Turing machine is unphysical because it tries out all possibilities at once and if there is a solution, then it solves the problem (which is curiously a popular misconception of what a quantum computer is capable of doing).

 

[haael]

The very definition of non-deterministic Turing machine is unphysical because it tries out all possibilities at once and if there is a solution, then it solves the problem

Yes, but you can simulate it by serializing all possibilities.

Both deterministic and nondeterministic Turing machines can be simulated or can not, depending on what you mean by simulation.

 

[Truecrimson]

What I tried to convey when I said that the a non-deterministic Turing machine is unphysical is really simple, and probably doesn't contradict or even related to what you argued at all. It is the same as saying that it is unphysical for me to go to two different places at the same time and then based on those "experiences," pick the place that I'm happier to be into be real.

But now I understand the reason behind your choice of words better.

 

[Strilanc]

There are certainly other ways to compute things in quantum physics. Moreover, if you take a look at the literature on quantum computation, path integrals are (almost) never mentioned.

The main mention I've seen of path integrals in quantum computing is in the proof that PSPACE = BQPSPACE.

The contributions to a single output amplitude can be figured out up by iterating through all the ways the input amplitudes flow to it through the intermediate states and operations. Each individual flow-path's contribution is cheap to compute in both time and space. There's a huge number of these paths, so it will take a lot of time to add them all up, but you only need to consider one at a time (and keep track of the total) so it doesn't take much space.

With the ability to generate the amplitude of individual output states, you can pick one with the correct probability. Choose a random number between 0 and 1, then iterate through all the possible output states while cumulatively subtracting the squared magnitude of their amplitude off of that number. Once it hits or goes past zero, return the current output state. Again this may take a lot of time, since there's exponentially many states to go through, but you only need to track the remaining total so it doesn't take much space.