Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem

Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun

Type: Article

Publication Date: 2024-05-29

Citations: 25

DOI: https://doi.org/10.1126/sciadv.adm6761

View Publication

Locations

Science Advances - View
PubMed Central - View
arXiv (Cornell University) - View - PDF
OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) - View
PubMed - View

Similar Works

Action	Title	Year	Authors
+	Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem	2023	Ruslan Shaydulin Changhao Li Shouvanik Chakrabarti Matthew DeCross Dylan Herman Niraj Kumar Jeffrey Larson Danylo Lykov Pierre Minssen Yue Sun
+ PDF Chat	End-to-End Protocol for High-Quality QAOA Parameters with Few Shots	2024	Tianyi Hao Zichang He Ruslan Shaydulin Jeffrey Larson Marco Pistoia
+ PDF Chat	Evaluating Quantum Approximate Optimization Algorithm: A Case Study	2019	Ruslan Shaydulin Yuri Alexeev
+	A Review on Quantum Approximate Optimization Algorithm and its Variants	2023	Kostas Blekos Dean Brand Andrea Ceschini Chiao-Hui Chou Rui-Hao Li Komal Pandya Alessandro Summer
+ PDF Chat	Approximating under the Influence of Quantum Noise and Compute Power	2024	Simon Thelen Hila Safi Wolfgang Mauerer
+ PDF Chat	NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems	2023	Rhonda Au-Yeung Nicholas Chancellor Pascal Halffmann
+	NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems	2022	Rhonda Au-Yeung Nicholas Chancellor Pascal Halffmann
+	Quantum Approximate Optimization for Hard Problems in Linear Algebra	2020	Ajinkya Borle Vincent E. Elfving Samuel J. Lomonaco
+	Quantum Approximate Optimization for Hard Problems in Linear Algebra	2020	Ajinkya Borle Vincent E. Elfving Samuel J. Lomonaco
+	Quantum algorithms: A survey of applications and end-to-end complexities	2023	Alexander M. Dalzell Sam McArdle Mario Berta Przemysław Bienias Chi-Fang Chen András Gilyén Connor T. Hann Michael J. Kastoryano Emil T. Khabiboulline Aleksander Kubica
+	Optimization Applications as Quantum Performance Benchmarks	2023	Thomas Lubinski Carleton Coffrin Catherine C. McGeoch Pratik Sathe Joshua Apanavicius David E. Bernal Neira
+	Information scrambling and entanglement in quantum approximate optimization algorithm circuits	2023	Qian Chen Wei-Feng Zhuang Rui-Cheng Guo Mengjun Hu Dong E. Liu
+ PDF Chat	Optimization Applications as Quantum Performance Benchmarks	2024	Thomas Lubinski Carleton Coffrin Catherine C. McGeoch Pratik Sathe Joshua Apanavicius David E. Bernal Quantum Economic Development Consortium Collaboration
+	Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware	2022	Johannes Weidenfeller Lucia C. Valor Julien Gacon Caroline Tornow Luciano Bello Stefan Woerner Daniel J. Egger
+ PDF Chat	Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware	2022	Johannes Weidenfeller Lucia C. Valor Julien Gacon Caroline Tornow Luciano Bello Stefan Woerner Daniel J. Egger
+	Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits	2023	Nikola Yanakiev Normann Mertig Christopher K. Long David R. M. Arvidsson-Shukur
+ PDF Chat	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices	2020	Leo Zhou Sheng-Tao Wang Soonwon Choi Hannes Pichler Mikhail D. Lukin
+	Practical Quantum Search by Variational Quantum Eigensolver on Noisy Intermediate-scale Quantum Hardware	2023	Chen-Yu Liu
+ PDF Chat	Entanglement-assisted variational algorithm for discrete optimization problems	2025	Lorenzo Fioroni Vincenzo Savona
+ PDF Chat	EQUAL: Improving the Fidelity of Quantum Annealers by Injecting Controlled Perturbations	2022	Ramin Ayanzadeh Poulami Das Swamit Tannu Moinuddin K. Qureshi

Works That Cite This (17)

Action	Title	Year	Authors
+	Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions	2023	Yuri Alexeev Maximilian Amsler P. G. Baity Marco Antonio Barroca Sanzio Bassini Torey Battelle Daan Camps David Casanova Young Jai Choi Frederic T. Chong
+ PDF Chat	Quantum-centric supercomputing for materials science: A perspective on challenges and future directions	2024	Yuri Alexeev Maximilian Amsler Marco Antonio Barroca Sanzio Bassini Torey Battelle Daan Camps David Casanova Young Jay Choi Frederic T. Chong Charles Chung
+	Quantum Optimization: Potential, Challenges, and the Path Forward	2023	Amira Abbas Andris Ambainis Brandon Augustino Andreas Baertschi Harry Buhrman Carleton Coffrin G. Cortiana Vedran Dunjko Daniel J. Egger Bruce G. Elmegreen
+	Efficient quantum circuits based on the quantum natural gradient	2024	Ananda Roy Sameer Erramilli Robert Konik
+	Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions	2023	Yuri Alexeev Stephan Eidenbenz Antonio Mezzacapo Scott Pakin
+	Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering	2024	Zewen Zhang Roger Paredes Bhuvanesh Sundar David Quiroga Anastasios Kyrillidis Leonardo Dueñas‐Osorio Guido Pagano Kaden R. A. Hazzard
+	The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze	2023	Enrico Fontana Dylan Herman Shouvanik Chakrabarti Niraj Kumar Romina Yalovetzky Jamie Heredge Shree Hari Sureshbabu Marco Pistoia
+	A model of randomly-coupled Pauli spins	2023	Masanori Hanada Antal Jevicki Xianlong Liu Enrico Rinaldi Masaki Tezuka
+	High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices	2023	Elijah Pelofske Andreas Bärtschi John Golden Stephan Eidenbenz
+ PDF Chat	Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems	2024	Filip B. Maciejewski Stuart Hadfield Benjamin Hall Mark Hodson Maxime Dupont Bram Evert James Sud M. Sohaib Alam Zhihui Wang Stephen Jeffrey

Works Cited by This (42)

Action	Title	Year	Authors
+	Low autocorrelation binary sequences : statistical mechanics and configuration space analysis	1987	J. Bernasconi
+ PDF Chat	Speedup via quantum sampling	2008	Paweł Wocjan Anura Abeyesinghe
+ PDF Chat	Fast quantum methods for optimization	2015	Sergio Boixo Gerardo Ortíz Rolando D. Somma
+ PDF Chat	Quantum Simulations of Classical Annealing Processes	2008	R. D. Somma Sergio Boixo Howard Barnum E. Knill
+	Advances in the merit factor problem for binary sequences	2013	Jonathan Jedwab Daniel J. Katz Kai‐Uwe Schmidt
+ PDF Chat	Landscape statistics of the low-autocorrelation binary string problem	2000	Fernando F. Ferreira José F. Fontanari Peter F. Stadler
+	Quantum amplitude amplification and estimation	2002	Gilles Brassard Peter Høyer Michele Mosca Alain Tapp
+ PDF Chat	Low-autocorrelation binary sequences: On improved merit factors and runtime predictions to achieve them	2017	Borko Bošković F. Brglez Janez Brest
+ PDF Chat	A Short Path Quantum Algorithm for Exact Optimization	2018	M. B. Hastings
+ PDF Chat	Quantum approximate optimization algorithm for MaxCut: A fermionic view	2018	Zhihui Wang Stuart Hadfield Jiang Zhang Eleanor Rieffel