Implementing real-world optimisation use cases in state-of-the-art quantum devices

The topology of the Aspen-M-2 quantum computer
The Aspen-M-2 device. The latest superconducting qubit device developed by Rigetti Computing. It hosts 80 quantum bits (qubits), and its average coherence times are T1 ≃ 28 μs and T2≃ 18 μs at the time of experiment.

Minimum Vertex Cover

The Minimum Vertex Cover (MVC) of a graph is defined as the smallest set of nodes connected to every edge in the graph. Computing the MVC has been shown to be a generically NP-hard problem.

Finding the Minimum Vertex Cover, the Maximum Independent Set and the Maximum Clique of a graph are equivalent combinatorial optimisation problems.

Real World Use Cases

We chose to focus on the MVC problem to explore commercial applications across a wide variety of fields. Our problem instances were sourced from three different areas in which the MVC, MIS and MC emerge naturally:

  • Water distribution networks: Given their physical structure, these systems are usually represented by graphs. A common problem that arises in this field is how to optimally distribute sensors to monitor the network. This translates into an MVC problem, where the nodes belonging to the MVC determine where the monitoring units should be placed.
  • Synthetic biology: In this field, genetic constructs are often designed and built by combining DNA sequences known to have particular functions. Generating synthetic DNA constructs that involve many parts with similar sequences can lead to cell stability problems. Therefore, one key challenge is to build libraries of DNA parts whose sequences are as diverse as possible. Given a set of DNA parts as strings, this problem can be formulated as finding a MIS, by mapping the strings into nodes of a graph and adding edges between them whenever the strings share more letters than a specified length.
  • Portfolio Allocation: One approach for designing a portfolio allocation strategy is to make use of market graphs. A market graph is constructed by mapping a set of stocks into the nodes of a graph and drawing edges between them whenever their correlation over a certain period of time is larger than a fixed threshold. A straightforward application of market graphs is to obtain the maximal number of correlated stocks, which maps onto finding the MC of the graph.
Left: Sensors placed in the nodes of a network are used to monitor all outgoing connections to subsequent nodes. Center: Strings are mapped into nodes, and edges are drawn between them whenever they share a repetition (red letters) of length L > Lmax. Right: The market graph is constructed by mapping a stock to a node (cryptocurrencies in this example) and connecting them when their correlations (written on the edges) are higher than some threshold Cth.

Problem Implementation

We implemented the problem instances on the hardware following three steps:

  1. Qubit selection: From all possible sets of qubits that could host the problem instance, we kept the set with the highest average fidelity.
  2. Qubit routing: Using SWAP operations, we generated the connections present in the instance but not on Aspen-M-2.
  3. Gate parallelisation and unfencing: We applied the pulse-level control tools hosted by Rigetti’s software package, Quil-T, to enable simultaneous execution of the parallelised circuit gates.
Hardware implementation of problem instances.

Finding the MVC using quantum computing

We employed two different algorithms to find the MVC: the Quantum Approximate Optimisation Algorithm (QAOA), the go-to algorithm for optimisation with noisy quantum computers; and its recursive version (RQAOA), which reduces the size of the problem recursively until it is small enough that it can be solved exactly. In particular, we developed an adaptive version of RQAOA (Ada-RQAOA) that enables a faster decrease of the problem size, while maintaining comparable levels of performance.

Hardware Performance

The quality of the experiments is limited by the coherence times of the hardware. To maximise the performance of quantum computing, it is essential to minimise the depth of the circuit to operate within the permitted time scale.

  • Qubit selection criteria: In a real device, each qubit has a different coherence time. We found that a poor choice of qubits can dramatically impact the performance. By selecting sets with the highest fidelity we obtained good results, but we expect other aspects, such as the role of specific qubits in the routing schedule, to be also of high importance.
  • Number of edges in the instance: Naturally, a large number of edges will result in a deeper circuit to implement. Accordingly, for larger/denser instances, we observed a decline in the performance of the algorithms. Based on our experiments, we estimate that reasonable performances can be obtained up to ∼150 edges.
  • Optimality of routing schedule: There are multiple ways of swapping qubits to satisfy the structure of the instance at hand. Doing so in a sub-optimal way inevitably results in longer circuit execution times. We thus performed an additional optimisation routine to minimise the number of SWAP operations required to build the schedule. Nevertheless, for certain instances, we only observed a clear optimisation process once Ada-RQAOA had reduced the size enough such that, even after routing, we were operating within the average coherence time.
Finding MVCs using quantum computing. (a)-(c) Costs obtained from QAOA, Ada-RQAOA and random solutions (avg. over 5000 samples) and the exact solution. Better solutions correspond to lower costs. Labels in brackets denote the number of nodes N and average degree ⟨d⟩, as (N,⟨d⟩). (d)-(f) The recursive optimization process. Problem instances: (a) Water distribution networks repository, (b) Data sets in Hossain et al. Nature Biotechnology 38, 1466 (2020), (c) Kaggle data set on cryptocurrency evolution.

Conclusion

This study explores the potential for quantum computing to play an increasing role in tackling hard optimisation problems. We illustrate key methodologies and challenges associated with executing QAOA and related algorithms at scale.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Entropica Labs

Entropica Labs

58 Followers

The Quantum Software House, making quantum computers useful.