Hard combinatorial problems and minor embeddings on lattice graphs

DOI10.1007/S11128-019-2323-5OpenAlexW2901983189MaRDI QIDQ2105986FDOQ2105986

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)

Cites Work

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

Cited In (3)

• Template-Based Minor Embedding for Adiabatic Quantum Optimization
• Intersecting longest cycles in Archimedean tilings
• Embedding of complete graphs in broken Chimera graphs

   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 👍 👎

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)