skip to main content

Title: Constrained percolation, Ising model, and XOR Ising model on planar lattices
Publication Date:
Journal Name:
Random Structures & Algorithms
Page Range or eLocation-ID:
p. 474-525
Wiley Blackwell (John Wiley & Sons)
Sponsoring Org:
National Science Foundation
More Like this
  1. The Ising model has been explored as a framework for modeling NP-hard problems, with several diverse systems proposed to solve it. The Magnetic Tunnel Junction– (MTJ) based Magnetic RAM is capable of replacing CMOS in memory chips. In this article, we propose the use of MTJs for representing the units of an Ising model and leveraging its intrinsic physics for finding the ground state of the system through annealing. We design the structure of a basic MTJ-based Ising cell capable of performing the functions essential to an Ising solver. The hardware overhead of the Ising model is analyzed, and a technique to use the basic Ising cell for scaling to large problems is described. We then go on to propose Ising-FPGA, a parallel and reconfigurable architecture that can be used to map a large class of NP-hard problems, and show how a standard Place and Route tool can be utilized to program the Ising-FPGA. The effects of this hardware platform on our proposed design are characterized and methods to overcome these effects are prescribed. We discuss how three representative NP-hard problems can be mapped to the Ising model. Further, we suggest ways to simplify these problems to reduce the usemore »of hardware and analyze the impact of these simplifications on the quality of solutions. Simulation results show the effectiveness of MTJs as Ising units by producing solutions close/comparable to the optimum and demonstrate that our design methodology holds the capability to account for the effects of the hardware.« less
  2. Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.