4 ms·
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
by vimax 3y ago
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.
- chermi 3y agoJust 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.
- eigenket 3y agoThey 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.