paper / edwardfarhi / Apr 20
Tree parameters, instance-independent and pre-chosen for large girth graphs, yield QAOA approximation ratios exceeding conjectured bounds and rivaling full optimization on random instances. A warm-start QAOA using an optimized product state from the Goemans-Williamson algorithm further matches GW performance at low depth p ≳ 3 for random 3-regular graphs with hundreds of vertices. Numerical evidence indicates a practical regime for scalable QAOA deployment without parameter optimization, reducing quantum and classical computational demands.
qaoaquantum-approximate-optimizationmaxcuttree-parameterswarm-startquantum-algorithmsquant-ph
“Tree parameters achieve approximation ratios well beyond conjectured lower bounds and comparable to full optimization”
paper / edwardfarhi / Apr 20
Analysis of QAOA at depth p ≥ 7 on 3-regular graphs with girth g ≥ 16 establishes new lower bounds on the maximum cut size, surpassing prior results via classical numerical evaluation of expected performance. This proves existence of larger cuts without constructing them explicitly. Quantum implementation offers constant-depth circuits for efficient cut discovery, claiming exponential speedup over classical algorithms for these graphs. The approach extends to improved bounds for Maximum Independent Set on the same graph class.
maxcutqaoahigh-girth-graphs3-regular-graphsquantum-algorithmscombinatoricsindependent-set
“QAOA at depth p ≥ 7 improves on previously known lower bounds for MaxCut on 3-regular graphs with girth g ≥ 16”
paper / edwardfarhi / Jun 24
This document summarizes a panel discussion on the future of quantum computing that took place at the 8th International Conference on Quantum Techniques in Machine Learning. The panel, held on November 26th, 2024, featured four discussants and was hosted by the University of Melbourne. The content focuses on the discussion points raised during this session.
quantum-computingquantum-physicsmachine-learningconference-summaryfuture-technologyscientific-discussionarxiv-paper
“The article is a detailed summary of a panel discussion on the future of quantum computing.”