Engineering topics
Wurtz, Jonathan
Publications and source records attributed to Wurtz, Jonathan.
Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm
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 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 > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
Understanding the best known parameters, performance, and systematic behavior of the Quantum Approximate Optimization Algorithm (QAOA) remain open research questions, even as the algorithm gains popularity. We introduce QAOAKit, a Python toolkit for the QAOA built for exploratory research. QAOAKit is a unified repository of preoptimized QAOA parameters and circuit generators for common quantum simulation frameworks. We combine, standardize, and cross-validate previously known parameters for the MaxCut problem, and incorporate this into QAOAKit. We also build conversion tools to use these parameters as inputs in several quantum simulation frameworks that can be used to reproduce, compare, and extend known results from various sources in the literature. We describe QAOAKit and provide examples of how it can be used to reproduce research results and tackle open problems in quantum optimization.
Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs
The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.