Hard combinatorial problems and minor embeddings on lattice graphs

DOI10.1007/S11128-019-2323-5MaRDI QIDQ2105986zbMATH OpenOpenAlexFDO

Authors Andrew Lucas

Publication date 8 December 2022

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.01789

zbMATH Keywords

minor embeddingNP-hard optimizationquantum adiabatic optimization

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Graph minors (05C83)

Recommendations

• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Efficiently embedding QUBO problems on adiabatic quantum computers
• Embedding of complete graphs in broken Chimera graphs
• Graph minors from simulated annealing for annealing machines with sparse connectivity

Cites work

• A case study in programming a quantum annealer for hard operational planning problems
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Anderson localization makes adiabatic quantum optimization fail
• Fast clique minor generation in Chimera qubit connectivity graphs
• Faster parameterized algorithms for minor containment
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Phase Transition in the Number Partitioning Problem
• Probabilistic analysis of the number partitioning problem
• Pseudo-Boolean optimization
• Quantum versus classical annealing of Ising spin glasses
• Random-energy model: an exactly solvable model of disordered systems
• Systematic and deterministic graph minor embedding for Cartesian products of graphs
• Where are the hard knapsack problems?

Cited in

(7)

• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Efficiently embedding QUBO problems on adiabatic quantum computers
• Intersecting longest cycles in Archimedean tilings
• Adiabatic quantum programming: minor embedding with hard faults
• Template-Based Minor Embedding for Adiabatic Quantum Optimization
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Embedding of complete graphs in broken Chimera graphs

This page was built for publication: Hard combinatorial problems and minor embeddings on lattice graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105986)