{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T05:28:29Z","timestamp":1774070909138,"version":"3.50.1"},"reference-count":0,"publisher":"Rinton Press","issue":"13&14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>We consider some classical and quantum approximate optimization algorithms with bounded depth.  First, we define a class of \"local\" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2.  Second, we show that this class of classical algorithms generalizes a class previously considered in the literature\\cite{hirvonen2014large}, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances.  In fact, for all but 4 choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining 4 choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of ``global\" classical algorithms.  These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.<\/jats:p>","DOI":"10.26421\/qic19.13-14-3","type":"journal-article","created":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T19:18:39Z","timestamp":1613416719000},"page":"1116-1140","source":"Crossref","is-referenced-by-count":45,"title":["Classical and quantum bounded depth approximation algorithms"],"prefix":"10.26421","volume":"19","author":[{"given":"Matthew B.","family":"Hastings","sequence":"first","affiliation":[]}],"member":"10955","published-online":{"date-parts":[[2019,11]]},"container-title":["quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T19:18:43Z","timestamp":1613416723000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC19.13-14-3.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":0,"journal-issue":{"issue":"13&14","published-online":{"date-parts":[[2019,11]]},"published-print":{"date-parts":[[2019,11]]}},"URL":"https:\/\/doi.org\/10.26421\/qic19.13-14-3","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}