Session E34: Quantum Annealing and Optimization II

Live

While quantum annealers usually use ground or thermal equilibrium states for combinatorial optimization, other kinds of machines using quantum or classical driven systems have been proposed in the past several years [1-7]. Among them, Quantum bifurcation Machine (QbM) [4-7] based on quantum bifurcations of Kerr-nonlinear parametric oscillators (KPOs) [4-10] is as powerful as gate-based universal quantum computers [10-12]. A classical machine inspired by QbM, called “Simulated Bifurcation Machine (SBM),” has also exhibited high performance for large-scale combinatorial optimization [13]. Here we review QbM and SBM together with related works.
[1] S. Utsunomiya et al., Opt. Exp. 19, 18091 (2011).
[2] Z. Wang et al., Phys. Rev. A 88, 063853 (2013).
[3] I. Mahboob et al., Sci. Adv. 2, e1600236 (2016).
[4] H. Goto, J. Phys. Soc. Jpn. 88, 061015 (2019).
[5] H. Goto, Sci. Rep. 6, 21686 (2016).
[6] S. E. Nigg et al., Sci. Adv. 3, e1602273 (2017).
[7] S. Puri et al., Nat. Commun. 8, 15785 (2017).
[8] Z. Wang et al., Phys. Rev. X 9, 021049 (2019).
[9] T. Yamaji et al., arXiv:2010.02621 (2020).
[10] A. Grimm et al., Nature 584, 205 (2020).
[11] H. Goto, Phys. Rev. A 93, 050301(R) (2016).
[12] S. Puri et al., npj Quant. Inf. 3, 18 (2017).
[13] H. Goto et al., Sci. Adv. 5, eaav2372 (2019).   

Live

As Moore's Law comes to an end, high performance computing has often turned to dedicated hardware capable of solving a specific family of problems for increased computational power. Quadratic Unconstrained Binary Optimization (QUBO) problems, or equivalently, two-body Ising problems, have been the focus of a multitude of new dedicated hardware devices of different types: fully classical (Fujitsu, Toshiba, STATICA, MemComputing, etc.), semiclassical (Coherent Ising Machine), and quantum (D-Wave). Development of QUBO-specific algorithms has likewise been prolific. Benchmarks across these QUBO solvers have not been uniform, partly due to differences in characteristics like connectivity, precision, maximum size, etc. Important questions like the current state of quantum QUBO solvers vs. classical QUBO solvers, and more practically which solver to use when, have gone only partially addressed. In this work, we seek to provide answers to these questions by uniform benchmarks across a wide range of state-of-the-art solvers, both classical and quantum, including the establishment of scaling comparisons on planted solution instances.   

Live

Nonlinear parametric resonator networks are promising candidates as Ising machines for annealing and optimization. An important question concerns the validity of this Ising analogy for this intrinsically nonlinear many-body systems. Here we address this question by considering a network of two parametric resonators. Even in the weak coupling regime, we find physics beyond the Ising paradigm with the occurrence of ghost bifurcations involving only unstable solutions. These bifurcations become highly relevant in the presence of noise as they determine the transition paths and the switching rates between stable solutions. We verify our findings with a simple table-top experiment involving capacitively coupled electrical resonators. The presented results demonstrate that the dynamics of these networks are not fully captured by the Ising analogy. Our work emphasizes the need for further exploration of many body effects beyond the Ising analogy for applications as optimization devices.   

Live

Quantum annealers, which make use of the adiabatic theorem to efficiently find the ground state of a physically realizable Hamiltonian, provide an alternative approach to quantum computing. Such devices are currently commercially available and have been successfully applied to several combinatorial and discrete optimization problems. However, the application of quantum annealers to problems in chemistry remains a relatively sparse area of research due to the difficulty in mapping molecular systems to the Ising model Hamiltonian. In this paper we review two different methods for finding the ground state of molecular Hamiltonians using quantum annealers. In addition, we compare the relative effectiveness of each method by calculating some of the ground state properties of a few simple molecules. We find that while each of these methods is capable of accurately predicting the ground state properties of small molecules, neither demonstrates an improvement over modern classical algorithms.   

Live

A tool capable to efficiently generate realistic structural models of disordered systems has been a goal of material science for many years. We show the feasibility of quantum annealing in exploring the energy landscape of materials that deviate from the ideal crystalline phase, specifically vacancy defects in graphene and disordered silicon. By mapping the competing interactions onto quadratic unconstrained binary optimization problems (QUBO), our approach guarantees access to all the arrangements of the multiple defects on the graphene sheet respecting the relative formation energies. In the case of silicon, a large portion of the structural models with increasing disorder is encoded in the low energy spectrum of the QUBO formulation and detected in the annealing process. Our approach reproduces known results and provides a stepping-stone towards applications of quantum annealing to more complex problems of physical-chemical interest.   

Live

Quantum annealers have grown in complexity to the point that devices with few thousand qubits are approaching capacities to tackle material science problems. Starting from a representation of crystal structures in terms of networks, we develop models of order-disorder phase transitions for two prototypical classes of materials (entropy stabilized alloys and perovskites) that are directly implementable on the D-Wave devices. Cost functions are built to encode the ordered phase, while disordered phases appear as excited states in the spectrum of the classical Ising Hamiltonian, which accounts for the competing interactions in the material. Taking advantage of the statistical nature of the quantum annealing, we explore the energy landscape and generate all the structural models for each step of the order-disorder phenomenon. Besides providing a correct description in terms of critical temperatures, our model allows accessing a wide range of structural models, overcoming some limitations of classical methods.   

