Mapping NP-Hard Problems to Restricted Adiabatic Quantum Architectures

Abstract

We introduce a framework for mapping NP-Hard problems to adiabatic quantum computing (AQC) architectures that are heavily restricted in both connectivity and dynamic range of couplings, for which minor-embedding -- the standard problem mapping method -- cannot be directly applied. Separating the mapping into two distinct stages, we introduce problem-specific reductions for both quadratic unconstrained binary optimisation (QUBO) and satisfiability (SAT) and develop the subdivision-embedding method that is suitable for directly embedding onto these heavily restricted architectures. The theory underpinning this framework provides tools to aid in the manipulation of Ising Hamiltonians for the purposes of Ising energy minimisation, and could be used to assist in developing and optimising further problem mapping techniques. For each of the problem mapping methods presented, we examine how the physical qubit count scales with problem size on architectures of varying connectivity.

35 pages, 28 figures

References in corpus (9)

• A practical heuristic for finding graph minors
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
• Quantum annealing correction for random Ising problems
• Noise resistance of adiabatic quantum computation using random matrix theory
• Decoherence in a scalable adiabatic quantum computer
• Next-Generation Topology of D-Wave Quantum Processors
• Algorithm engineering for a quantum annealing platform
• Scalable Superconducting Architecture for Adiabatic Quantum Computation