Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Solving combinatorial optimization problems on current noisy quantum devices is currently being advocated for (and restricted to) binary polynomial optimization with equality constraints via quantum heuristic approaches. This is achieved using, for example, the variational quantum eigensolver (VQE)...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9238006/ |
| _version_ | 1819011822350499840 |
|---|---|
| author | Claudio Gambella Andrea Simonetto |
| author_facet | Claudio Gambella Andrea Simonetto |
| author_sort | Claudio Gambella |
| collection | DOAJ |
| description | Solving combinatorial optimization problems on current noisy quantum devices is currently being advocated for (and restricted to) binary polynomial optimization with equality constraints via quantum heuristic approaches. This is achieved using, for example, the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). In this article, we present a decomposition-based approach to extend the applicability of current approaches to “quadratic plus convex” mixed binary optimization (MBO) problems, so as to solve a broad class of real-world optimization problems. In the MBO framework, we show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms), and continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers). The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit, an open-source quantum computing software development framework. |
| first_indexed | 2024-12-21T01:34:16Z |
| format | Article |
| id | doaj.art-81ab9fe2a3d14789917e5d74372c02d3 |
| institution | Directory Open Access Journal |
| issn | 2689-1808 |
| language | English |
| last_indexed | 2024-12-21T01:34:16Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj.art-81ab9fe2a3d14789917e5d74372c02d32022-12-21T19:20:17ZengIEEEIEEE Transactions on Quantum Engineering2689-18082020-01-01112210.1109/TQE.2020.30331399238006Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum ComputersClaudio Gambella0https://orcid.org/0000-0001-7134-0852Andrea Simonetto1https://orcid.org/0000-0003-2923-3361IBM Quantum, IBM Research Ireland, Mulhuddart, IrelandIBM Quantum, IBM Research Ireland, Mulhuddart, IrelandSolving combinatorial optimization problems on current noisy quantum devices is currently being advocated for (and restricted to) binary polynomial optimization with equality constraints via quantum heuristic approaches. This is achieved using, for example, the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). In this article, we present a decomposition-based approach to extend the applicability of current approaches to “quadratic plus convex” mixed binary optimization (MBO) problems, so as to solve a broad class of real-world optimization problems. In the MBO framework, we show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms), and continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers). The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit, an open-source quantum computing software development framework.https://ieeexplore.ieee.org/document/9238006/Mathematical programmingoptimizationquantum computing |
| spellingShingle | Claudio Gambella Andrea Simonetto Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers IEEE Transactions on Quantum Engineering Mathematical programming optimization quantum computing |
| title | Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers |
| title_full | Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers |
| title_fullStr | Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers |
| title_full_unstemmed | Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers |
| title_short | Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers |
| title_sort | multiblock admm heuristics for mixed binary optimization on classical and quantum computers |
| topic | Mathematical programming optimization quantum computing |
| url | https://ieeexplore.ieee.org/document/9238006/ |
| work_keys_str_mv | AT claudiogambella multiblockadmmheuristicsformixedbinaryoptimizationonclassicalandquantumcomputers AT andreasimonetto multiblockadmmheuristicsformixedbinaryoptimizationonclassicalandquantumcomputers |