Approximate approximation on a quantum annealer
Irmi Sax, Sebastian Feld, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff–Popien, Wolfgang Mauerer
Abstract
Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems.
Topics & Concepts
HeuristicsProbabilistic logicQuantumComputer scienceClass (philosophy)Quantum annealingQuantum computerComputational complexity theoryApproximation algorithmMathematical optimizationTheoretical computer scienceAlgorithmMathematicsArtificial intelligenceQuantum mechanicsPhysicsOperating systemQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum-Dot Cellular Automata