Query: an ising computer

Candidate papers:

abstract: In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real world applications. In this paper, we present our FPGA based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48 by 48 king graph with 8 bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9% solution with a probability of 99% than SA running on a state of the art CPU.
author_names: Takuya Okuyama

Masato Hayashi

Masanao Yamaoka
title: An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method
venue: 2017 IEEE International Conference on Rebooting Computing (ICRC)
year: 2017

abstract: Masanao Yamaoka, Ph.D. Chihiro Yoshimura Masato Hayashi Takuya Okuyama Hidetaka Aoki Hiroyuki Mizuno, Ph.D. OVERVIEW: A major challenge facing AI is the enormous computational load it imposes, of which combinational optimization makes up a large part. Hitachi has devised a computing technology based on a new paradigm that is capable of solving combinatorial optimization problems efficiently using an Ising model, and has built a prototype 20k spin Ising computer chip using a 65 nm process. An Ising chip represents a combinatorial optimization problem by mapping it onto an Ising model based on the spin of magnetic materials, and solves the problem by taking advantage of the system's natural tendency to converge. This convergence is implemented using a CMOS circuit. In addition to demonstrating its ability to solve combinatorial optimization problems and operate at 100 MHz, the prototype chip has been demonstrated to consume approximately 1,800 times less power to obtain the solution than would be required by a conventional computer with a von Neumann architecture.
author_names: Masanao Yamaoka

D Ph

Chihiro Yoshimura

Masato Hayashi

Takuya Okuyama

Hidetaka Aoki

Hiroyuki Mizuno
title: Advanced Research into AI Ising Computer
year: 2016

abstract: Masanao Yamaoka, Ph.D. Chihiro Yoshimura Masato Hayashi Takuya Okuyama Hidetaka Aoki Hiroyuki Mizuno, Ph.D. OVERVIEW: The optimization of social infrastructure systems will be among the requirements of Hitachi's Social Innovation Business in the future, therefore, there will be a need to solve combinatorial optimization problems. Hitachi has devised a computing technology based on a new paradigm that is capable of solving combinatorial optimization problems efficiently using an Ising model, and has built a prototype 20,000 spin Ising chip using a 65 nm process. An Ising chip represents a combinatorial optimization problem by mapping it onto an Ising model based on the spin of magnetic materials, and solves the problem by taking advantage of the system's natural tendency to converge. This convergence is implemented using a CMOS circuit. In addition to demonstrating its ability to solve combinatorial optimization problems and operate at 100 MHz, the prototype chip consumes approximately 1,800 times less power to obtain the solution than required by a conventional Neumann architecture computer.
author_names: Masanao Yamaoka

D Ph

Chihiro Yoshimura

Masato Hayashi

Takuya Okuyama

Hidetaka Aoki

Hiroyuki Mizuno
title: New Computing Paradigm for Analyzing Increasingly Complex Social Infrastructure Systems Ising Computer
year: 2015

abstract: We present an exact simulation of a one dimensional transverse Ising spin chain with a quantum computer. We construct an efficient quantum circuit that diagonalizes the Ising Hamiltonian and allows to obtain all eigenstates of the model by just preparing the computational basis states. With an explicit example of that circuit for $n=4$ spins, we compute the expected value of the ground state magnetization, the time evolution simulation and provide a method to also simulate thermal evolution. All circuits are run in IBM and Rigetti quantum devices to test and compare them qualitatively.
author_names: Alba Cervera-Lierta
title: Exact Ising model simulation on a quantum computer
year: 2018

abstract: Ising machines have attracted attention, which is expected to obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot placement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logic block placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slot placement problem with additional constraints, called a constrained slot placement problem, where several item pairs must be placed within a given distance. Since the behavior of Ising machines is stochastic, the obtained solution does not always satisfy the slot placement constraint, which is different from the conventional methods such as the conventional simulated annealing. To resolve the problem, we propose an interpretation method in which a feasible solution is generated by post processing procedures. Using an Ising machine computer, feasible solutions could be obtained up to 50 times faster than the conventional simulated annealing without degrading accuracy for constrained slot placement problems with 6 x 6 slots and 27 items at the maximum.
author_names: Sho Kanamaru

Kazushi Kawamura

Shu Tanaka

Yoshinori Tomita

Hidetoshi Matsuoka

Kaoru Kawamura

Nozomu Togawa
title: Mapping Constrained Slot Placement Problems to Ising Models and its Evaluations by an Ising Machine
venue: 2019 IEEE 9th International Conference on Consumer Electronics (ICCE Berlin)
year: 2019

