REVIEW 4 cited by
Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms
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
Signed reviews
abstract
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study a new class of hybrid approaches to quantum optimization, termed Iterative Quantum Algorithms, which in particular generalizes the Recursive Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard problem constraints, which we demonstrate by considering the Maximum Independent Set (MIS) problem. We show that, for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
Forward citations
Cited by 4 Pith papers
-
Analytical Expressions for the Quantum Approximate Optimization Algorithm and its Variants
Exact analytical expressions are derived for QAOA cost expectation values, unifying product-mixer variants and giving the first exact multi-layer results for Grover-type mixers, which are shown to be sensitive to cycl...
-
Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models
For shallow QAOA on maximum independent set, loss landscape variance increases with system size instead of vanishing, contradicting dynamical Lie algebra predictions.
-
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.
-
Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms
A framework extends iterative quantum algorithms to arbitrary k-local constraint problems and builds a quantum DPLL SAT solver whose QAOA branching provably matches classical heuristics in a limit.
Discussion (0). Continue with ORCID to comment.