SIAM News Blog
SIAM News

How Will Early Quantum Computing Benefit Computational Methods?

The first half of 2017 saw considerable news about the imminent impact of quantum computing (QC) on science, math, and data analysis [9]. Diverse viewpoints predict wildly-varying timescales—from years to decades—for initial impact, and debate what types of problems will first be affected. At the 2017 SIAM Annual Meeting, held in Pittsburgh, Pa., this July, we organized a minisymposium entitled “Identifying Computational Methods for Early Benefit from Quantum Computing,” which addressed how QC will become useful to practicing computational scientists. We aimed to identify computational methods that are likely to benefit from QC in the next five years, and share the experiences of early QC application developers.

The conceptual appeal of QC systems is the use of their computational power, which grows exponentially with the number of quantum bits (or qubits), to reduce the time spent executing combinatorial algorithms, which on classical computers grows exponentially with the number of variables. The most advanced commercially available quantum computers are currently delivered by D-Wave Systems; the number of qubits in these systems has doubled every other year for the past six years, a trend that is expected to continue. We believe that D-Wave quantum computers will deliver high-quality solutions quickly and in a sustainable way.

Quantum Annealing

Scott Pakin of Los Alamos National Laboratory (LANL) described the current state of QC systems, where contemporary quantum computers implement one of two computational models: the gate or circuit model [4], or the quantum annealing (QA) model [5]. Here we focus on QA-based quantum computers, as they are the most commercially advanced.

A QA-based processor is a special-purpose device that natively solves the quadratic unconstrained binary optimization (QUBO) problem. The goal of a QUBO is to find the $$x_i \in \{0, 1\}$$ that minimize

$x^{\mathsf{T}}Q x \tag1$

for upper-triangular matrix $$Q$$ with $$Q_{i,j} \in \mathbb{R}$$. The QUBO form is equivalent to the unconstrained binary quadratic programming (UBQP) problem and the Ising model.

One can think of a quantum annealer as a hardware implementation of simulated annealing that uses quantum effects—superpositioning, entanglement, and quantum tunneling—to reduce the likelihood of getting stuck in a local minimum. In both quantum and simulated annealers, finding the $$x_i$$ that truly minimize $$(1)$$ is not guaranteed. Instead, the goal is normally to find good solutions quickly. A D-Wave quantum computer can propose a solution to $$(1)$$ in only $$5\mu$$s even for $$N > 2000$$ (where the search space is greater than 22000), as supported by a D-Wave 2000Q™ system.

Mapping computational problems into QUBO form, which requires creativity and ingenuity but can lead to encouraging results when accomplished, is a key challenge that all subsequently-described applications face.

Applications

Graph Partitioning. Combinatorial optimization as graph-theoretic problems is ubiquitous throughout mathematics, computer science, physics, chemistry, bioscience, machine learning, and complex systems. Many of these problems are NP-hard and therefore rely on heuristic solutions. The availability of quantum computers provides new opportunities to explore relevant quantum graph algorithms, particularly novel QA heuristics and hybrid methods that may out-perform classical approaches or efficiently solve new problem types.

Sue Mniszewski of LANL presented her team’s work on graph partitioning algorithms using QA on the D-Wave 2X™ system [6], motivated by recent studies on graph-based electronic structure theory. Graph partitioning is a natural fit to the QUBO form solved by the D-Wave 2X system. One can naturally map unconstrained community clustering—based on the modularity metric—onto the QUBO, despite its status as a “very hard” problem for a classical computer. When constraints are imposed (e.g., equal partitioning), QUBO reformulation is necessary. Mniszewski demonstrated concurrent partitioning based on the graph coloring problem, community clustering via modularity, and iterative multilevel partitioning with refinement (similar to METIS and KaHIP) on benchmark graphs and electronic structure graphs. Even graphs with approximately self-similar structure, which are traditionally difficult to partition, benefit from quantum graph partitioning (see Figure 1). Graph partitioning results from quantum and hybrid classical-quantum approaches show that the D-Wave 2X system is comparable to current state-of-the-art methods, and sometimes better.

