Reachability Deficits in Quantum Approximate Optimization.

Akshay, V; Philathong, H; Morales, MES; Biamonte, JD

Reachability Deficits in Quantum Approximate Optimization.

Akshay, V Philathong, H Morales, MES Biamonte, JD

Permalink

Publisher:: American Physical Society (APS)
Publication Type:: Journal Article
Citation:: Physical review letters, 2020, 124, (9)
Issue Date:: 2020-03

In Progress

	Filename	Description	Size
	1906.11259v2.pdf	Accepted Manuscript	536.94 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is being processed and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Akshay, V
dc.contributor.author	Philathong, H
dc.contributor.author	Morales, MES
dc.contributor.author	Biamonte, JD
dc.date.accessioned	2021-03-23T03:43:53Z
dc.date.available	2020-02-03
dc.date.available	2021-03-23T03:43:53Z
dc.date.issued	2020-03
dc.identifier.citation	Physical review letters, 2020, 124, (9)
dc.identifier.issn	0031-9007
dc.identifier.issn	1079-7114
dc.identifier.uri	http://hdl.handle.net/10453/147471
dc.description.abstract	The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm's ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
dc.format	Print
dc.language	eng
dc.publisher	American Physical Society (APS)
dc.relation.ispartof	Physical review letters
dc.relation.isbasedon	https://dx.doi.org/10.1103/physrevlett.124.090504
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.rights	The following article has been submitted to/accepted by [Physical review letters]. After it is published, it will be found at (https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.124.090504).
dc.subject	01 Mathematical Sciences, 02 Physical Sciences, 09 Engineering
dc.subject.classification	General Physics
dc.title	Reachability Deficits in Quantum Approximate Optimization.
dc.type	Journal Article
utslib.citation.volume	124
utslib.location.activity	United States
utslib.for	01 Mathematical Sciences
utslib.for	02 Physical Sciences
utslib.for	09 Engineering
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	in_progress	*
pubs.consider-herdc	false
dc.date.updated	2021-03-23T03:43:50Z
pubs.issue	9
pubs.publication-status	Published
pubs.volume	124
utslib.citation.issue	9

Abstract:

The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm's ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/147471