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
- Proactively incremental-learning QAOA [9.677961025372115]
We propose an advanced Quantum Approximate Optimization Algorithm (QAOA) based on incremental learning.
Our method has superior performance on Approximation Ratio (AR) and training time compared to prevalent works of QAOA.
arXiv Detail & Related papers (2023-11-04T02:15:26Z) - 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) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - 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) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form.
Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries.
This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
arXiv Detail & Related papers (2020-08-03T18:00:05Z)
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.