Journal
QUANTUM
Volume 5, Issue -, Pages -Publisher
VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
DOI: 10.22331/q-2021-04-08-428
Keywords
-
Funding
- IBM
Ask authors/readers for more resources
This paper discusses using Grover Adaptive Search (GAS) to solve Constrained Polynomial Binary Optimization (CPBO) problems, particularly Quadratic Unconstrained Binary Optimization (QUBO) problems, by developing efficient oracles, demonstrating potential speed-up in combinatorial optimization and QUBO, and applying to higher-degree polynomial objective functions and constrained optimization problems.
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available