Quantum isomer search

English version

Autoři: Jason P. Terry ^aff001; Prosper D. Akrobotu ^aff004; Christian F. A. Negre ^aff005; Susan M. Mniszewski ^aff006
Působiště autorů: Department of Physics and Astronomy, University of Georgia, Athens, Georgia, United States of America ^aff001; Data Science Initiative, Brown University, Providence, Rhode Island, United States of America ^aff002; Center for Nonlinear Studies (T-CNLS), Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America ^aff003; Department of Mathematical Sciences, The University of Texas at Dallas, Richardson, Texas, United States of America ^aff004; Physics and Chemistry of Materials (T-1), Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America ^aff005; Information Sciences (CCS-3), Computer, Computational and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico, United States of America ^aff006
Vyšlo v časopise: PLoS ONE 15(1)
Kategorie: Research Article
doi: https://doi.org/10.1371/journal.pone.0226787

Souhrn

Isomer search or molecule enumeration refers to the problem of finding all the isomers for a given molecule. Many classical search methods have been developed in order to tackle this problem. However, the availability of quantum computing architectures has given us the opportunity to address this problem with new (quantum) techniques. This paper describes a quantum isomer search procedure for determining all the structural isomers of alkanes. We first formulate the structural isomer search problem as a quadratic unconstrained binary optimization (QUBO) problem. The QUBO formulation is for general use on either annealing or gate-based quantum computers. We use the D-Wave quantum annealer to enumerate all structural isomers of all alkanes with fewer carbon atoms (n < 10) than Decane (C₁₀H₂₂). The number of isomer solutions increases with the number of carbon atoms. We find that the sampling time needed to identify all solutions scales linearly with the number of carbon atoms in the alkane. We probe the problem further by employing reverse annealing as well as a perturbed QUBO Hamiltonian and find that the combination of these two methods significantly reduces the number of samples required to find all isomers.

Klíčová slova:

Carbon – Isomers – Qubits – Simulated annealing – Alkanes – Perturbation theory – Quantum computing – Constitutional isomers

Zdroje

1. Lucas A. Ising formulations of many NP problems. Frontiers in Physics. 2014;2:5. doi: 10.3389/fphy.2014.00005

2. Cervera-Lierta A. Exact Ising model simulation on a quantum computer. Quantum. 2018;2:114. doi: 10.22331/q-2018-12-21-114

3. Bian Z, Chudak F, Macready W, Rose G. The Ising model: teaching an old problem new tricks. D-Wave Systems. 2010;.

4. Ushijima-Mwesigwa H, Negre CFA, Mniszewski SM. Graph Partitioning Using Quantum Annealing on the D-Wave System. In: Proceedings of the Second International Workshop on Post Moores Era Supercomputing. PMES’17. New York, NY, USA: ACM; 2017. p. 22–29. Available from: http://doi.acm.org/10.1145/3149526.3149531.

5. Negre CFA, Ushijima-Mwesigwa H, Mniszewski SM. Detecting Multiple Communities Using Quantum Annealing on the D-Wave System. arXiv preprint arXiv:190109756. 2019;.

6. Minkin VI. Glossary of terms used in theoretical organic chemistry. J Macromol Sci Part A Pure Appl Chem. 1999;71(10):1919–1981.

7. Moss GP. Basic terminology of stereochemistry (IUPAC Recommendations 1996). J Macromol Sci Part A Pure Appl Chem. 1996;68(12):2193–2222.

8. Reading E, Munoz-Muriedas J, Roberts AD, Dear GJ, Robinson CV, Beaumont C. Elucidation of Drug Metabolite Structural Isomers Using Molecular Modeling Coupled with Ion Mobility Mass Spectrometry. Analytical Chemistry. 2016;88(4):2273–2280. doi: 10.1021/acs.analchem.5b04068 26752623

9. Mäki-Arvela P, Kaka khel T, Azkaar M, Engblom S, Murzin D. Catalytic Hydroisomerization of Long-Chain Hydrocarbons for the Production of Fuels. Catalysts. 2018;8(534).

10. Ranzi E, Pierucci S, Dente M, van Goethem M, van Meeuwen D, Wagner E. Correct Molecular Reconstruction of Cracking Feeds: a Need for the Accurate Predictions of Ethylene Yields. Chemical Engineering Transactions. 2015;43:871–876.

11. Faulon JL, Visco DP, Roe D. Enumerating Molecules. In: Reviews in Computational Chemistry. vol. 21. Hoboken, New Jersey: John Wiley & Sons Inc.; 2005. p. 209–275.

12. Lederberg J. Topology of Molecules. In: The Mathematical sciences; a collection of essays. Cambridge, Mass.: M.I.T. Press; 1969. p. 37–51.

13. Lindsay RK, Buchanan BG, Feigenbaum EA, Lederberg J. Applications of Artificial Intelligence for Organic Chemistry: The DENDRAL Project. New York: McGraw-Hill; 1980.

