Session P08: Quantum Annealing and Optimization III

Projecting NISQ-era quantum advantage with QAOA

A major milestone in quantum computing research is the demonstration of quantum supremacy, where some computation is performed by a quantum computer that is unfeasible classically. Recently, the efforts culminated in the experiment by Google's quantum teams and collaborators of sampling from random circuits. However, it is important to recognize that supremacy demonstrations based on artificial tasks bring very limited advantage for practical applications. A common problem used in benchmarking high performance computing is MaxCut, with applications in domains such as machine scheduling, image recognition, electronic circuit layout, and others. Maxcut has been used extensively, both theoretically and experimentally, to assess the performance of the hybrid Quantum Approximate Optimization Algorithm (QAOA), one of the leading candidates to demonstrate quantum advantage in the NISQ era. Here we project the performance of QAOA by considering the challenges due to its variational and stochastic nature and compare it with several among the best performing classical solvers in terms of time to solution and quality. The results demonstrate the importance of algorithm and problem selection and we discuss the performance data in the context of projecting NISQ-era quantum advantage.   

Small-parameter and operator series approaches for quantum approximate optimization

We show a calculus for analyzing algorithms based on quantum alternating operator ansatze, in particular the quantum approximate optimization algorithm (QAOA). Our framework relates cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function structure. For QAOA we show an exact series expansion in the algorithm parameters and cost gradient operators. This enables analysis in different parameter regimes which yields novel insights. In the small-parameter regime, for single-layer QAOA-1 the leading-order change in solution probability is determined by cost differences; for sufficiently small parameters probability provably flows from lower to higher cost states on average (or vice versa via parameter selection). On the other hand, we derive a classical random algorithm which emulates QAOA-1 in the same small-parameter regime, i.e. outputs samples with the same probabilities up to small error. Our results apply generally under minimal cost function assumptions. For deeper QAOA-p circuits we derive analogous results in several settings. We discuss applications to performance, parameter setting, and design of more effective QAOA mixing operators.   

Reinforcement Learning for Finding QAOA Parameters

Quantum Approximate Optimization Algorithm (QAOA) is an important variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems on NISQ devices. The quality of the solution obtained by QAOA depends on the performance of the classical optimizer used to optimize the variational parameters, but finding these optimal parameters can be hard to achieve. To address this problem, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances using two machine learning based approaches. We used reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits and a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on the small-sized problem instances, which can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Our proposed RL and KDE based approaches reduce the optimality gap by factors up to 30 when compared to other commonly used standard optimizers.   

Quantum approximate optimization of the exact-cover problem on a superconducting quantum processor

Superconducting qubits are one of the leading technologies for building useful quantum processors. Currently available devices, where error correction and fault tolerance is not yet possible, are usually referred to as noisy intermediate-scale quantum (NISQ) devices. Such processors hold yet great promise, for instance they might allow for running heuristic quantum algorithms solving combinatorial optimization. On small-scale quantum processors, these algorithms serve as important technology demonstrators. Here, we use the quantum approximate optimization algorithm (QAOA) to solve small instances of the NP-complete exact-cover problem. This problem has many real-world applications, such as work-shift scheduling and tail assignment for airlines. We implement the QAOA on our hardware platform consisting of two superconducting transmon qubits and one parametrically modulated coupler. We explore iteration levels of the algorithm up to two, and compare the performance of three different black-box optimizers. Our results show that the exact-cover problem can be solved by the QAOA with high success probability.   

QAOA for Optimal Flight Gate Assignment

The QAOA is one of the candidates for quantum algorithms which might outperform classical approaches, while being amenable to NISQ devices. The target application for this approach is finding approximate solutions to combinatorial optimization problems. Since real world combinatorial optimization problems almost always have hard constraint, the algorithm was generalized to the Quantum Alternating Operator Ansatz. This approach consists of two alternating operators. First the phase separation operator which stems from the original cost function and second, a suitable mixing operator which explores the whole feasible subspace while conserving the hard constraints.

