Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2009 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Quantum Circuit Simulation

verfasst von: George F. Viamontes, Igor L. Markov, John P. Hayes

Verlag: Springer Netherlands

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Quantum Circuit Simulation covers the fundamentals of linear algebra and introduces basic concepts of quantum physics needed to understand quantum circuits and algorithms. It requires only basic familiarity with algebra, graph algorithms and computer engineering. After introducing necessary background, the authors describe key simulation techniques that have so far been scattered throughout the research literature in physics, computer science, and computer engineering. Quantum Circuit Simulation also illustrates the development of software for quantum simulation by example of the QuIDDPro package, which is freely available and can be used by students of quantum information as a "quantum calculator."

Inhaltsverzeichnis

Frontmatter
1. Introduction
The construction of computer algorithms and software models that simulate physical systems plays a fundamental role in all branches of science and engineering. The physicist and Nobel laureate Richard Feynman, among others, observed in the 1980s that the important task of simulating quantum-mechanical processes on a standard computer requires an extraordinary amount of computer memory and runtime [41]. Such observations gave rise to the notion of quantum computing, where quantum mechanics itself is used to simulate quantum behavior. The key insight is to replace the familiar 0 and 1 bits of conventional or classical computing with information units called qubits (quantum bits) that capture quantum states of elementary particles or atomic nuclei. By operating on qubits, a quantum computer can, in principle, process exponentially more data than a classical computer in a similar number of steps. In the 1990s, several fast quantum methods were discovered for such applications as searching large databases [38] and factoring large numbers [82]; the latter is a basic step in some forms of codebreaking.
2. Gate Modeling and Circuit Simulation
As with other sophisticated technologies in information processing, the practical implementation and use of electronic circuits is preceded by their mathematical modeling and simulation. Detailed calculations of physical parameters are employed to characterize individual circuit elements with respect to environmental conditions and manufacturing variations, but are difficult to scale to very large integrated circuits. In this context, a compact model captures the essence of a circuit's operation without unnecessary details. Such models express the expected outputs of each circuit component given its inputs, and are key to fast algorithms for simulating the functional behavior of the entire circuit: its speed, power dissipation, temperature distribution, etc. Simulation is thus an important prerequisite to validating the operation of the circuit.
This chapter discusses the modeling and simulation of classical digital circuits to introduce and motivate the methods used for quantum circuit simulation. Emphasis is placed on functional simulation and its use in formal verification of both combinational and sequential circuits.
3. Linear Algebra and Quantum Mechanics
Boolean algebra is commonly viewed as the mathematical foundation of classical logic circuits. The analogous role for quantum logic circuits is played by linear algebra. The physical principles of quantum circuits are governed by quantum mechanics, which makes heavy use of the theory of linear operators in Hilbert space. Section 3.1 reviews the portions of linear algebra that are most relevant to quantum mechanics. Then Section 3.2 reviews the key concepts of quantum mechanics that are most relevant to quantum circuits.
4. Quantum Information Processing
This chapter introduces the gate and circuit models for quantum computation. To reduce the air of mystery commonly associated with quantum circuits, we compare and contrast the concepts presented here with their classical analogues discussed in Chapter 2. First, we define the basic types of quantum gates, and then show how multiple gates can be combined to create quantum circuits. In each case, we try to connect the quantum circuit concepts to their linear-algebraic underpinnings discussed in Chapter 3. This connection is critically important to quantum circuit simulation, which is explored in great detail in the remainder of the book.
5. Special Case: Simulating Stabilizer Circuits
We begin the discussion of quantum circuit simulation techniques with an in-depth analysis of a well-known technique which makes use of group theory to efficiently simulate a particular class of quantum circuits. The background material from Chapters 2, 3 and 4 will be combined to show how this class of quantum circuits, namely stabilizer circuits, and a corresponding compact representation, the stabilizer formalism, make up some key elements of a quantum circuit simulator. This special case study will set the stage for understanding the overall structure of a variety of other quantum circuit simulation techniques covered in the remainder of the book.
6. Generic Circuit Simulation Techniques
In this chapter, we discuss several distinct methods that have been proposed for simulating arbitrary quantum circuits. They include qubit-wise multiplication, p-blocked simulation, the use of tensor networks, Vidal's “slightly entangled” technique, and a few others. Each approach has advantages that makes it especially well-suited to certain specific classes of quantum circuits. We also consider programming environments for quantum computing, most of which include front-ends to general-purpose quantum simulation software. Here we focus on the more powerful and sophisticated simulation algorithms and assess their advantages and disadvantages. This chapter may be skipped without significant loss of continuity.
7. State-Vector Simulation with Decision Diagrams
This chapter covers the theory behind the QuIDD and related data structures, all of which are based on the decision diagram (DD) concepts described in Section 2.2. As will be seen, QuIDDs allow simulations of n-qubit systems to achieve runtime and memory complexities that range from constant-time to exponential, and the worst case is not typical for structured circuits arising in practical applications. Later in the chapter, benchmark results with Grover's quantum search algorithm will reveal that a QuIDD-based simulator outperforms several implementations of qubit-wise multiplication in terms of asymptotic runtime and memory usage.
8. Density-Matrix Simulation with QuIDDs
This chapter extends QuIDD-based quantum circuit simulation to handle density matrices, which are crucial in capturing interactions between quantum states and their environment. Besides the usual operations required to simulate with the state-vector model, including matrix multiplication and the tensor product, simulation with density matrices requires the outer product and the partial trace. We therefore present algorithms to implement the outer product and the partial trace with QuIDDs. The outer product is used in the initialization of density matrices. The partial trace is invaluable in error modeling as it facilitates descriptions of single qubit states that are affected by noise and other phenomena. We also describe a set of quantum circuit benchmarks that incorporate errors, error correction, reversible logic, quantum communication, and quantum search. To evaluate the improvements offered by the QuIDD-based approach empirically, we use these benchmarks to compare QuIDDPro with an array-based density matrix simulator called QCSim that makes extensive use of qubit-wise multiplication.
9. Checking Equivalence of States and Circuits
Equivalence checking is a basic task in the synthesis and verification of classical digital circuits. A hardware designer needs to know whether a circuit's implementation is functionally equivalent to its specification. In addition, the equivalence of different versions of the same (sub-)circuit must be checked throughout the complex computer-aided design process. Traditional combinational equivalence checking is solved in practice with high-performance solvers for Boolean Satisfiability, and its negative version (non-equivalence) is NP-complete.
Equivalence checking is likely to be just as important in quantum CAD, and the non-equivalence of quantum circuits is QMA-complete.1 However, the equivalence of quantum states and operators can be subtle. Unlike their classical counterparts, qubits and quantum gates can differ by global and relative phase, and yet be equivalent upon measurement. Building upon the algorithmic blocks developed in Chapter 7, we present QuIDD algorithms to check quantum states and operators for equivalence. As we will see, the variety of algorithms available to solve this problem is surprising.
10. Improving QuIDD-based Simulation
This chapter describes some ways to speed up QuIDD-based simulation that are facilitated by the QuIDDPro language. These techniques apply to QuIDD matrix multiplication, the tensor product, and the partial trace, which are key operations for simulation with and without errors. First, we describe algorithms for efficiently applying controlled- and 1-qubit gates to QuIDD state vectors. The simulator uses these algorithms when processing particular source-code expressions in its input. Next, we show how one can selectively tensor and remove, via the partial trace operation, qubits that do not affect a computation's final outcome. Although this technique cannot be used in every case, it can exponentially reduce simulation complexity in important special cases. We illustrate this by simulating a circuit with several types of continuous errors and evaluating the effectiveness of “bang-bang” error correction.
11. Closing Remarks
In general, quantum circuit simulation requires runtime and memory resources that grow exponentially with the number of qubits simulated. Some circuits can be simulated quickly, but are unlikely to exhibit quantum speed-ups. To this end, quantum circuit simulation often suggests certain limitations of quantum circuits and algorithms.
Quantum simulation can also aid in quantum engineering efforts by evaluating and sanity-checking small versions of quantum circuits before actual implementation. Quantum circuits are significantly more complicated than classical digital logic circuits, and their properties are difficult to capture with traditional CAD techniques. One of the most important of these properties is the fragile nature of quantum information. Quantum states are often damaged over time by several types of gate-specific and environmental errors, which experimental physicists find difficult to characterize. Additionally, the notion of equivalence, while trivial in the classical case, takes on a surprisingly rich set of interpretations in the quantum case, offering several computational challenges of varying complexity. As a result, useful quantum CAD tools must incorporate special models and efficient, classical simulation techniques to overcome these obstacles for classes of circuits with practical value.
Backmatter
Metadaten
Titel
Quantum Circuit Simulation
verfasst von
George F. Viamontes
Igor L. Markov
John P. Hayes
Copyright-Jahr
2009
Verlag
Springer Netherlands
Electronic ISBN
978-90-481-3065-8
Print ISBN
978-90-481-3064-1
DOI
https://doi.org/10.1007/978-90-481-3065-8

Neuer Inhalt

    Bildnachweise