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

Efficient quantum circuit simulation.

John P. Hayes, Igor L. Markov, George F. Viamontes

Published Jan 1, 2007• 15 citations
OpenAlex

Abstract

Quantum-mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, while the securest forms of communication rely on quantum data encoding. When they involve a finite number of basis states, these phenomena can be modeled as quantum circuits, the quantum analogue of conventional or classical logic circuits. Simulation of quantum circuits can therefore be used as a tool to evaluate issues in the design of quantum information processors. Unfortunately, simulating such phenomena efficiently is exceedingly difficult. The matrices representing quantum operators (gates) and vectors modeling quantum states grow exponentially with the number of quantum bits. The information represented by quantum states and operators often exhibits structure that can be exploited when simulating certain classes of quantum circuits. We study the development of simulation methods that run on classical computers and take advantage of such repetitions and redundancies. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). A QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data. We develop a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluate their complexity. These algorithms have been implemented in a general-purpose simulator program for quantum-mechanical applications called QuIDDPro. Through extensive experiments conducted on representative quantum simulation applications, including Grover's search algorithm, error characterization, and reversible circuits, we demonstrate that QuIDDPro is faster than other existing quantum-mechanical simulators such as the National Institute of Standards and Technology's QCSim program, and is far more memory-efficient. Using QuIDDPro, we explore the advantages of quantum computation over classical computation, simulate quantum errors and error correction, and study the impact of numerical precision on the fidelity of simulations. We also develop several novel algorithms for testing quantum circuit equivalence and compare them empirically. The QuIDDPro software is equipped with a user-friendly interface and is distributed with numerous example scripts. It has been used as a laboratory supplement for quantum computing courses at several universities.

Related papers

Graph-based simulation of quantum computation in the density matrix representation

George F. Viamontes, Igor L. Markov, John P. Hayes

Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. A major complication is caused by errors (noise) due to unwanted interactions between the quantum states and the environment. Consequently, simulating quantum circuits and their associated errors using the density matrix representation is potentially significant in many applications, but is well beyond the computational abilities of most classical simulation techniques in both time and memory resources. The size of a density matrix grows exponentially with the number of qubits simulated, rendering array-based simulation techniques that explicitly store the density matrix intractable. In this work, we propose a new technique aimed at efficiently simulating quantum circuits that are subject to errors. In particular, we describe new graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector representation, these new algorithms use the density matrix representation. To gauge the improvements offered by QuIDDPro/D, we compare its simulation performance with an optimized array-based simulator called QCSim. Empirical results, generated by both simulators on a set of quantum circuit benchmarks involving error correction, reversible logic, communication, and quantum search, show that the graph-based approach far outperforms the array-based approach for these circuits.

Quantum Information and Computation•May 1, 2005•45 citations

Gate-Level Simulation of Quantum Circuits

George F. Viamontes, Manoj Rajagopalan, Igor L. Markov +1 more

While thousands of experimental physicists and chemists are currently trying to build scalable quantum computers, it appears that simulation of quantum computation will be at least as critical as circuit simulation in classical VLSI design. However, since the work of Richard Feynman in the early 1980s little progress was made in practical quantum simulation. Most researchers focused on polynomial-time simulation of restricted types of quantum circuits that fall short of the full power of quantum computation. Simulating quantum computing devices and useful quantum algorithms on classical hardware now requires excessive computational resources, making many important simulation tasks infeasible. In this work we propose a new technique for gate-level simulation of quantum circuits which greatly reduces the difficulty and cost of such simulations. The proposed technique is implemented in a simulation tool called the Quantum Information Decision Diagram (QuIDD) and evaluated by simulating Grover's quantum search algorithm. The back-end of our package, QuIDD Pro, is based on Binary Decision Diagrams, well-known for their ability to efficiently represent many seemingly intractable combinatorial structures. This reliance on a well-established area of research allows us to take advantage of existing software for BDD manipulation and achieve unparalleled empirical results for quantum simulation.

arXiv:quant-ph/0208003•Aug 1, 2002•6 citations

High-performance QuIDD-based simulation of quantum circuits

