Southwest Quantum Information and Technology

Optimized Grover Adaptive Search oracles for Constrained Polynomial Binary Optimization

Presenting Author: Phattharaporn Singkanipa, University of Southern California
Contributing Author(s): Ewan Munro

Grover Adaptive Search (GAS) is a quantum algorithm that can provide a quadratic speed-up for unstructured search. A challenge in GAS is to define an oracle, a procedure that could be non-systematic. An efficient method for constructing oracles to solve Constrained Polynomial Binary Optimization (CPBO) problems has been proposed in arXiv:1912.04088v3. This method is based on converting the problem into the Quadratic Unconstrained Binary Optimization (QUBO) form of Hamiltonian while using an additional CNOT in the oracle for each extra constraint that does not fit in the QUBO form. In this work, we propose a further-optimized way to construct oracles using Quadratic Constrained Binary Optimization (QCBO), which modifies the oracle to account for every constraint and exhibits a linear form of the Hamiltonian for numerous CPBO problems. We demonstrate the validity of this approach by presenting two examples of constructing QCBO form of oracles to solve number partitioning and bin packing problems, both of which show a polynomial reduction in the number of qubits and circuit depth compared to using the QUBO form of oracles.

(Session 5 : Thursday from 5:00 pm - 7:00 pm)