What are intractable problems for a traditional computer?
These are types of problems whose solution requires processing times that grow exponentially with their size, so that even relatively-small instances cannot be solved in a reasonable time even by the most powerful computers. SAT (Boolean satisfiability) is the type of intractable problem par excellence, with numerous industrial applications (circuit verification, planning, logistics, artificial intelligence, ...).
Whereas research has made tremendous progress over the past 20 years in this field, relatively-small instances of SAT problems are still beyond the reach of traditional computers.
It is the belief of many scientists that quantum computers can represent a solution to intractable problems. "With my collaborators - explains Roberto Sebastiani, professor at the Department of Information Engineering and Science - "we are trying to solve the SAT problems using a Quantum Annealer, a particular kind of quantum computer developed by D-Wave Systems Inc. The first results we have obtained are very encouraging.”
A Quantum Annealer is a quantistic device specialized for solving only one type of problem called QUBO, though very efficiently; the research work of prof. Sebastiani, using an innovative approach, manages to "translate" the intractable SAT problem into a QUBO problem and then to have it solved quantistically by the quantum annealer much faster than traditional computers.
The preliminary results of the research have been published in the journal "Information and Computation" in an article entitled "Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results" by prof. Sebastiani, the former PhD student Stefano Varotti and collaborators of D-Wave Systems Inc.
The final goal of this research, to which prof. Sebastiani is working with a team of new collaborators, is to use second-generation quantum annealers to solve SAT problems currently beyond the reach of traditional computers, and to achieve the so-called "quantum supremacy" in the field of intractable problems.
Keywords:
Quantum Annealing, SAT, QUBO, Intractable problems