14. Lederberg J, Sutherland GL, Buchanan BG, Feigenbaum EA, Robertson AV, Duffield AM, et al. Applications of artificial intelligence for chemical inference. I. Number of possible organic compounds. Acyclic structures containing carbon, hydrogen, oxygen, and nitrogen. Journal of the American Chemical Society. 1969;91(11):2973–2976. doi: 10.1021/ja01039a025

15. Hendrickson JB, Parks CA. Generation and enumeration of carbon skeletons. Journal of Chemical Information and Computer Sciences. 1991;31(1):101–107.

16. Contreras ML, Valdivia R, Rozas R. Exhaustive generation of organic isomers. 1. Acyclic structures. Journal of Chemical Information and Computer Sciences. 1992;32(4):323–330.

17. Luinge HJ. AEGIS, a Structure Generation Program in Prolog. MATCH. 1992;27:175.

18. Zhu SY, Zhang JP. Exhaustive generation of structural isomers for a given empirical formula—a new algorithm. Journal of Chemical Information and Computer Sciences. 1982;22(1):34–38.

19. Barone R, Barberis F, Chanon M. Exhaustive Generation of Organic Isomers from Base 2 and Base 4 Numbers. MATCH. 1995;32:19–25.

20. Kerber A, Laue R, Moser DA. Structure Generator for Molecular Graphs. Analytica Chimica Acta. 1990;235:2973.

21. Le Bret C. Exhaustive Isomer Generation using the Genetic Algorithm. Match. 2000;41: 79–97.

22. Carhart RE, Smith DH. Applications of artificial intelligence for chemical inference–XX. Computers & Chemistry. 1977;1:79–84.

23. Carhart RE, Smith DH, Gray NAB, Nourse JG, Djerassi C. GENOA: A computer program for structure elucidation utilizing overlapping and alternative substructures. Journal of Organic Chemistry—J ORG CHEM. 1981;46.

24. Badertscher M, Korytko AI, Schulz KP, Madison MS, Munk ME, Portmann P, et al. Assemble 2.0: a structure generator. Chemometrics and Intelligent laboratory Systems. 2000;51(1):73–79. doi: 10.1016/S0169-7439(00)00056-3

25. Funatsu K, Miyabayashi N, Sasaki S. Further development of structure generation in the automated structure elucidation system CHEMICS. Journal of Chemical Information and Computer Sciences. 1988;28(1):18–28.

26. Carabedian M, Dagane I, Dubois JE. Elucidation by progressive intersection of ordered substructures from carbon-13 nuclear magnetic resonance. Analytical Chemistry. 1988;60(20):2186–2192. doi: 10.1021/ac00171a005

27. Bohanec S, Zupan J. Structure Generator GEN. MATCH. 1992;27:49.

28. Elyashberg ME, Blinov KA, Williams AJ, Martirosian ER, Molodtsov SG. Application of a New Expert System for the Structure Elucidation of Natural Products from Their 1D and 2D NMR Data. Journal of Natural Products. 2002;65(5):693–703. doi: 10.1021/np0103315 12027744

29. Lindel T, Junker J, Köck M. Cocon: From NMR Correlation Data to Molecular Constitutions. Molecular modeling annual. 1997;3(8):364–368. doi: 10.1007/s008940050052

30. Will M, Fachinger W, Richert JR. Fully Automated Structure ElucidationA Spectroscopist’s Dream Comes True. Journal of Chemical Information and Computer Sciences. 1996;36(2):221–227. doi: 10.1021/ci950092p

31. Hu C, Xu L. Computer Automated Structure Elucidation Expert System, Esesoc. Fenxi Huaxue. 1992;20:643.

32. Hao J, Xu L, Hu C. Expert System for Elucidation of Structures of Organic Compounds (Esesoc)- Algorithm on Stereoisomer Generation. vol. 43 of B: Chemistry. Science in China; 2000.

33. Faulon JL. Stochastic Generator of Chemical Structure. 1. Application to the Structure Elucidation of Large Molecules. Journal of Chemical Information and Computer Sciences. 1994;34(5):1204–1218.

34. Faulon JL. Stochastic Generator of Chemical Structure. 2. Using Simulated Annealing To Search the Space of Constitutional Isomers. Journal of Chemical Information and Computer Sciences. 1996;36(4):731–740. doi: 10.1021/ci950179a

35. Steinbeck C. SENECA: A Platform-Independent, Distributed, and Parallel System for Computer-Assisted Structure Elucidation in Organic Chemistry. Journal of Chemical Information and Computer Sciences. 2001;41(6):1500–1507. doi: 10.1021/ci000407n 11749575

36. Christie BD, Munk ME. Structure generation by reduction: a new strategy for computer-assisted structure elucidation. Journal of Chemical Information and Computer Sciences. 1988;28(2):87–93. doi: 10.1021/ci00058a009 3392122