George F. Viamontes, Igor L. Markov, John P. Hayes

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with the number of qubits. It has been shown experimentally that the QuIDD (Quantum Information Decision Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the number of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover's algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead.

Design, Automation, and Test in Europe•Jul 20, 2004•42 citations

Graph-based simulation of quantum computation in the density matrix representation

George F. Viamontes, Igor L. Markov, John P. Hayes

Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. A major complication is caused by errors (noise) due to unwanted interactions between the quantum states and the environment. Consequently, simulating quantum circuits and their associated errors using the density matrix representation is potentially significant in many applications, but is well beyond the computational abilities of most classical simulation techniques in both time and memory resources. The size of a density matrix grows exponentially with the number of qubits simulated, rendering array-based simulation techniques that explicitly store the density matrix intractable. In this work, we propose a new technique aimed at efficiently simulating quantum circuits that are subject to errors. In particular, we describe new graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector representation, these new algorithms use the density matrix representation. To gauge the improvements offered by QuIDDPro/D, we compare its simulation performance with an optimized array-based simulator called QCSim. Empirical results, generated by both simulators on a set of quantum circuit benchmarks involving error correction, reversible logic, communication, and quantum search, show that the graph-based approach far outperforms the array-based approach.

arXiv:quant-ph/0403114•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•31 citations

Approximating Decision Diagrams for Quantum Circuit Simulation

Stefan Hillmich, Alwin Zulehner, Richard Kueng +2 more

Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.

ACM Transactions on Quantum Computing•Apr 25, 2022•14 citations

High-performance QuIDD-based simulation of quantum circuits

George F. Viamontes, Igor L. Markov, John P. Hayes

Simulating quantum computation on a classical com-puter is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow ex-ponentially with the number of qubits. It has been shown ex-perimentally that the QuIDD (Quantum Information Deci-sion Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the num-ber of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover’s algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead. 1.

Design, Automation, and Test in Europe•Feb 16, 2004•31 citations
Quantum-mechanical phenomena are playing an increasing role in information processing as transistor sizes approach the nanometer level, while the securest forms of communication rely on quantum data encoding. When they involve a finite number of basis states, these phenomena can be modeled as quantum circuits, the quantum analogue of conventional or classical logic circuits. Simulation of quantum circuits can therefore be used as a tool to evaluate issues in the design of quantum information processors. Unfortunately, simulating such phenomena efficiently is exceedingly difficult. The matrices representing quantum operators (gates) and vectors modeling quantum states grow exponentially with the number of quantum bits. The information represented by quantum states and operators often exhibits structure that can be exploited when simulating certain classes of quantum circuits. We study the development of simulation methods that run on classical computers and take advantage of such repetitions and redundancies. In particular, we define a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD). A QuIDD is a compressed graph representation of a vector or matrix and permits computations to be performed directly on the compressed data. We develop a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluate their complexity. These algorithms have been implemented in a general-purpose simulator program for quantum-mechanical applications called QuIDDPro. Through extensive experiments conducted on representative quantum simulation applications, including Grover's search algorithm, error characterization, and reversible circuits, we demonstrate that QuIDDPro is faster than other existing quantum-mechanical simulators such as the National Institute of Standards and Technology's QCSim program, and is far more memory-efficient. Using QuIDDPro, we explore the advantages of quantum computation over classical computation, simulate quantum errors and error correction, and study the impact of numerical precision on the fidelity of simulations. We also develop several novel algorithms for testing quantum circuit equivalence and compare them empirically. The QuIDDPro software is equipped with a user-friendly interface and is distributed with numerous example scripts. It has been used as a laboratory supplement for quantum computing courses at several universities.
Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. A major complication is caused by errors (noise) due to unwanted interactions between the quantum states and the environment. Consequently, simulating quantum circuits and their associated errors using the density matrix representation is potentially significant in many applications, but is well beyond the computational abilities of most classical simulation techniques in both time and memory resources. The size of a density matrix grows exponentially with the number of qubits simulated, rendering array-based simulation techniques that explicitly store the density matrix intractable. In this work, we propose a new technique aimed at efficiently simulating quantum circuits that are subject to errors. In particular, we describe new graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector representation, these new algorithms use the density matrix representation. To gauge the improvements offered by QuIDDPro/D, we compare its simulation performance with an optimized array-based simulator called QCSim. Empirical results, generated by both simulators on a set of quantum circuit benchmarks involving error correction, reversible logic, communication, and quantum search, show that the graph-based approach far outperforms the array-based approach for these circuits.
While thousands of experimental physicists and chemists are currently trying to build scalable quantum computers, it appears that simulation of quantum computation will be at least as critical as circuit simulation in classical VLSI design. However, since the work of Richard Feynman in the early 1980s little progress was made in practical quantum simulation. Most researchers focused on polynomial-time simulation of restricted types of quantum circuits that fall short of the full power of quantum computation. Simulating quantum computing devices and useful quantum algorithms on classical hardware now requires excessive computational resources, making many important simulation tasks infeasible. In this work we propose a new technique for gate-level simulation of quantum circuits which greatly reduces the difficulty and cost of such simulations. The proposed technique is implemented in a simulation tool called the Quantum Information Decision Diagram (QuIDD) and evaluated by simulating Grover's quantum search algorithm. The back-end of our package, QuIDD Pro, is based on Binary Decision Diagrams, well-known for their ability to efficiently represent many seemingly intractable combinatorial structures. This reliance on a well-established area of research allows us to take advantage of existing software for BDD manipulation and achieve unparalleled empirical results for quantum simulation.
Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with the number of qubits. It has been shown experimentally that the QuIDD (Quantum Information Decision Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the number of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover's algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead.
Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. A major complication is caused by errors (noise) due to unwanted interactions between the quantum states and the environment. Consequently, simulating quantum circuits and their associated errors using the density matrix representation is potentially significant in many applications, but is well beyond the computational abilities of most classical simulation techniques in both time and memory resources. The size of a density matrix grows exponentially with the number of qubits simulated, rendering array-based simulation techniques that explicitly store the density matrix intractable. In this work, we propose a new technique aimed at efficiently simulating quantum circuits that are subject to errors. In particular, we describe new graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector representation, these new algorithms use the density matrix representation. To gauge the improvements offered by QuIDDPro/D, we compare its simulation performance with an optimized array-based simulator called QCSim. Empirical results, generated by both simulators on a set of quantum circuit benchmarks involving error correction, reversible logic, communication, and quantum search, show that the graph-based approach far outperforms the array-based approach.
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.
Simulating quantum computation on a classical com-puter is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow ex-ponentially with the number of qubits. It has been shown ex-perimentally that the QuIDD (Quantum Information Deci-sion Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the num-ber of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover’s algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead. 1.