Live

I present ongoing work on experimentally testing the performance of a new way of encoding integer variables onto quantum annealers based on the physics of domain walls as presented in [1]. This encoding is compared to a traditional "one hot" constraint using simple colouring problems. I show experiments performed on the D-Wave Systems Inc. quantum annealers using both the "2000Q" and "advantage" generation of QPU. Preliminary results suggest that the domain wall encoding out performs the traditional method. I discuss a possible explanation in the fact that one hot encodings are susceptable to a mode of failure where the minor embedding chains used to map a graph of higher connectivity in the hardware graph break and decode to a qubit state which does not correspond to a valid problem solution. This work was performed in collaboration with Jie Chen at Durham University and Tobias Stollenwerk at DLR. In addition reporting the new experimental results, I will briefly review the encoding techniques in [1], and discuss applications of the encoding in quantum simulation [2].

[1] Nicholas Chancellor 2019 Quantum Sci. Technol. 4 045004
[2] Steven Abel, Nicholas Chancellor, Michael Spannowsky arXiv:2003.07374; Steven Abel, Michael Spannowsky arXiv:2006.06003   

Live

We propose a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of n_c classical variables can be implemented on as little as O(log n_c) qubits. By dividing the classical variables into subsystems, we use ancilla qubits to capture intra-subsystem correlations and register qubits to encode the address of each subsystem within the quantum state. We examine the limit where each subsystem consists of only a single classical variable. The resulting quantum state, without capturing any classical correlations, allows for an exponential reduction in the qubits required. With this minimal encoding, approximate solutions for a 64-variable problem can be found using only 7 qubits. We then show how two-body correlations can be encoded, and how these correlations can bring about an improvement in the quality of the solutions obtained. We demonstrate the encoding for two-body correlations by finding approximate solutions to a 42-variable Max-Cut problem using 8 qubits. Lastly, we present the general framework for extending the expressibility of the probability distribution for capturing multi-body correlations.   

Live

Quantum versions of random walks (QW) have long been known to solve the unordered search problem.
Recently, we showed that QW can also solve more realistic hard problems using many repeats of short runs. This is promising for practical application on realistic noisy quantum hardware, either purpose-built quantum annealers, or using QAOA algorithms. By exploiting the correlations in the problem, we find numerically that QW provide a better scaling than search for spin glass ground state problems [Callison et al, NJP, 21 123022, 2019], MAX2SAT, and maximum independent set. However, the most important comparison is with state-of-the-art classical algorithms for the same problems. By this metric, pure QW do not beat the best classical. However, hard problem instances for classical algorithms are not necessarily hard for QW, and vice versa: correlation of problem hardness (at testable sizes) is weak. This points to hybrid algorithms as the best approach for speeding up practical optimisation problems, both quantum-classical, and quantum-quantum, generalizing QW to rapid quenches [Callison et al, arXiv:2007.11599].   

Live

Combinatorial optimization on near-term quantum devices is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise levels and limited error-mitigation. In this paper, we propose an iterative Layer-VQE (L-VQE) approach, inspired by Variational Quantum Eigensolver. We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE to QAOA, and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to sampling noise and has a higher chance of finding the solution, as compared to standard approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.   

Live

In combinatorial optimization, approximation algorithms aim to find approximate solutions with provable guarantees on the distance between the returned solution and the global optimum. The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical algorithm that seeks to achieve approximate solutions by iteratively alternating between intervals of controlled quantum evolution. Here, we examine the effect of analog precision errors on QAOA performance both from the perspective of algorithmic training and canonical distance metrics between quantum states. Leveraging cumulant expansions and the filter function formalism (FFF), we recast the faulty QAOA as a control problem in which precision errors are synonymous with multiplicative control noise. We show that the FFF proves to be a useful tool for understanding QAOA evolution subject to precision errors. Furthermore, we show that the FFF approach to QAOA lends itself to more general noise scenarios and the calculation of error bounds on QAOA performance and broader classes of variational quantum algorithms.   

Live

Large networks of parametric oscillators hold the promise to solve a paradigmatic NP-hard problem, namely finding the ground state of frustrated Ising models. Recent theoretical studies and experiments based on linear stability analysis showed that coherent Ising machines necessarily encounters two major obstacles: The system can either be trapped in oscillatory persistent beats, or get stuck in a wrong configuration dictated by the eigenvalues of the coupling matrix. These obstacles make networks of coupled parametric oscillator close to threshold intrinsically not an Ising solver. Here we show that for pump power sufficiently above the threshold the system can find correct Ising solutions. Our study highlights the role of nonlinearities in understanding the dynamics of coupled parametric oscillators and brings hope for their applicability as Ising solvers.   

Live

The RFQA method (Kapit and Oganesyan, arxiv:1710.11056), wherelocal, low-frequency oscillations are added to transverse field terms in adia-batic quantum computing or quantum annealing, can generate polynomialquantum speedups in solving hard optimization problems. Inspired by theperformance of RFQA in continuous time evolution in quantum anneal-ing, we explore a digitized version that could be simulated on universalgate model machines. We apply the digitized version of RFQA to varioustrial problems using classical numerical simulation, and show that RFQAis a potentially promising tool for solving hard problems in optimizationand machine learning.