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

ACM Symposium on Applied Computing

Scalable quantum simulation by reductions and decompositions through the Id-operator

Anderson Ávila, Renata Reiser, Adenauer Yamin, Mauricio Lima Pilla

Published Apr 4, 2016• 6 citations
Publisher

Abstract

One of the main obstacles for the adoption of quantum algorithm simulation is the exponential increase in temporal and spatial complexities, due to the expansion of transformations and read/write memory states by using tensor product in multi-dimension applications. Reduction and decomposition optimizations via the Id-operator provide a smart and appropriate storage and distribution of quantum information. Reductions are achieved by avoiding replication and sparsity inherited from such operators. By using decompositions, applications may be divided into sub-steps to store only distinct values from Id-operators, instead of executing quantum transformations in a single step. Additional optimizations based on mixed partial processes provide control over increase in read/write memory states in quantum transformations, also contributing to increase the scalability regarding hardware-GPUs memory limit. Hadamard and Discret Quantum Fourier Transforms were simulated up to 28 qubits applications over a single GPU with drastic temporal complexity reduction and simulation time.

DOI
10.1145/2851613.2851936

Related papers

Optimizing D-GM quantum computing by exploring parallel and distributed quantum simulations under GPUs arquitecture

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla +1 more

The exponential increase in the temporal and spatial complexities is one of the main challenges in the widespread use of quantum algorithm simulation, especially in dense quantum transformations (QTs) such as the Hadamard transformation (H), which has found wide applications in computer and communication science and also comprising the simplest quantum universal set of QTs. The main reason for these costs is the expansion of QTs by using tensor product in multi-dimension quantum applications. In this work, new optimizations for the execution of reduction and decomposition based on the Identity operator are introduced in the Distributed Geometric Machine framework (D-GM). Instead of executing the quantum transformation in a single step, they are divided in sub-quantum transformations and only the values different from Identity transformations are stored. Mixed Partial Processes provide control over the increase in the size of read/write memory states in the calculation of a QT, thus contributing to increase the scalability of applications regarding hardware-GPUs memory limit. In the evaluation of this D-GM extension, Hadamard Transformations were simulated up to 28 qubits applications over a single GPU. Our new simulator is 10, 829χ faster and allows for the simulation of more qubits when compared to our previous implementation running on the same GPU.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2016•10 citations

Reduction and Decomposition Optimizations in Quantum Computing Simulation Applied to the Shor’s Algorithm

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla

Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Apr 14, 2017•0 citations

Quantum computing simulation through reduction and decomposition optimizations with a case study of Shor's algorithm

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla

Summary Because of the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is very relevant to develop and test new quantum algorithms. In order to overcome the increase in simulation complexity, this work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are reached by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Hadamard transformations from 21 to 28 qubits and Quantum Fourier Transforms from 26 to 28 qubits were simulated over CPU, sequentially and in parallel, and in graphics processing unit, showing reduced temporal complexity and, consequently, shorter simulation time. Moreover, evaluations of the Shor's algorithm considering 2n + 3 qubits in the order‐finding quantum algorithm were simulated up to 25 qubits. When comparing our implementations running on the same hardware with language‐integrated quantum operation, academic release version, our new simulator was faster and allowed for the simulation of more qubits. Copyright © 2016 John Wiley & Sons, Ltd.

Concurrency and Computation Practice and Experience•Nov 10, 2016•6 citations

Parallel simulation of Shor's and Grover's algorithms in the distributed geometric machine

Anderson Ávila, Renata Reiser, Adenauer Yamin +1 more

The exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial complexity and memory access patterns are major performance hazards. A new methodology employs reduction and decomposition optimizations, exploring properties such as the sparsity of the Id-Operator and the partiality of dense unitary transformations to improve storage and distribution of quantum states. In this work, Shor's and Grover's algorithms are simulated in both CPU and GPU in the Distributed Geometric Machine environment. Additionally, they are compared to LIQUi|〉's results. In all cases, our simulation was faster and allowed for an improved number of qubits when compared to the academic release version of LIQUi|〉, with relative speedups up to 118×.

International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)•Jul 1, 2017•7 citations

Optimizing Quantum Simulation for Heterogeneous Computing: a Hadamard Transformation Study

Anderson Ávila, Murilo Schumalfuss, Renata Reiser +2 more

The D-GM execution environment improves distributed simulation of quantum algorithms in heterogeneous computing environments comprising both multi-core CPUs and GPUs. The main contribution of this work consists in the optimization of the environment VirD-GM, conceived in three steps: ( i ) the theoretical studies and implementation of the abstractions of the Mixed Partial Process defined in the qGM model, focusing on the reduction of the memory consumption regarding multidimensional QTs; ( ii ) the distributed/parallel implementation of such abstractions allowing its execution on clusters of GPUs; ( iii ) and optimizations that predict multiplications by zero-value of the quantum states/transformations, implying reduction in the number of computations. The results obtained in this work embrace the distribute/parallel simulation of Hadamard gates up to 21 qubits, showing scalability with the increase in the number of computing nodes.

