[vimax]

The thing that stands out to me is the described proof of BQP-completeness where they say they prove any quantum system can be similarities as balls and springs, but later they say you may need an exponential number of springs for a classical simulation. That sounds like the BQP reduction would be exponential, guess I'll have to read the paper to see what I'm missing.

[eigenket]

They have exponentially many classical oscillators, but then they simulate them with their quantum algorithm with exponential speed up. The two exponential factors cancel and you end up with a quantum algorithm for a BQP complete problem which runs in polynomial time.

[chermi]

Just a gut feeling but it could be related to the ability to map so much stuff to path integrals with harmonic fields. I too need to read it better.