Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization

• URL: http://arxiv.org/abs/2305.03857v3
• Date: Sun, 7 Jan 2024 19:24:41 GMT
• Title: Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Authors: Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, Marco Pistoia
• Abstract summary: 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.
• Score: 11.445200448951072
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm, which it can approximate with sufficient depth. However, it is unclear to what extent the lessons from the adiabatic regime apply to QAOA as executed in practice with small to moderate depth. In this paper, we demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state. Specifically, we observe that the best performance is obtained when the initial state of QAOA is set to be the ground state of the mixing Hamiltonian, as required by the adiabatic algorithm. We provide numerical evidence using the examples of constrained portfolio optimization problems with both low ($p\leq 3$) and high ($p = 100$) QAOA depth. Additionally, we successfully apply QAOA with XY mixer to portfolio optimization on a trapped-ion quantum processor using 32 qubits and discuss our findings in near-term experiments.

Related papers

• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
  arXiv  Detail & Related papers  (2024-06-25T09:02:31Z)
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
  The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem. We observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers.
  arXiv  Detail & Related papers  (2023-08-04T14:17:21Z)
• 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)
• Quantum Alternating Operator Ansatz (QAOA) Phase Diagrams and Applications for Quantum Chemistry [0.0]
  We modify QAOA to apply to finding ground states of molecules and empirically evaluate the modified algorithm on several molecules. We find robust qualitative behavior for QAOA as a function of a number of steps and size of the parameters, and demonstrate this behavior also occurs in standard QAOA search.
  arXiv  Detail & Related papers  (2021-08-30T08:24:38Z)
• 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)
• 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)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Bridging Classical and Quantum with SDP initialized warm-starts for QAOA [4.76507354067301]
  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.
  arXiv  Detail & Related papers  (2020-10-27T02:57:22Z)

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.