Designing hybrid algorithms for neutral-atom quantum hardware using Bayesian optimization

The BMW group sponsors PhD students to research novel approaches to address computational challenges in the automotive industry. Their goal is to bridge the gap between academia and industry, accelerate technology transfer, and create pathways for early-career researchers who want to apply their skills and expertise towards the hardest problems in industry.

In this blog post, Jernej Rudi Finžgar describes recent results from his research within the scope of his BMW PhD program. In collaboration [1] with the BMW Group, the Amazon Quantum Solutions Lab, the Technical University of Munich, and the Tokyo Institute of Technology, he investigated efficient Bayesian optimization protocols for quantum optimization problems with QuEra’s Rydberg quantum computer on Amazon Braket.

Introduction

Combinatorial optimization plays an essential role in the automotive industry — be it the problem of orchestrating the motion of robotic arms in production plants or determining the optimal choice of features for test vehicles [2]. Given the complexity of optimizing such processes, the BMW Group is exploring quantum computing as a promising alternative solution strategy. Recently, much interest has been devoted to developing optimization routines that run on special-purpose analog quantum devices. While these devices lack the flexibility of general-purpose digital quantum computers, their special-purpose nature oftentimes makes them easier to scale up, making larger optimization problems accessible on present-day devices. Moreover, the use of such devices facilitates exploiting connections between the physics underlying a particular analog device and the optimization problem of interest.

Prime examples of this approach are Rydberg atom based quantum computers. It has been shown, that the maximum independent set (MIS) problem, a common optimization problem in industry, naturally maps to the physics of large configurable arrays of Rydberg atoms [3]. In the MIS problem, the challenge is to identify the largest possible group of vertices within a graph such that no pair of selected vertices share an edge. While conceptually simple, the problem is computationally challenging (NP-Hard) and is of large commercial relevance [4, 5], e.g., in the context of vehicle routing, antenna placement, or portfolio optimization problems.

Maximum independent set on neutral atom quantum processors

Let’s dive a bit deeper into how a neutral atom quantum computer, such as the QuEra Aquila device available through Amazon Braket, can help solve the MIS problem. To keep things relatively simple, we will concentrate on a special type of graph known as unit disk graphs (UDG). In these graphs, nodes are only connected by an edge if they are within a certain distance from each other, defined by a threshold radius (R_d). Even with this restriction, finding the MIS of UDGs remains an NP-Hard problem [6]. We can then place the atoms in a Rydberg array to mimic the graph of interest and exploit the natural interactions between individual Rydberg atoms to enforce the independence constraint of MIS. In what follows we briefly summarize the principles of operation of a Rydberg atom quantum device. For more details, we recommend a previous blog post presenting details on how to use neutral atom quantum computers to solve the MIS problem.

On the QuEra Aquila device, the user can specify the time dependence of the Rabi frequency (Ω), and laser detuning (Δ) within the following Hamiltonian:

The time dependence of the rabi frequency and laser detuning using a Hamiltonian.

where the schedules will be specified via parameters (θ). Here σ_i^x is the Pauli-x matrix, and n_i counts the number of excited atoms on each site.

Neutral atom quantum computers exploit the Rydberg blockade mechanism, captured by the interaction terms ∼ V_ij. This physical phenomenon prevents two atoms in close proximity (i.e., closer than the Rydberg radius R_b) to be simultaneously excited into the Rydberg state |1〉. By setting up the system parameters such that the Rydberg radius R_b aligns with the unit-disk threshold radius R_d, and associating the |1〉state with a node being part of the independent set, the ground state of the above Hamiltonian matches the solution to the MIS problem, if we set Δ > 0. To see this, consider that the Δ terms favor maximizing the number of excitations (corresponding to the nodes assigned to the independent set). At the same time the Rydberg blockade, captured by the term V_ij, penalizes two connected nodes that are in the state |1〉, i.e., enforces the independence constraint. On the other hand, by setting Δ < 0, the ground state is |00..0〉.

