The development of quantum algorithms for solving the computational task of searching molecular substructures in a database is central to a wide range of problems in the field of cheminformatics, including recognition of the largest common substructure among a diverse set of chemical structures in a database for drug discovery, and finding molecular precursors in retrosynthetic studies based on the identification of the largest substructure common to the two sides of a chemical reaction in organic synthesis. Here, we propose a deterministic algorithm based on the graph representation of molecular structures, so searching a molecular substructure can be formulated in terms of the so-called subgraph isomorphism problem: Given two graphs G and H the task is to determine whether H contains a subgraph that is isomorphic to G. Current algorithms for solving this problem are known to suffer from poor scalability as well as poor generalization to novel reactions.

We solve the graph isomorphic problem by implementing a hybrid quantum classical approach based on the well-known Bernstein – Vazirani algorithm and efficient classical methods to sample subgraphs of H. Our approach has numerous advantages over existing methods. First, the expressive power of qubits allows the compact representation of all Ο(n!) permutations in a superposition of Ο(n²)-bit strings. Second, the deterministic nature of the algorithm allows us to obtain always the correct answer with certainty, rather than relying on variational quantum algorithms. Third, the circuit architecture involved does not require tuning the quantum gate parameters for different graphs of the same size, and only require changes on qubit initialization. Therefore, we can search over a large numbers of reactants of the same size without changing the circuit, making this approach practical for experimental implementation.

In addition to the implementation on conventional quantum computers based on qubits, we introduce the implementation of our algorithm for computing quantum devices with continuous-variable modes, allowing us to solve the subgraph isomorphism problem in the near future hybrid architectures containing both qubits and bosonic modes with hardware efficiency.

Nam Vu

Appearances