Quantum Computing for Computer Architects

✍ Scribed by Tzvetan Metodi, Frederic Chong, Arvin Faruque

• Publisher: Morgan & Claypool Publishers
• Year: 2011
• Tongue: English
• Leaves: 203
• Series: Synthesis Lectures on Computer Architecture
• Edition: 2
• Category: Library

✦ Synopsis

Quantum computers can (in theory) solve certain problems far faster than a classical computer running any known classical algorithm. While existing technologies for building quantum computers are in their infancy, it is not too early to consider their scalability and reliability in the context of the design of large-scale quantum computers. To architect such systems, one must understand what it takes to design and model a balanced, fault-tolerant quantum computer architecture. The goal of this lecture is to provide architectural abstractions for the design of a quantum computer and to explore the systems-level challenges in achieving scalable, fault-tolerant quantum computation. In this lecture, we provide an engineering-oriented introduction to quantum computation with an overview of the theory behind key quantum algorithms. Next, we look at architectural case studies based upon experimental data and future projections for quantum computation implemented using trapped ions. While we focus here on architectures targeted for realization using trapped ions, the techniques for quantum computer architecture design, quantum fault-tolerance, and compilation described in this lecture are applicable to many other physical technologies that may be viable candidates for building a large-scale quantum computing system. We also discuss general issues involved with programming a quantum computer as well as a discussion of work on quantum architectures based on quantum teleportation. Finally, we consider some of the open issues remaining in the design of quantum computers. Table of Contents: Introduction / Basic Elements for Quantum Computation / Key Quantum Algorithms / Building Reliable and Scalable Quantum Architectures / Simulation of Quantum Computation / Architectural Elements / Case Study: The Quantum Logic Array Architecture / Programming the Quantum Architecture / Using the QLA for Quantum Simulation: The Transverse Ising Model / Teleportation-Based Quantum Architectures / Concluding Remarks

✦ Table of Contents

Preface......Page 11
Introduction......Page 13
Classical vs. Quantum Signal States (bits vs. qubits)......Page 19
Logic Operations and Circuits......Page 20
Quantum Measurement......Page 25
Example: The 3-Qubit Quantum Toffoli Gate......Page 27
Example: Quantum Fourier Transform (QFT)......Page 28
Example: Deutsch's Quantum Algorithm......Page 29
Quantum Entanglement and EPR Pairs......Page 31
Other Models of Quantum Computation......Page 33
The Integer Factorization Problem......Page 35
A Quantum Integer Factorization Algorithm......Page 36
Order Finding......Page 37
Order Finding as Quantum Eigenvalue Estimation......Page 39
Order Finding: Continued Fractions......Page 41
Proof Sketch of the Correctness of the Phase Estimation Circuit......Page 43
Eigenvalue Estimation......Page 46
The Hidden Subgroup Problem......Page 48
Grover's Algorithm for Quantum Search......Page 50
Grover's Algorithm......Page 51
Proof Sketch of the Correctness of Grover Iteration......Page 52
Quantum Adiabatic Algorithms......Page 56
3-SAT: An example of a Quantum Adiabatic algorithm......Page 58
Building Reliable and Scalable Quantum Architectures......Page 61
Reliable and realistic implementation technology......Page 63
Optical Quantum Computation: Photons as Qubits......Page 65
Trapped-Ion Quantum Computation: Ions as Qubits......Page 66
Robust Error Correction and Fault-Tolerant Structures......Page 69
Noise Model Assumptions......Page 70
Error Correction: Basics and Notation......Page 73
Example: The Steane [[7,1,3]]Code......Page 79
Logical Qubits in Quantum Computation......Page 83
Quantum Error Correction and Fault-Tolerance: The Threshold Result......Page 84
Scale-Up in System Size due to Error Correction......Page 87
Error Correction Slowdown......Page 88
Quantum Resource Distribution......Page 91
Physical Qubit Movement......Page 92
Teleportation-Based Communication and Quantum Repeaters......Page 93
Simulation of Quantum Computation......Page 97
Simulation of Error Propagation......Page 98
Stabilizer Method for Quantum Simulation......Page 101
Architectural Elements......Page 103
Quantum Processing Elements (PE's)......Page 105
Quantum Memory Hierarchy......Page 106
Quantum Addressing Scheme for Classical Memory......Page 109
Effects of Ancilla Preparation and Layout......Page 111
Optimizing Error Correction along Critical Paths......Page 113
QLA Architecture Overview......Page 115
The Logical Qubit Design in the QLA......Page 117
Logical Qubit Interconnect......Page 119
Compressed QLA Architecture: CQLA......Page 129
Communication Issues: Executing the Toffoli Gate......Page 132
Memory Hierarchy in the CQLA Architecture......Page 134
Simulating the Cache in the CQLA......Page 136
Qualypso......Page 138
Programming the Quantum Architecture......Page 141
Physical-Level Instruction Scheduling......Page 142
High-Level Compiler Design......Page 144
Architecture-Independent Circuit Synthesis......Page 145
Mapping Circuits to Architecture......Page 146
The Fault-Tolerant Threshold Estimates......Page 150
Circuit Scheduling and The Fault-Tolerance Constraint......Page 152
Threshold Calculations......Page 155
Summary Discussion......Page 157
The Transverse Ising Model Overview......Page 161
Phase estimation circuit......Page 162
Decomposition of the TIM quantum circuit into fault-tolerant gates......Page 164
Mapping the TIM circuit onto the QLA architecture......Page 167
Resource estimates for the 1-D TIM problem......Page 168
Teleportation-Based Quantum Architectures......Page 171
The cnot Gate and Single-Qubit Gates through Teleportation......Page 173
The Architecture......Page 175
Error Correction through Teleportation......Page 178
Concluding Remarks......Page 181
Bibliography......Page 183
Authors' Biographies......Page 203