REVIEW 7 cited by
qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
read the original 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.
Forward citations
Cited by 7 Pith papers
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Variational quantum methods with spectral preprocessing, CVaR optimization, and ancilla-assisted superposition solve maximum independent set to optimality on graphs up to 180 vertices, claimed as the largest such gate...
-
Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data
qReduMIS hybrid pipeline improves QAOA performance on real financial MIS instances up to 225 assets, achieving higher success probabilities and better scaling on Quantinuum trapped-ion hardware.
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Variational quantum methods with spectral reordering, sparsification, CVaR optimization, and ancilla-assisted superposition solve MIS to optimality on 64-, 99-, and 180-vertex graphs, the largest such gate-based demon...
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Ancilla-assisted multi-seed superposition plus excitation-preserving VQE and classical post-processing recovers exact MIS on 64-, 99-, and 180-node graphs, with partial hardware transfer.
-
A quantum wire approach to weighted combinatorial graph optimisation problems
Demonstrates a quantum wire encoding using Rydberg atom chains to solve MWIS and QUBO problems on neutral atom arrays with reduced ancilla overhead and experimental validation.
-
Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data
qReduMIS, using QAOA frozen-node signals plus classical reductions, solves real market MIS portfolio instances up to 225 assets on Helios with far better success and TTS scaling than standalone QAOA.
-
Reducibility of native weighted graphs on Rydberg Arrays
Classical kernelisation fully reduces many small and sparse unit-disk graphs for MIS and MWIS native to Rydberg arrays, but dense graphs retain finite irreducible kernels, with vertex weights increasing reducibility a...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.