Standard QAOA faces an intrinsic feasibility bottleneck on permutation problems that CE QAOA overcomes with an exponential gain in feasible probability for sublinear-to-linear depths under mild hypergraph growth.
hub
[Fin24] Jernej Rudi Finžgar
11 Pith papers cite this work. Polarity classification is still indexing.
11
Pith papers citing it
hub tools
citation-role summary
background 2
citation-polarity summary
roles
background 1polarities
support 1representative citing papers
Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-spin model.
QUACOD decomposes drone scheduling into quantum-solvable subproblems via coordinate descent, outperforming prior quantum methods in completion time while scaling to 5x more drones and 35x more routes.
Graph sparsification and decomposition reduce worst-case H_Ising pulses from O(n²) to O(n log(n/ε)) and Pauli-X flips from O(n²) to O(n log(n/ε)/ε²) for (1-ε) Max-Cut approximation in trapped-ion QAOA compilations.
QAOA for random k-SAT derives efficacy from an adiabatic manifold that supports rigorous performance guarantees at depth Θ(n²) and sublinear parameter optimization via SAMP at depth O(n).
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
Compositional quantum circuits with symmetry-induced invariant losses produce trainable equivariant quantum GNNs that generalize on max-clique problems and improve hybrid recursive search accuracy and scalability.
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up to 156 qubits, with hardware runs confirming gains up to p=10.
Optimization-free Recursive QAOA solves the Binary Paint Shop Problem near-optimally with reduced quantum resources and robustness to parameter choice compared to standard QAOA.
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.
citing papers explorer
-
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
Standard QAOA faces an intrinsic feasibility bottleneck on permutation problems that CE QAOA overcomes with an exponential gain in feasible probability for sublinear-to-linear depths under mild hypergraph growth.
-
Quantum Glassiness From Efficient Learning
Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-spin model.
-
QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling
QUACOD decomposes drone scheduling into quantum-solvable subproblems via coordinate descent, outperforming prior quantum methods in completion time while scaling to 5x more drones and 35x more routes.
-
Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations
Graph sparsification and decomposition reduce worst-case H_Ising pulses from O(n²) to O(n log(n/ε)) and Pauli-X flips from O(n²) to O(n log(n/ε)/ε²) for (1-ε) Max-Cut approximation in trapped-ion QAOA compilations.
-
Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization
QAOA for random k-SAT derives efficacy from an adiabatic manifold that supports rigorous performance guarantees at depth Θ(n²) and sublinear parameter optimization via SAMP at depth O(n).
-
Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
-
Compositional Quantum Heuristics for Max-Clique Detection
Compositional quantum circuits with symmetry-induced invariant losses produce trainable equivariant quantum GNNs that generalize on max-clique problems and improve hybrid recursive search accuracy and scalability.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up to 156 qubits, with hardware runs confirming gains up to p=10.
-
Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
Optimization-free Recursive QAOA solves the Binary Paint Shop Problem near-optimally with reduced quantum resources and robustness to parameter choice compared to standard QAOA.
-
Mind the gaps: The fraught road to quantum advantage
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
-
Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs
Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.