The Role of Experimental Noise in a Hybrid Classical-Molecular Computer to Solve Combinatorial Optimization Problems

Veronica K. Krasecki, Abhishek Sharma, Andrew C. Cavell, Christopher J. Forman, Si Yue Guo, E. Jensen, Mackinsey A. Smith, R.n. Czerwinski, Pascal Friederich, Riley J. Hickman, Nathan C. Gianneschi, Alán Aspuru‐Guzik, Leroy Cronin, Randall H. GoldsmithACS 2023 · DOI

TL;DR

This paper introduces a hybrid classical-molecular computer (HCMC) that leverages a chemical system (pH changes detected by fluorescence) and a classical computer to solve complex optimization problems. Crucially, the HCMC utilizes inherent experimental noise from the chemical readout, rather than relying on artificial "in silico" noise, to successfully navigate local minima and find global solutions.

What Problem Does This Paper Address?

The relentless march of silicon-based computing is hitting physical and economic limits. Researchers are exploring alternative computing paradigms, including molecular and chemical computers, which promise advantages like low power consumption and inherent randomness. However, fully molecular computers are still in their infancy. This paper tackles the challenge of bridging the gap between current digital computing and future molecular computing by developing a hybrid system. This HCMC combines the strengths of both worlds: the precision and programmability of classical computers with the unique properties of chemical systems. Specifically, they aim to solve computationally hard problems (like number partitioning and prime factorization) and demonstrate how the "messiness" of real-world chemical measurements can be a feature, not a bug, in computation.

Methods

The core of the HCMC is a feedback loop between a classical computer and a chemical system.

  • Chemical System: An array of electrodes on a printed circuit board (PCB) chip is coated with a gel containing a hydroquinone/benzoquinone redox couple. This couple, when subjected to electrochemical potentials from the electrodes, reversibly alters the local pH.
  • Optical Readout: A pH-sensitive fluorescent dye (Carboxy-SNARF-1) is added to the gel. This dye emits fluorescence at two different wavelengths, and the ratio of these emissions is directly proportional to the local pH. This ratio is captured by cameras.
  • Classical Computer: A classical computer receives the fluorescence intensity ratio (IR) from the cameras. It then converts this IR into a digital "state value" for each electrode site. This state value represents a variable in the computational problem.
  • Feedback Loop: The classical computer uses these state values to perform a gradient descent algorithm to find the minimum of a problem's cost function (represented as an Ising Hamiltonian). Based on the calculated "target" state for the next step, the classical computer applies specific voltages to the electrodes, which in turn alters the pH, creating a new fluorescence signal. This cycle repeats until a solution is found.
  • Noise Utilization: The key innovation is the use of experimental noise inherent in the optical readout. Instead of adding artificial "in silico" random numbers to the gradient descent (Mode 2), they run the system using only the measured states (Mode 3). This experimental noise, primarily from the optical measurement, helps the algorithm escape local minima that would trap a "perfect" system (Mode 1).

Datasets

The paper does not use traditional "datasets" in the machine learning sense. Instead, it evaluates the HCMC on well-defined computational problems:

  • Number Partitioning: A classic NP-complete problem. They use a specific set of numbers {1,2,3,1,3} to create a problem Hamiltonian.
  • Prime Factorization: They demonstrate factorization of the number 91 into its prime factors (7 and 13).
  • 3-SAT: They mention solving 3-SAT problems with 7 variables and 28 clauses, though detailed results for this are in the supplementary information.

The "benchmark" here is the ability to correctly solve these problems and find the global minimum of their associated cost functions, often comparing performance against idealized (noise-free) and in silico noisy simulations.

