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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Input Data Format for Sparse Matrix in Quantum Annealing Emulator

Sohei Shimomai, Kei Ueda, Shinji Kimura

Published Sep 24, 2023• 2 citations
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 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.

DOI
10.1587/transfun.2023vlp0002

Related papers

Compressed Input Data Format of 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 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.

DCC•Mar 1, 2023•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

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

An edge-based and subspace reduction encoding scheme to solve the traveling salesman problem in quantum computers

Anandu Kalleri Madhu, Chi-Kwong Li, Jami Rönkkö +2 more

This paper introduces a novel edge-based encoding technique for solving the Traveling Salesman Problem (TSP) on a quantum computer, reducing the required number of qubits. For implementation in real quantum devices, we applied the subspace reduction encoding to further reduce the dimension of the TSP solution space. We attack the TSP for 4-, 5-, and 6-city instances in both simulators and real quantum computers across different encoding frameworks. Optimal solutions of the 4-city TSP instance are obtained on state-of-the art IQM quantum computer. Our study presents a comparative analysis between edge-based encoding scheme and the node-based encoding methodology in the literature. Our findings indicate that the proposed encoding scheme outperforms conventional methods in terms of statistical measures, quantum resource utilization, and computational efficiency when applied to smaller TSP instances.

quant-pharXiv:2512.17291•Dec 22, 2025•0 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 Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem

Yuefeng Lin, Chao Zheng, Cong Guo

The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.

quant-pharXiv:2605.00739•May 4, 2026•0 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 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.
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.
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.
This paper introduces a novel edge-based encoding technique for solving the Traveling Salesman Problem (TSP) on a quantum computer, reducing the required number of qubits. For implementation in real quantum devices, we applied the subspace reduction encoding to further reduce the dimension of the TSP solution space. We attack the TSP for 4-, 5-, and 6-city instances in both simulators and real quantum computers across different encoding frameworks. Optimal solutions of the 4-city TSP instance are obtained on state-of-the art IQM quantum computer. Our study presents a comparative analysis between edge-based encoding scheme and the node-based encoding methodology in the literature. Our findings indicate that the proposed encoding scheme outperforms conventional methods in terms of statistical measures, quantum resource utilization, and computational efficiency when applied to smaller TSP instances.
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.
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.