Figure 1. From left to right: Phenyl dendrimer molecular structure to the electronic structure graph and the resulting 8-concurrent graph partitioning using a D-Wave system. Image credit: Susan Mniszewski, Los Alamos National Laboratory.

Traffic Flow Optimization. Florian Neukart from Volkswagen (VW) described the mapping of certain parts of the real-world problem of maximizing traffic flow into a form suitable for QA [7]. The objective is to reduce the time required for a set of cars to travel between their individual sources and destinations by minimizing total congestion over all road segments. To combat the limited size and connectivity of current-generation D-Wave systems, the VW team developed a hybrid quantum and classical workflow—based on the T-Drive trajectory dataset of the cars’ GPS coordinates—that mimics traffic flow optimization in near-real time, integrating calls to the D-Wave system.

The team maximized simulated traffic flow between the Beijing city center and airport by redirecting a subset of 418 selected taxis to alternate routes, thus minimizing the number of congested (i.e., having more than a given number of vehicles at a given time) road segments. This required simultaneous optimization over all vehicles. The program considered three alternative routes, described by lists of street segments, for each trip between the city center and airport, and assigned cars to routes that minimized the number of congested road segments. The left half of Figure 2 displays the traffic density on the Beijing road graph before optimization, and the right displays the density after optimization via D-Wave’s qbsolv tool [2].

Figure 2. Heatmaps of traffic congestion in unoptimized (left) and optimized (right) flows. Image credit: Florian Neukart, Volkswagen Group of America.

The VW team focused on finding good quality solutions within short periods of calculation. They ultimately showed that time-critical optimization tasks, such as continuous redistribution of position data for cars in dense road networks, are suitable candidates for quantum applications.

Finance. Phil Goddard of 1QB Information Technologies (1QBit) works with applications in computational finance, where many high-value problems can be cast as combinatorial optimization problems and are hence solvable with QA. Specific applications include multiperiod mean-variance portfolio optimization, (quantum) hierarchical risk parity feature selection for credit scoring, and tax loss harvesting [1]. While adhering to realistic investment constraints, the problem variables can be discretized and reduced through suitable transformations to the QUBO form solved by a D-Wave system. The size of the solvable optimization problem (measured in number of problem variables) depends on several factors, including the technique used to discretize the problem and the way it is embedded onto the Chimera graph topology in which the D-Wave system’s qubits are laid out. Conceptually, the benefits of using QC will increase with problem size.

Programming

Steve Reinhardt of D-Wave Systems described the range of software tools available to solve problems on existing commercial quantum computers. Only in the last year or two have interfaces emerged that are higher level than the system-dependent quantum machine instruction exposed by D-Wave’s low-level system interface [3]. Several groups of tool developers deliver interfaces that allow a problem to be stated as a polynomial and then converted to a QUBO. Two groups deliver solvers that solve a problem larger than that natively supported by the hardware by repeatedly decomposing the problem into chunks that can be executed on the system. These tools have become essential for application and higher-level tool development. QC Ware Platform [10] and edif2qmasm [8] are tools that enable subject-matter experts to express problems in high-level forms and map those problems to a QUBO for D-Wave execution.

Summary

When comparing techniques for the different applications, we see that effectively mapping a problem to QUBO form is essential to obtaining good results. Some problems map directly to QUBOs while others map with intermediate steps that may add ancillary variables. Either approach matches well with a D-Wave quantum computer, ideally resulting in a problem that is sufficiently hard, as D-Wave systems are more likely to deliver a performance advantage over classical systems in the case of hard problems. Additionally, programs solving real-world problems invariably execute in a hybrid classical-quantum mode. All of the aforementioned applications also take advantage of a decomposing solver to fit the problem—in chunks—onto the QC system.

References