An Introduction to Quantum Computing
Format: PDF / Kindle (mobi) / ePub
This concise, accessible text provides a thorough introduction to quantum computing - an exciting emergent field at the interface of the computer, engineering, mathematical and physical sciences. Aimed at advanced undergraduate and beginning graduate students in these disciplines, the text is technically detailed and is clearly illustrated throughout with diagrams and exercises. Some prior knowledge of linear algebra is assumed, including vector spaces and inner products. However, prior familiarity with topics such as tensor products and spectral decomposition is not required, as the necessary material is reviewed in the text.
9.6 Block Sensitivity 197 9.6.1 Examples of Block Sensitivity Lower Bounds 197 9.7 Adversary Methods 198 9.7.1 Examples of Adversary Lower Bounds 200 9.7.2 Generalizations 203 10 QUANTUM ERROR CORRECTION 204 10.1 Classical Error Correction 204 10.1.1 The Error Model 205 10.1.2 Encoding 206 10.1.3 Error Recovery 207 10.2 The Classical Three-Bit Code 207 10.3 Fault Tolerance 211 10.4 Quantum Error Correction 212 10.4.1 Error Models for Quantum Computing 213 10.4.2
However, in this text we will restrict use of the word ‘gate’ to refer to operations that do not output such classical information. Thus the most general kind of operation implementable by a gate is a superoperator. Furthermore, for convenience, we will restrict attention to unitary gates. 61 TEAM LinG 62 A QUANTUM MODEL OF COMPUTATION Fig. 4.1 A quantum circuit. The 4-qubit state | 0 | 0 | 0 | 0 enters the circuit on the left. The boxes labelled U 1 , U 2 , U 3 , U 4 represent quantum
|sb mod N , s < N. (7.4.2) We assume that we know r, the order of b. Because of the quantum factoring algorithm, we assume that we can factor r into its prime factors, and we can therefore reduce the discrete logarithm problem to the base a to less than log r instances of the discrete logarithms problem for elements a of prime order (see Appendix A.2). We will therefore assume for convenience that r is prime, but the algorithm would also work for composite r with a slightly more
derive a quantum equivalent of a classical random walk, which we call quantum walks. Quantum walks are another interesting par- adigm in which to discover new quantum algorithms. For example, the optimal quantum algorithm for element distinctness can be found using a quantum walk algorithm. TEAM LinG 9 QUANTUM COMPUTATIONAL COMPLEXITY THEORY AND LOWER BOUNDS We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain
i 10.4.2 Encoding Once we have a description of the potential errors, we need to find a way to protect the logical states |ψ of our quantum system against these errors. As in the classical case we will enlarge the system at hand by adding an ancilla to the logical states. Without loss of generality, we will assume that our ancilla is initialized to | 00 · · · 0 . We then look for transformations that map the joint states |ψ ⊗ | 00 · · · 0 to some encoded states |ψ enc . The subspace