Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

DCC

Compressed Input Data Format of Quantum Annealing Emulator

Sohei Shimomai, Kei Ueda, Shinji Kimura

Published Mar 1, 2023• 1 citation
Publisher

Abstract

Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for the hardware emulation since its usable memory size and its bandwidth are limited. As an improved Coordinate (COO) format for a sparse matrix, Compressed Sparse Row (CSR) has been proposed [1]. We have checked CSR on an Ising model but found that the compression efficiency is not high.

DOI
10.1109/dcc55655.2023.00088

Related papers

Input Data Format for Sparse Matrix in Quantum Annealing Emulator

Sohei Shimomai, Kei Ueda, Shinji Kimura

Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for accelerating by the hardware emulation since the usable memory size and its bandwidth are limited. The paper proposes the compression method of input sparse matrices for QA emulator. The proposed method uses the sparseness of the coefficient matrix and the reappearance of the same values. An independent table is introduced and data are compressed by the search and registration method of two consecutive data in the value table. The proposed method is applied to Traveling Salesman Problem (TSP) with 32, 64 and 96 cities and Nurse Scheduling Problem (NSP). The proposed method could reduce the amount of data by 1/40 for 96 city TSP and could manage 96 city TSP on the hardware emulator. When applied to NSP, we confirmed the effectiveness of the proposed method by the compression ratio ranging from 1/4 to 1/11.8. The data reduction is also useful for the simulation/emulation performance when using the compressed data directly and 1.9 times faster speed can be found on 96 city TSP than the CSR-based method.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Sep 24, 2023•2 citations

FPGA-Based Prototype of a Quantum Annealing Simulator for Sparse Ising Model

Hasitha Muthumala Waidyasooriya, Yuta Ohma, Masanori Hariyama

Quantum annealing (QA) is a probabilistic approx-imation method to find the global optimum of a combinatorial optimization problem. QA is done on quantum annealers such as D-wave using quantum properties. Since the number of qubits in quantum annealers is limited, it is difficult to use those to solve large-scale real-world problems. Therefore, quantum annealing simulation on digital computers is necessary. In this paper, we discuss an FPGA based quantum annealing simulator for sparse Ising model. Unlike a fully-connected Ising model, the number of connections among spins in sparse model is limited. Highly sparse Ising models require significantly low amount of computations while allowing more parallel operations. One the other hand, sparsity and the connections among spins are not the same for different Ising models, and it is difficult to propose one specific accelerator architecture for all. We propose a method to automatically generate an application specific accelerator archi-tecture for a given sparse Ising model. The proposed accelerator fully exploits the parallelism to increase the processing speed. We design an FPGA prototype of the proposed accelerator and confirmed the correct behavior. In future, we expect to extend the proposed method to execute large quantum annealing simulations using multiple FPGAs.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 1, 2022•1 citation

A Compressed QUBO Format for Traveling Salesperson Problems

Chu-Yuan Huang, Kazuhiko Komatsu, Makoto Onoda +3 more

Ising machines have recently gained a significant attention as a promising approach to combinatorial optimization problems, which are notoriously challenging for conventional computers to solve efficiently. In contrast to conventional computers, Ising machines operate based on the principles of the Ising model derived from statistical mechanics. Ising machines tackle combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Traveling Salesperson Problem (TSP) is a prominent example of such optimization challenges and is widely recognized for its computational difficulty on conventional computers. Although Ising machines offer the potential for efficiently solving TSPs, the process of a QUBO formulation, namely the generation of a QUBO matrix that represents a TSP, demands substantial memory resources and considerable computation overheads. This study proposes a compressed QUBO format for TSP. This format reduces the dimensionality of the QUBO matrix for TSP by leveraging repetitive values, structural patterns, and sparsity within the matrix. The proposed format enhances the efficiency of data preprocessing, significantly reducing both the computational time required for QUBO matrix generation and the associated memory usage. These improvements contribute to the practical applicability of digital hardware-based Ising machines for addressing large-scale combinatorial optimization problems, thereby expanding their utility in solving complex real-world challenges.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•1 citation

Quantum optimization with linear Ising penalty functions for customer data science

Puya Mirkarimi, Ishaan Shukla, David C. Hoyle +2 more

Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024

arXiv:2404.05467•Physical Review Research•Dec 5, 2024•7 citations

Discrete optimization using quantum annealing on sparse Ising models

Zhengbing Bian, Fabián A. Chudak, Robert B. Israel +3 more

This paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.

Frontiers in Physics•Sep 18, 2014•129 citations

Data-Transfer-Bottleneck-Less Architecture for FPGA-Based Quantum Annealing Simulation

