Rigetti Computing, Inc. announced that it was awarded a Defense Advanced Research Projects Agency (DARPA) project as part of the Imagining Practical Applications for a Quantum Tomorrow (IMPAQT) program to advance in quantum algorithms for solving combinatorial optimization problems. Rigetti?s project, Scheduling Problems with Efficient Encoding of Qubits (SPEEQ), seeks to develop a novel and efficient encoding of optimization problems onto qubits, with the goal of enabling larger problems to be mapped to currently available NISQ-era quantum computers. The project will specifically address scheduling problems, which are among the best-known and most pervasive types of combinatorial optimization problems across numerous industries, as well as some of the most challenging to solve. Current quantum algorithms are limited in the size of the problems they can solve by the available number of qubits on a QPU.

One of the main objectives of the SPEEQ project is to enable quantum algorithms to solve large problems so that better comparisons can be made to current classical heuristic algorithms. The problems solved by current benchmarked hybrid quantum-classical algorithms are about 100 times smaller than those solved by classical algorithms, which means it is difficult to determine how these hybrid algorithms will perform at relevant scale. The SPEEQ project emerged from findings in Rigetti?s project for the DARPA ONISQ program, Scheduling Applications with Advanced Mixers (SAAM). In partnership with NASA and USRA, Rigetti is implementing hybrid quantum classical algorithms for solving binary optimization problems by mapping these problems to quantum processors at increasing scales.

The team is observing that the algorithmic performance improves with an increased number of quantum operations. However, the problem size in the SAAM project can still be solved efficiently with classical heuristic algorithms, which are capable of solving problems with up to 10,000 variables. The SPEEQ project will leverage the findings and benchmarks from the SAAM project to address a central question regarding the trade-off between number of qubits used and number of quantum operations used, which is critical in designing new algorithms. The qubit-efficient encoding scheme proposed in this project has potential for numerous benefits beyond solving scheduling problems. Novel algorithms that solve hard combinatorial optimization problems could have a profound impact on supply chains, logistics, and other industries with complex operations.