abstract: Floorplanning of modules has been a significant role in VLSI design automation and it can be formulated as the "Rectangle Packing Problem." Ising model based computers (or annealing machines) are the type of a non von Neumann computer and recently expected to solve combinatorial optimization problems efficiently. In this paper, we propose a mapping of "Rectangle Packing Problem" for solving it by the annealing machines. In our proposed mapping, a sequence pair is represented on an Ising model. Our proposed approach maps a "Rectangle Packing Problem" with N rectangles onto a 3N3 spin logical Ising model. Experimental results demonstrate that through the proposed approach we can solve the problem with 18 rectangles at the maximum on a fully connected annealing machine and the problem with three rectangles at the maximum on 20k spin CMOS annealing machine.
author_names: Kotaro Terada

Daisuke Oku

Sho Kanamaru

Shu Tanaka

Masato Hayashi

Masanao Yamaoka

Masao Yanagisawa

Nozomu Togawa
title: An Ising model mapping to solve rectangle packing problem
venue: 2018 International Symposium on VLSI Design, Automation and Test (VLSI DAT)
year: 2018

abstract: We consider Grover's search algorithm on a model quantum computer implemented on a chain of four or five nuclear spins with first and second neighbour Ising interactions. Noise is introduced into the system in terms of random fluctuations of the external fields. By averaging over many repetitions of the algorithm, the output state becomes effectively a mixed state. We study its overlap with the nominal output state of the algorithm, which is called the fidelity. We analyse the behaviour of the fidelity as a function of the noise intensity for static and random noise on either the Larmor frequencies or the Rabi frequency, and we compare our results to theoretical predictions and numerical simulations which are based on more abstract quantum computer models.
author_names: Thomas Gorin

Lorena Lara

Gustavo V Lopez
title: Simulation of static and random errors on Grover's search algorithm implemented in an Ising nuclear spin chain quantum computer with a few qubits
year: 2010

abstract: An Ising computing that is specialized to solve combinatorial optimization problems is proposed. The computing maps problems to an Ising model and solves the optimization problems by its own convergence property. We proposed a CMOS implementation of Ising computing and fabricated two prototypes of the computer. The 1st generation prototype confirmed the power efficiency is 1800 times higher than that of the conventional vonNeumann computers. The 2nd generation prototype is organized by FPGA, and used to explore its applications.
author_names: Masanao Yamaoka
title: An ising computing to solve combinatorial optimization problems
venue: 2017 Fifth Berkeley Symposium on Energy Efficient Electronic Systems Steep Transistors Workshop (E3S)
year: 2017

abstract: Given samples from an unknown multivariate distribution <inline formula> <tex math notation="LaTeX"$p$ /tex math>/inline formula> is it possible to distinguish whether <inline formula> <tex math notation="LaTeX"$p$ /tex math>/inline formula> is the product of its marginals versus <inline formula> <tex math notation="LaTeX"$p$ /tex math>/inline formula> being far from every product distribution? Similarly, is it possible to distinguish whether <inline formula> <tex math notation="LaTeX"$p$ /tex math>/inline formula> equals a given distribution <inline formula> <tex math notation="LaTeX"$q$ /tex math>/inline formula> versus <inline formula> <tex math notation="LaTeX"$p$ /tex math>/inline formula> and <inline formula> <tex math notation="LaTeX"$q$ /tex math>/inline formula> being far from each other? These problems of testing independence and goodness of fit have received enormous attention in statistics, information theory, and theoretical computer science, with sample optimal algorithms known in several interesting regimes of parameters. Unfortunately, it has also been understood that these problems become intractable in large dimensions, necessitating exponential sample complexity. Motivated by the exponential lower bounds for general distributions as well as the ubiquity of Markov random fields (MRFs) in the modeling of high dimensional distributions, we initiate the study of distribution testing on <italic>structured</italic> multivariate distributions, and in particular, the prototypical example of MRFs: <italic>the Ising Model</italic> We demonstrate that, in this structured setting, we can avoid the curse of dimensionality, obtaining sample, and time efficient testers for independence and goodness of fit. One of the key technical challenges we face along the way is bounding the variance of functions of the Ising model.
author_names: Constantinos Daskalakis

Nishanth Dikkala

Gautam Kamath
title: Testing Ising Models
venue: IEEE Transactions on Information Theory
year: 2019

abstract: We implement Grover's quantum search algorithm on a nuclear spin chain quantum computer, taking Ising type interactions between nearest and second nearest neighbours into account. The performance of this implementation is studied by numerical simulations with four spins. We determine the temporal behaviour of the fidelity during the algorithm, and we compute the final fidelity as a function of the Rabi frequency. For the latter, we obtain pronounced maxima at frequencies which fulfil the condition of the 2pk method with respect to the second nearestneighbour interactions. (Some figures in this article are in colour only in the electronic version)
author_names: Gustavo V Lopez

Thomas Gorin

Lorena Lara
title: Simulation of Grover's quantum search algorithm in an Ising nuclear spin chain quantum computer with first and second nearest neighbour couplings
year: 2008