Distributed Quantum Approximate Optimization Algorithm on a Quantum-Centric Supercomputing Architecture

• URL: http://arxiv.org/abs/2407.20212v2
• Date: Fri, 21 Mar 2025 17:40:01 GMT
• Title: Distributed Quantum Approximate Optimization Algorithm on a Quantum-Centric Supercomputing Architecture
• Authors: Seongmin Kim, Vincent R. Pascuzzi, Zhihao Xu, Tengfei Luo, Eungkyu Lee, In-Saeng Suh,
• Abstract summary: Quantum approximate optimization algorithm (QAOA) has shown promise in solving optimization problems by providing quantum speedup on gate-based quantum computing systems.<n>However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits.<n>We present a distributed QAOA (DQAOA) which decomposes a large computational workload into smaller tasks that require fewer qubits and shallower circuits.
• Score: 1.953969470387522
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum approximate optimization algorithm (QAOA) has shown promise in solving combinatorial optimization problems by providing quantum speedup on near-term gate-based quantum computing systems. However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits, limiting its scalability for real-world applications. In this study, we present a distributed QAOA (DQAOA), which leverages distributed computing strategies to decompose a large computational workload into smaller tasks that require fewer qubits and shallower circuits than necessitated to solve the original problem. These sub-problems are processed using a combination of high-performance and quantum computing resources. The global solution is iteratively updated by aggregating sub-solutions, allowing convergence toward the optimal solution. We demonstrate that DQAOA can handle considerably large-scale optimization problems (e.g., 1,000-bit problem) achieving a high approximation ratio ($\sim$99%) and short time-to-solution ($\sim$276 s), outperforming existing strategies. Furthermore, we realize DQAOA on a quantum-centric supercomputing architecture, paving the way for practical applications of gate-based quantum computers in real-world optimization tasks. To extend DQAOA's applicability to materials science, we further develop an active learning algorithm integrated with our DQAOA (AL-DQAOA), which involves machine learning, DQAOA, and active data production in an iterative loop. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible. We expect the proposed DQAOA to be applicable to a wide range of optimization problems and AL-DQAOA to find broader applications in material design.

Related papers

• Distributed Variational Quantum Algorithm with Many-qubit for Optimization Challenges [0.25782420501870296]
  Existing quantum algorithms struggle with scalability and accuracy due to excessive reliance on entanglement. We propose variational quantum optimization algorithm (VQOA), which leverages many-qubit (MQ) operations in an ansatz solely employing quantum superposition. We also introduce distributed VQOA, which integrates high-performance computing with quantum computing to achieve superior performance across MQ systems and classical nodes.
  arXiv  Detail & Related papers  (2025-02-28T22:13:23Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Multiscale Quantum Approximate Optimization Algorithm [0.0]
  The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions to optimization problems. We propose a new version of QAOA that incorporates the capabilities of QAOA and the real-space renormalization group transformation.
  arXiv  Detail & Related papers  (2023-12-11T07:47:16Z)
• Quantum-Informed Recursive Optimization Algorithms [0.0]
  We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps. We use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware.
  arXiv  Detail & Related papers  (2023-08-25T18:02:06Z)
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers [0.2150989251218736]
  We develop a scheme with which near-term quantum computers can be applied to solve multi-objective optimization problems. We focus on an implementation based on the quantum approximate optimization algorithm (QAOA)
  arXiv  Detail & Related papers  (2023-08-16T09:22:01Z)
• 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)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent Ising model suitable for the quantum device. We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Prog-QAOA.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• 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 constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.