Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale

arXiv:2606.28866 · quant-ph · Submitted 2026-06-27 · Read on arXiv

quant-ph

Submitted: 2026-06-27

Updated: 2026-09-22

Terminology

• Benchmark — 26× in this paper · explained in 2 episodes
• Maximum Independent Set — 24× in this paper
• Ancilla Qubits — 19× in this paper · explained in 1 episode
• Post-Selection — 18× in this paper · explained in 2 episodes
• Entanglement — 15× in this paper · explained in 3 episodes
• Ablation — 9× in this paper · explained in 1 episode
• Core — 9× in this paper · explained in 2 episodes
• Quantum Approximate Optimization Algorithm — 6× in this paper
• Combinatorial Optimization — 5× in this paper · explained in 2 episodes
• Variational Quantum Eigensolver — 4× in this paper
• Ablation study — 3× in this paper · explained in 1 episode
• Entanglement Entropy — 3× in this paper · explained in 2 episodes
• Adaptation — 2× in this paper · explained in 1 episode
• Alignment — 2× in this paper · explained in 1 episode
• Hamiltonian-Guided Leverage Embedding — 2× in this paper
• Hilbert Space — 2× in this paper · explained in 2 episodes
• Robustness — 2× in this paper · explained in 5 episodes
• Ablation Studies — 1× in this paper · explained in 1 episode
• Accuracy — 1× in this paper · explained in 1 episode
• Benchmarking — 1× in this paper · explained in 3 episodes
• Clustering — 1× in this paper · explained in 2 episodes
• Distribution Shift — 1× in this paper · explained in 5 episodes
• Failure Modes — 1× in this paper · explained in 3 episodes
• Fidelity — 1× in this paper · explained in 2 episodes
• Hybrid Approach — 1× in this paper · explained in 4 episodes
• QUBO Formulation — 1× in this paper · explained in 3 episodes
• Quantum Circuits — 1× in this paper · explained in 2 episodes
• Reverse Cuthill-McKee — 1× in this paper
• Semantic Alignment — 1× in this paper · explained in 3 episodes
• Simultaneous Perturbation Stochastic Approximation — 1× in this paper
• Transferability — 1× in this paper · explained in 4 episodes
• Variational Quantum Eigensolver (VQE) — 1× in this paper · explained in 5 episodes

Sources

• A Quantum Approximate Optimization Algorithm
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Multistart Methods for Quantum Approximate Optimization
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• QAOA Parameter Transferability for Maximum Independent Set using Graph Attention Networks
• qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem
• MPS-JuliQAOA: User-friendly, Scalable MPS-based Simulation for Quantum Optimization
• Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity