How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

Thomas Gabor; Marian Lingsch  Rosenfeld; Claudia Linnhoff-Popien; Sebastian Feld

doi:10.1109/SANER53432.2022.00149

How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

Thomas Gabor, Marian Lingsch Rosenfeld, Claudia Linnhoff-Popien, Sebastian Feld

Quantum Circuit Architectures and Technology

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

1 Citation (Scopus)

5 Downloads (Pure)

Abstract

Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

Original language	English
Title of host publication	Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)
Editors	C. Ceballos
Place of Publication	Piscataway
Publisher	IEEE
Pages	1249-1257
Number of pages	9
ISBN (Electronic)	978-1-6654-3786-8
ISBN (Print)	978-1-6654-3787-5
DOIs	https://doi.org/10.1109/SANER53432.2022.00149
Publication status	Published - 2022
Event	2022 IEEE International Conference on Software Analysis, Evolution and Reengineering - Honolulu, United States Duration: 15 Mar 2022 → 18 Mar 2022

Publication series

Name	Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022

Conference

Conference	2022 IEEE International Conference on Software Analysis, Evolution and Reengineering
Abbreviated title	Saner 2022
Country/Territory	United States
City	Honolulu
Period	15/03/22 → 18/03/22

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

quadratic unconstrained binary optimization
QUBO
quantum computing

Access to Document

10.1109/SANER53432.2022.00149

How_to_Approximate_any_Objective_Function_via_Quadratic_Unconstrained_Binary_OptimizationFinal published version, 400 KB

Cite this

Gabor, T., Rosenfeld, M. L., Linnhoff-Popien, C., & Feld, S. (2022). How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization. In C. Ceballos (Ed.), Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER) (pp. 1249-1257). Article 9825802 (Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022). IEEE. https://doi.org/10.1109/SANER53432.2022.00149

Gabor, Thomas ; Rosenfeld, Marian Lingsch ; Linnhoff-Popien, Claudia et al. / How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization. Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). editor / C. Ceballos. Piscataway : IEEE, 2022. pp. 1249-1257 (Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022).

@inproceedings{6f8f8866a5804bcba94ee6161bfde197,

title = "How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization",

abstract = "Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).",

keywords = "quadratic unconstrained binary optimization, QUBO, quantum computing",

author = "Thomas Gabor and Rosenfeld, {Marian Lingsch} and Claudia Linnhoff-Popien and Sebastian Feld",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering , Saner 2022 ; Conference date: 15-03-2022 Through 18-03-2022",

year = "2022",

doi = "10.1109/SANER53432.2022.00149",

language = "English",

isbn = "978-1-6654-3787-5",

series = "Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022",

publisher = "IEEE",

pages = "1249--1257",

editor = "C. Ceballos",

booktitle = "Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)",

address = "United States",

}

Gabor, T, Rosenfeld, ML, Linnhoff-Popien, C & Feld, S 2022, How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization. in C Ceballos (ed.), Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)., 9825802, Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022, IEEE, Piscataway, pp. 1249-1257, 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering , Honolulu, United States, 15/03/22. https://doi.org/10.1109/SANER53432.2022.00149

How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization. / Gabor, Thomas; Rosenfeld, Marian Lingsch ; Linnhoff-Popien, Claudia et al.
Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). ed. / C. Ceballos. Piscataway: IEEE, 2022. p. 1249-1257 9825802 (Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

AU - Gabor, Thomas

AU - Rosenfeld, Marian Lingsch

AU - Linnhoff-Popien, Claudia

AU - Feld, Sebastian

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2022

Y1 - 2022

N2 - Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

AB - Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

KW - quadratic unconstrained binary optimization

KW - QUBO

KW - quantum computing

UR - http://www.scopus.com/inward/record.url?scp=85135847851&partnerID=8YFLogxK

U2 - 10.1109/SANER53432.2022.00149

DO - 10.1109/SANER53432.2022.00149

M3 - Conference contribution

SN - 978-1-6654-3787-5

T3 - Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022

SP - 1249

EP - 1257

BT - Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)

A2 - Ceballos, C.

PB - IEEE

CY - Piscataway

T2 - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering

Y2 - 15 March 2022 through 18 March 2022

ER -

Gabor T, Rosenfeld ML, Linnhoff-Popien C, Feld S. How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization. In Ceballos C, editor, Proceedings of the 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER). Piscataway: IEEE. 2022. p. 1249-1257. 9825802. (Proceedings - 2022 IEEE International Conference on Software Analysis, Evolution and Reengineering, SANER 2022). doi: 10.1109/SANER53432.2022.00149

How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this