Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 1/2022

18-05-2021

Design space exploration for an FPGA-based quantum annealing simulator with interaction-coefficient-generators

Authors: Chia-Yin Liu, Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Published in: The Journal of Supercomputing | Issue 1/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Quantum annealing simulation attracts much attention recently for solving combinatorial optimization problems. FPGA acceleration is a promising way to reduce the huge processing time in quantum annealing simulations. However, the performance of FPGA accelerators is often restricted by the small external memory bandwidth. To solve this problem, we propose a data-transfer-bottleneck-less FPGA-based accelerator for quantum annealing simulation. The proposed architecture is implemented on an FPGA and achieved up to 179 times speed-up compared to single-core CPU implementation. The proposed accelerator is two times faster compared to previous FPGA accelerators, and process up to 262,144 spins, which is not possible in any existing FPGA accelerators due to limited external memory capacity.
next article Load balancing in cloud computing environment using the Grey wolf optimization algorithm based on the reliability: performance evaluation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Lawler Eugene L (1985) The travelling salesman problem: a guided tour of combinatorial optimization. Wiley, New York
2.
Neukart Florian, Compostella Gabriele, Seidel Christian, von Dollen David, Yarkoni Sheir, Parney Bob (2017) Traffic flow optimization using a quantum annealer. Frontiers in ICT 4:29–29CrossRef
3.
Orus Roman, Mugel Samuel, Lizaso Enrique (2019) Quantum computing for finance: Overview and prospects. Rev Phys 4:100028CrossRef
4.
Elsokkary N, Khan FS, La Torre D, Humble TS, Gottlieb J (2017) Financial portfolio management using d-wave quantum optimizer: The case of abu dhabi securities exchange. Technical report, Oak Ridge National Lab.(ORNL), Oak Ridge, TN (United States),
5.
Titiloye Olawale, Crispin Alan (2011) Quantum annealing of the graph coloring problem. Discret Optim 8(2):376–384MathSciNetCrossRef
6.
Ushijima H, Negre CFA, Mniszewski SM (2017) Graph partitioning using quantum annealing on the d-wave system. In: Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pp 22–29
7.
Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58:5355–5363CrossRef
8.
Tadashi K (June 1998) Study of optimization problems by quantum annealing. PhD thesis, Department of Physics, Tokyo Institute of Technology
9.
10.
11.
Zaribafiyan Arman, Marchand Dominic J, Rezaei Seyed Saeed Changiz (2017) Systematic and deterministic graph minor embedding for cartesian products of graphs. Q Inf Process 16(5):1–26MathSciNetMATH
12.
Suzuki M, Miyashita S, Kuroda A (1977) Monte carlo simulation of quantum spin systems i. Prog Theor Phys 58(5):1377–1387MathSciNetCrossRef
13.
Crosson E, Harrow AW (Oct 2016) Simulated quantum annealing can be exponentially faster than classical simulated annealing. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp 714–723
14.
15.
Liu C, Waidyasooriya HM, Hariyama M (2019) Data-transfer-bottleneck-less architecture for fpga-based quantum annealing simulation. In: 2019 Seventh International Symposium on Computing and Networking (CANDAR), pp 164–170
16.
Suzuki M (1976) Relationship between d-dimensional quantal spin systems and (d+1)-dimensional ising systems: Equivalence, critical exponents and systematic approximants of the partition function and spin correlations. Prog Theor Phys 56(5):1454–1469CrossRef
17.
Stinchcombe R B (1973) Ising model in a transverse field. i. basic theory. J Phys C: Solid State Phys 6(15):2459–2483CrossRef
18.
19.
Yamaoka M, Yoshimura C, Hayashi M, Okuyama T, Aoki H, Mizuno H (2016) A 20k-spin ising chip to solve combinatorial optimization problems with cmos annealing. IEEE J Solid-State Circuits 51(1):303–309CrossRef
20.
Weigel M (2012) Performance potential for simulating spin models on gpu. J Comput Phys 231(8):3064–3082CrossRef
21.
Cook C, Zhao H, Sato T, Hiromoto M, Tan SX-D (2018) Gpu based parallel ising computing for combinatorial optimization problems in vlsi physical design. arXiv preprint arXiv:​1807.​10750,
22.
Waidyasooriya HM, Hariyama M (2020) A gpu-based quantum annealing simulator for fully-connected ising models utilizing spatial and temporal parallelism. IEEE Access 8:67929–67939CrossRef
23.
Okuyama T, Hayashi M, Yamaoka M (2017) An ising computer based on simulated quantum annealing by path integral monte carlo method. In: 2017 IEEE International Conference on Rebooting Computing (ICRC), pp 1–6
24.
Okuyama T, Hayashi M, Yamaoka M (Nov 2017) An ising computer based on simulated quantum annealing by path integral monte carlo method. In: 2017 IEEE International Conference on Rebooting Computing (ICRC), pp 1–6
25.
Waidyasooriya HM, Araki Y, Hariyama M (2018) Accelerator architecture for simulated quantum annealing based on resource-utilization-aware scheduling and its implementation using opencl. In: 2018 International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS), pp 335–340
26.
Waidyasooriya HM, Hariyama M, Miyama MJ, Ohzeki M (2019) OpenCL-based design of an FPGA accelerator for quantum annealing simulation. J Supercomput 75(8):5019–5039CrossRef
27.
28.
29.
Metadata
Title
Design space exploration for an FPGA-based quantum annealing simulator with interaction-coefficient-generators
Authors
Chia-Yin Liu
Hasitha Muthumala Waidyasooriya
Masanori Hariyama
Publication date
18-05-2021
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 1/2022
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-021-03859-5

Other articles of this Issue 1/2022

The Journal of Supercomputing 1/2022 Go to the issue

OriginalPaper

Analysing software prefetching opportunities in hardware transactional memory

OriginalPaper

Efficient XML data placement schemes over multiple mobile wireless broadcast channels

OriginalPaper

Adaptive market-oriented combinatorial double auction resource allocation model in cloud computing

OriginalPaper

Field equations for incompressible non-viscous fluids using artificial intelligence

OriginalPaper

Maximum Network Lifetime Problem with Time Slots and coverage constraints: heuristic approaches

OriginalPaper

Amended hybrid multi-verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing

Premium Partner

    Image Credits