Journal of Physics Conference Series•Oct 19, 2015•7 citations

Efficient In-Situ Quantum Computing Simulation of Shor's and Grover's Algorithms

Anderson Ávila, Renata Reiser, Adenauer Yamin +1 more

Exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this an important application for HPC. A new methodology employing reduction and decomposition optimizations has shown great results, but its GPU implementation could be further improved. In this work, we intend to do a new implementation for in-situ GPU simulation that better explores its resources without requiring further HPC hardware. Shors and Grovers algorithms are simulated and compared to the previous version and to LIQUi|s simulator, showing better results with relative speedups up to 15.5× and 765.76× respectively.

International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW)•Oct 1, 2017•4 citations
One of the main obstacles for the adoption of quantum algorithm simulation is the exponential increase in temporal and spatial complexities, due to the expansion of transformations and read/write memory states by using tensor product in multi-dimension applications. Reduction and decomposition optimizations via the Id-operator provide a smart and appropriate storage and distribution of quantum information. Reductions are achieved by avoiding replication and sparsity inherited from such operators. By using decompositions, applications may be divided into sub-steps to store only distinct values from Id-operators, instead of executing quantum transformations in a single step. Additional optimizations based on mixed partial processes provide control over increase in read/write memory states in quantum transformations, also contributing to increase the scalability regarding hardware-GPUs memory limit. Hadamard and Discret Quantum Fourier Transforms were simulated up to 28 qubits applications over a single GPU with drastic temporal complexity reduction and simulation time.
The exponential increase in the temporal and spatial complexities is one of the main challenges in the widespread use of quantum algorithm simulation, especially in dense quantum transformations (QTs) such as the Hadamard transformation (H), which has found wide applications in computer and communication science and also comprising the simplest quantum universal set of QTs. The main reason for these costs is the expansion of QTs by using tensor product in multi-dimension quantum applications. In this work, new optimizations for the execution of reduction and decomposition based on the Identity operator are introduced in the Distributed Geometric Machine framework (D-GM). Instead of executing the quantum transformation in a single step, they are divided in sub-quantum transformations and only the values different from Identity transformations are stored. Mixed Partial Processes provide control over the increase in the size of read/write memory states in the calculation of a QT, thus contributing to increase the scalability of applications regarding hardware-GPUs memory limit. In the evaluation of this D-GM extension, Hadamard Transformations were simulated up to 28 qubits applications over a single GPU. Our new simulator is 10, 829χ faster and allows for the simulation of more qubits when compared to our previous implementation running on the same GPU.
Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.
Summary Because of the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is very relevant to develop and test new quantum algorithms. In order to overcome the increase in simulation complexity, this work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are reached by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Hadamard transformations from 21 to 28 qubits and Quantum Fourier Transforms from 26 to 28 qubits were simulated over CPU, sequentially and in parallel, and in graphics processing unit, showing reduced temporal complexity and, consequently, shorter simulation time. Moreover, evaluations of the Shor's algorithm considering 2n + 3 qubits in the order‐finding quantum algorithm were simulated up to 25 qubits. When comparing our implementations running on the same hardware with language‐integrated quantum operation, academic release version, our new simulator was faster and allowed for the simulation of more qubits. Copyright © 2016 John Wiley & Sons, Ltd.
The exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial complexity and memory access patterns are major performance hazards. A new methodology employs reduction and decomposition optimizations, exploring properties such as the sparsity of the Id-Operator and the partiality of dense unitary transformations to improve storage and distribution of quantum states. In this work, Shor's and Grover's algorithms are simulated in both CPU and GPU in the Distributed Geometric Machine environment. Additionally, they are compared to LIQUi|〉's results. In all cases, our simulation was faster and allowed for an improved number of qubits when compared to the academic release version of LIQUi|〉, with relative speedups up to 118×.
The D-GM execution environment improves distributed simulation of quantum algorithms in heterogeneous computing environments comprising both multi-core CPUs and GPUs. The main contribution of this work consists in the optimization of the environment VirD-GM, conceived in three steps: ( i ) the theoretical studies and implementation of the abstractions of the Mixed Partial Process defined in the qGM model, focusing on the reduction of the memory consumption regarding multidimensional QTs; ( ii ) the distributed/parallel implementation of such abstractions allowing its execution on clusters of GPUs; ( iii ) and optimizations that predict multiplications by zero-value of the quantum states/transformations, implying reduction in the number of computations. The results obtained in this work embrace the distribute/parallel simulation of Hadamard gates up to 21 qubits, showing scalability with the increase in the number of computing nodes.
Exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this an important application for HPC. A new methodology employing reduction and decomposition optimizations has shown great results, but its GPU implementation could be further improved. In this work, we intend to do a new implementation for in-situ GPU simulation that better explores its resources without requiring further HPC hardware. Shors and Grovers algorithms are simulated and compared to the previous version and to LIQUi|s simulator, showing better results with relative speedups up to 15.5× and 765.76× respectively.