$Figure 1 - Example detuning \mathbf{\Delta} and rabi frequency \mathbf{\Omega} schedules. Taken from [2].$

Figure 1 – Example detuning (Δ) and Rabi frequency (Ω) schedules. Taken from [1].

To solve the MIS problem on a neutral atom quantum computer, we make use of the adiabatic theorem of quantum mechanics, which is the theoretical underpinning of the adiabatic quantum computing paradigm [7-9]. The adiabatic theorem tells us that a system prepared in the ground state of a Hamiltonian will remain in the ground state of the time dependent Hamiltonian, if the rate of change of the Hamiltonian is sufficiently slow. For example, we can prepare the ground state |00..0〉of H at Δ < 0 and slowly ramp up the detuning until some Δ > 0 such that the ground state of the final Hamiltonian encodes the solution to the MIS problem. The maximum ramp-up speed of Δ is related to the spectral gap profile of the intermediate Hamiltonian. Specifically, the spectral gap in this case corresponds to the difference between the energies of the ground state and the first excited state of the Hamiltonian. The smaller this gap, the slower the rate of change for Δ(t) has to be to avoid undesired transitions into excited states.

Ideally, one would like to tailor the Δ(t) schedule to the spectral gap profile. Ramp Δ rapidly while the gap is large and as slowly as possible when the gap narrows. However, the spectral profile of a given problem Hamiltonian is not known a priori. How can one then find optimized schedules in such a scenario?

We can for example use a classical optimizer to derive an optimized schedule for the detuning Δ(t). Optimizing such (quasi-)adiabatic schedules has previously been proposed and used by Ebadi et al. [3], leading to remarkable results on neutral atom quantum hardware. However, this approach typically requires performing around 10⁵ measurements to optimize the protocols. In this blog post, we’re proposing Bayesian optimization as a more resource-efficient method to optimize these schedules, requiring an order of magnitude less measurements than the original proposal by Ebadi et al. This leads to substantial time and cost savings when optimizing protocols on analog devices.

Schematic visualization of the Bayesian optimization (BO) pipeline showing relation between quantum and classical hardware and iterations of the optimizer

Figure 2 – Schematic visualization of the Bayesian optimization (BO) pipeline. BO suggests parameters used to create schedules deployed on the neutral atom quantum processors. The results obtained from the quantum hardware are then passed back to BO which updates its surrogate model and suggests a new parameter set to evaluate. Taken from [1].

Designing the schedules using Bayesian Optimization

Bayesian optimization (BO) is a widely used global optimization routine, especially suitable to optimize black-box functions which are expensive to evaluate, be it in terms of the duration, or monetary cost [10]. As such, it is an attractive candidate to optimize analog protocols on quantum devices.

So how does BO work? Let’s imagine we have an objective function, f(θ), that measures the effectiveness of the solutions to the MIS problem obtained from a neutral atom quantum computer. Here, θ represents the parameters we want to tweak in order to maximize f. For solving the MIS problem on a neutral atom device, these parameters might specify the (quasi-)adiabatic protocol, defining the detuning and Rabi frequency schedules.

BO works by building a “surrogate” model of f(θ) using Gaussian Processes (GPs). GPs are a powerful tool in machine learning and statistics that are good at modeling complex unknown functions. They do this by assuming that any finite collection of points has a multivariate Gaussian distribution. In other words, they provide a flexible way to model complex relationships. Moreover, we can then use the model we have built using GPs to determine the next parameter set to probe, by balancing exploitation (i.e., trying out points in parameter regions where we have previously obtained good results) and exploration (i.e., exploring previously unseen parts of the parameter space).

In our implementation we found the following schedule parametrization to work well in practice. We fixed the Rabi frequency schedule Ω(t) and used four parameters to specify the detuning schedule Δ(t). However, this is one particular design choice that can be modified according to the needs and resources of the end-user. We use the classical MIS cost function [11] as the figure of merit (i.e., f(θ)) to evaluate the quality associated with the bit strings obtained from the QuEra Aquila device. We set α=1.2 for enforcing the constraints.

