Exponential qubit reduction in quantum optimization

In this talk, I will discuss how we can address the limited number of qubits available when using gate-based NISQ devices to solve industrial scale quadratic binary optimization (QUBO) problems.



In the first part I will discuss our novel encoding scheme that allows variational quantum algorithms to solve problems of nc classical variables using O(log nc) number of qubits. I will describe how, in conjunction with a variational method, approximate solutions for randomly generated QUBO problems of size nc = 3896 binary variables can be solved using only 15-30 qubits. I will also present applications of the above in two problems from industry– the vehicle routing problem with time windows in logistics, and the transaction settlement in finance. These problem instances were generated using industry-relevant data, and are the largest problem instances of their kind to be solved using gate-based quantum devices

On the second part, I will present another idea utilizing the concept of localization landscape from condensed matter physics to solve QUBO problems. I will describe how low energy solutions can be sampled with higher probability and outline how this state can be prepared using quantum linear solvers, reducing the heuristic nature of finding approximate solutions to QUBO problems within the fault-tolerant regime. In addition, I also discuss how such a state can be prepared using NISQ-friendly approaches, and compare the solutions obtained with those from QAOA.