Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Compressed Quadratization of Higher Order Binary Optimization Problems

Abstract: 

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space $\ising$ or in Boolean space $\bool$. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

up
0 users have voted:

Paper Details

Authors:
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima
Submitted On:
31 March 2020 - 4:52pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Avradip Mandal
Session:
Posters
Document Year:
2020
Cite

Document Files

Hobo2QuboDCC-poster.pdf

(33)

Keywords

Additional Categories

Subscribe

[1] Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima, "Compressed Quadratization of Higher Order Binary Optimization Problems", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5087. Accessed: Jul. 10, 2020.
@article{5087-20,
url = {http://sigport.org/5087},
author = {Avradip Mandal; Arnab Roy; Sarvagya Upadhyay; Hayato Ushijima },
publisher = {IEEE SigPort},
title = {Compressed Quadratization of Higher Order Binary Optimization Problems},
year = {2020} }
TY - EJOUR
T1 - Compressed Quadratization of Higher Order Binary Optimization Problems
AU - Avradip Mandal; Arnab Roy; Sarvagya Upadhyay; Hayato Ushijima
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5087
ER -
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. (2020). Compressed Quadratization of Higher Order Binary Optimization Problems. IEEE SigPort. http://sigport.org/5087
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima, 2020. Compressed Quadratization of Higher Order Binary Optimization Problems. Available at: http://sigport.org/5087.
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. (2020). "Compressed Quadratization of Higher Order Binary Optimization Problems." Web.
1. Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. Compressed Quadratization of Higher Order Binary Optimization Problems [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5087