# Improving Gate-Level Simulation of Quantum Circuits

@article{Viamontes2003ImprovingGS, title={Improving Gate-Level Simulation of Quantum Circuits}, author={George F. Viamontes and Igor L. Markov and John Patrick Hayes}, journal={Quantum Information Processing}, year={2003}, volume={2}, pages={347-380} }

AbstractSimulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and the vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a novel data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, a useful subset of operator matrices and state vectors can be represented in a form that grows polynomially with the number… Expand

#### Figures, Tables, and Topics from this paper

#### 89 Citations

High-performance QuIDD-based simulation of quantum circuits

- Computer Science
- Proceedings Design, Automation and Test in Europe Conference and Exhibition
- 2004

An improved implementation of QuIDDs is presented which can simulate Grover's algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead. Expand

Efficient quantum circuit simulation

- Computer Science
- 2007

This work defines a new data structure for simulating quantum circuits called the quantum information decision diagram (QuIDD), and develops a comprehensive set of algorithms for operating on QuIDDs in both the state-vector and density-matrix formats, and evaluates their complexity. Expand

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

- Computer Science, Mathematics
- SPIE Defense + Commercial Sensing
- 2004

This work proposes a new technique aimed at efficiently simulating quantum circuits that are subject to errors, and describes new graph-based algorithms implemented in the simulator QuIDDPro/D that use the density matrix representation. Expand

One-way quantum computer simulation

- Computer Science, Physics
- Microprocess. Microsystems
- 2015

A general direct simulator for 1WQC, called OWQS, is presented and the simulator is adjusted to simulate the measurement patterns with a generalized flow without calculating the measurement probabilities which is called extended one-way quantum computation simulator (EOWQS). Expand

APPLICATION OF DECISION DIAGRAMS TO DESIGN QUANTUM LOGIC CIRCUITS

- Computer Science
- 2012

A thorough study of the properties of binary and multi-valued quantum logic along with the impact of Quantum Information Decision Diagram (QUIDD), Quantum Multi-Valued Decision diagrams in quantum logic. Expand

Advanced Simulation of Quantum Computations: Compact Representation Rather than Hardware Power

- Physics, Computer Science
- ArXiv
- 2017

This work revisits the basics of quantum computation, investigates how corresponding quantum states and quantum operations can be represented, and, eventually, simulated in a more efficient fashion, and proposes a simulation approach which works complementary different to the state-ofthe-art. Expand

A QUANTUM CIRCUIT SIMULATOR BASED ON DECISION DIAGRAMS

- 2007

The advantages of quantum computing as compared to classical computing are currently being researched; therefore, the ability to correctly simulate quantum circuits is becoming increasingly more… Expand

Advanced Simulation of Quantum Computations

- Computer Science, Mathematics
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- 2019

The basics of quantum computation are revisited, how corresponding quantum states and quantum operations can be represented even more compactly, and, eventually, simulated in a more efficient fashion are investigated, leading to a new graph-based simulation approach which outperforms state-of-the-art simulators. Expand

Algebraic and Logical Emulations of Quantum Circuits

- Computer Science
- Trans. Comput. Sci.
- 2018

This work describes three such formalisms for quantum circuits that appear novel and employs only simple Boolean formulas, optionally limited to a form the authors call “parity-of-AND” equations, and shows capable of vast improvements in the emulation time in natural instances. Expand

Recursive Path-Summing Simulation of Quantum Computation

- Physics, Mathematics
- 2017

Classical simulation of quantum computation has often been viewed as the method to determine where the horizon of quantum supremacy is located---that is, where quantum computation can no longer be… Expand

#### References

SHOWING 1-10 OF 34 REFERENCES

Gate-level simulation of quantum circuits

- Computer Science, Physics
- ASP-DAC '03
- 2003

This work implemented a general-purpose quantum computing simulator in C++ called QuIDDPro and tested it on Grover's algorithm and found that it asymptotically outperforms other known simulation techniques. Expand

The Heisenberg Representation of Quantum Computers

- Mathematics, Physics
- 1998

Since Shor`s discovery of an algorithm to factor numbers on a quantum computer in polynomial time, quantum computation has become a subject of immense interest. Unfortunately, one of the key features… Expand

Elementary gates for quantum computation.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1995

U(2) gates are derived, which derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number of unitary operations on arbitrarily many bits. Expand

Multiple-Valued Quantum Logic

- Mathematics
- 2002

This paper introduces the concept of multiplevalued quantum logic, where more than two quantum basis states are introduced, for instance { 0 , 1 , 2 } for ternary quantum logic. Since the binary… Expand

Tight bounds on quantum searching

- Computer Science, Physics
- 1996

A lower bound on the efficiency of any possible quantum database searching algorithm is provided and it is shown that Grover''s algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table. Expand

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

- Computer Science, Mathematics
- SIAM Rev.
- 1999

Efficient randomized algorithms are given for factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and have been used as the basis of several proposed cryptosystems. Expand

Quantum Mechanics Helps in Searching for a Needle in a Haystack

- Physics
- 1997

Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing $N$ names arranged in completely random order. To find someone's… Expand

Graph-Based Algorithms for Boolean Function Manipulation

- Computer Science
- IEEE Transactions on Computers
- 1986

Experimental results from applying a new data structure for representing Boolean functions and an associated set of manipulation algorithms to problems in logic design verification demonstrate the practicality of this approach. Expand

Feynman And Computation

- Computer Science, Mathematics
- 2002

Feynmans Course On Computation Feynman and Computation (John J. Hopfield) Neural Networks and Physical Systems with Emergent Collective Computational Abilities (John J. Hopfield) Feynman as a… Expand

Algebric Decision Diagrams and Their Applications

- Computer Science
- ICCAD '93
- 1993

A treatment founded in Boolean algebras is presented and algorithms and results in several areas of application are discussed: Matrix multiplication, shortest path algorithms, and direct methods for numerical linear algebra. Expand