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

International Conference on Genetic and Evolutionary Computing

On the Research of BDD Based Simulation of Grover's Algorithm

Xiling Xue, Hanwu Chen, Kaizhong Chen, Zhiqiang Li

Published Sep 1, 2008• 2 citations
Publisher

Abstract

In this paper, we adopt an efficient data structure called the binary decision diagram (BDD) that exploits the structure displayed in quantum computing to simulate Grover's quantum search algorithm. First we adapt the original BDD and implement a series of algorithms to represent and manipulate matrices and vectors. Then instances of Grover's algorithm are simulated using our programme written in C++. In the last part we present an intensive analysis of the counter-intuitive experimental results in quantum mechanism, which may help understand the essence of quantum algorithms.

DOI
10.1109/wgec.2008.87

Related papers

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

Efficient quantum circuit simulation.

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

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.

•Jan 1, 2007•15 citations

An Idea to Improve QuIDD Based Quantum Simulations

Katalin Friedl, László Kabódi

Simulating quantum algorithms is a hard problem on classical computers, it usually needs exponential time and space. Viamontes et al. proposed a new data structure the Quantum Information Decision Diagram (QuIDD) to overcome this problem and implemented it in the QuIDDPro software. Using this structure several algorithms can be simulated on classical computers with polynomial time and space. In this paper we suggest further improvement and analyse in detail its behavior on Grover’s search algorithm.

Periodica Polytechnica Electrical Engineering and Computer Science•Jan 1, 2015•1 citation

Symbolic Quantum Simulation with Quasimodo

Meghana Aparna Sistla, Swarat Chaudhuri, Thomas Reps

Abstract The simulation of quantum circuits on classical computers is an important problem in quantum computing. Such simulation requires representations of distributions over very large sets of basis vectors, and recent work has used symbolic data-structures such as Binary Decision Diagrams (BDDs) for this purpose. In this tool paper, we present Quasimodo, an extensible, open-source Python library for symbolic simulation of quantum circuits. Quasimodo is specifically designed for easy extensibility to other backends. Quasimodo allows simulations of quantum circuits, checking properties of the outputs of quantum circuits, and debugging quantum circuits. It also allows the user to choose from among several symbolic data-structures—both unweighted and weighted BDDs, and a recent structure called Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs)—and can be easily extended to support other symbolic data-structures.

arXiv:2302.04349•Lecture notes in computer science•Jan 1, 2023•25 citations

Analysis and Simulation of Grover’s Search Algorithm

Jiayu Zhuang, Junsuo Zhao, Fanjiang Xu +2 more

A quantum computation problem of quantum search is discussed in this paper.Grover's search algorithm, the most commonly used quantum search algorithm, is introduced in details.The flow of quantum search algorithm and the quantum circuit model are shown.And the error of the search value, as well as the probability of measurement, is analyzed.For further research we simulated the Grover's search algorithm in classical computer.By quantum simulator the probability distribution of the measuring result of search value is presented and the computational efficiency is discussed.The simulation result demonstrates the effectiveness of the proposed algorithm.

International Journal of Machine Learning and Computing•Feb 1, 2014•5 citations
In this paper, we adopt an efficient data structure called the binary decision diagram (BDD) that exploits the structure displayed in quantum computing to simulate Grover's quantum search algorithm. First we adapt the original BDD and implement a series of algorithms to represent and manipulate matrices and vectors. Then instances of Grover's algorithm are simulated using our programme written in C++. In the last part we present an intensive analysis of the counter-intuitive experimental results in quantum mechanism, which may help understand the essence of quantum algorithms.
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, 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.
Simulating quantum algorithms is a hard problem on classical computers, it usually needs exponential time and space. Viamontes et al. proposed a new data structure the Quantum Information Decision Diagram (QuIDD) to overcome this problem and implemented it in the QuIDDPro software. Using this structure several algorithms can be simulated on classical computers with polynomial time and space. In this paper we suggest further improvement and analyse in detail its behavior on Grover’s search algorithm.
Abstract The simulation of quantum circuits on classical computers is an important problem in quantum computing. Such simulation requires representations of distributions over very large sets of basis vectors, and recent work has used symbolic data-structures such as Binary Decision Diagrams (BDDs) for this purpose. In this tool paper, we present Quasimodo, an extensible, open-source Python library for symbolic simulation of quantum circuits. Quasimodo is specifically designed for easy extensibility to other backends. Quasimodo allows simulations of quantum circuits, checking properties of the outputs of quantum circuits, and debugging quantum circuits. It also allows the user to choose from among several symbolic data-structures—both unweighted and weighted BDDs, and a recent structure called Context-Free-Language Ordered Binary Decision Diagrams (CFLOBDDs)—and can be easily extended to support other symbolic data-structures.
A quantum computation problem of quantum search is discussed in this paper.Grover's search algorithm, the most commonly used quantum search algorithm, is introduced in details.The flow of quantum search algorithm and the quantum circuit model are shown.And the error of the search value, as well as the probability of measurement, is analyzed.For further research we simulated the Grover's search algorithm in classical computer.By quantum simulator the probability distribution of the measuring result of search value is presented and the computational efficiency is discussed.The simulation result demonstrates the effectiveness of the proposed algorithm.