Practical integer-to-binary mapping for quantum annealers

DOI10.1007/S11128-019-2213-XMaRDI QIDQ670020zbMATH OpenOpenAlexWikidataFDO

Authors Sahar Karimi, Pooya Ronagh

Publication date 15 March 2019

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.01945

zbMATH Keywords

adiabatic quantum computationbounded-coefficient encodinginteger encodinginteger programmingsimulated quantum annealing

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Variational principles of physics (49S05) Quantum computation (81P68) Atomic physics (81V45) Integer programming (90C10) Mixed integer programming (90C11)

Abstract: Recent advancements in quantum annealing hardware and numerous studies in this area suggests that quantum annealers have the potential to be effective in solving unconstrained binary quadratic programming problems. Naturally, one may desire to expand the application domain of these machines to problems with general discrete variables. In this paper, we explore the possibility of employing quantum annealers to solve unconstrained quadratic programming problems over a bounded integer domain. We present an approach for encoding integer variables into binary ones, thereby representing unconstrained integer quadratic programming problems as unconstrained binary quadratic programming problems. To respect some of the limitations of the currently developed quantum annealers, we propose an integer encoding, named bounded- coefficient encoding, in which we limit the size of the coefficients that appear in the encoding. Furthermore, we propose an algorithm for finding the upper bound on the coefficients of the encoding using the precision of the machine and the coefficients of the original integer problem. Finally, we experimentally show that this approach is far more resilient to the noise of the quantum annealers compared to traditional approaches for the encoding of integers in base two.

Recommendations

• A case study in programming a quantum annealer for hard operational planning problems
• Embedding equality constraints of optimization problems into a quantum annealer
• Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Boosting quantum annealer performance via sample persistence

Cites work

• A case study in programming a quantum annealer for hard operational planning problems
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• A subgradient approach for constrained binary optimization via quantum adiabatic evolution
• Adiabatic quantum optimization with qudits
• Linear and mixed integer programming for portfolio optimization
• Optimization using quantum mechanics: quantum annealing through adiabatic evolution
• Performance of two different quantum annealing correction codes
• Quantum versus classical annealing of Ising spin glasses
• Scheduling in supply chains using mixed integer programming

Cited in

(5)

• A case study in programming a quantum annealer for hard operational planning problems
• Least-squares solutions to polynomial systems of equations with quantum annealing
• Models in quantum computing: a systematic review
• A copositive framework for analysis of hybrid Ising-classical algorithms
• Calculating Nash equilibrium on quantum annealers

Describes a project that uses

Uses Software

• Gurobi

This page was built for publication: Practical integer-to-binary mapping for quantum annealers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670020)