Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping Article Swipe

PDF

Filip B. Maciejewski , Jacob Biamonte , Stuart Hadfield , Davide Venturelli ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2404.01412

We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios $0.9$-$0.96$ for random, fully connected graphs on $n=82$ qubits, using only depth $p=1$ QAOA with NDAR. This compares to $0.34$-$0.51$ for standard $p=1$ QAOA with the same number of function calls.

Related Topics

Computer Science

Quantum

Algorithm

Artificial Intelligence

Mathematics

Physics

Quantum Mechanics

Concepts

Noise (video) Computer science Quantum Mathematical optimization Algorithm Artificial intelligence Mathematics Physics Quantum mechanics Image (mathematics)

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2404.01412
PDF: https://arxiv.org/pdf/2404.01412
OA Status: green
Cited By: 2
Related Works: 10
OpenAlex ID: https://openalex.org/W4393924656

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4393924656

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2404.01412

Digital Object Identifier
Title: Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-04-01

Full publication date if available
Authors: Filip B. Maciejewski, Jacob Biamonte, Stuart Hadfield, Davide Venturelli

List of authors in order
Landing page: https://arxiv.org/abs/2404.01412

Publisher landing page
PDF URL: https://arxiv.org/pdf/2404.01412

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2404.01412

Direct OA link when available
Concepts: Noise (video), Computer science, Quantum, Mathematical optimization, Algorithm, Artificial intelligence, Mathematics, Physics, Quantum mechanics, Image (mathematics)

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2024: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4393924656
doi	https://doi.org/10.48550/arxiv.2404.01412
ids.doi	https://doi.org/10.48550/arxiv.2404.01412
ids.openalex	https://openalex.org/W4393924656
fwci
type	preprint
title	Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
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.9973999857902527
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.9854000210762024
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
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C99498987
concepts[0].level	3
concepts[0].score	0.6210340261459351
concepts[0].wikidata	https://www.wikidata.org/wiki/Q2210247
concepts[0].display_name	Noise (video)
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.5912487506866455
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C84114770
concepts[2].level	2
concepts[2].score	0.567762017250061
concepts[2].wikidata	https://www.wikidata.org/wiki/Q46344
concepts[2].display_name	Quantum
concepts[3].id	https://openalex.org/C126255220
concepts[3].level	1
concepts[3].score	0.3399750590324402
concepts[3].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[3].display_name	Mathematical optimization
concepts[4].id	https://openalex.org/C11413529
concepts[4].level	1
concepts[4].score	0.3251674175262451
concepts[4].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[4].display_name	Algorithm
concepts[5].id	https://openalex.org/C154945302
concepts[5].level	1
concepts[5].score	0.23413890600204468
concepts[5].wikidata	https://www.wikidata.org/wiki/Q11660
concepts[5].display_name	Artificial intelligence
concepts[6].id	https://openalex.org/C33923547
concepts[6].level	0
concepts[6].score	0.22239258885383606
concepts[6].wikidata	https://www.wikidata.org/wiki/Q395
concepts[6].display_name	Mathematics
concepts[7].id	https://openalex.org/C121332964
concepts[7].level	0
concepts[7].score	0.22008734941482544
concepts[7].wikidata	https://www.wikidata.org/wiki/Q413
concepts[7].display_name	Physics
concepts[8].id	https://openalex.org/C62520636
concepts[8].level	1
concepts[8].score	0.12174904346466064
concepts[8].wikidata	https://www.wikidata.org/wiki/Q944
concepts[8].display_name	Quantum mechanics
concepts[9].id	https://openalex.org/C115961682
concepts[9].level	2
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q860623
concepts[9].display_name	Image (mathematics)
keywords[0].id	https://openalex.org/keywords/noise
keywords[0].score	0.6210340261459351
keywords[0].display_name	Noise (video)
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.5912487506866455
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/quantum
keywords[2].score	0.567762017250061
keywords[2].display_name	Quantum
keywords[3].id	https://openalex.org/keywords/mathematical-optimization
keywords[3].score	0.3399750590324402
keywords[3].display_name	Mathematical optimization
keywords[4].id	https://openalex.org/keywords/algorithm
keywords[4].score	0.3251674175262451
keywords[4].display_name	Algorithm
keywords[5].id	https://openalex.org/keywords/artificial-intelligence
keywords[5].score	0.23413890600204468
keywords[5].display_name	Artificial intelligence
keywords[6].id	https://openalex.org/keywords/mathematics
keywords[6].score	0.22239258885383606
keywords[6].display_name	Mathematics
keywords[7].id	https://openalex.org/keywords/physics
keywords[7].score	0.22008734941482544
keywords[7].display_name	Physics
keywords[8].id	https://openalex.org/keywords/quantum-mechanics
keywords[8].score	0.12174904346466064
keywords[8].display_name	Quantum mechanics
language	en
locations[0].id	pmh:oai:arXiv.org:2404.01412
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/2404.01412
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/2404.01412
locations[1].id	doi:10.48550/arxiv.2404.01412
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.2404.01412
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5015959426
authorships[0].author.orcid	https://orcid.org/0000-0002-8503-1193
authorships[0].author.display_name	Filip B. Maciejewski
authorships[0].author_position	first
authorships[0].raw_author_name	Maciejewski, Filip B.
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5079523895
authorships[1].author.orcid	https://orcid.org/0000-0002-0590-3327
authorships[1].author.display_name	Jacob Biamonte
authorships[1].author_position	middle
authorships[1].raw_author_name	Biamonte, Jacob
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5076190671
authorships[2].author.orcid	https://orcid.org/0000-0002-4607-3921
authorships[2].author.display_name	Stuart Hadfield
authorships[2].author_position	middle
authorships[2].raw_author_name	Hadfield, Stuart
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5102985745
authorships[3].author.orcid	https://orcid.org/0000-0003-0452-7603
authorships[3].author.display_name	Davide Venturelli
authorships[3].author_position	last
authorships[3].raw_author_name	Venturelli, Davide
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/2404.01412
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-04-05T00:00:00
display_name	Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
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.9973999857902527
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/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W4391913857
cited_by_count	2
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2404.01412
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/2404.01412
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/2404.01412
primary_location.id	pmh:oai:arXiv.org:2404.01412
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/2404.01412
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/2404.01412
publication_date	2024-04-01
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	6, 25, 33, 38, 65, 82
abstract_inverted_index.In	37
abstract_inverted_index.We	0, 21, 110, 126
abstract_inverted_index.an	112
abstract_inverted_index.as	105
abstract_inverted_index.be	44
abstract_inverted_index.by	15, 58
abstract_inverted_index.in	64, 120
abstract_inverted_index.is	99
abstract_inverted_index.of	19, 85, 92, 158
abstract_inverted_index.on	89, 122, 136
abstract_inverted_index.to	24, 46, 107, 148
abstract_inverted_index.Our	51
abstract_inverted_index.The	75, 96
abstract_inverted_index.can	43
abstract_inverted_index.end	97
abstract_inverted_index.for	9, 131, 150
abstract_inverted_index.it.	109
abstract_inverted_index.the	47, 54, 61, 69, 79, 86, 90, 93, 155
abstract_inverted_index.way	66
abstract_inverted_index.QAOA	143, 153
abstract_inverted_index.This	146
abstract_inverted_index.aids	102
abstract_inverted_index.into	72, 81
abstract_inverted_index.only	140
abstract_inverted_index.runs	119
abstract_inverted_index.same	156
abstract_inverted_index.such	41
abstract_inverted_index.that	31, 67, 100
abstract_inverted_index.with	29, 144, 154
abstract_inverted_index.$p=1$	142, 152
abstract_inverted_index.NDAR.	145
abstract_inverted_index.based	88
abstract_inverted_index.depth	141
abstract_inverted_index.fully	133
abstract_inverted_index.noise	42, 55, 70, 101
abstract_inverted_index.noisy	26
abstract_inverted_index.state	57
abstract_inverted_index.step.	95
abstract_inverted_index.types	18
abstract_inverted_index.using	139
abstract_inverted_index.$n=82$	137
abstract_inverted_index.(QAOA)	118
abstract_inverted_index.access	23
abstract_inverted_index.binary	12
abstract_inverted_index.calls.	160
abstract_inverted_index.global	34
abstract_inverted_index.graphs	135
abstract_inverted_index.noise.	20
abstract_inverted_index.number	157
abstract_inverted_index.ratios	129
abstract_inverted_index.report	127
abstract_inverted_index.result	98
abstract_inverted_index.state.	36
abstract_inverted_index.(NDAR),	5
abstract_inverted_index.Quantum	114
abstract_inverted_index.certain	17
abstract_inverted_index.changes	78
abstract_inverted_index.device.	125
abstract_inverted_index.opposed	106
abstract_inverted_index.present	1, 111
abstract_inverted_index.quantum	27, 48, 124
abstract_inverted_index.qubits,	138
abstract_inverted_index.random,	132
abstract_inverted_index.results	91
abstract_inverted_index.solving	11
abstract_inverted_index.Adaptive	3
abstract_inverted_index.compares	147
abstract_inverted_index.consider	22
abstract_inverted_index.dynamics	30
abstract_inverted_index.features	32
abstract_inverted_index.function	159
abstract_inverted_index.improved	113
abstract_inverted_index.previous	94
abstract_inverted_index.problems	14
abstract_inverted_index.setting,	40
abstract_inverted_index.solution	84
abstract_inverted_index.standard	39, 151
abstract_inverted_index.Algorithm	117
abstract_inverted_index.Remapping	4
abstract_inverted_index.Rigetti's	123
abstract_inverted_index.algorithm	8, 52
abstract_inverted_index.attractor	35, 56, 71, 80
abstract_inverted_index.connected	134
abstract_inverted_index.heuristic	7
abstract_inverted_index.hindering	108
abstract_inverted_index.processor	28
abstract_inverted_index.bootstraps	53
abstract_inverted_index.leveraging	16
abstract_inverted_index.solutions.	74
abstract_inverted_index.transforms	68
abstract_inverted_index.Approximate	115
abstract_inverted_index.Hamiltonian	63, 87
abstract_inverted_index.detrimental	45
abstract_inverted_index.effectively	77
abstract_inverted_index.experiments	121
abstract_inverted_index.iteratively	59
abstract_inverted_index.variational	103
abstract_inverted_index.$0.9$-$0.96$	130
abstract_inverted_index.Optimization	116
abstract_inverted_index.optimization	13, 49
abstract_inverted_index.performance.	50
abstract_inverted_index.$0.34$-$0.51$	149
abstract_inverted_index.approximately	10
abstract_inverted_index.approximation	128
abstract_inverted_index.cost-function	62
abstract_inverted_index.optimization,	104
abstract_inverted_index.Noise-Directed	2
abstract_inverted_index.higher-quality	73, 83
abstract_inverted_index.transformation	76
abstract_inverted_index.gauge-transforming	60
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile