Contents xi 4.3 Controlled operations 177 4.4 Measurement 185 4.5 Universal quantum gates 188 4.5.1 Two-level unitary gates are universal 189 4.5.2 Single qubit and CNOT gates are universal 191 4.5.3 A discrete set of universal operations 194 4.5.4 Approximating arbitrary unitary gates is generically hard 198 4.5.5 Quantum computational complexity 200 4.6 Summary of the quantum circuit model of computation 202 4.7 Simulation of quantum systems 204 4.7.1 Simulation in action 204 4.7.2 The quantum simulation algorithm 206 4.7.3 An illustrative example 209 4.7.4 Perspectives on quantum simulation 211 5 The quantum Fourier transform and its applications 216 5.1 The quantum Fourier transform 217 5.2 Phase estimation 221 5.2.1 Performance and requirements 223 5.3 Applications:order-finding and factoring 226 5.3.1 Application:order-finding 226 5.3.2 Application:factoring 232 5.4 General applications of the quantum Fourier transform 234 5.4.1 Period-finding 236 5.4.2 Discrete logarithms 238 5.4.3 The hidden subgroup problem 240 5.4.4 Other quantum algorithms? 242 6 Quantum search algorithms 248 6.1 The quantum search algorithm 248 6.1.1 The oracle 248 6.1.2 The procedure 250 6.1.3 Geometric visualization 252 6.1.4 Performance 253 6.2 Quantum search as a quantum simulation 255 6.3 Quantum counting 261 6.4 Speeding up the solution of NP-complete problems 263 6.5 Quantum search of an unstructured database 265 6.6 Optimality of the search algorithm 269 6.7 Black box algorithm limits 271 7 Quantum computers:physical realization 277 7.1 Guiding principles 277 7.2 Conditions for quantum computation 279 7.2.1 Representation of quantum information 279 7.2.2 Performance of unitary transformations 281Contents xi 4.3 Controlled operations 177 4.4 Measurement 185 4.5 Universal quantum gates 188 4.5.1 Two-level unitary gates are universal 189 4.5.2 Single qubit and CNOT gates are universal 191 4.5.3 A discrete set of universal operations 194 4.5.4 Approximating arbitrary unitary gates is generically hard 198 4.5.5 Quantum computational complexity 200 4.6 Summary of the quantum circuit model of computation 202 4.7 Simulation of quantum systems 204 4.7.1 Simulation in action 204 4.7.2 The quantum simulation algorithm 206 4.7.3 An illustrative example 209 4.7.4 Perspectives on quantum simulation 211 5 The quantum Fourier transform and its applications 216 5.1 The quantum Fourier transform 217 5.2 Phase estimation 221 5.2.1 Performance and requirements 223 5.3 Applications: order-finding and factoring 226 5.3.1 Application: order-finding 226 5.3.2 Application: factoring 232 5.4 General applications of the quantum Fourier transform 234 5.4.1 Period-finding 236 5.4.2 Discrete logarithms 238 5.4.3 The hidden subgroup problem 240 5.4.4 Other quantum algorithms? 242 6 Quantum search algorithms 248 6.1 The quantum search algorithm 248 6.1.1 The oracle 248 6.1.2 The procedure 250 6.1.3 Geometric visualization 252 6.1.4 Performance 253 6.2 Quantum search as a quantum simulation 255 6.3 Quantum counting 261 6.4 Speeding up the solution of NP-complete problems 263 6.5 Quantum search of an unstructured database 265 6.6 Optimality of the search algorithm 269 6.7 Black box algorithm limits 271 7 Quantum computers: physical realization 277 7.1 Guiding principles 277 7.2 Conditions for quantum computation 279 7.2.1 Representation of quantum information 279 7.2.2 Performance of unitary transformations 281