37. Christie BD, Munk ME. The role of two-dimensional nuclear magnetic resonance spectroscopy in computer-enhanced structure elucidation. Journal of the American Chemical Society. 1991;113(10):3750–3757. doi: 10.1021/ja00010a018

38. Peng C, Yuan S, Zheng C, Hui Y, Wu H, Ma K, et al. Application of Expert System CISOC-SES to the Structure Elucidation of Complex Natural Products. Journal of Chemical Information and Computer Sciences. 1994;34(4):814–819.

39. Elyashberg ME, Martirosian ER, Karasev YZ, Thiele H, Somberg H. X-PERT: a user-friendly expert system for molecular structure elucidation by spectral methods. Analytica Chimica Acta. 1997;337:265–286. doi: 10.1016/S0003-2670(96)00391-1

40. D-Wave. The D-Wave 2000Q System;. https://www.dwavesys.com/d-wave-two-system.

41. D-Wave QPU Architecture: Chimera; 2019. Available from: https://docs.dwavesys.com/docs/latest/c_gs_4.html [cited 2019 July 11].

42. Matsuda Y, Nishimori H, Katzgraber H . Quantum annealing for problems with ground-state degeneracy. Journal of Physics: Conference Series. 2009;143(012003).

43. Bondy JA, Murty USR. Graph Theory. vol. 244 of Graduate Text in Mathematics. Springer-Verlag London; 2008.

44. Glover FW, Kochenberger GA. A Tutorial on Formulating QUBO Models. CoRR. 2018;abs/1811.11538.

45. D-Wave’s Ocean Software; 2019. Available from: https://ocean.dwavesys.com/ [cited 2019 July 11].

46. D-Wave. Solving a Problem on the QPU; 2019. https://docs.dwavesys.com/docs/latest/c_handbook_6.html#overcoming-imprecisions-of-qubit-biases-and-coupling-strengths.

47. D-Wave. D-Wave Makes New Lower-Noise Quantum Processor Available in Leap; 2019. https://www.dwavesys.com/press-releases/d-wave-makes-new-lower-noise-quantum-processor-available-leap.

48. D-Wave. Los Alamos National Laboratory Upgrades to D-Wave 2000Q™ Quantum Computer; 2019. https://www.dwavesys.com/press-releases/los-alamos-national-laboratory-upgrades-d-wave-2000q%E2%84%A2-quantum-computer.

49. Pudenz KL, Albash T, Lidar DA. Quantum annealing correction for random Ising problems. Physical Review A. 2015;91(4):042302. doi: 10.1103/PhysRevA.91.042302

50. King J, Mohseni M, Bernoudy W, Fréchette A, Sadeghi H, Isakov S, et al. Quantum-Assisted Genetic Algorithm. arXiv preprint arXiv:190700707. 2019;.

51. Peruzzo A, McClean J, Shadbolt P, Yung M, Zhou X, Love P, et al. A variational eigenvalue solver on a photonic quantum processor. Nature Communications. 2014;5 (4213). doi: 10.1038/ncomms5213 25055053

52. Farhi E, Goldstone J. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:14114028. 2014;.

53. Qiskit; 2019. Available from: https://qiskit.org/ [cited 2019 July 11].

54. IBM Q systems; 2019. Available from: https://www.research.ibm.com/ibm-q/technology/devices/ [cited 2019 July 11].

55. Kelley J. A Preview of Bristlecone, Google’s New Quantum Processor; 2018.

56. Numpy; 2019. Available from: https://www.numpy.org/ [cited 2019 July 11].

57. Sympy; 2018. Available from: https://www.sympy.org/en/index.html [cited 2019 July 11].

58. Hagberg AA, Schult DA, Swart PJ. Exploring Network Structure, Dynamics, and Function using NetworkX. In: Proceedings of the 7th Python in Science Conference (SciPy 2008). SciPy 2008. ACM; 2008. p. 11–16.

59. Matplotlib; 2019. Available from: https://matplotlib.org/ [cited 2019 July 11].

60. D-Wave. Breakdown of QPU Access Time; 2019. https://docs.dwavesys.com/docs/latest/c_timing_2.html.

61. D-Wave. Types of Postprocessing; 2019. https://docs.dwavesys.com/docs/latest/c_post-processing_1.html.

62. D-Wave. Sampling Tests and Results; 2019. https://docs.dwavesys.com/docs/latest/c_post-processing_4.html#sampling-tests-and-results.

63. Denchev V, Boixo S, Isakov S, Ding N, Babbush R, Smelyanskiy V, et al. What is the Computational Value of Finite Range Tunneling? arXiv preprint arXiv:151202206. 2016;.

Quantum isomer search

Souhrn

Klíčová slova:

Zdroje

PLOS One

INSIGHTS from European Respiratory Congress

Současné pohledy na riziko v parodontologii

Svět praktické medicíny 3/2024 (znalostní test z časopisu)

Kardiologické projevy hypereozinofilií

Střevní příprava před kolonoskopií