{"id":168373,"date":"2023-07-26T14:25:19","date_gmt":"2023-07-26T19:25:19","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2023\/07\/sampling-frequency-thresholds-for-the-quantum-advantage-of-the-quantum-approximate-optimization-algorithm"},"modified":"2023-07-26T14:25:19","modified_gmt":"2023-07-26T19:25:19","slug":"sampling-frequency-thresholds-for-the-quantum-advantage-of-the-quantum-approximate-optimization-algorithm","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2023\/07\/sampling-frequency-thresholds-for-the-quantum-advantage-of-the-quantum-approximate-optimization-algorithm","title":{"rendered":"Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/sampling-frequency-thresholds-for-the-quantum-advantage-of-the-quantum-approximate-optimization-algorithm.jpg\"><\/a><\/p>\n<p>We compare the performance of the <i>Quantum<\/i> Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p &gt; 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p \u2264 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits [\u2026]<\/p>\n","protected":false},"author":661,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,1617],"tags":[],"class_list":["post-168373","post","type-post","status-publish","format-standard","hentry","category-information-science","category-quantum-physics"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/168373","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/661"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=168373"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/168373\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=168373"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=168373"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=168373"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}