3 ms·
Barring the sky falling, our best bet for NP hard problems is approximate solutions that have provable lower bounds on approximation ratio. From that purview,
by soganess 4y ago
Barring the sky falling, our best bet for NP hard problems is approximate solutions that have provable lower bounds on approximation ratio.
From that purview, a general heuristic for approximating combinatorial optimization problems would be a godsent. Even if algorithms like the QAOA do not improve(or tightly match) approximation ratios beyond that of a carefully crafted classical algorithm... A turn key algorithm on a coherent high-qubit-count quantum computer would change the industrial use landscape forever. The number of developer hours saved would be uncountable.
We're just aiming way too dang high.
- elcritch 4y agoI mean that sounds a lot like what DWave and Google are pursuing with the adiabatic QCs.
- pyinstallwoes 4y agoKind of like how instead of modeling the entire economy and figuring out how to influence the behavior, you just identify a key parameter such as inflation or interest rates and modify that to affect every possible outcome.