Paper: [Local minima in quantum systems](https://arxiv.org/abs/2309.16596), av Chen, Huang, [[John Preskill]], og Zhou. Quanta-artikkel: [Physicists Finally Find a Problem That Only Quantum Computers Can Do](https://www.quantamagazine.org/physicists-finally-find-a-problem-only-quantum-computers-can-do-20240312/) Quanta-artikkelen beskriver oppdagelsen som overraskende, > Researchers began to wonder if the question of determining a system’s local minimum energy level was also universally hard. —men dette ville vel motsagt [[Extended Church-Turing-Deutsch thesis]], så hvis vi trodde på den var det vel bare et spørsmål om tid før noen oppdaget en algoritme for dette? Fra Quanta igjen: > “A lot of chemists, material scientists and quantum physicists are working on finding ground states,” said [Robert Huang](https://hsinyuan-huang.github.io/), one of the new paper authors and a research scientist at Google Quantum AI. “It is known to be extremely hard.” > > It’s so hard that after more than a century of work, researchers still haven’t found an effective computational approach to determining a system’s ground state from first principles. Nor does there appear to be any way for a quantum computer to do it. Scientists have concluded that finding a system’s ground state is hard for both classical and quantum computers. > > But some physical systems exhibit a more complex energy landscape. When cooled, these complex systems are content to settle not in their ground state, but rather at a nearby low energy level, known as a local minimum energy level. Minner meg om [[Scotts såpebobler]]. [[John Preskill]], fra Quanta-artikkelen: > “Now we have a problem: finding a local amount of the energy, which is still hard classically, but which we can say is quantumly easy,” Preskill said. “So that puts us in the arena where we want to be for quantum advantage.” Men hva mener han med dette? Hva vet vi om kompleksiteten til problemet? Vet vi for eksempel at det er [[BQP]]-komplett? (Ville vært ideelt.) Update: Paperet svarer *ja* på dette spørsmålet, og beviser det i Teorem 8! > While finding a local minimum under local unitary perturbations is classically easy, the characterization of the energy landscape in these BQP-hard Hamiltonians HC implies that finding a local minimum under thermal perturbations is universal for quantum computation and is hence classically hard if BPP $\neq$ BQP.