The optimization of the detuning schedule then proceeds as follows: We begin by evaluating a collection of random parameter sets on the quantum computer. The parameters, together with the obtained value for the figure of merit, serve as initial anchors for the construction of the GP surrogate model. We then proceed by selecting successive points chosen by maximizing the acquisition function. One could additionally design the pipeline such that, initially exploration would be preferred and increasingly exploit the acquired knowledge of the optimization landscape as the optimization progresses.

For illustration, we provide a minimal implementation, executing the pipeline for an example graph on the simulator of the QuEra Aquila device, available on Amazon Braket. Note: Some basic function definitions that are not instrumental to the understanding of our pipeline have been omitted.

from braket.ahs.analog_hamiltonian_simulation import AnalogHamiltonianSimulation
from braket.devices import LocalSimulator

# Define the objective function
def objective_function(params, total_time, device, graph, register, number_of_shots=100):
    """Objective function for Bayesian optimization."""
    # Run the quantum protocol with the provided parameters
    bitstrings = run_protocol(params, total_time, register, device, number_of_shots=number_of_shots)
    # Compute the cost of the obtained solutions
    mis_costs = [get_mis_cost(graph, bs) for bs in bitstrings]
    return -np.mean(mis_costs)  # We want to maximize the cost, hence the negative sign

def run_protocol(params, total_time, register, device):
    """Simulate the AnalogHamiltonianSimulation."""
    # get the drive
    drive = get_drive(params, total_time)
    # compile the program
    ahs_program = AnalogHamiltonianSimulation(drive=drive, register=register)
    # run the program
    result = device.run(ahs_program, shots=number_of_shots).result()
    # extract and return the bitstrings
    bitstrings = np.array([np.array(s.post_sequence) for s in result.measurements])

    return bitstrings

# Prepare the register, the graph, and the device (simulator)
vertex_positions = []  # Replace with actual vertex positions
register = register_from_atom_positions(vertex_positions)
graph = udg_from_atom_positions(vertex_positions)
device = LocalSimulator('braket_ahs')

# Parameter bounds for Bayesian optimization
num_params = 4
max_delta = 125000000.0
parameter_bounds = {f"delta_{i}": (-max_delta, max_delta) for i in range(1, num_params + 1)}

# Prepare objective function
total_time = 4e-6
objective_func = lambda params: objective_function(params, total_time, device, graph, register, number_of_shots=100)

# Initialize Bayesian optimization
optimizer = BayesianOptimization(f=objective_func, pbounds=parameter_bounds)

# Optimize the parameters
num_iterations = 50
num_initialpoints = 10
optimizer.maximize(init_points=num_initialpoints, n_iter=num_iterations)

# Print the best parameters and cost
print(f"Best parameters: {optimizer.max['params']}")
print(f"Best cost: {optimizer.max['target']}")

Results

We first consider three small graph example instances (see top row in Figure 3), with 9 or 10 nodes, for which we can classically (numerically) simulate the protocols.

Figure 3 – Top Row: Three example toy graphs, with the unique maximum independent set represented by the dark nodes. Middle Row: Results obtained in the naïve linear protocol. Bottom Row: Results obtained with the optimized Bayesian optimization schedule.

For the graphs in Figure 3, as a baseline we first try the naïve linear Δ(t) protocol, without any optimization of the parameters (see middle panel in Figure 3). Here, the colors of the nodes correspond to the probability of a certain node being assigned to the independent set in the bit strings obtained from the QuEra Aquila device. While it is possible to recognize certain features of the reference colors (top row in Figure 3), the results are far from ideal. Let us now optimize the detuning schedule using BO. As evident from the bottom row of Figure 3 we find that BO can yield immediate improvements, obtaining nearly perfect solutions for this set of small example problems.

The question begs, how much of this generalizes beyond the toy instances studied thus far. To this end, we considered larger graphs with 137 nodes (qubits). We again compare the linear protocol to the BO-designed protocol for a collection of such graphs.

