Is quantum physics (easily?) computable?

It feels like the actual implemented physics shouldn't much affect how computation works. After all, we live in a quantum universe and classical physics is still simpler to compute.

If I understand Scott Aaronson correctly (his site seeks to correct public understanding of quantum computing), any quantum system can be simulated with a classical system, but with exponential slowdown (as far as we know -- it's not proven whether someone will be able to come up with a clever way to do it with less of a slowdown). But everything computable via a quantum system is computable via a classical system, just not necessarily as fast.

The formal term for the question of whether classical computers can work as efficiently as quantum computers is that of "Is BQP = P?". (BQP = problems solvable in polynomial time using a quantum computer; P = problems solvable in polynomial time with classic.)

Discrete particles vs. continuous wave functions is a red herring, I think. It's true that in a simulation of QM one would have to approximate amplitudes up to some finite precision (and approximate infinite dimensional Hilbert spaces using finite dimensional Hilbert spaces). But this is not a problem that is unique to QM. Simulating classical mechanics also requires approximating the positions and momenta of particles to finite precision.

You are right, though, that computing quantum mechanics is harder than computing classical mechanics. This is true even if we completely discretize both theories. The length of a vector representing the state of a classical system is linear in the size of the system, but the length of a vector representing the state of a quantum system is exponential in the size of the system.

Continuous wave functions seems to be far harder than discrete particles.

True, but consider that discrete particles are a special case of continuous wave functions: The case where the phase-space distribution is a delta function or some very good approximation to it. If you limit your quantum mechanics to cases that classical mechanics can describe well, then you are operating, in effect, on delta functions, and this simplifies the math immensely.

The apparent simplicity of classical mechanics comes from looking only at these special cases; quantum mechanics deals with more general situations, so it is unavoidably more complex. But if you made a quantum-mechanics program to predict only classical situations, it would not necessarily be more complex than the corresponding program using the laws of Newton, who is not forgotten.

I presume that you refer to the difference between point particles and fields. The wave function in QM is essentially a classical field), where for every point in space you have a set of numbers describing the quantum state. This state evolved in time according to the time-dependent Schrodinger equation, until "something classical" happens, at which point you have to throw dice to pick one of the preferred states (also known as the wave-function collapse or the MWI world split).

The part of QM which is just the evolution of the Schrodinger equation is computationally equivalent to that of modeling diffusion or heat flow: the equation structure is very similar, with complex numbers instead of reals. The "measurement" part (calculating an outcome) is nearly trivial, just pick one of the outcomes (or one of the worlds, if you are a fan of MWI), according to the Born rule.

While it is true that there are many shortcuts to solving the Schrodinger equation numerically, and a set of these shortcuts is what tends to be studied in most QM courses, there is no substitution for numerical evolution in a general case.

Quantum computing is a rather different beast from the regular quantum physics, just like classical computing is different from classical physics: computing is an abstraction level on top, it lets you think only about the parts of the problem that are relevant, and not worry about the underlying details. Quantum computing is no more about quantum mechanics than the classical computer science is about the physics of silicon gates.

One final piont. It is a general observation that understanding of any scientific topic is greatly enhanced by teaching it, and teaching it to an ultimate idiot savant, a computer, is bound to probe your understanding of the topic extensively. So, if you want to learn QM, get your hands dirty with one of the computational projects like this one, and if you want to learn quantum computing, write a simulation of the Schor's algorithm or something similar.

There are a variety of ways of measuring how complex something is. Three of them seem relevant here. The first is, given a sequence a_i of integers, what is the smallest classical Turing machine which on input i outputs a_i. This is really tough in general, and quickly leads to unsolvability issues. In general, the simpler question "what is the smallest Turing machine which outputs string S" is called the Kolmogorov complexity of S and is essentially undecidable in the general case. One can look at empirical Kolmogorov complexity and ask the same question about smallest known. This turns out to be not that useful as I understand it.

