qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem

• URL: http://arxiv.org/abs/2503.12551v1
• Date: Sun, 16 Mar 2025 15:41:42 GMT
• Title: qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
• Authors: Martin J. A. Schuetz, Romina Yalovetzky, Ruben S. Andrist, Grant Salton, Yue Sun, Rudy Raymond, Shouvanik Chakrabarti, Atithi Acharya, Ruslan Shaydulin, Marco Pistoia, Helmut G. Katzgraber,
• Abstract summary: We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem.<n>We show that qReduMIS can help address fundamental performance limitations faced by a broad set of solvers including Rydberg quantum devices.<n>We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions.
• Score: 10.162280421416208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracted from quantum devices. Our larger framework consists of dedicated application, algorithm, and hardware layers, and easily generalizes to the maximum weight independent set problem. In this hybrid quantum-classical framework, which we call qReduMIS, the quantum computer is used as a co-processor to inform classical reduction logic about frozen vertices that are likely (or unlikely) to be in large independent sets, thereby opening up the reduction space after removal of targeted subgraphs. We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on Rydberg quantum hardware available through Amazon Braket. Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices. We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions, and we discuss potential future extensions.

Related papers

• Enhancing variational quantum algorithms by balancing training on classical and quantum hardware [1.8377902806196762]
  Variational quantum algorithms (VQAs) have the potential to provide a near-term route to quantum utility or advantage. VQAs have been proposed for a multitude of tasks such as ground-state estimation. There remain major challenges in its trainability and resource costs on quantum hardware.
  arXiv  Detail & Related papers  (2025-03-20T17:17:58Z)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs. We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
  arXiv  Detail & Related papers  (2024-05-01T20:49:50Z)
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
  We show how to exploit multilevel carriers of quantum information -- qudits -- for the construction of constrained quantum optimization algorithms. We propose a hybrid classical quantum strategy that allows us to sample constrained solutions while greatly reducing the search space of the problem.
  arXiv  Detail & Related papers  (2023-06-07T13:16:15Z)
• Bootstrap Embedding on a Quantum Computer [4.138095344167023]
  We extend molecular bootstrap embedding to make it appropriate for implementation on a quantum computer. We show how a quadratic speedup can be obtained over the classical algorithm, in principle.
  arXiv  Detail & Related papers  (2023-01-04T05:49:15Z)
• Towards Neural Variational Monte Carlo That Scales Linearly with System Size [67.09349921751341]
  Quantum many-body problems are central to demystifying some exotic quantum phenomena, e.g., high-temperature superconductors. The combination of neural networks (NN) for representing quantum states, and the Variational Monte Carlo (VMC) algorithm, has been shown to be a promising method for solving such problems. We propose a NN architecture called Vector-Quantized Neural Quantum States (VQ-NQS) that utilizes vector-quantization techniques to leverage redundancies in the local-energy calculations of the VMC algorithm.
  arXiv  Detail & Related papers  (2022-12-21T19:00:04Z)
• 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)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21: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)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  We provide the first complete characterization of sources of error in a neutral-atom quantum computer. We develop a novel and distinctly efficient method to address the most important errors associated with the decay of atomic qubits to states outside of the computational subspace. Our protocols can be implemented in the near-term using state-of-the-art neutral atom platforms with qubits encoded in both alkali and alkaline-earth atoms.
  arXiv  Detail & Related papers  (2021-05-27T23:29:53Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58: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.