3 ms·
Physicists Finally Find a Problem for Quantum Computers Alone
- mock-possum 3y agoThe problem, which the article somehow manages to avoid mentioning: > In this work, we study the problem of finding local minima in quantum systems under thermal perturbations. While local minima are much easier to find than ground states, we show that finding a local minimum is computationally hard for classical computers, even when the task is to output a single-qubit observable at any local minimum. In contrast, we prove that a quantum computer can always find a local minimum efficiently using a thermal gradient descent algorithm that mimics the cooling process in Nature. (I have no idea what most of that means)
- Vecr 3y agoNo they haven't, a classical Turing machine has at most an exponential slowdown compared to a quantum Turing machine.
- lupire 3y agoQuanta headlines are very commonly gobbledygook.
- klyrs 3y agoThe problem with that exponential slowdown is that a million-year runtime is so impractical it should be considered impossible. And if that isn't convincing, double the problem size and square the runtime for a trillion years. The sun will engulf the Earth long before the progress bar reads 1%.