Key Insights and Ideas

  • Experimental Noise as a Computational Resource: This is the central theme. Instead of fighting experimental noise, the HCMC actively uses it to improve computational performance, particularly in escaping local minima. This is a significant departure from traditional computational approaches that aim for perfect precision.
  • Bridging Digital and Molecular Computing: The hybrid architecture provides a tangible pathway towards more complex molecular computing systems by demonstrating how chemical processes can be integrated into computational workflows.
  • Scalability of Chemical Systems: The paper shows that by simply adding more electrodes, the HCMC can tackle problems with more variables, demonstrating a potential for inexpensive scaling.
  • Programmability in a Chemical Context: The HCMC allows for programmability through the classical computer's control over electrode potentials and the definition of the problem Hamiltonian, a key advantage over purely chemical systems.

Key Results

  • Successful Optimization: The HCMC successfully solved number partitioning and prime factorization problems.
  • Noise-Assisted Convergence: When starting from a "flat" region of the cost function (a saddle point), the noise-free system (Mode 1) often failed to converge or got stuck. In contrast, the HCMC using experimental noise (Mode 3) consistently converged to correct solutions, performing comparably to systems with added artificial noise (Mode 2).
  • Improved Success Rates: For a number partitioning problem with multiple solutions and local minima, Mode 3 (experimental noise) achieved a 25:75 split between two global solutions across all runs, and in another scenario, achieved 54% convergence to global minima with a noise level similar to experimental noise.
  • Scalability Demonstration: The system was scaled from 4 to 7 variables, demonstrating an increase in computational capability.
  • Prime Factorization Success: 8 out of 10 runs successfully factored 91.

Limitations and Future Work

  • Speed: The paper acknowledges that mass transport in solution-phase molecules can limit clock speed, though miniaturization could help.
  • Reproducibility: While chemical systems offer potential for reproducible dynamics, this has not yet been fully demonstrated for this specific HCMC.
  • Degradation: The need for optical readout and electrochemical cycling can lead to degradation, requiring further optimization.
  • Noise Characterization: While the paper quantifies experimental noise and shows its benefit, further work is needed to fully understand its origins and how to precisely tune it for different computational problems.
  • Fully Molecular Systems: The current system is hybrid. The ultimate goal is to develop fully molecular implementations.
  • Miniaturization: The authors suggest that miniaturizing electrode arrays and improving optical resolution could enable tackling even more complex problems and potentially leverage other noise sources like Poisson noise from small molecular populations.

Summary updated

Abstract

Chemical and molecular-based computers may be promising alternatives to modern silicon-based computers. In particular, hybrid systems, where tasks are split between a chemical medium and traditional silicon components, may provide access and demonstration of chemical advantages such as scalability, low power dissipation, and genuine randomness. This work describes the development of a hybrid classical-molecular computer (HCMC) featuring an electrochemical reaction on top of an array of discrete electrodes with a fluorescent readout. The chemical medium, optical readout, and electrode interface combined with a classical computer generate a feedback loop to solve several canonical optimization problems in computer science such as number partitioning and prime factorization. Importantly, the HCMC makes constructive use of experimental noise in the optical readout, a milestone for molecular systems, to solve these optimization problems, as opposed to <i>in silico</i> random number generation. Specifically, we show calculations stranded in local minima can consistently converge on a global minimum in the presence of experimental noise. Scalability of the hybrid computer is demonstrated by expanding the number of variables from 4 to 7, increasing the number of possible solutions by 1 order of magnitude. This work provides a stepping stone to fully molecular approaches to solving complex computational problems using chemistry.
BibTeX
@inproceedings{krasecki2023role,
  author = {Veronica K. Krasecki and Abhishek Sharma and Andrew C. Cavell and Christopher J. Forman and Si Yue Guo and E. Jensen and Mackinsey A. Smith and R.N. Czerwinski and Pascal Friederich and Riley J. Hickman and Nathan C. Gianneschi and Alán Aspuru‐Guzik and Leroy Cronin and Randall H. Goldsmith},
  title = {{The Role of Experimental Noise in a Hybrid Classical-Molecular Computer to Solve Combinatorial Optimization Problems}},
  booktitle = {ACS},
  year = {2023},
  doi = {10.1021/acscentsci.3c00515},
}
Figure