In this work, we present a Quantum Alternating Operator Ansatz for the problem of optimal assignment of airplanes to gates in a large airport hub. This is a hard operational planning problem with real world impact. We investigate several problem variations and their different relationships to NP-hard graph coloring problems. Our primary contribution is the development of novel mixing operators for the different problem settings and facilitate efficient QAOA implementation. For each case we analyse the quantum resource requirements and discuss the feasibility of using real-world problem input data.   

Probing topological defect formation in a quantum annealer

When a quantum phase transition is crossed in finite time, the breakdown of adiabatic dynamics leads to the formation of topological defects. The average density of defects scales with the quench rate following a universal power-law predicted by the Kibble- Zurek mechanism. The later provides useful heuristics for adiabatic quantum computation. Physics beyond the Kibble-Zurek mechanism can be probed by characterizing the full counting statistics of topological defects. We argue that the distribution of the number of defects generally follows a Poisson binomial distribution with all cumulants exhibiting a universal power-law scaling with the quench rate. As an example, we report the exact kink number distribution in the transverse-field quantum Ising model. For this system, we test kink statistics in a D-Wave machine and show that the study of the kink number distribution can be used to benchmark the performance of a quantum processor.

References:
[1] A. del Campo, Phys. Rev. Lett. 121, 200601 (2018)
[2] Jin-Ming Cui, F. J. Gómez-Ruiz, Yun-Feng Huang, Chuan-Feng Li, Guang-Can Guo, A. del Campo, arXiv:1903.02145
[3] Y. Bando et al, TBS (2019)   

Simulations of the Ising Model on a Shastry-Sutherland Lattice by Quantum Annealing

The Ising Hamiltonian offers a versatile model for studying the microscopic behavior of several material systems. We study an Ising Hamiltonian on a geometrically-frustrated Shastry-Sutherland lattice, which has been used to explain the magnetic properties of the rare-earth tetraborides. Variants of this model can produce a complex phase diagram with emergent fractional magnetization plateaus. We present a novel embedding of the lattice into the D-Wave 2000Q processor and use forward and reverse annealing to compute the phase diagram and probe the magnetization plateaus in the classical limit of zero transverse field. Empirical results enable us to calculate the static structure factor in the different phases and critical regimes opening opportunities for direct comparisons to reciprocal-space experimental techniques. Using quantum Monte-Carlo calculations to validate our results, this work indicates that quantum annealing provides a versatile method of material simulation that can accelerate scientific discovery.   

Excited-state search by quantum annealing toward quantum chemistry calculations

We report two methods to obtain an excited state of a spin-1/2 system using quantum annealing (QA) and adiabatic quantum computation (AQC), and evaluate their performance based on the fidelity of the output states. Although QA and AQC has been developed to search ground states of Ising Hamiltonians, excited state is also required when we analyze quantum systems such as electrons in molecules. We propose two methods to obtain the excited states: methods using non-adiabatic transition and adiabatic transition. It is unclear which method is better under noisy environment. In order to compare the methods, we numerically solved the Lindblad master equation for a certain simple model, and compared their fidelity of output states. As a result, we found that the output of method using adiabatic transition was as high fidelity as the other even when the problem seemed to be difficult for the adiabatic method.   

Isomer Search on the D-Wave Quantum Annealer

Isomer search or molecule enumeration refers to the problem of finding all the isomers for a given molecule. Many classical search methods have been developed in order to tackle this problem. However, the availability of quantum computing architectures has given us the opportunity to address this problem with new (quantum) techniques. This paper describes a procedure for determining all the structural isomers of alkanes. We first formulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. We use the D-Wave quantum annealer to enumerate all structural isomers of all alkanes with fewer carbon atoms (n < 10) than Decane (C10H22). The number of isomer solutions increases with the number of carbon atoms. We find that the sampling time needed to identify all solutions scales linearly with the number of carbon atoms in the alkane. We probe the problem further by employing reverse annealing as well as a perturbed QUBO Hamiltonian and find that the combination of these two methods significantly reduces the number of samples required to find all isomers.   

Exploring phase transitions in a quantum dimer using a quantum annealer

It is well known that problems with exponentially decreasing gaps can cause adiabatic quantum computation (AQC) to fail. However, this does not imply that open-system quantum annealing (QA) will also fail for these problems. We consider an archetypical problem that is classically trivial, but difficult for AQC: an Ising ladder exhibiting a first-order phase transition with an exponentially closing gap, and a second-order phase transition with a polynomially closing gap. We investigate the performance of QA at these quantum phase transitions/ gap scalings theoretically using open quantum systems theory and experimentally using the D-Wave quantum annealer.   

Solving the Graph Isomorphism Problem on a Quantum Annealer

The Graph Isomorphism (GI) problem—the task of deciding whether two graphs are isomorphic—has garnered considerable interest both for its wide range of applications in industry and for its particular computational complexity. One possible approach is measuring certain graph invariants—quantities that remain unchanged under vertex relabeling. While a complete graph invariant that would unequivocally distinguish non-isomorphic graphs is yet unknown, the energy spectrum of the quantum Ising Hamiltonian is a possible candidate. This is the Hamiltonian implemented by commercially available quantum annealers, making quantum annealing a natural tool for solving certain hard instances of the GI problem. Following the lead of previous work, we use a D-Wave quantum annealer to distinguish between pairs of graphs with the same classical Ising spectrum by gathering statistics on the energy and other observables. We show that introducing a pause at intermediate points in the anneal yields clearly different results for graphs that had previously been undistinguishable using standard annealing schedules.   

Optimizing annealing parameters using genetic algorithms

Quantum annealing is an emerging technology that has the potential to be useful for solving combinatorial optimization problems such as maximum satisfiability. Prior work showed that annealing times [1] and inclusion of pauses [2] can significantly impact the probability of obtaining exact solutions. Less is known about leveraging other parameters such as flux biases implemented on the most recent D-Wave 2000Q annealer. We seek to bridge this gap by using genetic algorithms to select parameters. We explore various statistical measures, such as stochastic for ranking settings. Evaluations are performed using the Ames Research Center annealer.

[1] E. Crosson, arXiv:1401.7320
[2] J. Marshall, PhysRevApplied.11.044083   

Quantum annealing applied to ionic diffusion analysis

We applied the quantum annealing framework to a problem of ionic diffusions in solids. The problem has been one of the important issues both in scientific and industrial sense in the field of materials science, which originally attracted interests in the microscopic analysis of mechanical strengths but is recently getting more active in exploring better batteries because the ionic diffusions as the charge carriers affect the efficiency in the solid electrolytes. We developed a scheme to formulate the problem in terms of the mapping into a quantum spin systems described by the Ising Hamiltonian. A key quantity to describe the diffusion can be evaluated from the output of annealing simulations, which has been quite difficult to be obtained by classical counterparts.   

Experimentally Testing Quantum Critical Dynamics Beyond the Kibble-Zurek Mechanism

We experimentally verify the distribution of kink pairs resulting from driving a one-dimensional quantum Ising chain through the paramagnet-ferromagnet quantum phase transition, using a single trapped ion as a quantum simulator in momentum space. The number of kink pairs after the transition follows a Poisson binomial distribution, in which all cumulants scale with a universal power-law as a function of the quench time in which the transition is crossed. We experimentally verified this scaling for the first cumulants and report deviations due to noise-induced dephasing of the trapped ion. Our results establish that the universal character of the critical dynamics can be extended beyond the paradigmatic Kibble-Zurek mechanism, which accounts for the mean kink number, to characterize the full probability distribution of topological defects.   

Quantum Simulations of Superconducting Flux Circuits

One of the main avenues being explored as of late to obtain quantum speedups by annealing is that of quantum simulations, wherein one performs measurements mid-anneal. To that aim, there is a tremendous ongoing effort to fabricate superconducting flux circuits which are non-stoquastic in their qubit representation. Because of this these circuits are thought to be “unsimulatable” by classical approaches such as quantum Monte Carlo; however, we present the results of a study which aims to simulate the circuit Hamiltonian directly by utilizing an infinite Hilbert representation that is, in fact, stoquastic. Our approach obviates the reduction to a qubit representation and produces results that we feel are more in spirit with the experiential setup.