A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem

• URL: http://arxiv.org/abs/2304.03576v1
• Date: Fri, 7 Apr 2023 10:23:28 GMT
• Title: A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
• Authors: Massimiliano Proietti, Filippo Cerocchi, Massimiliano Dispenza
• Abstract summary: Photonic quantum computers currently concur with gate-based platforms in the race towards useful quantum advantage. We propose an MBQC algorithm to run the Quantum Approximate Optimization Algorithm (QAOA) We conclude analyzing the resource-cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules showing up to a 30-fold improvement.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Photonic quantum computers, programmed within the framework of the measurement-based quantum computing (MBQC), currently concur with gate-based platforms in the race towards useful quantum advantage, and some algorithms emerged as main candidates to reach this goal in the near term. Yet, the majority of these algorithms are only expressed in the gate-based model of computation, which is incompatible with photonic platforms. Methods to translate gate-based algorithms into the MBQC framework exist, but they are not always optimal in terms of resource cost. In our work, we propose an MBQC algorithm to run the Quantum Approximate Optimization Algorithm (QAOA). Furthermore, we apply the MBQC-QAOA algorithm to the MAX $K$-CUT problem, working for all values of $K$, expressing the cost Hamiltonian and its constraints in a form easily implementable in the MBQC model. We conclude analyzing the resource-cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules showing up to a 30-fold improvement. With our work, we contribute to close the gap between gate-based and MBQC near-term algorithms, a gap not reflecting the current status of the hardware development.

Related papers

• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio. We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters. Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
  arXiv  Detail & Related papers  (2024-07-29T10:26:28Z)
• A Novel Quantum Algorithm for Ant Colony Optimization [9.750158948621216]
  We introduce a hybrid quantum-classical algorithm by combining the clustering algorithm with QACO algorithm. The developed QACO algorithm shows better performance under multiple data set. Our work shows that the combination of the clustering algorithm with QACO has effectively extended the application scenario of QACO in current NISQ era of quantum computing.
  arXiv  Detail & Related papers  (2024-03-01T08:49:33Z)
• Deterministic Ans\"atze for the Measurement-based Variational Quantum Eigensolver [0.0]
  This study introduces MBVQE-ans"atze that respect determinism and resemble the widely used problem-agnostic hardware-efficient VQE ansatz. We find that ensuring determinism works better via postselection than by adaptive measurements at the expense of increased sampling cost. We propose an efficient MBQC-inspired method to prepare the resource state, specifically the cluster state, on hardware with heavy-hex connectivity.
  arXiv  Detail & Related papers  (2023-12-20T18:08:25Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• 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)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Optimal Qubit Mapping with Simultaneous Gate Absorption [9.530683922512873]
  A key step in compilation is mapping the qubits in the program to physical qubits on a given quantum computer. We present OLSQ-GA, an optimal qubit mapper with a key feature of simultaneous SWAP gate absorption. OLSQ-GA reduces depth by up to 50.0% and SWAP count by 100% compared to other state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-09-14T05:15:36Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization [0.0]
  We study the problem of detecting problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm. We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage.
  arXiv  Detail & Related papers  (2020-01-22T20:42:02Z)

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.