Adiabatic Quantum Computing (AQC) is an attractive paradigm for solving hard integer polynomial optimization problems. Available hardware restricts the Hamiltonians to be of a structure that allows only pairwise interactions. This requires that the original optimization problem to be first converted -- from its polynomial form -- to a quadratic unconstrained binary optimization (QUBO) problem, which we frame as a problem in algebraic geometry. Additionally, the hardware graph where such a QUBO-Hamiltonian needs to be embedded -- assigning variables of the problem to the qubits of the physical optimizer -- is not a complete graph, but rather one with limited connectivity. This "problem graph to hardware graph" embedding can also be framed as a problem of computing a Groebner basis of a certain specially constructed polynomial ideal. We develop a systematic computational approach to prepare a given polynomial optimization problem for AQC in three steps. The first step reduces an input polynomial optimization problem into a QUBO through the computation of the Groebner basis of a toric ideal generated from the monomials of the input objective function. The second step computes feasible embeddings. The third step computes the spectral gap of the adiabatic Hamiltonian associated to a given embedding. These steps are applicable well beyond the integer polynomial optimization problem. Our paper provides the first general purpose computational procedure that can be used directly as a
translator to solve polynomial integer optimization. Alternatively, it can be used as a test-bed (with small size problems) to help design efficient heuristic quantum compilers by studying various choices of reductions and embeddings in a systematic and comprehensive manner. An added benefit of our framework is in designing Ising architectures through the study of
Y−minor universal graphs.
Adiabatic Quantum Computation (AQC) is a quantum model proposed by Farhi, et al., in 2000, and has been proven to be equivalent to conventional quantum computation (quantum gate model). Unlike classical computation or conventional quantum (gate) model in which an algorithm is discrete, an adiabatic quantum algorithm is continuous. In this talk, I will give an introduction of AQC, in particular, on the design and analysis of adiabatic quantum algorithms for the NP-hard maximum independent set problem. I will also discuss the adiabatic quantum architecture design and minor-embedding problems.