QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines

• URL: http://arxiv.org/abs/2205.11762v1
• Date: Tue, 24 May 2022 03:49:10 GMT
• Title: QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines
• Authors: Zeqiao Zhou, Yuxuan Du, Xinmei Tian, Dacheng Tao
• Abstract summary: 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.
• Score: 81.4597482536073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The design of fast algorithms for combinatorial optimization greatly contributes to a plethora of domains such as logistics, finance, and chemistry. Quantum approximate optimization algorithms (QAOAs), which utilize the power of quantum machines and inherit the spirit of adiabatic evolution, are novel approaches to tackle combinatorial problems with potential runtime speedups. However, hurdled by the limited quantum resources nowadays, QAOAs are infeasible to manipulate large-scale problems. To address this issue, here we revisit the MaxCut problem via the divide-and-conquer heuristic: seek the solutions of subgraphs in parallel and then merge these solutions to obtain the global solution. Due to the $\mathbb{Z}_2$ symmetry in MaxCut, we prove that the merging process can be further cast into a new MaxCut problem and thus be addressed by QAOAs or other MaxCut solvers. With this regard, we propose QAOA-in-QAOA ($\text{QAOA}^2$) to solve arbitrary large-scale MaxCut problems using small quantum machines. We also prove that the approximation ratio of $\text{QAOA}^2$ is lower bounded by 1/2. Experiment results illustrate that under different graph settings, $\text{QAOA}^2$ attains a competitive or even better performance over the best known classical algorithms when the node count is around 2000. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale combinatorial optimization problems.

Related papers

• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
  We propose a framework for designing QAOA circuits to solve larger-scale Max-Cut problem. We derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Our framework only consumes $18$ qubits and $0.9950$ approximation ratio on average.
  arXiv  Detail & Related papers  (2023-07-28T02:06:42Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
  arXiv  Detail & Related papers  (2023-05-23T16:17:57Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers. We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
  arXiv  Detail & Related papers  (2022-06-07T20:59:19Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
  We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the challenges for graph maximum cut (MaxCut) problem. DC-QAOA achieves 97.14% approximation ratio (20.32% higher than classical counterpart) It also reduces the time complexity of conventional QAOA from exponential to quadratic.
  arXiv  Detail & Related papers  (2021-02-26T03:10:30Z)

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.