Chia-Yin Liu, Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Quantum Annealing (QA) is a classical probabilistic algorithm that provides a heuristic to find the globally optimal solution for a combinatorial optimization problem by using quantum tunneling processes. Quantum annealing simulation can be implemented on Field Programmable Gate Arrays (FPGAs) using Quantum Monte Carlo (QMC) simulation in the transverse Ising model. Since input data of the QMC simulation increases exponentially with the problem size, we have to use the DRAM of an FPGA board to store these data. However, storing data in DRAM causes two problems. One is the limited data access bandwidth, and the other is the limitation of DRAM capacity. We propose a data-transfer-bottleneck-less FPGA-based accelerator for quantum annealing simulation and apply it to implement number partitioning problem, which is one of the combinatorial optimization problems. The critical idea of our architecture is not storing but computing the large data in FPGA kernels and eliminating the burden on data transfer. We implement the proposed architecture on Stratix 10 FPGA and achieve up to 39.6 times speed-up compared to CPU-based quantum annealing simulation. We also achieve up to 2.8 times speed-up and implement 262,144 spins, which is 64 times increase compared to the most recent FPGA implementation.

International Symposium on Computing and Networking•Nov 1, 2019•10 citations
Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for the hardware emulation since its usable memory size and its bandwidth are limited. As an improved Coordinate (COO) format for a sparse matrix, Compressed Sparse Row (CSR) has been proposed [1]. We have checked CSR on an Ising model but found that the compression efficiency is not high.
Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for accelerating by the hardware emulation since the usable memory size and its bandwidth are limited. The paper proposes the compression method of input sparse matrices for QA emulator. The proposed method uses the sparseness of the coefficient matrix and the reappearance of the same values. An independent table is introduced and data are compressed by the search and registration method of two consecutive data in the value table. The proposed method is applied to Traveling Salesman Problem (TSP) with 32, 64 and 96 cities and Nurse Scheduling Problem (NSP). The proposed method could reduce the amount of data by 1/40 for 96 city TSP and could manage 96 city TSP on the hardware emulator. When applied to NSP, we confirmed the effectiveness of the proposed method by the compression ratio ranging from 1/4 to 1/11.8. The data reduction is also useful for the simulation/emulation performance when using the compressed data directly and 1.9 times faster speed can be found on 96 city TSP than the CSR-based method.
Quantum annealing (QA) is a probabilistic approx-imation method to find the global optimum of a combinatorial optimization problem. QA is done on quantum annealers such as D-wave using quantum properties. Since the number of qubits in quantum annealers is limited, it is difficult to use those to solve large-scale real-world problems. Therefore, quantum annealing simulation on digital computers is necessary. In this paper, we discuss an FPGA based quantum annealing simulator for sparse Ising model. Unlike a fully-connected Ising model, the number of connections among spins in sparse model is limited. Highly sparse Ising models require significantly low amount of computations while allowing more parallel operations. One the other hand, sparsity and the connections among spins are not the same for different Ising models, and it is difficult to propose one specific accelerator architecture for all. We propose a method to automatically generate an application specific accelerator archi-tecture for a given sparse Ising model. The proposed accelerator fully exploits the parallelism to increase the processing speed. We design an FPGA prototype of the proposed accelerator and confirmed the correct behavior. In future, we expect to extend the proposed method to execute large quantum annealing simulations using multiple FPGAs.
Ising machines have recently gained a significant attention as a promising approach to combinatorial optimization problems, which are notoriously challenging for conventional computers to solve efficiently. In contrast to conventional computers, Ising machines operate based on the principles of the Ising model derived from statistical mechanics. Ising machines tackle combinatorial optimization problems by transforming them into Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Traveling Salesperson Problem (TSP) is a prominent example of such optimization challenges and is widely recognized for its computational difficulty on conventional computers. Although Ising machines offer the potential for efficiently solving TSPs, the process of a QUBO formulation, namely the generation of a QUBO matrix that represents a TSP, demands substantial memory resources and considerable computation overheads. This study proposes a compressed QUBO format for TSP. This format reduces the dimensionality of the QUBO matrix for TSP by leveraging repetitive values, structural patterns, and sparsity within the matrix. The proposed format enhances the efficiency of data preprocessing, significantly reducing both the computational time required for QUBO matrix generation and the associated memory usage. These improvements contribute to the practical applicability of digital hardware-based Ising machines for addressing large-scale combinatorial optimization problems, thereby expanding their utility in solving complex real-world challenges.
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024
This paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.
Quantum Annealing (QA) is a classical probabilistic algorithm that provides a heuristic to find the globally optimal solution for a combinatorial optimization problem by using quantum tunneling processes. Quantum annealing simulation can be implemented on Field Programmable Gate Arrays (FPGAs) using Quantum Monte Carlo (QMC) simulation in the transverse Ising model. Since input data of the QMC simulation increases exponentially with the problem size, we have to use the DRAM of an FPGA board to store these data. However, storing data in DRAM causes two problems. One is the limited data access bandwidth, and the other is the limitation of DRAM capacity. We propose a data-transfer-bottleneck-less FPGA-based accelerator for quantum annealing simulation and apply it to implement number partitioning problem, which is one of the combinatorial optimization problems. The critical idea of our architecture is not storing but computing the large data in FPGA kernels and eliminating the burden on data transfer. We implement the proposed architecture on Stratix 10 FPGA and achieve up to 39.6 times speed-up compared to CPU-based quantum annealing simulation. We also achieve up to 2.8 times speed-up and implement 262,144 spins, which is 64 times increase compared to the most recent FPGA implementation.