Quantum-Assisted Greedy Algorithms Article Swipe
Ramin Ayanzadeh
,
John E. Dorband
,
Milton Halem
,
Tim Finin
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.02042
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.02042
We show how to leverage quantum annealers (QAs) to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use QAs that sample from the ground state of problem-dependent Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin of the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results on a D-Wave 2000Q quantum processor demonstrate that the proposed quantum-assisted greedy algorithm (QAGA) scheme can find notably better solutions compared to the state-of-the-art techniques in the realm of quantum annealing
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2208.02042
- https://arxiv.org/pdf/2208.02042
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4298129262
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4298129262Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2208.02042Digital Object Identifier
- Title
-
Quantum-Assisted Greedy AlgorithmsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-08-03Full publication date if available
- Authors
-
Ramin Ayanzadeh, John E. Dorband, Milton Halem, Tim FininList of authors in order
- Landing page
-
https://arxiv.org/abs/2208.02042Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2208.02042Direct 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/2208.02042Direct OA link when available
- Concepts
-
Quantum annealing, Heuristics, Leverage (statistics), Quantum, Greedy algorithm, Algorithm, Computer science, Mathematical optimization, Quantum algorithm, Mathematics, Artificial intelligence, Physics, Quantum mechanicsTop 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/W4298129262 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2208.02042 |
| ids.doi | https://doi.org/10.48550/arxiv.2208.02042 |
| ids.openalex | https://openalex.org/W4298129262 |
| fwci | |
| type | preprint |
| title | Quantum-Assisted Greedy Algorithms |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10682 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Quantum Computing Algorithms and Architecture |
| topics[1].id | https://openalex.org/T10020 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9905999898910522 |
| 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 Information and Cryptography |
| topics[2].id | https://openalex.org/T10101 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9732000231742859 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1710 |
| topics[2].subfield.display_name | Information Systems |
| topics[2].display_name | Cloud Computing and Resource Management |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C90408235 |
| concepts[0].level | 4 |
| concepts[0].score | 0.8873666524887085 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q938141 |
| concepts[0].display_name | Quantum annealing |
| concepts[1].id | https://openalex.org/C127705205 |
| concepts[1].level | 2 |
| concepts[1].score | 0.729944109916687 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q5748245 |
| concepts[1].display_name | Heuristics |
| concepts[2].id | https://openalex.org/C153083717 |
| concepts[2].level | 2 |
| concepts[2].score | 0.659946620464325 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q6535263 |
| concepts[2].display_name | Leverage (statistics) |
| concepts[3].id | https://openalex.org/C84114770 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6054660081863403 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q46344 |
| concepts[3].display_name | Quantum |
| concepts[4].id | https://openalex.org/C51823790 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5541014671325684 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q504353 |
| concepts[4].display_name | Greedy algorithm |
| concepts[5].id | https://openalex.org/C11413529 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5399467945098877 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[5].display_name | Algorithm |
| concepts[6].id | https://openalex.org/C41008148 |
| concepts[6].level | 0 |
| concepts[6].score | 0.5228698253631592 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[6].display_name | Computer science |
| concepts[7].id | https://openalex.org/C126255220 |
| concepts[7].level | 1 |
| concepts[7].score | 0.4390879273414612 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[7].display_name | Mathematical optimization |
| concepts[8].id | https://openalex.org/C137019171 |
| concepts[8].level | 3 |
| concepts[8].score | 0.39475247263908386 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q2623817 |
| concepts[8].display_name | Quantum algorithm |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.3112984299659729 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C154945302 |
| concepts[10].level | 1 |
| concepts[10].score | 0.16136229038238525 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[10].display_name | Artificial intelligence |
| concepts[11].id | https://openalex.org/C121332964 |
| concepts[11].level | 0 |
| concepts[11].score | 0.13634687662124634 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[11].display_name | Physics |
| concepts[12].id | https://openalex.org/C62520636 |
| concepts[12].level | 1 |
| concepts[12].score | 0.11832645535469055 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[12].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/quantum-annealing |
| keywords[0].score | 0.8873666524887085 |
| keywords[0].display_name | Quantum annealing |
| keywords[1].id | https://openalex.org/keywords/heuristics |
| keywords[1].score | 0.729944109916687 |
| keywords[1].display_name | Heuristics |
| keywords[2].id | https://openalex.org/keywords/leverage |
| keywords[2].score | 0.659946620464325 |
| keywords[2].display_name | Leverage (statistics) |
| keywords[3].id | https://openalex.org/keywords/quantum |
| keywords[3].score | 0.6054660081863403 |
| keywords[3].display_name | Quantum |
| keywords[4].id | https://openalex.org/keywords/greedy-algorithm |
| keywords[4].score | 0.5541014671325684 |
| keywords[4].display_name | Greedy algorithm |
| keywords[5].id | https://openalex.org/keywords/algorithm |
| keywords[5].score | 0.5399467945098877 |
| keywords[5].display_name | Algorithm |
| keywords[6].id | https://openalex.org/keywords/computer-science |
| keywords[6].score | 0.5228698253631592 |
| keywords[6].display_name | Computer science |
| keywords[7].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[7].score | 0.4390879273414612 |
| keywords[7].display_name | Mathematical optimization |
| keywords[8].id | https://openalex.org/keywords/quantum-algorithm |
| keywords[8].score | 0.39475247263908386 |
| keywords[8].display_name | Quantum algorithm |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.3112984299659729 |
| keywords[9].display_name | Mathematics |
| keywords[10].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[10].score | 0.16136229038238525 |
| keywords[10].display_name | Artificial intelligence |
| keywords[11].id | https://openalex.org/keywords/physics |
| keywords[11].score | 0.13634687662124634 |
| keywords[11].display_name | Physics |
| keywords[12].id | https://openalex.org/keywords/quantum-mechanics |
| keywords[12].score | 0.11832645535469055 |
| keywords[12].display_name | Quantum mechanics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2208.02042 |
| 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/2208.02042 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| 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/2208.02042 |
| locations[1].id | doi:10.48550/arxiv.2208.02042 |
| 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 | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| 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.2208.02042 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5082674928 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-6687-5668 |
| authorships[0].author.display_name | Ramin Ayanzadeh |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ayanzadeh, Ramin |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5051006031 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | John E. Dorband |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Dorband, John E |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5004628313 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-5614-3612 |
| authorships[2].author.display_name | Milton Halem |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Halem, Milton |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5009972149 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Tim Finin |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Finin, Tim |
| 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/2208.02042 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Quantum-Assisted Greedy Algorithms |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10682 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Quantum Computing Algorithms and Architecture |
| related_works | https://openalex.org/W3183948672, https://openalex.org/W3173606202, https://openalex.org/W3110381201, https://openalex.org/W2948807893, https://openalex.org/W2778153218, https://openalex.org/W2758277628, https://openalex.org/W1531601525, https://openalex.org/W3119129187, https://openalex.org/W4286585841, https://openalex.org/W229008713 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2208.02042 |
| 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/2208.02042 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| 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/2208.02042 |
| primary_location.id | pmh:oai:arXiv.org:2208.02042 |
| 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/2208.02042 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| 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/2208.02042 |
| publication_date | 2022-08-03 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 70, 87 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.as | 69 |
| abstract_inverted_index.at | 28, 43, 62 |
| abstract_inverted_index.in | 12, 111 |
| abstract_inverted_index.of | 40, 55, 65, 114 |
| abstract_inverted_index.on | 86 |
| abstract_inverted_index.to | 3, 8, 50, 107 |
| abstract_inverted_index.we | 31, 60 |
| abstract_inverted_index.Our | 83 |
| abstract_inverted_index.QAs | 33 |
| abstract_inverted_index.all | 75 |
| abstract_inverted_index.and | 46, 73 |
| abstract_inverted_index.are | 81 |
| abstract_inverted_index.can | 101 |
| abstract_inverted_index.for | 23 |
| abstract_inverted_index.how | 2 |
| abstract_inverted_index.the | 37, 52, 66, 94, 108, 112 |
| abstract_inverted_index.use | 32, 47 |
| abstract_inverted_index.More | 58 |
| abstract_inverted_index.each | 29, 63 |
| abstract_inverted_index.find | 102 |
| abstract_inverted_index.from | 36 |
| abstract_inverted_index.look | 61 |
| abstract_inverted_index.show | 1 |
| abstract_inverted_index.spin | 64 |
| abstract_inverted_index.that | 19, 34, 93 |
| abstract_inverted_index.(QAs) | 7 |
| abstract_inverted_index.2000Q | 89 |
| abstract_inverted_index.Ising | 67 |
| abstract_inverted_index.model | 68 |
| abstract_inverted_index.realm | 113 |
| abstract_inverted_index.state | 39 |
| abstract_inverted_index.whose | 78 |
| abstract_inverted_index.(QAGA) | 99 |
| abstract_inverted_index.D-Wave | 88 |
| abstract_inverted_index.Unlike | 15 |
| abstract_inverted_index.better | 9, 104 |
| abstract_inverted_index.employ | 20 |
| abstract_inverted_index.greedy | 13, 17, 97 |
| abstract_inverted_index.ground | 38 |
| abstract_inverted_index.making | 24 |
| abstract_inverted_index.random | 71 |
| abstract_inverted_index.sample | 35 |
| abstract_inverted_index.scheme | 100 |
| abstract_inverted_index.select | 10 |
| abstract_inverted_index.stage, | 30 |
| abstract_inverted_index.choices | 27 |
| abstract_inverted_index.locally | 25 |
| abstract_inverted_index.notably | 103 |
| abstract_inverted_index.optimal | 26 |
| abstract_inverted_index.problem | 56, 76 |
| abstract_inverted_index.quantum | 5, 90, 115 |
| abstract_inverted_index.results | 85 |
| abstract_inverted_index.samples | 49 |
| abstract_inverted_index.compared | 106 |
| abstract_inverted_index.contract | 74 |
| abstract_inverted_index.estimate | 51 |
| abstract_inverted_index.leverage | 4 |
| abstract_inverted_index.proposed | 95 |
| abstract_inverted_index.variable | 72 |
| abstract_inverted_index.algorithm | 98 |
| abstract_inverted_index.annealers | 6 |
| abstract_inverted_index.annealing | 116 |
| abstract_inverted_index.cryogenic | 44 |
| abstract_inverted_index.empirical | 84 |
| abstract_inverted_index.processor | 91 |
| abstract_inverted_index.retrieved | 48 |
| abstract_inverted_index.solutions | 105 |
| abstract_inverted_index.variables | 77 |
| abstract_inverted_index.algorithms | 18 |
| abstract_inverted_index.candidates | 11 |
| abstract_inverted_index.heuristics | 22 |
| abstract_inverted_index.techniques | 110 |
| abstract_inverted_index.variables. | 57 |
| abstract_inverted_index.algorithms. | 14 |
| abstract_inverted_index.demonstrate | 92 |
| abstract_inverted_index.negligible. | 82 |
| abstract_inverted_index.probability | 53 |
| abstract_inverted_index.Hamiltonians | 42 |
| abstract_inverted_index.conventional | 16 |
| abstract_inverted_index.distribution | 54 |
| abstract_inverted_index.temperatures | 45 |
| abstract_inverted_index.corresponding | 79 |
| abstract_inverted_index.specifically, | 59 |
| abstract_inverted_index.uncertainties | 80 |
| abstract_inverted_index.problem-specific | 21 |
| abstract_inverted_index.quantum-assisted | 96 |
| abstract_inverted_index.state-of-the-art | 109 |
| abstract_inverted_index.problem-dependent | 41 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |