arXiv (Cornell University) · 2018 · 10 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryQuantum ComputingAdiabatic Quantum ComputingComputational AlgebraQuantum CircuitsQuantum CompilationQuantum ComputationQuantum Hardware ArchitecturesAdiabatic OptimizationAdiabatic Quantum ComputationAlgebraic Geometry ComputationComputational Algebraic GeometryPolynomial OptimizationQuantum Circuit CompilationQuantum Hardware EmbeddingToric Ideal Computation
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 $\mathcal Y-$minor universal graphs.
15
Ising formulations of many NP problems
Andrew Lucas · Frontiers in Physics · 2014 · 2.5K citations · Full text
Computing, Computer Science, Physics +15
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et al. · Science · 2001 · 2.1K citations · Full text
Computing, Computer Science, Physics +15
Quantum annealing with manufactured spins
Mark W. Johnson, M. H. S. Amin, S. Gildert et al. · Nature · 2011 · 1.9K citations