Figure 4 – Results for large graph instances. The histograms show the quality of the obtained bit strings, as measured by value of the MIS cost function, comparing the naïve linear protocol and the results from the optimized schedules. We report the approximation ratios obtained by each schedule for both BO-designed schedules and standard linear (L) protocols. Taken from [1].

As seen from the histograms in the bottom row of Figure 4, it is apparent that the quality of the solutions can be improved substantially with the help of our BO-designed protocols. To obtain these results, around sixty iterations of Bayesian optimization were performed, amounting to a total of 6,000 measurements required. A previous study by Ebadi et al. [3] proposed schemes requiring roughly 100,000 calls to the quantum device, highlighting the resource-efficiency of Bayesian optimization.

Discussion, outlook, and next steps

In summary, we have shown that analog models of quantum computation can be improved when paired with suitable classical optimizers, in our case BO. We encourage the interested reader to read the original publication [1], where additional use-cases for BO are presented. Moreover, one can find several useful technical details therein; these may further improve the performance on top of the functionalities provided in the code snippet above. Finally, there is still much to be explored in this nascent field. Promising future research could include extending the study to other (analog) quantum information processors or combining BO with other classical optimizers better suited for fine tuning the parameters. We hope that this blogpost, and the associated publication [1], spurs research into these exciting possibilities.

The content and opinions in this post are those of the third-party author and AWS is not responsible for the content or accuracy of this post.

References

[1] Finžgar, Jernej Rudi, Martin J. A. Schuetz, J. Kyle Brubaker, Hidetoshi Nishimori, and Helmut G. Katzgraber. 2023. ‘Designing Quantum Annealing Schedules Using Bayesian Optimization’. arXiv: 2305.13365.

[2] Finžgar, Jernej Rudi, Philipp Ross, Leonhard Holscher, Johannes Klepsch, and Andre Luckow. 2022. ‘QUARK: A Framework for Quantum Computing Application Benchmarking’. Pp. 226–37 in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Broomfield, CO, USA: IEEE.

[3] Ebadi, S., A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J. G. Liu, R. Samajdar, X. Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S. T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. 2022. ‘Quantum Optimization of Maximum Independent Set Using Rydberg Atom Arrays’. Science 376(6598):1209–15. doi: 10.1126/science.abo6587.

[4] Wurtz, Jonathan, Pedro Lopes, Nathan Gemelke, Alexander Keesling, and Shengtao Wang. 2022. ‘Industry Applications of Neutral-Atom Quantum Computing Solving Independent Set Problems’. arXiv:2205.08500.

[5] Dong, Yuanyuan, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, and Quico Spaen. 2021. ‘New Instances for Maximum Weight Independent Set From a Vehicle Routing Application’. Operations Research Forum 2(4):48. doi: 10.1007/s43069-021-00084-x.

[6] Pichler, Hannes, Sheng-Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail D. Lukin. 2018. ‘Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays’. doi: 10.48550/arXiv.1808.10816.

[7] Kadowaki, Tadashi, and Hidetoshi Nishimori. 1998. ‘Quantum Annealing in the Transverse Ising Model’. Physical Review E 58(5):5355–63. doi: 10.1103/PhysRevE.58.5355.

[8] Farhi, Edward, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. 2001. ‘A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem’. Science 292(5516):472–75. doi: 10.1126/science.1057726.

[9] Hauke, Philipp, Helmut G. Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D. Oliver. 2020. ‘Perspectives of Quantum Annealing: Methods and Implementations’. Reports on Progress in Physics 83(5):054401. doi: 10.1088/1361-6633/ab85b8.

[10] Mockus, Jonas. 2012. Bayesian Approach to Global Optimization Theory and Applications. S.l.: Springer Netherlands.

[11] Lucas, Andrew. 2014. ‘Ising Formulations of Many NP Problems’. Frontiers in Physics 2. doi: 10.3389/fphy.2014.00005.

AWS Quantum Technologies Blog