Skip to main content
Journal cover image

Alternative computational models: A comparison of biomolecular and quantum computation extended abstract

Publication ,  Conference
Reif, JH
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 1998

Molecular Computation (MC) is massively parallel computation where data is stored and processed within objects of molecular size. Biomolecular Computation (BMC) is MC using biotechnology techniques, e.g. recombinant DNA operations. In contrast, Quantum Computation (QC) is a type of computation where unitary and measurement operations are executed on linear superpositions of classical states. Both BMC and QC may be executed at the micromolecular scale by a variety of methodologies and technologies. This paper surveys various methods for doing BMC and QC and discusses the considerable theoretical and practical advances in BMC and QC made in the last few years. We compare bounds on key resource such as time, volume (number of molecules times molecular density), energy and error rates achievable, taking particular note of the scalability of these methods with the size of the problem solved. In addition to NP search problems and database search problems, we enumerate a wide variety of further potential practical applications of BMC and QC. We observe that certain problems if solved with polynomial time bounds appear to require exponentially large volume for BMC (e.g., NP search problems) and QC (e.g., the observation operation). We discuss techniques for decreasing errors in BMC (e.g., annealing errors) and QC (e.g., decoherence errors), and volume where possible, to insure the scalability of BMC and QC to problems of large input size. In addition, we consider how BMC might be used to assist QC (e.g., to do observation operations for Bulk QC) and also how quantum techniques might be used to assist BMC (e.g., to do exquisite detection of very small quantities of a molecule in solution within a large volume). © Springer-Verlag Berlin Heidelberg 1998.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540653844

Publication Date

December 1, 1998

Volume

1530 LNCS

Start / End Page

102 / 126

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1998). Alternative computational models: A comparison of biomolecular and quantum computation extended abstract. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 1530 LNCS, pp. 102–126). https://doi.org/10.1007/978-3-540-49382-2_10
Reif, J. H. “Alternative computational models: A comparison of biomolecular and quantum computation extended abstract.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1530 LNCS:102–26, 1998. https://doi.org/10.1007/978-3-540-49382-2_10.
Reif JH. Alternative computational models: A comparison of biomolecular and quantum computation extended abstract. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1998. p. 102–26.
Reif, J. H. “Alternative computational models: A comparison of biomolecular and quantum computation extended abstract.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1530 LNCS, 1998, pp. 102–26. Scopus, doi:10.1007/978-3-540-49382-2_10.
Reif JH. Alternative computational models: A comparison of biomolecular and quantum computation extended abstract. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1998. p. 102–126.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540653844

Publication Date

December 1, 1998

Volume

1530 LNCS

Start / End Page

102 / 126

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences