> So that’s what the team behind the new paper ended up doing: They ported an optimization tool from mathematics into their field of quantum learning. First they reformulated the problem of calculating a system’s Hamiltonian into a family of polynomial equations. Now the goal was to prove that they could solve these equations reasonably quickly — which seemed like an equally hard goal. “In general, if I have an arbitrary polynomial system, I cannot hope to solve it efficiently,” Bakshi said. Even simple polynomial systems are just too hard.
> But theoretical computer scientists are good at finding workarounds in such situations, by using what’s called a relaxation technique. This approach converts problems that are hard to optimize — they have too many solutions that appear right but aren’t valid everywhere — into simpler ones with a unique global solution. By approximating difficult problems via simpler ones, the relaxation technique helps find solutions closer to the true solution.
> The relaxation technique is well known in the field of approximation algorithms, but it had never been tried in quantum learning.
> So that’s what the team behind the new paper ended up doing: They ported an optimization tool from mathematics into their field of quantum learning. First they reformulated the problem of calculating a system’s Hamiltonian into a family of polynomial equations. Now the goal was to prove that they could solve these equations reasonably quickly — which seemed like an equally hard goal. “In general, if I have an arbitrary polynomial system, I cannot hope to solve it efficiently,” Bakshi said. Even simple polynomial systems are just too hard.
> But theoretical computer scientists are good at finding workarounds in such situations, by using what’s called a relaxation technique. This approach converts problems that are hard to optimize — they have too many solutions that appear right but aren’t valid everywhere — into simpler ones with a unique global solution. By approximating difficult problems via simpler ones, the relaxation technique helps find solutions closer to the true solution.
> The relaxation technique is well known in the field of approximation algorithms, but it had never been tried in quantum learning.