Efficient Quantum Counting and Quantum Content-Addressable Memory for DNA similarity Article Swipe
J. Balewski
,
Daan Camps
,
Katherine Klymko
,
Andrew Tritt
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.00699
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.00699
We present QCAM, a quantum analogue of Content-Addressable Memory (CAM), useful for finding matches in two sequences of bit-strings. Our QCAM implementation takes advantage of Grover's search algorithm and proposes a highly-optimized quantum circuit implementation of the QCAM oracle. Our circuit construction uses the parallel uniformly controlled rotation gates, which were used in previous work to generate QBArt encodings. These circuits have a high degree of quantum parallelism which reduces their critical depth. The optimal number of repetitions of the Grover iterator used in QCAM depends on the number of true matches and hence is input dependent. We additionally propose a hardware-efficient implementation of the quantum counting algorithm (HEQC) that can infer the optimal number of Grover iterations from the measurement of a single observable. We demonstrate the QCAM application for computing the Jaccard similarity between two sets of k-mers obtained from two DNA sequences.
Related Topics
Concepts
Computer science
Quantum
Quantum circuit
Oracle
Quantum computer
Algorithm
Quantum algorithm
Parallel computing
Theoretical computer science
Quantum error correction
Physics
Quantum mechanics
Software engineering
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2308.00699
- https://arxiv.org/pdf/2308.00699
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4385894646
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4385894646Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2308.00699Digital Object Identifier
- Title
-
Efficient Quantum Counting and Quantum Content-Addressable Memory for DNA similarityWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-08-01Full publication date if available
- Authors
-
J. Balewski, Daan Camps, Katherine Klymko, Andrew TrittList of authors in order
- Landing page
-
https://arxiv.org/abs/2308.00699Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2308.00699Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2308.00699Direct OA link when available
- Concepts
-
Computer science, Quantum, Quantum circuit, Oracle, Quantum computer, Algorithm, Quantum algorithm, Parallel computing, Theoretical computer science, Quantum error correction, Physics, Quantum mechanics, Software engineeringTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4385894646 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2308.00699 |
| ids.doi | https://doi.org/10.48550/arxiv.2308.00699 |
| ids.openalex | https://openalex.org/W4385894646 |
| fwci | |
| type | preprint |
| title | Efficient Quantum Counting and Quantum Content-Addressable Memory for DNA similarity |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T13182 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9980000257492065 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Quantum-Dot Cellular Automata |
| topics[1].id | https://openalex.org/T10682 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9914000034332275 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Quantum Computing Algorithms and Architecture |
| topics[2].id | https://openalex.org/T10207 |
| topics[2].field.id | https://openalex.org/fields/13 |
| topics[2].field.display_name | Biochemistry, Genetics and Molecular Biology |
| topics[2].score | 0.9573000073432922 |
| topics[2].domain.id | https://openalex.org/domains/1 |
| topics[2].domain.display_name | Life Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1312 |
| topics[2].subfield.display_name | Molecular Biology |
| topics[2].display_name | Advanced biosensing and bioanalysis techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.6965111494064331 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C84114770 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5407616496086121 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q46344 |
| concepts[1].display_name | Quantum |
| concepts[2].id | https://openalex.org/C124148022 |
| concepts[2].level | 5 |
| concepts[2].score | 0.4941149055957794 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2122210 |
| concepts[2].display_name | Quantum circuit |
| concepts[3].id | https://openalex.org/C55166926 |
| concepts[3].level | 2 |
| concepts[3].score | 0.47067078948020935 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2892946 |
| concepts[3].display_name | Oracle |
| concepts[4].id | https://openalex.org/C58053490 |
| concepts[4].level | 3 |
| concepts[4].score | 0.44405829906463623 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q176555 |
| concepts[4].display_name | Quantum computer |
| concepts[5].id | https://openalex.org/C11413529 |
| concepts[5].level | 1 |
| concepts[5].score | 0.4240819215774536 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[5].display_name | Algorithm |
| concepts[6].id | https://openalex.org/C137019171 |
| concepts[6].level | 3 |
| concepts[6].score | 0.42135488986968994 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2623817 |
| concepts[6].display_name | Quantum algorithm |
| concepts[7].id | https://openalex.org/C173608175 |
| concepts[7].level | 1 |
| concepts[7].score | 0.406451016664505 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[7].display_name | Parallel computing |
| concepts[8].id | https://openalex.org/C80444323 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3471025824546814 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[8].display_name | Theoretical computer science |
| concepts[9].id | https://openalex.org/C51003876 |
| concepts[9].level | 4 |
| concepts[9].score | 0.1864299774169922 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q1536431 |
| concepts[9].display_name | Quantum error correction |
| concepts[10].id | https://openalex.org/C121332964 |
| concepts[10].level | 0 |
| concepts[10].score | 0.09489637613296509 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[10].display_name | Physics |
| concepts[11].id | https://openalex.org/C62520636 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[11].display_name | Quantum mechanics |
| concepts[12].id | https://openalex.org/C115903868 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q80993 |
| concepts[12].display_name | Software engineering |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.6965111494064331 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/quantum |
| keywords[1].score | 0.5407616496086121 |
| keywords[1].display_name | Quantum |
| keywords[2].id | https://openalex.org/keywords/quantum-circuit |
| keywords[2].score | 0.4941149055957794 |
| keywords[2].display_name | Quantum circuit |
| keywords[3].id | https://openalex.org/keywords/oracle |
| keywords[3].score | 0.47067078948020935 |
| keywords[3].display_name | Oracle |
| keywords[4].id | https://openalex.org/keywords/quantum-computer |
| keywords[4].score | 0.44405829906463623 |
| keywords[4].display_name | Quantum computer |
| keywords[5].id | https://openalex.org/keywords/algorithm |
| keywords[5].score | 0.4240819215774536 |
| keywords[5].display_name | Algorithm |
| keywords[6].id | https://openalex.org/keywords/quantum-algorithm |
| keywords[6].score | 0.42135488986968994 |
| keywords[6].display_name | Quantum algorithm |
| keywords[7].id | https://openalex.org/keywords/parallel-computing |
| keywords[7].score | 0.406451016664505 |
| keywords[7].display_name | Parallel computing |
| keywords[8].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[8].score | 0.3471025824546814 |
| keywords[8].display_name | Theoretical computer science |
| keywords[9].id | https://openalex.org/keywords/quantum-error-correction |
| keywords[9].score | 0.1864299774169922 |
| keywords[9].display_name | Quantum error correction |
| keywords[10].id | https://openalex.org/keywords/physics |
| keywords[10].score | 0.09489637613296509 |
| keywords[10].display_name | Physics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2308.00699 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2308.00699 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2308.00699 |
| locations[1].id | doi:10.48550/arxiv.2308.00699 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2308.00699 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5065230562 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-1899-6526 |
| authorships[0].author.display_name | J. Balewski |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Balewski, Jan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5015674933 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-0236-4353 |
| authorships[1].author.display_name | Daan Camps |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Camps, Daan |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5034924651 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-4158-5776 |
| authorships[2].author.display_name | Katherine Klymko |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Klymko, Katherine |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5076792091 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-1617-449X |
| authorships[3].author.display_name | Andrew Tritt |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Tritt, Andrew |
| authorships[3].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2308.00699 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-08-18T00:00:00 |
| display_name | Efficient Quantum Counting and Quantum Content-Addressable Memory for DNA similarity |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T13182 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9980000257492065 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Quantum-Dot Cellular Automata |
| related_works | https://openalex.org/W2409877639, https://openalex.org/W4388704119, https://openalex.org/W2910123824, https://openalex.org/W4200149527, https://openalex.org/W4213379151, https://openalex.org/W1889203613, https://openalex.org/W4281550036, https://openalex.org/W3206120658, https://openalex.org/W4390992964, https://openalex.org/W3131420525 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2308.00699 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2308.00699 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2308.00699 |
| primary_location.id | pmh:oai:arXiv.org:2308.00699 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2308.00699 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2308.00699 |
| publication_date | 2023-08-01 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 3, 30, 62, 100, 122 |
| abstract_inverted_index.We | 0, 97, 125 |
| abstract_inverted_index.in | 14, 52, 83 |
| abstract_inverted_index.is | 94 |
| abstract_inverted_index.of | 6, 17, 24, 35, 65, 76, 78, 89, 103, 115, 121, 138 |
| abstract_inverted_index.on | 86 |
| abstract_inverted_index.to | 55 |
| abstract_inverted_index.DNA | 143 |
| abstract_inverted_index.Our | 19, 39 |
| abstract_inverted_index.The | 73 |
| abstract_inverted_index.and | 28, 92 |
| abstract_inverted_index.can | 110 |
| abstract_inverted_index.for | 11, 130 |
| abstract_inverted_index.the | 36, 43, 79, 87, 104, 112, 119, 127, 132 |
| abstract_inverted_index.two | 15, 136, 142 |
| abstract_inverted_index.QCAM | 20, 37, 84, 128 |
| abstract_inverted_index.from | 118, 141 |
| abstract_inverted_index.have | 61 |
| abstract_inverted_index.high | 63 |
| abstract_inverted_index.sets | 137 |
| abstract_inverted_index.that | 109 |
| abstract_inverted_index.true | 90 |
| abstract_inverted_index.used | 51, 82 |
| abstract_inverted_index.uses | 42 |
| abstract_inverted_index.were | 50 |
| abstract_inverted_index.work | 54 |
| abstract_inverted_index.QBArt | 57 |
| abstract_inverted_index.QCAM, | 2 |
| abstract_inverted_index.These | 59 |
| abstract_inverted_index.hence | 93 |
| abstract_inverted_index.infer | 111 |
| abstract_inverted_index.input | 95 |
| abstract_inverted_index.takes | 22 |
| abstract_inverted_index.their | 70 |
| abstract_inverted_index.which | 49, 68 |
| abstract_inverted_index.(CAM), | 9 |
| abstract_inverted_index.(HEQC) | 108 |
| abstract_inverted_index.Grover | 80, 116 |
| abstract_inverted_index.Memory | 8 |
| abstract_inverted_index.degree | 64 |
| abstract_inverted_index.depth. | 72 |
| abstract_inverted_index.gates, | 48 |
| abstract_inverted_index.k-mers | 139 |
| abstract_inverted_index.number | 75, 88, 114 |
| abstract_inverted_index.search | 26 |
| abstract_inverted_index.single | 123 |
| abstract_inverted_index.useful | 10 |
| abstract_inverted_index.Jaccard | 133 |
| abstract_inverted_index.between | 135 |
| abstract_inverted_index.circuit | 33, 40 |
| abstract_inverted_index.depends | 85 |
| abstract_inverted_index.finding | 12 |
| abstract_inverted_index.matches | 13, 91 |
| abstract_inverted_index.optimal | 74, 113 |
| abstract_inverted_index.oracle. | 38 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.propose | 99 |
| abstract_inverted_index.quantum | 4, 32, 66, 105 |
| abstract_inverted_index.reduces | 69 |
| abstract_inverted_index.Grover's | 25 |
| abstract_inverted_index.analogue | 5 |
| abstract_inverted_index.circuits | 60 |
| abstract_inverted_index.counting | 106 |
| abstract_inverted_index.critical | 71 |
| abstract_inverted_index.generate | 56 |
| abstract_inverted_index.iterator | 81 |
| abstract_inverted_index.obtained | 140 |
| abstract_inverted_index.parallel | 44 |
| abstract_inverted_index.previous | 53 |
| abstract_inverted_index.proposes | 29 |
| abstract_inverted_index.rotation | 47 |
| abstract_inverted_index.advantage | 23 |
| abstract_inverted_index.algorithm | 27, 107 |
| abstract_inverted_index.computing | 131 |
| abstract_inverted_index.sequences | 16 |
| abstract_inverted_index.uniformly | 45 |
| abstract_inverted_index.controlled | 46 |
| abstract_inverted_index.dependent. | 96 |
| abstract_inverted_index.encodings. | 58 |
| abstract_inverted_index.iterations | 117 |
| abstract_inverted_index.sequences. | 144 |
| abstract_inverted_index.similarity | 134 |
| abstract_inverted_index.application | 129 |
| abstract_inverted_index.demonstrate | 126 |
| abstract_inverted_index.measurement | 120 |
| abstract_inverted_index.observable. | 124 |
| abstract_inverted_index.parallelism | 67 |
| abstract_inverted_index.repetitions | 77 |
| abstract_inverted_index.additionally | 98 |
| abstract_inverted_index.bit-strings. | 18 |
| abstract_inverted_index.construction | 41 |
| abstract_inverted_index.implementation | 21, 34, 102 |
| abstract_inverted_index.highly-optimized | 31 |
| abstract_inverted_index.hardware-efficient | 101 |
| abstract_inverted_index.Content-Addressable | 7 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |