Constraint satisfaction problems (CSPs) are a class of problems aiming to produce an object satisfying given constraints. Examples of such problems include map colouring problem where the number of available colours is limited and no two adjacent regions must share the same colour, and Sudoku, where each number can appear only once in each quadrant, row and column. Solving CSPs efficiently remains an elusive goal for classical computers, as known algorithms typically exhibit exponential time complexity, but quantum computers can offer significantly better performance.
Rational protein design requires solving a large number of CSPs, including residue conformation, binding site geometries and force fields. The number of possible configurations, N, grows exponentially as a function of the number of residues modelled. Searching among these possibilities becomes unattainable for large proteins, forcing the classical approaches to use sampling methods. Quantum computing, however, can promise a significant speed-up, enabling more systematic and comprehensive optimisation.
Towards this, we have shown how the challenge of generating a set of points satisfying pairwise Euclidean distances can be framed as a CSP. Leveraging the representation of CSPs as quadratic forms we have explored this optimisaiton using the D-Wave quantum computer with 6000 qubits. This approach serves as a foundation for addressing broader protein design constraints using quantum computing.
This research aims to unlock the potential of quantum computing in solving complex CSPs, with implications spanning various domains, from combinatorial problems to rational protein design and beyond.