More effective methods look not at the Turing machine's size but how much tape space or how much time it takes up. You may have heard of this sort of thing in the context of P?= NP. In this context, the set of function problems which can be performed by a quantum computer reliably in polynomial time is BQP. We do have specific problems that seem to be in BQP that cannot be performed in reasonable time on a classical computer in polynomial time. Although this has not been formally proven, recent work by Scott Aaaronson leads one to suspect the stronger statement that BQP includes problems which are outside what is called the polynomial hierarchy, which is a much broader computational framework. If this is the case, then quantum computing must be very hard.

Note that when talking about BQP one is getting essentially a single bit of information out, so it can always be performed with finite resources (in fact in PSPACE and thus bounded by exponential time). If one wants to predict more behavior of the system then you need do need a lot more resources and it seemed potentially infinite resources to fully predict basic behavior.

Classical physics isn't exactly computable, because some systems are critically dependent on their initial conditions, and an exact specification of the initial conditions requires an infinite amount of information (unlimited precision real number).

Just a quick question in case anybody knows... the complex amplitude value that each point in configuration space contributes to the amplitude of some future point in configuration space... the phase can be any value, but is the magnitude variable too? Or are there just lots of vector additions of the same sized vectors pointing in different directions?

If you're talking about the complexity of the program, as opposed to how much computing power it takes to actually run, time-dependent quantum physics is pretty easy. You just take a n^m lattice (that is n x n x n x n x ... x n) of complex numbers, calculate the Hamiltonian (a constant times the sum of the double derivatives for each dimension plus potential energy) multiply it by i times the current amplitude, and add a tiny fraction of that to the current amplitude. You have to do this to really high precision to prevent error from accumulating (though you could improve it to make error accumulate slower).

Time independent quantum mechanics isn't so easy. You could calculate it propagating out from some initial condition, but I think this will result in runaway amplitude. I suspect that if you mess with the Born rule and make the probability go down as the position moves further from the origin and get it to work about right.

If that doesn't work, if you calculate enough of these improper universes, you should be able to get a proper one as a linear combination of them. Just keep track of how much they're running away, and add them so it all goes to zero.

It all depends on your system. If you're computing the fully quantum system of a spin glass on a regular grid using an Ising Hamiltonian or something like that, it can be computed far more straightforwardly than most fully classical systems of a similar number of particles.

It also depends on the approximations you're making. You mention the ideal gas law, but that doesn't apply to gases sufficiently far from thermal equilibrium, or even mechanical equilibrium. If you pop a balloon in outer space, the gases will self-sort by momentum, and thus cool faster than the ideal gas law over their volume would suggest.

So, each time we learn new physics that isn't clever approximation, new effects are being added. They will necessarily add computational complexity, unless they allow new, different approximations to be made which more than make up for that new complexity.

By "relativity" you mean what? If relativistic mechanics of point particles in a given background, then it is computationally as complex as classical mechanics. If the background (i.e. gravitational and electromagnetic fields) is to be determined dynamically, then it is harder because you have infinitely many degrees of freedom. But that's the case of many non-relativistic classical systems (fluid dynamics...) too.

it seems to me that you would have to set up a system where the outcomes of relativity are explicitly stated, while the classical outcomes are implicit

What does this mean? I can think of several interpretations, all of them false:

1. It is impossible to calculate the evolution of a relativistic system from the initial state only, you also need to know the final state too.
2. It is possible to do calculate the relativistic evolution from the initial state, but you have to do it symbolically, numerical methods won't work.
3. It is impossible to calculate anything numerically in a relativistic system, solutions have to be guessed and later verified, they can't be systematically constructed.

Our best models of things require an infinite number of classical bits to completely specify. Though it's not like that's new - it takes an infinite number of bits to specify an arbitrary classical velocity too.

The basic rules are already pretty simple. It's just that representing them on a classical computer is impossible.

No.