Faster quantum algorithms for combinatorial optimization
New Cambridge Quantum research brings real-world applications closer by speeding up convergence, accuracy and scalability of quantum algorithms for combinatorial optimization
By Mattia Fiorentini and Matthias Rosenkranz
Many industries face tough optimization problems that are challenging for classical computers. Take a steel manufacturer producing a variety of products: from metal sheets and pipes to railway wheels and crankshafts. Manufacturing all products in time and at minimal cost requires complex scheduling of several production processes. Another example is a logistics company trying to optimize the routes for its drivers transporting goods between different locations safely and at minimal cost given current demands, supply and traffic.
These are examples of combinatorial optimization problems — finding the optimal solution in a finite set of potential solutions. Exactly solving combinatorial optimization problems is notoriously difficult for any computer, quantum computers included. This is why practitioners resort to approximate or heuristic solutions.
Quantum heuristics can solve tough problems
If these problems are so difficult, what advantage could quantum computers bring? Over the past decade, researchers have developed new heuristics: quantum algorithms that solve combinatorial optimization problems approximately. Running those new heuristics on powerful quantum hardware could improve the accuracy of approximate solutions.
The best known examples of this crop of algorithms are the Quantum Approximate Optimization Algorithm (QAOA) and, to some extent, the Variational Quantum Eigensolver (VQE), which is a popular choice for chemistry problems. They work by encoding the optimization task in the energy landscape that a quantum system explores. The valley reaching the deepest point corresponds to the optimal solution of the original problem (or valleys in case of multiple, equivalent solutions). The quantum system acts like a ball rolling on this landscape, and the algorithm’s task is to guide it into the deepest valley. At CQ, making those heuristics useful on today’s noisy intermediate-scale quantum (NISQ) hardware is a continuing source of inspiration for developing new algorithms.
The Filtering Variational Quantum Eigensolver is a novel, fast, and accurate quantum heuristic
This is where our new research article “Filtering variational quantum algorithms for combinatorial optimization” comes in. Our team has developed and tested new methods to speed up convergence, improve the solution quality and reduce hardware resource requirements compared to standard VQE and QAOA. In essence, these methods push the quantum system into the deepest valley of the landscape in fewer steps most of the times. We call this approach the Filtering Variational Quantum Eigensolver (F-VQE).
The basic idea of this algorithm is simple but effective. At each optimization step, the algorithm modifies the landscape by applying a filter. A filter is a transformation that increases the valleys’ relative depths but does not change the position of the valleys. As a consequence, the algorithm finds those deeper valleys and hops out of the shallow ones much faster than in the original landscape. We say that the algorithm converges faster. We have observed 10–100 times faster convergence compared to VQE and QAOA on simulators and confirmed this behaviour on the Honeywell System Model H1 trapped-ion quantum computer.
The team also found that the solutions proposed by the new algorithm cluster tightly around the optimal solution of each problem. This means that a candidate solution found by our algorithm is more likely to be close to an optimal solution than one found with the algorithms we had previously available. The experiments indicate that this result holds while increasing the number of variables in the optimization problem.
Combined with causal cones, F-VQE solves larger optimization problems using fewer qubits
Finally, these new methods can scale to large problem sizes even on hardware with limited capacity. Many quantum optimization algorithms roughly map each binary variable of an optimization problem to one qubit. This limits instance sizes on today’s hardware to 10s of variables. To go beyond this limit, the team combined filters with the concept of causal cones that CQ had previously explored. Causal cones are a systematic way of breaking up large quantum circuit evaluations into smaller pieces involving only a few qubits. Effectively, this technique decouples problem size and the number of required physical qubits. As an example, the team solved an optimization problem embedded in the state of 23 qubits using a maximum of 6 hardware qubits. Importantly, this approach is flexible and can adapt to improving hardware quality. As our techniques will help scaling up solutions, it will be of interest to study the interplay with barren plateaus (J. R. McClean et al. and M. Cerezo et al.), which limits the effectiveness of certain variational quantum algorithms.
Improving quantum hardware and algorithms together will pave the way to better optimization heuristics
The methods we developed push the boundaries of the problem sizes that quantum optimization heuristics can attack with current hardware — from the typical few qubits to a few tens of qubits. This development is significant as it narrows the gap between the qubits that are physically available and the ones that can be effectively used to solve problems of applied interest. F-VQE is a step towards our goal of making today’s quantum hardware useful for the combinatorial optimization problems encountered across manufacturing, logistics, supply chain management and finance. Ultimately, we believe that the combination of hardware improvements and algorithmic innovations is what is needed to progress towards a quantum advantage in optimization.
Link to the arXiv paper: https://arxiv.org/abs/2106.10055
