Source-linked AI summary
Molecular Docking with Gaussian Boson Sampling
Leonardo Banchi, Mark Fingerhuth, Tomas Babej, Christopher Ing, Juan Miguel Arrazola
TL;DR
Molecular docking requires efficient prediction of stable ligand-receptor configurations for pharmaceutical screening. The paper maps docking to a vertex-weighted maximum-clique problem and uses GBS sampling with classical post-processing; on the TACE-AS benchmark, hybrid search reaches substantially higher success rates than classical strategies and remains robust to noise when squeezing is adjusted.
Problem
Molecular docking must identify stable ligand-receptor configurations while using few computational resources for high-throughput screening of large chemical libraries.
Method
The paper maps molecular docking to finding maximum weighted cliques in vertex-weighted binding interaction graphs, then combines GBS sampling with classical shrinking and local search.
Results
After k = 8 local expansion steps, GBS hybrid search finds the maximum weighted clique with probability as high as 60%, versus < 30% for the classical strategy.
Takeaways & Limitations
GBS can predict accurate molecular docking configurations and enhance classical algorithms for finding molecular binding poses.
Abstract
from arXiv · showhide
Gaussian Boson Samplers are photonic quantum devices with the potential to perform tasks that are intractable for classical systems. As with other near-term quantum technologies, an outstanding challenge is to identify specific problems of practical interest where these quantum devices can prove useful. Here we show that Gaussian Boson Samplers can be used to predict molecular docking configurations: the spatial orientations that molecules assume when they bind to larger proteins. Molecular docking is a central problem for pharmaceutical drug design, where docking configurations must be predicted for large numbers of candidate molecules. We develop a vertex-weighted binding interaction graph approach, where the molecular docking problem is reduced to finding the maximum weighted clique in a graph. We show that Gaussian Boson Samplers can be programmed to sample large-weight cliques, i.e., stable docking configurations, with high probability, even in the presence of photon loss. We also describe how outputs from the device can be used to enhance the performance of classical algorithms and increase their success rate of finding the molecular binding pose. To benchmark our approach, we predict the binding mode of a small molecule ligand to the tumor necrosis factor-$α$ converting enzyme, a target linked to immune system diseases and cancer.
I. INTRODUCTION
The paper addresses the practical use of Gaussian Boson Sampling by applying it to molecular docking, a resource-sensitive problem in pharmaceutical drug design. It maps docking configurations to weighted-graph cliques and evaluates both direct GBS sampling and hybrid classical post-processing.
- Boson Sampling research has largely focused on testing the Extended Church-Turing thesis rather than practical applications.
- Gaussian Boson Sampling has nevertheless been proposed for molecular spectroscopy and combinatorial optimization involving large data clusters.
- Molecular docking predicts stable ligand-receptor configurations and is central to pharmaceutical drug design, especially when screening large chemical libraries.
- The paper reduces docking to finding large clusters in vertex-weighted binding interaction graphs and programs GBS to sample them.
- The approach supports direct sampling and hybrid algorithms that post-process GBS outputs classically, and is tested on a known ligand-receptor interaction.
II. BACKGROUND
The paper introduces background on Gaussian Boson Sampling, graph theory, and molecular docking before presenting its results.
- The background section precedes the paper’s presentation of results.
- Its stated background topics are Gaussian Boson Sampling, graph theory, and molecular docking.
- These topics provide the relevant background for the subsequent results.
A. Gaussian Boson Sampling
Gaussian Boson Sampling uses Gaussian quantum states measured with photon-counting or threshold detectors, producing outcomes governed by Hafnians. Although Gaussian-state evolution is efficiently simulable, these measurement outcomes are classically difficult to model.
- Gaussian quantum states are characterized by Gaussian Wigner functions and parametrized by displacement and covariance moments.
- Gaussian states can evolve efficiently under linear transformations, but photon-counting or threshold measurements make outcome modeling extremely challenging classically.
- For zero-displacement Gaussian states, photon-counting outcomes are described by a distribution involving submatrices selected from a matrix A and the Hafnian function.
- The Hafnian is #P-Hard to approximate for worst-case instances and counts perfect matchings through its defining combinatorial structure.
- Threshold detectors record binary clicks according to whether a mode contains at least one photon, requiring aggregation over photon-number outcomes.
B. GBS to find dense subgraphs
GBS can be programmed to favor dense subgraphs because Hafnian weights count perfect matchings, which are associated with graph density. This provides a sampling basis for combinatorial optimization.
- For an unweighted graph, the Hafnian of its adjacency matrix equals the number of perfect matchings.
- GBS can sample subgraphs with probability proportional to the squared magnitude of their Hafnians.
- In the collision-free subspace, the selected matrix is the adjacency matrix of the sampled subgraph, so large Hafnians favor subgraphs with many perfect matchings.
- Subgraphs with many perfect matchings tend to have high density, motivating GBS-based sampling of dense subgraphs.
- Hybrid quantum-classical optimization combines GBS random sampling with stochastic optimization procedures.
C. Molecular docking
Molecular docking predicts stable ligand–receptor orientations by searching configurations and scoring poses, supporting structure-based drug discovery and virtual screening. The paper represents molecular features and geometry through labeled pharmacophore distance graphs.
- Molecular docking searches ligand–receptor configurational space and scores candidate poses with a potential energy function.
- Reliable binding-pose prediction and ranking are central to pharmaceutical research and structure-based virtual screening.Accurate and computationally efficient prediction is especially important when screening very large compound libraries.
- A pharmacophore is represented by labeled points encoding features such as charge, hydrogen bonding, hydrophobicity, and aromatic rings.
- The labeled distance graph is built by connecting pharmacophore points with Euclidean-distance-weighted edges and assigning each vertex its pharmacophore label.
A. Mapping molecular docking to maximum weighted clique
The docking problem is converted into a vertex-weighted binding interaction graph whose cliques represent mutually compatible contacts. Under this model, the most likely poses correspond to maximum-weight cliques.
- The labeled distance graphs of the ligand and binding site are combined into one binding interaction graph, reducing docking to maximum weighted clique search.
- Each binding-interaction vertex represents a possible ligand–receptor contact, giving nm vertices when the component graphs contain n and m vertices.
- Edges connect pairs of contacts exactly when they are geometrically compatible, so pairwise-compatible contact sets form cliques.
- A contact pair is τ-flexible when corresponding ligand and binding-site distances are approximately consistent despite molecular flexibility.
- Vertex weights are computed from pharmacophore labels through a contact-potential function, favoring stronger intermolecular interactions.
- The most likely binding poses are vertex-heaviest cliques, while brute-force enumeration scales as O(2^n) over possible subgraphs.
B. Max weighted clique from GBS
The GBS construction biases sampling toward subgraphs that are both clique-like and heavy, using Hafnian-based sampling and a weight-dependent matrix scaling. The weighting parameter must balance these objectives.
- GBS is programmed to sample distributions that output the maximum weighted clique with high probability.
- In the collision-free subspace, a sample defines a subgraph whose Hafnian is maximized by a clique for a fixed photon number.
- The diagonal scaling matrix Ω can be chosen to favor subgraphs with larger total vertex weight.
- For small α, the determinant factor increases with the sampled subgraph’s total weight, biasing GBS toward heavier subgraphs.
- If α is too large, GBS may favor heavy non-cliques because the Hafnian term becomes less important, so α must be chosen carefully.
C. Hybrid algorithms
The paper combines high-rate GBS sampling with classical post-processing to recover useful cliques from sampled subgraphs. Greedy shrinking produces cliques, and local search can expand or improve them at additional classical cost.
- GBS random search directly checks sampled subgraphs for cliques, while post-processing recovers useful solutions from samples that are close to cliques.
- Greedy Shrinking: Greedy shrinking repeatedly removes low-degree vertices, using weights to break ties, until the sampled subgraph becomes a clique.
- Expansion with Local Search: Local search grows a clique by adding vertices connected to every current clique vertex whenever such vertices exist.
- Expansion with Local Search: When direct expansion is unavailable, swapping a vertex for another compatible vertex enables a same-size local change while considering vertex weight.
- Expansion with Local Search: GBS outputs provide starting configurations that are more informative than merely random vertices and can be close to maximum cliques after shrinking.
IV. NUMERICAL RESULTS
The numerical study applies GBS-based graph sampling to TACE–AS docking, comparing direct sampling, greedy shrinking, and hybrid local search against classical strategies. GBS favors high-weight cliques and improves maximum-clique discovery, including under modeled noise when squeezing is increased accordingly.
- Graph-based docking: The TACE–AS docking problem is represented as a vertex-weighted binding interaction graph whose maximum weighted clique encodes the predicted ligand–receptor superposition.The graph uses pharmacophore points, distance compatibility, and interaction-dependent vertex weights.
- Random search: GBS directly sampled roughly 300 cliques from 10^5 samples, whereas classical random search found only three and none had maximum weight.The TACE–AS graph had 19 cliques of size eight, and the largest and heaviest cliques both had eight vertices.
- Greedy shrinking: Greedy shrinking found the maximum weighted clique 12% of the time with GBS, compared with 1% for matched classical random data.The overall sampling rate for size-eight cliques was approximately 19%, and the maximum-weight clique had weight approximately 3.99.
- Shrinking + local search: After k = 8 local expansion steps, GBS reached a 60% maximum-clique success rate, compared with less than 30% for the classical strategy.After many steps, GBS approached 70% while the classical approach remained below approximately 35%.
- Noise robustness: GBS success was not diminished by modeled noise when squeezing was increased accordingly, preserving a significant margin over purely classical strategies.The noise and squeezing analysis concerns the shrinking and shrinking-plus-local-search variants.
V. CONCLUSIONS
The paper maps molecular docking to maximum weighted clique finding and programs GBS to sample large-weight cliques. It develops weighted graph and sampling machinery, including tunable output sizes and post-selection strategies.
- Conclusions: GBS predicts docking configurations by mapping the problem to finding large cliques in vertex-weighted binding interaction graphs.The heaviest clique corresponds to the most favourable binding pose.
- Conclusions: Weighted GBS can be programmed so its output distribution favors graph substructures with large total vertex weight.The construction uses a rescaled matrix whose spectrum can be made compatible with experimentally available squeezing.
- Conclusions: The normalization factor c tunes the average photon or click number and can bias sampling toward subgraphs of different sizes.For a single mode, c = tanh(rmax), while multimode output size depends on the corresponding matrix normalization.
- Conclusions: Postselecting outcomes of fixed size reduces brute-force sampling complexity from exponential to polynomial in the number of modes, with polynomial degree increasing with N.The fixed-size probability count scales as O(M^N), while individual probabilities still require exponentially many determinant evaluations in N.
- Conclusions: Numerical observations show that different values of the weighting parameter α enhance the maximum weighted clique problem for sparse graphs without careful tuning.The expected enhancement was observed across the tested α values.
- Conclusions: Vertex weights encode pharmacophore interaction strengths through a potential function applied to ligand–binding-site label pairs.This weighting biases the search toward stronger intermolecular interactions.
Appendix D: Supplementary figures
The supplementary figures examine maximum-clique structure, classical baselines, and the effects of noise and squeezing. GBS substantially outperforms matched random classical sampling and retains performance under adjusted squeezing.
- Fig. S1: The maximum weighted clique contains a heavy six-vertex core and two light vertices within the graph’s heavy-weight cluster.Lightweight cliques have low occurrence rates in a carefully programmed GBS distribution.
- Fig. S2: 1% versus 12%: classical random sampling finds the maximum weighted clique only 1% of the time, compared with 12% for GBS.The classical samples match the GBS distribution’s mean and variance of subgraph size but choose vertices uniformly.
- Fig. S3: rmax = 0.9702 corresponds to an average of approximately 8 detector clicks in the noiseless setting.The lossy comparison increases squeezing to rmax = 0.9780 to maintain approximately the same average click number.
- Fig. S3: Increasing squeezing accordingly prevents noise from diminishing the success rate after greedy shrinking.The noisy and noiseless GBS versions show similar success at iteration 0 and retain a significant margin as iterations increase.