Bridging Classical and Quantum with SDP initialized warm-starts for QAOA

• URL: http://arxiv.org/abs/2010.14021v3
• Date: Mon, 6 Jun 2022 22:24:42 GMT
• Title: Bridging Classical and Quantum with SDP initialized warm-starts for QAOA
• Authors: Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, Swati Gupta
• Abstract summary: We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph. We show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time.
• Score: 4.76507354067301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Quantum Approximate Optimization Algorithm (QAOA) in the context of the Max-Cut problem. Near-term (noisy) quantum devices are only able to (accurately) execute QAOA at low circuit depths while QAOA requires a relatively high circuit-depth in order to "see" the whole graph. We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph, referred to as a warm-start. In particular, our initialization informs QAOA by a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time (in the optimization stage for QAOA's variational parameters). We provide experimental evidence as well as theoretical intuition on performance of the proposed framework.

Related papers

• Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
  A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently. In this study, we employ the Langevin equation with a QNG force to demonstrate that its discrete-time solution gives a generalized form, which we call Momentum-QNG.
  arXiv  Detail & Related papers  (2024-09-03T15:21:16Z)
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era [3.734751161717204]
  Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum optimizations. Recent advances in parameter setting in QAOA make EFTQC experiments with QAOA practically viable.
  arXiv  Detail & Related papers  (2024-08-18T16:48:14Z)
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization [11.445200448951072]
  Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm. We demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state.
  arXiv  Detail & Related papers  (2023-05-05T21:54:28Z)
• Error Mitigation-Aided Optimization of Parameterized Quantum Circuits: Convergence Analysis [42.275148861039895]
  Variational quantum algorithms (VQAs) offer the most promising path to obtaining quantum advantages via noisy processors. gate noise due to imperfections and decoherence affects the gradient estimates by introducing a bias. Quantum error mitigation (QEM) techniques can reduce the estimation bias without requiring any increase in the number of qubits. QEM can reduce the number of required iterations, but only as long as the quantum noise level is sufficiently small.
  arXiv  Detail & Related papers  (2022-09-23T10:48:04Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
  We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
  arXiv  Detail & Related papers  (2021-12-21T12:41:31Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
  arXiv  Detail & Related papers  (2021-02-12T23:12:09Z)
• Quantum annealing initialization of the quantum approximate optimization algorithm [0.0]
  Quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm. external parameter optimization required in QAOA could become a performance bottleneck. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs.
  arXiv  Detail & Related papers  (2021-01-14T17:45:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.