Hard combinatorial problems and minor embeddings on lattice graphs

DOI10.1007/s11128-019-2323-5OpenAlexW2901983189MaRDI QIDQ2105986

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 computation (81P68) Graph minors (05C83) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (2)

Template-Based Minor Embedding for Adiabatic Quantum Optimization ⋮ Intersecting longest cycles in Archimedean tilings

Cites Work

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

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