In February of 2022, Agnostiq released a study providing the present state-of-the-art for solving combinatorial optimization problems on real, noisy gate-model quantum computers. Although the study was primarily focused on the optimization of discrete financial portfolios, the work is much more general with consequences for other industrially important problems including vehicle routing, task scheduling and facility location services.
While this post encompasses broadly the the performance of different gate-model quantum processors for performing portfolio optimization tasks, for a greater level of detail, we recommend that the reader consult the full paper now available on arXiV.
A combinatorial optimization problem arises whenever we are presented with a number of choices and we task ourselves with selecting the best choice. One example surfaces from a problem often posed by delivery companies: “given a set of possible vehicle routes, which one permits the driver to deliver all parcels the fastest?” Another is asked in telecommunications: “given a set number of approved locations for broadcast antennas, which sites should be used to maximize the reach of mobile phone signal?” Lastly, and directly related to this post, a financial investor asks: “Given a list of stocks and a budget for how many different stocks can be bought, which assignment maximizes the amount of cash accumulated over time with the minimal amount of risk?”.
Although hotly debated, many believe that such problems will be best solved using near-future quantum processors; a much sought-after achievement of quantum supremacy for useful problems. All of the above companies now ask: “given present-generation noisy quantum computers, how far are we along the path to possible quantum supremacy?”
While it is quite difficult to say if/when supremacy will be achieved, when judged by the quantum volume benchmark, it is clear that the general quality of qubits is improving. Given this improvement in general metrics, has application-specific performance kept up? While one may naively suggest that improvements in the former implies improvement for the latter, a recent paper in Nature has shown that general performance metrics like quantum volume overestimate the performance actually achieved in structured programs like quantum-optimization algorithms. In this post, we show explicitly that performance in discrete combinatorial optimization has improved and further expose the non-alignment of general and application specific performance. So, let’s benchmark some quantum computers; what are our options?
While there are a plethora of different ways to make a quantum computer, at the time of writing, there are two leading paradigms. One is using trapped ion qubits. Here, the two-level system of an individual qubit is realized through naturally occurring electronic states of an ion trapped/arranged in an electromagnetic field. Qubits are manipulated (i.e, their gates are implemented by) lasers incident on the ions. The other leading method is to use superconducting transmon qubits. Here, a kind of ‘artificial atom’ is created through the careful pairing of capacitors and Josephson junctions linked by superconducting wires. In this case, qubits can be manipulated using microwave resonators.
While each paradigm has its pros and cons, the only way to know which systems perform well for given applications is to test them. We did just that by performing portfolio optimization tasks on superconducting transmon QPUs from IBM and Rigetti and a trapped ion QPU from IonQ.
How did we judge the portfolio optimization performance for each QPU? Given a set of well known stocks in the tech space (GOOG, AMZN, FB, NVDA, TSLA etc.), we tasked each QPU with making the best choice of stocks to invest in given (i) historical market data and (ii) a fixed number of tickers. To understand how the performance of each QPU is judged, we need to first understand a feature of the underlying algorithm performing the optimization: The Quantum Approximate Optimization Algorithm (QAOA).
Broadly speaking, the QAOA samples answers to combinatorial optimization problems from a distribution biased towards sampling good solutions. Our metric - the rather formally named Normalized and Complementary Wasserstein Distance (NCWD) - measures how well the QPU was able to bias the distribution. Importantly, increasing one parameter - the number of layers p in the QAOA circuit - is known to improve the bias imparted by the QAOA. At odds with this is the requirement of a larger number of one and two qubit gates required to increase p. That is, since present QPUs are noise-prone, there comes a point of diminishing returns where any would-be increases in performance coming with larger p are stifled by the tide of noise which acts to degrade performance. Now, a natural question to ask is: at what point do these effects balance for the QPUs we benchmarked?
For regular QAOA (R-QAOA; the original formulation of the algorithm), this point occurs with a large peak in performance at p = 4 for 3 stocks on a IonQ’s 11 qubit trapped ion chip [Figure 1(a)]. For 2 stocks, increasing performance with p was observed up to p = 5 for superconducting chips [shown for Rigetti in Figure 1(b)]. Although no exactly comparable benchmarks have previously been performed, this amounts to a sizable improvement over the most related benchmarks in recent years. Indeed, just two short years ago, the original observation of increasing performance with p was landmark; using two qubits (equivalent to two stocks here) performance increased from p = 1 to 2 when studying a different optimization problem.
Clearly such an observation is now common throughout most hardware at larger depths and qubit counts. Even more recently, benchmarks on Google Sycamore revealed that problems native to the qubit topology (the map of which qubits can directly interact with each other; see the insets of Figure 1) showed increasing performance up to p = 3 using more than 10 qubits. However, one always has to read the small print. These problems were on average efficiently solvable using classical algorithms in stark contrast to discrete portfolio optimization which is not. The work on Google Sycamore did also study harder problems (see the supplement of the paper for the important details) but did not observe peak performance at p = 4 and 3 qubits as we have here.
We also deployed two variations of more advanced versions of the QAOA (the Quantum Alternating Operator Ansätz) to the QPUs. These benchmarks have not been performed on quantum hardware for any combinatorial optimization problem making these measurements first-of-a-kind. This extension to R-QAOA takes an alternative approach to ensuring the algorithm keeps true to the budget for the number of stocks that can be purchased. In this case, portfolios which exceed or fall short of the budget are strictly forbidden (on an ideal QPU at least, noise does break this rule slightly) in contrast to the R-QAOA where they are allowed but penalized to discourage solutions that violate the budget constraint. Here, we call these variations E-QAOA-I (extended QAOA) and E-QAOA-II.
Each variation takes a slightly different approach which is fully explained in the paper. For both variations, we were able to observe increasing performance with p [Figure 1(b) shows this for 3 tickers from p = 1 to 2 in E-QAOA-I]. Remarkably, the E-QAOA variations produced good portfolios with better than random chance even when over 1000 one and two qubit gates were required. On the Rigetti Aspen-10 QPU, this can be attributed to the native implementation of XY gates upon which our E-QAOA variations rely upon.
Some striking observations can be made from the R-QAOA benchmarks taken on IBM machines. These machines have been given quantum volume figures by IBM so can be used to reliably ascertain whether quantum volume and application specific performance coincide. We found that they do not. Indeed, the machine with the lowest reported quantum volume we used (ibmq_lima, quantum volume of eight) actually performed the best for portfolio optimization within the IBM QPUs! Furthermore, the performance of all machines (not just IBM) was observed to be highly variable. Fluctuations of up to 29% in portfolio quality were observed in identical measurements. This makes it quite clear that alongside any benchmark must also come a measure of variability.
If you are to take anything away from this blog post, it should be that while hopes of quantum supremacy in combinatorial optimization may seem far away, hardware (and algorithms) are measurably improving; even over the results of recent years. Given our observations of the non-alignment of general qubit quality benchmarks like quantum volume with our benchmarks, it is clear that the best way to keep track of progress is to benchmark machines for given applications. Finally, remember that just because a QPU gives you a result once, does not mean it will do so reliably. That is, because the performance of present QPUs fluctuates between different runs, any benchmarks must be accompanied by a variability statistic.
To learn more about some of the ongoing work in quantum benchmarking check out the following resources: