Session J16: Quantum Annealing and Optimization I

Toward integration of Kerr-nonlinear parametric oscillators for adiabatic quantum computation with Lechner-Hauke-Zoller scheme

Adiabatic quantum computation with networks of Kerr-nonlinear parametric oscillators (KPOs) has been proposed, which can solve combinatorial optimization problems (or Ising problems) by using quantum bifurcation [1, 2]. KPO networks integrated in two-dimensional plane can deal with all-to-all connected Ising problems by utilizing Lechner-Hauke-Zoller (LHZ) scheme [3], where KPOs are coupled by local four-body interactions [4, 5]. In the previous studies, however, the number of effective KPOs is limited within three. In this study, we investigate LHZ-scheme KPO networks with larger number of KPOs. Based on numerical simulations, we confirm that the LHZ scheme works for a wide range of the amplitude of the four-body interactions. Besides, we propose a method to improve the LHZ-scheme KPO networks, which is important for the case of larger number of KPOs.
[1] H. Goto, Sci. Rep. 6, 21686 (2016). [2] H. Goto, J. Phys. Soc. Jpn. 88, 061015 (2019). [3] W. Lechner, P. Hauke, and P. Zoller, Sci. Adv. 1, e1500838 (2015). [4] S. Puri et al., Nat. Commun. 8, 15785 (2017). [5] P. Zhao et al., Phys. Rev. Appl. 10, 024019 (2018).   

Long range coupling through a chain of RF-SQUIDs for superconducting flux qubit quantum annealers

Increasing the degree of coupling in a quantum annealer can improve its computational power; however, each physical connection to a superconducting flux qubit increases its area and hence its susceptibility to noise. The coupler tree architecture is a proposed solution which allows increasing coupling degree without increasing qubit area. We report on a subgraph of the coupler tree consisting of 2 capacitively shunted flux qubits connected by 7 RF-SQUIDs. We experimentally demonstrate propagation of a magnetic flux signal through the chain, visible as a frequency step in the persistent current readouts attached to each qubit and coupler. Anticrossing spectroscopy is explored to confirm the quantum character of the coupling. Results are in agreement with full quantum circuit simulations. Prospects for measurement of entanglement and noise are discussed.   

Finding optimized anneal paths in capacitively shunted flux qubits

Quantum annealers require accurate control and optimization of system parameters to reduce noise levels and ultimately demonstrate a computational advantage over classical algorithms.
This requires a careful characterization of the system and its behavior in response to control biases.
In this work we study a capacitively shunted flux qubit (CSFQ), and use spectroscopy and dispersive readout to extract system parameters and model the qubit.
We confirm the multi-level structure of the circuit model of the CSFQ by annealing the qubit through small gaps and observing quantum signatures of level crossing between different eigenenergies.
We then use our model to mitigate the effect of noise by finding optimized anneal paths that minimize the transition width between the flux qubit's left and right wells.   

Quantum annealing with spin lock technique

Quantum annealing (QA) and adiabatic quantum computation (AQC) are attractive ways to tackle combinatorial optimization problems. However, the standard QA and AQC require strong interactions between qubits, and the coupling strength should be comparable with the resonant frequency of the qubits to solve practically useful problems. Such requirement prevents many systems from performing QA and AQC experimentally. Here, we propose an alternative way to implement a spin-lock based QA, which effectively tunes the qubit frequency by a continuous drive. Under the rotating-wave approximation, we show that our method is equivalent to the standard QA and AQC, and moreover we can analyze the deviation of the rotating-wave approximation systematically. Our method can be implemented by many systems such as superconducting transmon qubits, superconducting capacitive shunted flux qubits, and Si quantum-dots-based spin qubits. Since these systems have an advantage in scalability, our results pave the way to implement the practical QA and AQC.   

Assessing the potential of Rydberg atoms for adiabatic quantum computing of an NP-hard problem

When practically confronted with an NP-hard combinatorial optimization problem, the first question many computer scientists ask is whether a good approximation algorithm exists (i.e a tractable algorithm with provable guarantees on solution quality). We argue that the quality and potential of NISQ quantum annealers should therefore be assessed through the approximation ratio that they achieve on specific NP-hard problems. We put this methodology to practice for a platform consisting of neutral atoms trapped in optical arrays [1], which may be used to tackle an NP-hard problem called UD-MIS [2]. We present numerical estimates of the approximation ratio achieved by this approach under realistic noise conditions, on a class of experimentally-implementable random graphs. These results are then compared with the performances achieved by classical PTASs (Polynomial-Time Approximation Schemes) on the same problem.



[1] Barredo, D., De Léséleuc, S., Lienhard, V., Lahaye, T., & Browaeys, A. (2016). Science, 354(6315), 1021-1023.
[2] Pichler, H., Wang, S. T., Zhou, L., Choi, S., & Lukin, M. D. (2018). arXiv preprint arXiv:1808.10816.   

A theoretical analysis of the power of pausing

Recent experimental results have shown that adding a pause during quantum annealing can significantly improve the success probability for certain hard optimization problems. An optimal pausing position, where the maximum performance improvement compared to the unpaused case is achieved, has also been observed. In this work, we present a theoretical analysis that explains these observations. We identify the key features of examples known empirically to benefit from pausing. Using these features as building blocks, we then construct a toy model with a simple analytic structure. Using this model, we derive, in an open quantum system setting, a set of sufficient conditions for which an optimal pausing position exists.   

Quantum computation using Kerr-nonlinear parametric oscillators

In the past few years, the author and others have proposed quantum computation using Kerr-nonlinear parametric oscillators (KPOs). This approach opens new possibilities for adiabatic quantum computation [1-3], universal quantum computation [4,5], and physical implementations of qubits [6]. Since this idea is based on quantum bifurcations of KPOs [1], we refer to this kind of quantum computer as Quantum bifurcation Machine (QbM) [7]. Here we review the QbM with its recent progress.
[1] H. Goto, Sci. Rep. 6, 21686 (2016).
[2] S. E. Nigg, N. Lörch, and R. P. Tiwari, Sci. Adv. 3, e1602273 (2017).
[3] S. Puri, C. K. Andersen, A. L. Grimsmo, and A. Blais, Nat. Commun. 8, 15785 (2017).
[4] H. Goto, Phys. Rev. A 93, 050301(R) (2016).
[5] S. Puri, S. Boutin, and A. Blais, npj Quant. Informa. 3, 18 (2017).
[6] Z. Wang et al., Phys. Rev. X 9, 021049 (2019).
[7] H. Goto, J. Phys. Soc. Jpn. 88, 061015 (2019).   

Effectiveness of quantum annealing pause and partial gauges on embedded degree-bounded minimum spanning tree problems

Robust communication networks are essential to the growing use of small Unmanned Aerial Systems (sUAS) technologies. This work focused on evaluating the potential for harnessing quantum annealing to optimize communication routing in UAS communication networks subject to constraints. To support experimentation on early hardware, we consider as a surrogate problem finding the minimum degree-bounded spanning tree within a communication graph. While finding the minimum spanning tree is computationally tractable, with bounds on the degree the problem becomes NP hard. We provide a mapping of the degree-bounded minimum spanning tree problem to a Quantum Unconstrained Binary Optimization problem, and report on results demonstrating the effectiveness of an annealing pause on these embedded problem instances. Lastly, we demonstrate the effectiveness of partial gauge transformation for situations where asymmetric parameter ranges make standard gauge transformation infeasible.   

Quantum annealing with boundary canceling schedules

The boundary cancellation theorem (BCT) for open systems bounds the distance between the final equilibrium state and the evolved state of an ergodic dissipative Liouvillian, where the scaling with anneal time depends on the number of vanishing derivatives of the annealing schedule at the end of the evolution. We test the thermal scaling of small gadgets up to 8 qubits on the D-Wave quantum annealer by controlling the vanishing derivatives of the schedule during the thermalization phase. While the theoretical BCT bounds are not accessible experimentally, we find that such schedules improve thermal scaling during the anneal and consequentially enhance the ground state probability of the gadgets.   

The Perils of Embedding for Sampling Problems

Current quantum annealers impose constraints on the structure of the cost Hamiltonian due to the connectivity of the qubits. This means that in order to solve many problems of interest, one is required to embed the native graph into the hardware graph. The effect of embedding for sampling is more pronounced than for optimization, since one needs to consider states at all energies, and not just the ground states. We argue that as the problem size grows, the chance of a sample being in the logical subspace is exponentially suppressed. It is therefore necessary to construct post-processing techniques to evade this exponential sampling overhead, to project from the embedded distribution one is physically sampling from, back to the logical space. We observe that the simplest projection technique, majority vote, can fail quite spectacularly at preserving distribution properties. Furthermore, we show that even with care, one cannot avoid biasing the statistics. On the positive side, we demonstrate a new projection technique which substantially out-performs majority vote.   

Reproducing the Performance Enhancement of Adiabatic Reverse Annealing

We propose a conventional (forward) quantum annealing protocol with a diagonal catalyst of programmable strength λ. By adjusting λ we demonstrate an exponential improvement in the efficiency of quantum annealing for solving the p-spin model, reproducing the performance improvements of adiabatic reverse annealing¹. Our protocol allows us to identify the enhancement mechanism of such approaches: balancing Hamiltonian terms in a way that mitigates discontinuous shifts in the global minimum of the semiclassical potential. This observation allows us to identify and solve other problems amenable to such protocols.

1. Masaki Ohkuwa, Hidetoshi Nishimori, and Daniel A. Lidar, “Reverse annealing for the fully connected p-spin model,” Phys. Rev. A 98, 022314 (2018) (https://arxiv.org/abs/1806.02542).   

Reverse quantum annealing with dissipation

Reverse annealing is a variant of quantum annealing where one initializes the system in a random classical state. The transverse field is first increased and then decreased at an inversion point, to find a better output state than the initial state of a given optimization problem. The procedure may be iterated with the last output state as the new input state.

[1] studied the unitary dynamics of reverse annealing of the fully-connected ferromagnetic p-spin model. Here we investigate the performance of reverse annealing for the p-spin model in a low-temperature open system setting. We study a system of qubits with collective and individual system-bath interaction models. We simulate the Markovian dynamics over a range of initial states and inversion points, and show that the relaxation mechanism gives an overall enhancement of performance over the closed-system setting. We also analyze the case of pausing at the inversion point, and show that prolonged relaxation near the avoided crossing can allow us to find the correct ground state solution with near certainty.

[1] Y. Yamashiro, M. Ohkuwa, H. Nishimori, D.A. Lidar, arXiv:1906.10889 (Phys. Rev. A, in press).   

Quantum annealing in a degenerate two-level system

Quantum annealing is a method for avoiding the increase of the calculation cost of the combinatorial optimization problem. Since the combinatorial optimization problems are ubiquitous, quantum annealing machine with high efficiency and scalability will give an immeasurable impact on many fields. An idea for finding high success probability is one of the most important issues for quantum annealing. In this presentation, we show that a degenerate two-level system that is called quantum Wajnflasz-Pick model may provide the higher success probability than the conventional spin-1/2 model in a weak longitudinal magnetic field region. The origin of the higher success probability can be understood from the fact that the Hamiltonian in this model can be reduced into that of the spin-1/2 model. In the reduced Hamiltonian, the effective longitudinal magnetic field may open the energy gap, which suppresses the Landau–Zener tunneling providing leakage of the ground state.